Network Games, Control, and Optimization

This paper is a follow-up of (Eitan Altman, Dynamic Games and Applications, Springer Verlag, Vol. 3, No. 2 (2013) 313–323). It considers the same stochastic game that describes competition through advertisement over the popularity of their content. We show that the equilibrium may or may not be unique, depending on the system’s parameters. We further identify structural properties of the equilibria. In particular, we show that a finite improvement property holds on the best response pure policies which implies the existence of pure equilibria. We further show that all pure equilibria are fully ordered in the performance they provide to the players and we propose a procedure to obtain the best equilibrium.

The global Internet has enabled a massive access of internauts to content. At the same time it allowed individuals to use the Internet in order to distribute content. This introduced new types of competition between content over popularity, visibility, influence, reputation and user attention. The rules of these competitions are new with respect to those of traditional media, and they are determined by the way resources are allocated through network protocols (such as page rank in search engines and recommendation systems that are widely spread in social networks). In this paper we first present in the introduction an overview of some central competition issues both in the Internet as well as in other types of networks. We then describe the model of when to send content in order to maximize the exposure of the content. In the two last sections we finally describe research on two bio-inspired tools that have been used to study various competition aspects.

A central question in routing games has been to establish conditions for the uniqueness of the equilibrium, either in terms of network topology or in terms of costs. This question is well understood in two classes of routing games. The first is the non-atomic routing introduced by Wardrop on 1952 in the context of road traffic in which each player (car) is infinitesimally small; a single car has a negligible impact on the congestion. Each car wishes to minimize its expected delay. Under arbitrary topology, such games are known to have a convex potential and thus a unique equilibrium. The second framework is splitable atomic games: there are finitely many players, each controlling the route of a population of individuals (let them be cars in road traffic or packets in the communication networks). In this paper, we study two other frameworks of routing games in which each of several players has an integer number of connections (which are population of packets) to route and where there is a constraint that a connection cannot be split. Through a particular game with a simple three link topology, we identify various novel and surprising properties of games within these frameworks. We show in particular that equilibria are non unique even in the potential game setting of Rosenthal with strictly convex link costs. We further show that non-symmetric equilibria arise in symmetric networks.

In this paper, the fundamental limits of decentralized information transmission in the K-user Gaussian multiple access channel (G-MAC), with \(K\geqslant 2\), are fully characterized. Two scenarios are considered. First, a game in which only the transmitters are players is studied. In this game, the transmitters autonomously and independently tune their own transmit configurations seeking to maximize their own transmission rates, R ₁, …, R _K , respectively. On the other hand, the receiver adopts a fixed receive configuration that is known a priori to the transmitters. The main result consists of the full characterization of the set of rate tuples (R ₁, …, R _K ) that are achievable and stable in the G-MAC when stability is considered in the sense of the η-Nash equilibrium (NE), with \(\eta \geqslant 0\) arbitrarily small. Second, a sequential game in which the two categories of players (the transmitters and the receiver) play in a given order is presented. For this sequential game, the main result consists of the full characterization of the set of rate tuples (R ₁, …, R _K ) that are stable in the sense of an η-sequential equilibrium, with \(\eta \geqslant 0\) arbitrarily small.

In this paper, we consider the problem of wireless power control in an interference channel where transmitters aim to maximize their own benefit. When the individual payoff or utility function is derived from the transmission efficiency and the spent power, previous works typically study the Nash equilibrium of the resulting power control game. We propose to introduce concepts of correlated and communication equilibria from game theory to find efficient solutions (compared to the Nash equilibrium) for this problem. Communication and correlated equilibria are analyzed for the power control game, and we provide algorithms that can achieve these equilibria. Simulation results demonstrate that the correlation is beneficial under some settings, and the players achieve better payoffs.

We analyze the coexistence of selfish and malicious devices in a relay assisted Device-to-Device (D2D) network by using a non-cooperative game-theoretic framework. We consider that in the D2D network, the energy-aware individual devices maximize their fractional energy efficiency objectives. The malicious devices due to their different utility function compared to the regular devices, affect the energy efficiency of the regular devices through interference. We show the existence of a unique Nash Equilibrium (NE) in the defined energy efficiency game. We also numerically evaluate the effect of malicious devices on the energy efficiency of the regular devices.

We consider the problem of designing access control protocols for servers distributing background data, such as software and database updates, so that they cause the least possible disruption to flows carrying delay-sensitive data. Using a Markov decision process formulation we obtain the optimal policy analytically, which is not easy to implement in practice. A mean-field argument is employed to show that another policy, which is easier to implement and is based on water-filling, converges to the optimal as the number of bottleneck links increases. Using simulations we compare the performance of this policy with the standard case where no control is exercised by the server.

Due to the constant need for ever-increasing spectrum efficiency, licensed spectrum sharing approaches, where no exclusive rights are given to any single operator, have recently attracted significant attention. Under this setting, the operators, though still selfish, have motivation to cooperate so as to provide high Quality-of-Service to their respective customers. In this context, we present an approach based on a simple charging model where many operators may coexist efficiently by combining traditional power control with bargaining, using “take it or leave it” offers. We derive conditions for a successful bargain. For the special case of two operators, we show that, through our scheme, each operator always achieves a payoff that is higher than the Nash Equilibrium payoff. We also show analytically when our scheme maximizes the social welfare, i.e., the sum of payoffs. We then compare its performance through simulations with a scheme that maximizes the social welfare and a scheme that applies linear power pricing.

We propose an incentive mechanism for steering the strategies of noncooperative heterogeneous agents, each with strongly convex cost function depending on the average among the agents’ strategies, and all sharing a convex constraint, toward a competitive aggregative equilibrium. We consider a coordinator agent having access to the average among the agents’ strategies and broadcasting incentive signals that affect the decentralized optimal responses of the agents. Our mechanism ensures, based on the Picard–Banach fixed point iteration, global convergence to an equilibrium.

