Resource allocation games such as the famous Colonel Blotto (CB) and Hide-and-Seek (HS) games are often used to model a large variety of practical problems, but only in their one-shot versions. Indeed, due to their extremely large strategy space, it remains an open question how one can efficiently learn in these games. In this work, we show that the online CB and HS games can be cast as path planning problems with side-observations (SOPPP): at each stage, a learner chooses a path on a directed acyclic graph and suffers the sum of losses that are adversarially assigned to the corresponding edges; and she then receives semi-bandit feedback with side-observations (i.e., she observes the losses on the chosen edges plus some others). We propose a novel algorithm, Exp3-OE, the first-of-its-kind with guaranteed efficient running time for SOPPP without requiring any auxiliary oracle. We provide an expected-regret bound of Exp3-OE in SOPPP matching the order of the best benchmark in the literature. Moreover, we introduce additional assumptions on the observability model under which we can further improve the regret bounds of Exp3-OE. We illustrate the benefit of using Exp3-OE in SOPPP by applying it to the online CB and HS games.

The Colonel Blotto game is a famous game commonly used to model resource allocation problems in many domains ranging from security to advertising. Two players distribute a fixed budget of resources on multiple battlefields to maximize the aggregate value of battlefields they win, each battlefield being won by the player who allocates more resources to it. The continuous version of the game---where players can choose any fractional allocation---has been extensively studied, albeit only with partial results to date. Recently, the discrete version---where allocations can only be integers---started to gain traction and algorithms were proposed to compute the equilibrium in polynomial time; but these remain computationally impractical for large (or even moderate) numbers of battlefields. In this paper, we propose an algorithm to compute very efficiently an approximate equilibrium for the discrete Colonel Blotto game with many battlefields. We provide a theoretical bound on the approximation error as a function of the game's parameters. We also propose an efficient dynamic programming algorithm in order to compute for each game instance the actual value of the error. We perform numerical experiments that show that the proposed strategy provides a fast and good approximation to the equilibrium even for moderate numbers of battlefields

High availability of containerized applications requires to perform robust storage of applications' state. Since basic replication techniques are extremely costly at scale, storage space requirements can be reduced by means of erasure and/or repairing codes. In this paper we address storage regeneration using repair codes, a robust distributed storage technique with no need to fully restore the whole state in case of failure. In fact, only the lost servers' content is replaced. To do so, new clean-slate storage units are made operational at a cost for activating new storage servers and a cost for the transfer of repair data. Our goal is to guarantee maximal availability of containers' state files by a given deadline. Upon a fault occurring at a subset of the storage servers, we aim at ensuring that they are repaired by a given deadline. We introduce a controlled fluid model and derive the optimal activation policy to replace servers under such correlated faults. The solution concept is the optimal control of regeneration via the Pontryagin minimum principle. We characterize feasibility conditions and we prove that the optimal policy is of threshold type. Numerical results describe how to apply the model for system dimensioning and show the tradeoff between activation of servers and communication cost.

We study the scaling properties of a georouting scheme in a wireless multi-hop network of n mobile nodes. Our aim is to increase the network capacity quasi-linearly with n, while keeping the average delay bounded. In our model, we consider mobile nodes moving according to an independent identically distributed random walk with velocity v and transmitting packets to randomly chosen fixed and known destinations. The average packet delivery delay of our scheme is of order 1/v, and it achieves network capacity of order (n/log n log logn). This shows a practical throughput-delay tradeoff, in particular when compared with the seminal result of Gupta and Kumar, which shows network capacity of order (n/log n)1/2and negligible delay and the groundbreaking result of Grossglauser and Tse, which achieves network capacity of order n but with an average delay of order √n/v. The foundation of our improved capacity and delay tradeoff relies on the fact that we use a mobility model that contains straight-line segments, a model that we consider more realistic than classic Brownian motions. We confirm the generality of our analytical results using simulations under various interference models.

We study the scaling properties of a georouting scheme in a wireless multi-hop network of n mobile nodes. Our aim is to increase the network capacity quasi linearly with n while keeping the average delay bounded. In our model, mobile nodes move according to an i.i.d. random walk with velocity v and transmit packets to randomly chosen destinations. The average packet delivery delay of our scheme is of order 1/v and it achieves the network capacity of order n/(log n log log n). This shows a practical throughput-delay trade-off, in particular when compared with the seminal result of Gupta and Kumar which shows network capacity of order √(n/log n) and negligible delay and the groundbreaking result of Grossglauser and Tse which achieves network capacity of order n but with an average delay of order √n/v. The foundation of our improved capacity and delay trade-off relies on the fact that we use a mobility model that contains free space motion, a model that we consider more realistic than classic brownian motions. We confirm the generality of our analytical results using simulations under various interference models.

Random geometric graphs have proven to be extremely useful in modeling static wireless ad-hoc and sensor networks. The study of these graphs and their spectral properties is a very active field with many interesting applications. In this work, we study the spectral properties of these graphs and in particular we prove the lack of spectral gap in random geometric graphs under a wide range of cases. We also present some results on the spectral properties of generalized weighted versions of these graphs. We later focus on mobile geometric graphs or dynamic Boolean models as were introduced by van den Berg, Meester, and White in 1997. These mobile models have been used to model mobile ad-hoc and sensor networks. Our results are aimed at understanding the dynamics of message spreading in a real-world dynamical network. We simulate a message spreading process and present some results related to the total propagation time under different scenarios. We call total propagation time the time it takes for a certain message to reach all the nodes in the network. This message could be a packet, a virus, a rumor in a social network, or something more general. In particular, we study how the metric, the mobility properties, the presence or absence of obstacles and finally the propagation characteristics affect the dynamics of the message spreading.

In this paper we study the optimal placement and optimal number of active relay nodes through the traffic density in mobile sensor ad hoc networks. We consider a setting in which a set of mobile sensor sources is creating data and a set of mobile sensor destinations is receiving that data through multihop wireless paths. We make the assumption that the network is massively dense, i.e., there are so many sources, destinations, and relay nodes, that it is best to describe the network in terms of macroscopic parameters rather than in terms of microscopic parameters. A simple one-dimensional scenario is used to introduce the problem. We solve the two-dimensional scenario where the mobility of the nodes is deterministic and when it follows the brownian mobility model.