Eitan Altman

Stojan Trajanovski, Yezekael Hayel, Eitan Altman et al.

Defining an optimal protection strategy against viruses, spam propagation or any other kind of contamination process is an important feature for designing new networks and architectures. In this work, we consider decentralized optimal protection strategies when a virus is propagating over a network through a SIS epidemic process. We assume that each node in the network can fully protect itself from infection at a constant cost, or the node can use recovery software, once it is infected. We model our system using a game theoretic framework and find pure, mixed equilibria, and the Price of Anarchy (PoA) in several network topologies. Further, we propose both a decentralized algorithm and an iterative procedure to compute a pure equilibrium in the general case of a multiple communities network. Finally, we evaluate the algorithms and give numerical illustrations of all our results.

Chandramani Singh, Eitan Altman, Anurag Kumar et al.

We study the trade-off between delivery delay and energy consumption in a delay tolerant network in which a message (or a file) has to be delivered to each of several destinations by epidemic relaying. In addition to the destinations, there are several other nodes in the network that can assist in relaying the message. We first assume that, at every instant, all the nodes know the number of relays carrying the packet and the number of destinations that have received the packet. We formulate the problem as a controlled continuous time Markov chain and derive the optimal closed loop control (i.e., forwarding policy). However, in practice, the intermittent connectivity in the network implies that the nodes may not have the required perfect knowledge of the system state. To address this issue, we obtain an ODE (i.e., a deterministic fluid) approximation for the optimally controlled Markov chain. This fluid approximation also yields an asymptotically optimal open loop policy. Finally, we evaluate the performance of the deterministic policy over finite networks. Numerical results show that this policy performs close to the optimal closed loop policy.

Richard Combes, Zwi Altman, Eitan Altman

Future communication networks are expected to feature autonomic (or self-organizing) mechanisms to ease deployment (self-configuration), tune parameters automatically (self-optimization) and repair the network (self-healing). Self-organizing mechanisms have been designed as stand-alone entities, even though multiple mechanisms will run in parallel in operational networks. An efficient coordination mechanism will be the major enabler for large scale deployment of self-organizing networks. We model self-organizing mechanisms as control loops, and study the conditions for stability when running control loops in parallel. Based on control theory and Lyapunov stability, we propose a coordination mechanism to stabilize the system, which can be implemented in a distributed fashion. The mechanism remains valid in the presence of measurement noise via stochastic approximation. Instability and coordination in the context of wireless networks are illustrated with two examples and the influence of network geometry is investigated. We are essentially concerned with linear systems, and the applicability of our results for non-linear systems is discussed.

Stojan Trajanovski, Fernando A. Kuipers, Yezekael Hayel et al.

Designing an optimal network topology while balancing multiple, possibly conflicting objectives like cost, performance, and resiliency to viruses is a challenging endeavor, let alone in the case of decentralized network formation. We therefore propose a game-formation technique where each player aims to minimize its cost in installing links, the probability of being infected by a virus and the sum of hopcounts on its shortest paths to all other nodes. In this article, we (1) determine the Nash Equilibria and the Price of Anarchy for our novel network formation game, (2) demonstrate that the Price of Anarchy (PoA) is usually low, which suggests that (near-)optimal topologies can be formed in a decentralized way, and (3) give suggestions for practitioners for those cases where the PoA is high and some centralized control/incentives are advisable.

Younes Ben Mazziane, Cleque-Marlain Mboulou Moutoubi, Eitan Altman et al.

The Kelly or proportional allocation mechanism is a simple and efficient auction-based scheme that distributes an infinitely divisible resource proportionally to the agents bids. When agents are aware of the allocation rule, their interactions form a game extensively studied in the literature. This paper examines the less explored repeated Kelly game, focusing mainly on utilities that are logarithmic in the allocated resource fraction. We first derive this logarithmic form from fairness-throughput trade-offs in wireless network slicing, and then prove that the induced stage game admits a unique Nash equilibrium NE. For the repeated play, we prove convergence to this NE under three behavioral models: (i) all agents use Online Gradient Descent (OGD), (ii) all agents use Dual Averaging with a quadratic regularizer (DAQ) (a variant of the Follow-the-Regularized leader algorithm), and (iii) all agents play myopic best responses (BR). Our convergence results hold even when agents use personalized learning rates in OGD and DAQ (e.g., tuned to optimize individual regret bounds), and they extend to a broader class of utilities that meet a certain sufficient condition. Finally, we complement our theoretical results with extensive simulations of the repeated Kelly game under several behavioral models, comparing them in terms of convergence speed to the NE, and per-agent time-average utility. The results suggest that BR achieves the fastest convergence and the highest time-average utility, and that convergence to the stage-game NE may fail under heterogeneous update rules.

Xinying Zou, Samir M. Perlaza, Iñaki Esnaola et al.

In this paper, the worst-case probability measure over the data is introduced as a tool for characterizing the generalization capabilities of machine learning algorithms. More specifically, the worst-case probability measure is a Gibbs probability measure and the unique solution to the maximization of the expected loss under a relative entropy constraint with respect to a reference probability measure. Fundamental generalization metrics, such as the sensitivity of the expected loss, the sensitivity of the empirical risk, and the generalization gap are shown to have closed-form expressions involving the worst-case data-generating probability measure. Existing results for the Gibbs algorithm, such as characterizing the generalization gap as a sum of mutual information and lautum information, up to a constant factor, are recovered. A novel parallel is established between the worst-case data-generating probability measure and the Gibbs algorithm. Specifically, the Gibbs probability measure is identified as a fundamental commonality of the model space and the data space for machine learning algorithms.