In this paper, a novel framework for optimizing the coexistence between LTE and WiFi over unlicensed bands, is proposed. The problem is modeled using the framework of multi-game theory in which the WiFi users (WUs) are considered as leaders and the small base stations (SBSs) as followers. This multi-game framework encompasses two games of different types. In this regard, the competition between the WUs to access the unlicensed channels is formulated as a one-sided matching game while the power allocation problem of the SBSs is formulated as a noncooperative game. In this multi-game, the SBSs anticipate the channel allocation on the WiFi network and adapt their strategies accordingly while the WUs predict the power allocation of the SBSs. For the latter, the existence of a unique Debreu equilibrium is proved while for the matching game the existence of core stable outcome is shown and a decentralized algorithm that converges to the stable outcome is proposed.

This paper addresses the user association problem in a multi-cell broadcast transmission. We seek minimal total energy consumption by considering both transmission power and operational power cost. We propose a novel distributed solution based on network utility games and using so-called Markovian approximation we design the distributed base station (BS) selection algorithm. Extensive simulation results are provided and highlight the relative performance of the algorithm.

This paper studies spectrum allocation of Spectrum Shared pre-configured Cycle (SS-p-cycle) design in Elastic Optical Networks (EONs) with and without spectrum conversion capabilities. SS-p-Cycle design enhances spectrum sharing among multiple p-cycles that have common link(s). We develop Integer Linear Programming (ILP) models to minimize both spare capacity and the maximum number of spectrum usage for each of the two spectrum conversion cases. Simulation results indicate that the SS-p-cycle design requires the same maximum number of spectrum usage in the two cases while SS-p-cycle with spectrum conversion earns higher spectrum efficiency. Moreover, compared with traditional spectrum no-shared p-cycle design, SS-p-cycle design acquires more efficient spectrum allocation in both cases.

SIS epidemic non-zero sum games have been recently used to analyse virus protection in networks. A potential game approach was proposed for solving the game for the case of a fully connected network. In this paper we manage to extend this result to an arbitrary topology by showing that the general topology game has an ordinal potential game. We apply this result to study numerically some examples.

Despite the lure of a considerable increase in spectrum usage efficiency, the practical implementation of cognitive radio (CR) systems is being obstructed by the need for efficient and reliable protection mechanisms that can safeguard the quality of service (QoS) requirements of licensed users. This need becomes particularly apparent in dynamic wireless networks where channel conditions may vary unpredictably – thus making the task of guaranteeing the primary users (PUs)’ minimum quality of service requirements an even more challenging task. In this paper, we consider a pricing mechanism that penalizes the secondary users (SUs) for the interference they inflict on the network’s PUs and then compensates the PUs accordingly. Drawing on tools from online optimization, we propose an exponential learning power allocation policy that is provably capable of adapting quickly and efficiently to the system’s variability, relying only on strictly causal channel state information (CSI). If the transmission horizon T is known in advance by the SUs, we prove that the proposed algorithm reaches a “no-regret” state within \(\mathcal{O}(T^{-1/2})\) iterations; otherwise, if the horizon is not known in advance, the algorithm still reaches a no-regret state within \(\mathcal{O}(T^{-1/2}\log T)\) iterations. Moreover, our numerical results show that the interference created by the SUs can be mitigated effectively by properly tuning the parameters of the pricing mechanism.

In this work, we are interested in finding the most efficient use of a budget to promote an opinion by paying agents within a group to supplant their true opinions. We model opinions as continuous scalars ranging from 0 to 1 with 1 (0) representing extremely positive (negative) opinion. We focus on asymmetric confidence between agents. The iterative update of an agent corresponds to the best response to other agents’ actions. The resulting confidence matrix can be seen as an equivalent Markov chain. We provide simple and efficient algorithms to solve this problem and we show through an example how to solve the stated problem in practice.

Malware is a malicious software which aims to disrupt computer operations, gather sensitive information, and gain access to private computer systems. It can induce various sorts of damage, including economic costs, the leakage of private information, and instability of physical systems, etc. The distribution of antivirus patches in a network enables the control of the proliferation of malicious software and decreases possible losses. Multiple types of malware can coexist in a network. Hence it is important to protect a computer network from several heterogeneous malware, which can propagate in the network at the same time. In this study, we model the propagation of two types of malware using a modified two-virus epidemic model. We formulate an optimal control problem that seeks to minimize the total system cost that includes the economic value of security risks and resources required by countermeasures. We introduce an impulse control problem to provide efficient control of the epidemic model compared with its continuous control counterpart. Numerical experiments are used to corroborate the results.

Routing and Spectrum Assignment (RSA) is the fundamental problem in Elastic Optical Networks (EONs), which is an \(\mathcal{N}\mathcal{P}\)-complete problem. In this paper, we compare the performances of two typical RSA algorithms namely Spectrum-First and Route-First, and put forward a connection between the performances and the request distributions. The numerical results demonstrated that even though the Spectrum-First RSA algorithm outperforms significantly the Route-First RSA algorithm under concentrated distribution, the latter performs pretty better under uniform distribution, which is however somewhat different from that demonstrated in the literature.

This contribution is on the framework of a wireless network with multiple interfering transmitter-receiver pairs. We study the case where there is no direct communication channel between the multiple transmitters and the system is completely distributed (in terms of information available and decision making). Exchanging local channel state information (CSI) among the transmitters is one solution to the problem of improving the efficiency of the network. We introduce a novel power modulation scheme that facilitates reliable exchange of local CSI through the signal power strength assuming feedback of received signal strength indicator from each receiver to its transmitter. Numerical results demonstrate the value of our approach.