Andrea Fox, Francesco De Pellegrini, Eitan Altman

In edge computing systems, autonomous agents must make fast local decisions while competing for shared resources. Existing MARL methods often resume to centralized critics or frequent communication, which fail under limited observability and communication constraints. We propose a decentralized framework in which each agent solves a constrained Markov decision process (CMDP), coordinating implicitly through a shared constraint vector. For the specific case of offloading, e.g., constraints prevent overloading shared server resources. Coordination constraints are updated infrequently and act as a lightweight coordination mechanism. They enable agents to align with global resource usage objectives but require little direct communication. Using safe reinforcement learning, agents learn policies that meet both local and global goals. We establish theoretical guarantees under mild assumptions and validate our approach experimentally, showing improved performance over centralized and independent baselines, especially in large-scale settings.

S. Ramakrishnan, Jaswanthi Mandalapu, Subrahmanya Swamy Peruru et al.

In this work, we propose a Graph Convolutional Neural Networks (GCN) based scheduling algorithm for adhoc networks. In particular, we consider a generalized interference model called the $k$-tolerant conflict graph model and design an efficient approximation for the well-known Max-Weight scheduling algorithm. A notable feature of this work is that the proposed method do not require labelled data set (NP-hard to compute) for training the neural network. Instead, we design a loss function that utilises the existing greedy approaches and trains a GCN that improves the performance of greedy approaches. Our extensive numerical experiments illustrate that using our GCN approach, we can significantly ($4$-$20$ percent) improve the performance of the conventional greedy approach.

José Horta, Eitan Altman, Mathieu Caujolle et al.

Future electricity distribution grids will host a considerable share of the renewable energy sources needed for enforcing the energy transition. Demand side management mechanisms play a key role in the integration of such renewable energy resources by exploiting the flexibility of elastic loads, generation or electricity storage technologies. In particular, local energy markets enable households to exchange energy with each other while increasing the amount of renewable energy that is consumed locally. Nevertheless, as most ex-ante mechanisms, local market schedules rely on hour-ahead forecasts whose accuracy may be low. In this paper we cope with forecast errors by proposing a game theory approach to model the interactions among prosumers and distribution system operators for the control of electricity flows in real-time. The presented game has an aggregative equilibrium which can be attained in a semi-distributed manner, driving prosumers towards a final exchange of energy with the grid that benefits both households and operators, favoring the enforcement of prosumers' local market commitments while respecting the constraints defined by the operator. The proposed mechanism requires only one-to-all broadcast of price signals, which do not depend either on the amount of players or their local objective function and constraints, making the approach highly scalable. Its impact on distribution grid quality of supply was evaluated through load flow analysis and realistic load profiles, demonstrating the capacity of the mechanism ensure that voltage deviation and thermal limit constraints are respected.

Zakaria Ye, Rachid El-Azouzi, Tania Jimenez et al.

Although HTTP-based video streaming can easily penetrate firewalls and profit from Web caches, the underlying TCP may introduce large delays in case of a sudden capacity loss. To avoid an interruption of the video stream in such cases we propose the Backward-Shifted Coding (BSC). Based on Scalable Video Coding (SVC), BSC adds a time-shifted layer of redundancy to the video stream such that future frames are downloaded at any instant. This pre-fetched content maintains a fluent video stream even under highly variant network conditions and leads to high Quality of Experience (QoE). We characterize this QoE gain by analyzing initial buffering time, re-buffering time and content resolution using the Ballot theorem. The probability generating functions of the playback interruption and of the initial buffering latency are provided in closed form. We further compute the quasi-stationary distribution of the video quality, in order to compute the average quality, as well as temporal variability in video quality. Employing these analytic results to optimize QoE shows interesting trade-offs and video streaming at outstanding fluency.

K. P. Naveen, Anurag Kumar, Eitan Altman

We consider a setting in which two nodes (referred to as forwarders) compete to choose a relay node from a set of relays, as they ephemerally become available (e.g., wake up from a sleep state). Each relay, when it arrives, offers a (possibly different) "reward" to each forwarder. Each forwarder's objective is to minimize a combination of the delay incurred in choosing a relay and the reward offered by the chosen relay. As an example, we develop the reward structure for the specific problem of geographical forwarding over a network of sleep-wake cycling relays. We study two variants of the generic relay selection problem, namely, the completely observable (CO) case where, when a relay arrives, both forwarders get to observe both rewards, and the partially observable (PO) case where each forwarder can only observe its own reward. Formulating the problem as a two person stochastic game, we characterize solution in terms of Nash Equilibrium Policy Pairs (NEPPs). For the CO case we provide a general structure of the NEPPs. For the PO case we prove that there exists an NEPP within the class of threshold policy pairs. We then consider the particular application of geographical forwarding of packets in a shared network of sleep-wake cycling wireless relays. For this problem, for a particular reward structure, using realistic parameter values corresponding to TelosB wireless mote, we numerically compare the performance (in terms of cost to both forwarders) of the various NEPPs and draw the following key insight: even for moderate separation between the two forwarders, the performance of the various NEPPs is close to the performance of a simple strategy where each forwarder behaves as if the other forwarder is not present. We also conduct simulation experiments to study the end-to-end performance of the simple forwarding policy.