A Comprehensive Survey of Potential Game Approaches to Wireless Networks
---
paper_title: Distributed Strategic Learning for Wireless Engineers

paper_content:

Establishing the link between several theories, this book demonstrates what is needed to learn strategic interaction in wireless networks under uncertainty, randomness, and time delays. This robust game theory cookbook analyzes games where some parameters are uncertain and random. Starting with the fundamentals of strategic learning and game theory, the text then covers partially and fully distributed learning, combined learning for negotiation, bargaining solutions, Nash equilibria, Stackelberg solutions, correlated equilibria, conjectural variations, and satisfactory solutions. It concludes with practical algorithms and techniques to implement game theory in wireless networks.
---
paper_title: GADIA: A Greedy Asynchronous Distributed Interference Avoidance Algorithm

paper_content:

In this paper, the problem of distributed dynamic frequency allocation is considered for a canonical communication network, which spans several networks such as cognitive radio networks and digital subscriber lines (DSLs). A greedy asynchronous distributed interference avoidance (GADIA) algorithm for horizontal spectrum sharing has been proposed that achieves performance close to that of a centralized optimal algorithm. The convergence of the GADIA algorithm to a near-optimal frequency allocation strategy is proved and several asymptotic performance bounds have been established for various spatial configurations of the network nodes. Furthermore, the near-equilibrium dynamics of the GADIA algorithm has been studied using the Glauber dynamics, by identifying the problem with the antiferromagnetic inhomogeneous long-range Potts model. Using the near-equilibrium dynamics and methods from stochastic analysis, the robustness of the algorithm with respect to time variations in the activity of network nodes is studied. These analytic results along with simulation studies reveal that the performance is close to that of an optimum centralized frequency allocation algorithm. Further simulation studies confirm that our proposed algorithm outperforms the iterative water-filling algorithm in the low signal-to-interference-plus-noise ratio (SINR) regime, in terms of achieved sum rate, complexity, convergence rate, and robustness to time-varying node activities.
---
paper_title: Algorithms for Self-Organized Resource Allocation in Wireless Networks

paper_content:

We consider the problem of allocating orthogonal resources in a self-organized manner on conflict graphs that describe discretized interference couplings of wireless networks. The target is to find a global optimum, i.e., a conflict-free allocation. We consider both random planar and nonplanar graphs that result from a path-loss model in a wireless network. Two algorithms for the self-organized coloring of arbitrary graphs are devised, and their performances are compared with each other and a rule-based reasoning algorithm that is known from the literature. The semigreedy distributed local search (SDLS) algorithm, which is a particularly simple algorithm that is proposed here, is shown to outperform other algorithms in several cases. In a cellular system setting, we consider a negotiated worst coupling procedure to symmetrize the interference coupling between cells, targeting an improvement of the channel quality of cell-edge users. We compare this approach with an interference coupling based on the path loss that was experienced between base stations and see significant gains in cell-edge performance. In addition, we compare the channel quality that was experienced by users in a cellular network that employs SDLS with the channel quality in a network that employs an interference-reducing network algorithm which finds a local optimum in terms of real-valued interference couplings. In some cases, attempting global optimization based on a conflict graph interpretation outperforms local real-valued optimization.
---
paper_title: Adaptive channel allocation spectrum etiquette for cognitive radio networks

paper_content:

In this work, we propose a game theoretic framework to analyze the behavior of cognitive radios for distributed adaptive channel allocation. We define two different objective functions for the spectrum sharing games, which capture the utility of selfish users and cooperative users, respectively. Based on the utility definition for cooperative users, we show that the channel allocation problem can be formulated as a potential game, and thus converges to a deterministic channel allocation Nash equilibrium point. Alternatively, a no-regret learning implementation is proposed for both scenarios and it is shown to have similar performance with the potential game when cooperation is enforced, but with a higher variability across users. The no-regret learning formulation is particularly useful to accommodate selfish users. Non-cooperative learning games have the advantage of a very low overhead for information exchange in the network. We show that cooperation based spectrum sharing etiquette improves the overall network performance at the expense of an increased overhead required for information exchange
---
paper_title: Optimality and Complexity of Pure Nash Equilibria in the Coverage Game

paper_content:

In this paper, we investigate the coverage problem in wireless sensor networks using a game theory method. We assume that nodes are randomly scattered in a sensor field and the goal is to partition these nodes into K sets. At any given time, nodes belonging to only one of these sets actively sense the field. A key challenge is to achieve this partition in a distributed manner with purely local information and yet provide near optimal coverage. We appropriately formulate this coverage problem as a coverage game and prove that the optimal solution is a pure Nash equilibrium. Then, we design synchronous and asynchronous algorithms, which converge to pure Nash equilibria. Moreover, we analyze the optimality and complexity of pure Nash equilibria in the coverage game. We prove that, the ratio between the optimal coverage and the worst case Nash equilibrium coverage, is upper bounded by 2 - 1/m+1 (m is the maximum number of nodes, which cover any point, in the Nash equilibrium solution s*). We prove that finding pure Nash equilibria in the general coverage game is PLS-complete, i.e. "as hard as that of finding a local optimum in any local search problem with efficient computable neighbors". Finally, via extensive simulations, we show that, the Nash equilibria coverage performance is very close to the optimal coverage and the convergence speed is sublinear. Even under the noisy environment, our algorithms can still converge to the pure Nash equilibria.
---
paper_title: Pure Nash equilibria in player-specific and weighted congestion games

paper_content:

Unlike standard congestion games, weighted congestion games and congestion games with player-specific delay functions do not necessarily possess pure Nash equilibria. It is known, however, that there exist pure equilibria for both of these variants in the case of singleton congestion games, i. e., if the players' strategy spaces contain only sets of cardinality one. In this paper, we investigate how far such a property on the players' strategy spaces guaranteeing the existence of pure equilibria can be extended. We show that both weighted and player-specific congestion games admit pure equilibria in the case of matroid congestion games, i. e., if the strategy space of each player consists of the bases of a matroid on the set of resources. We also show that the matroid property is the maximal property that guarantees pure equilibria without taking into account how the strategy spaces of different players are interweaved. In the case of player-specific congestion games, our analysis of matroid games also yields a polynomial time algorithm for computing pure equilibria.
---
paper_title: Best-response potential games

paper_content:

Abstract Best-response potential games are introduced and characterized. Relations with other classes of potential games are indicated.
---
paper_title: State based potential games

paper_content:

There is a growing interest in the application of game theoretic methods to the design and control of multiagent systems. However, the existing game theoretic framework possesses inherent limitations with regards to these new prescriptive challenges. In this paper we propose a new framework, termed state based potential games, which introduces an underlying state space into the framework of potential games. This state space provides a system designer with an additional degree of freedom to help coordinate group behavior and overcome these limitations. Within the context of state based potential games, we characterize the limiting behavior of two learning algorithms termed finite memory better reply processes and log-linear learning. Lastly, we demonstrate the applicability of state based potential games on two cooperative control problems pertaining to distributed resource allocation and the design of local and distributed control laws.
---
paper_title: Near-Potential Games: Geometry and Dynamics

paper_content:

Potential games are a special class of games for which many adaptive user dynamics converge to a Nash equilibrium. In this article, we study properties of near-potential games, that is, games that are close in terms of payoffs to potential games, and show that such games admit similar limiting dynamics. ::: We first focus on finite games in strategic form. We introduce a distance notion in the space of games and study the geometry of potential games and sets of games that are equivalent, with respect to various equivalence relations, to potential games. We discuss how, given an arbitrary game, one can find a nearby game in these sets. We then study dynamics in near-potential games by focusing on continuous-time perturbed best response dynamics. We characterize the limiting behavior of this dynamics in terms of the upper contour sets of the potential function of a close potential game and approximate equilibria of the game. Exploiting structural properties of approximate equilibrium sets, we strengthen our result and show that for games that are sufficiently close to a potential game, the sequence of mixed strategies generated by this dynamics converges to a small neighborhood of equilibria whose size is a function of the distance from the set of potential games. ::: In the second part of the article, we study continuous games and show that our approach for characterizing the limiting sets in near-potential games extends to continuous games. In particular, we consider continuous-time best response dynamics and a variant of it (where players update their strategies only if there is at least ε utility improvement opportunity) in near-potential games where the strategy sets are compact and convex subsets of a Euclidean space. We show that these update rules converge to a neighborhood of equilibria (or the maximizer of the potential function), provided that the potential function of the nearby potential game satisfies some structural properties. Our results generalize the known convergence results for potential games to near-potential games.
---
paper_title: Dynamics in near-potential games

paper_content:

Except for special classes of games, there is no systematic framework for analyzing the dynamical properties of multi-agent strategic interactions. Potential games are one such special but restrictive class of games that allow for tractable dynamic analysis. Intuitively, games that are"close"to a potential game should share similar properties. In this paper, we formalize and develop this idea by quantifying to what extent the dynamic features of potential games extend to"near-potential"games. We study convergence of three commonly studied classes of adaptive dynamics: discrete-time better/best response, logit response, and discrete-time fictitious play dynamics. For better/best response dynamics, we focus on the evolution of the sequence of pure strategy profiles and show that this sequence converges to a (pure) approximate equilibrium set, whose size is a function of the"distance"from a close potential game. We then study logit response dynamics and provide a characterization of the stationary distribution of this update rule in terms of the distance of the game from a close potential game and the corresponding potential function. We further show that the stochastically stable strategy profiles are pure approximate equilibria. Finally, we turn attention to fictitious play, and establish that the sequence of empirical frequencies of player actions converges to a neighborhood of (mixed) equilibria of the game, where the size of the neighborhood increases with distance of the game to a potential game. Thus, our results suggest that games that are close to a potential game inherit the dynamical properties of potential games. Since a close potential game to a given game can be found by solving a convex optimization problem, our approach also provides a systematic framework for studying convergence behavior of adaptive learning dynamics in arbitrary finite strategic form games.
---
paper_title: Strategic complements and substitutes, and potential games

paper_content:

Abstract We show that games of strategic complements, or substitutes, with aggregation are “pseudo-potential” games. The upshot is that they possess Nash equilibria in pure strategies (NE), even if the strategy sets are not convex; and that various dynamic processes converge to NE. In particular, NE exist in Cournot oligopoly with indivisibilities in production. Our notion of aggregation is quite general and enables us to take a unified view of several disparate models.
---
paper_title: Potential Games: A Framework for Vector Power Control Problems With Coupled Constraints

paper_content:

In this paper we propose a unified framework, based on the emergent potential games to deal with a variety of network resource allocation problems. We generalize the existing results on potential games to the cases where there exists coupling among the (possibly vector) strategies of all players. We derive sufficient conditions for the existence and uniqueness of the Nash Equilibrium, and provide different distributed algorithms along their convergence properties. Using this new framework, we then show that many power control problems (standard and non-standard) with coupled constraints among the users, can be naturally formulated as potential games and, hence, efficiently solved. Finally, we point out an interesting interplay existing between potential games, classical optimization theory, and Lyapunov stability theory.
---
paper_title: CONGESTION MODELS AND WEIGHTED BAYESIAN POTENTIAL GAMES

paper_content:

Games associated with congestion situations à la Rosenthal (1973) have pure Nash equilibria. This result implicitly relies on the existence of a potential function. In this paper we provide a characterization of potential games in terms of coordination games and dummy games. Second, we extend Rosenthal's congestion model to an incomplete information setting, and show that the related Bayesian games are potential games and therefore have pure Bayesian equilibria.
---
paper_title: CONGESTION MODELS AND WEIGHTED BAYESIAN POTENTIAL GAMES

paper_content:

Games associated with congestion situations à la Rosenthal (1973) have pure Nash equilibria. This result implicitly relies on the existence of a potential function. In this paper we provide a characterization of potential games in terms of coordination games and dummy games. Second, we extend Rosenthal's congestion model to an incomplete information setting, and show that the related Bayesian games are potential games and therefore have pure Bayesian equilibria.
---
paper_title: Convergence of cognitive radio networks

paper_content:

In this paper, we examine the conditions and behavior of several common convergence dynamics from game theory and show how they influence the structure of networks of cognitive radios. We then apply these to previously proposed distributed power control algorithms and describe how they impact network complexity.
---
paper_title: What Does an Oligopoly Maximize

paper_content:

A monopolist maximizes a well-defined objective function, monetary profit. In a competitive industry, although each individual pursues selfish objectives, the market behaves as if an agent was maximizing an objective function, social welfare. Can we say the same for an oligopoly? Do firms pursuing selfish objectives and behaving strategically act as if an agent was maximizing a 'fictitious' objective function? Necessary and sufficient conditions for Nash equilibria of static and state-space games to be observationally equivalent to single optimization problems are derived. Nash equilibria of the game that are not maxima of the function are shown to be generically unstable. Copyright 1994 by Blackwell Publishing Ltd.
---
paper_title: Joint route selection and resource allocation in multihop wireless networks based on a game theoretic approach

paper_content:

In this work we aim to design simple, distributed self-configuring solutions for the problem of route selection and channel and power allocation in multihop autonomous wireless systems using a game theoretic perspective. We propose and compare three games with different levels of complexity: a potential flow game where players need complete network knowledge, a local flow game requiring full information of the flow and a low complexity cooperative link game which works with partial information of the flow. All these games have been designed to always assure the convergence to a stable point in order to be implemented as distributed algorithms. To evaluate their quality, we also obtain the best achievable performance in the system using mathematical optimization. The system is modeled with the physical interference model and two different definitions of the network utility are considered: the number of active flows and the aggregated capacity in bps. Results show that the proposed games approach the centralized solution, and specially, that the simpler cooperative link game provides a performance close to that of the flow games.
---
paper_title: A cross-layer resource allocation scheme for ICIC in LTE-Advanced

paper_content:

As a new technology, inter-eNB coordination has been included in LTE-Advanced study items. Moreover, the network architecture in LTE-Advanced system is modified to take into account coordinated transmission. In our study, we explore the problem of jointly optimizing the power level and scheduling of resource blocks for LTE-Advanced network based on orthogonal frequency division multiplexing (OFDM). We propose a distributed optimization scheme based on evolutionary potential games, and in the process of objective function modeling we employ the Lagrangian multiplier method to solve the constraint objective optimization problem. Then particle swarm optimization (PSO) method is adopted to find the optimal power allocation and scheduling for each resource block in the multi-cell framework. Numerical results prove that proposed algorithm notably improves the overall throughput, while user fairness is guaranteed. Importantly, additional computation and communication cost introduced by cross-layer optimization is also evaluated.
---
paper_title: Self-Organization in Small Cell Networks: A Reinforcement Learning Approach

paper_content:

In this paper, a decentralized and self-organizing mechanism for small cell networks (such as micro-, femto- and picocells) is proposed. In particular, an application to the case in which small cell networks aim to mitigate the interference caused to the macrocell network, while maximizing their own spectral efficiencies, is presented. The proposed mechanism is based on new notions of reinforcement learning (RL) through which small cells jointly estimate their time-average performance and optimize their probability distributions with which they judiciously choose their transmit configurations. Here, a minimum signal to interference plus noise ratio (SINR) is guaranteed at the macrocell user equipment (UE), while the small cells maximize their individual performances. The proposed RL procedure is fully distributed as every small cell base station requires only an observation of its instantaneous performance which can be obtained from its UE. Furthermore, it is shown that the proposed mechanism always converges to an epsilon Nash equilibrium when all small cells share the same interest. In addition, this mechanism is shown to possess better convergence properties and incur less overhead than existing techniques such as best response dynamics, fictitious play or classical RL. Finally, numerical results are given to validate the theoretical findings, highlighting the inherent tradeoffs facing small cells, namely exploration/exploitation, myopic/foresighted behavior and complete/incomplete information.
---
paper_title: Game Theoretic Analysis of Joint Channel Selection and Power Allocation in Cognitive radio Networks

paper_content:

In this work, we formulate the potential game model of joint channel selection and power allocation. First, under the interference constraint, a nonlinear optimization problem is formulated for improving the total throughput and considering the fairness in cognitive radio network. we also define the special objective function for each transmitting node and formulate a potential game to solve this problem distributively. The Nash equilibria of this potential game is investigated. It is shown that the distributed sequential play converges to a Nash equilibrium point and quickly satisfy the interference constraint. Finally, through simulations, the performances are examined and we further investigate the relationship between the parameters of the objective function and the performances of the whole cognitive radio network.
---
paper_title: Game Theoretic Approach for End-to-End Resource Allocation in Multihop Cognitive Radio Networks

paper_content:

This paper presents a game theoretic solution for end-to-end channel and power allocation in multihop cognitive radio networks analyzed under the physical interference model. The objective is to find a distributed solution that maximizes the number of flows that can be established in the network. The problem is addressed through three different games: a local flow game which uses complete information about the links of the flow, a potential flow game requiring global network knowledge and a cooperative link game based on partial information regarding the links of the flow. Results show that the proposed link game highly decreases the complexity of the channel and power allocation problem in terms of computational load, reducing the information shared between the links forming each flow with a performance similar to that of the more complex flow games.
---
paper_title: Joint Channel and Power Allocation in Wireless Mesh Networks: A Game Theoretical Perspective

paper_content:

This paper addresses the throughput maximization problem in wireless mesh networks. For the case of cooperative access points, we present a negotiation-based throughput maximization algorithm which adjusts the operating channel and power level among access points automatically, from a game-theoretical perspective. We show that this algorithm converges to the optimal channel and power assignment which yields the maximum overall throughput with arbitrarily high probability. Moreover, we analyze the scenario where access points belong to different regulation entities and hence non-cooperative. The long- term behavior and corresponding performance are investigated and the analytical results are verified by simulations.
---
paper_title: On the Partially Overlapped Channel Assignment on Wireless Mesh Network Backbone: A Game Theoretic Approach

paper_content:

The Wireless Mesh Network (WMN) has already been recognized as a promising broadband access network technology from both academic and commercial perspective. In order to improve the performance of WMNs, extensive research efforts have been dedicated towards finding means to increase the number of simultaneous transmissions in the network while avoiding signal interference among radios. In case of WMNs based on IEEE 802.11 b/g standards, most recent research works have relied upon the usage of orthogonal channels for solving the Channel Assignment (CA) problem. In this paper, we explore the possibility of exploiting Partially Overlapped Channels (POCs) by introducing a novel game theoretic distributed CA algorithm. Our proposed algorithm outperforms both the conventional orthogonal channel approach and the recent heuristic CA algorithms using POC. The proposed algorithm is shown to achieve near-optimal performance in the average case. In addition, the upper bound Price of Anarchy for Multi-Radio Multi-Channel (MRMC) networks is derived to evaluate the effectiveness of the proposed approach.
---
paper_title: Opportunistic Spectrum Access in Cognitive Radio Networks: Global Optimization Using Local Interaction Games

paper_content:

We investigate the problem of achieving global optimization for distributed channel selections in cognitive radio networks (CRNs), using game theoretic solutions. To cope with the lack of centralized control and local influences, we propose two special cases of local interaction game to study this problem. The first is local altruistic game, in which each user considers the payoffs of itself as well as its neighbors rather than considering itself only. The second is local congestion game, in which each user minimizes the number of competing neighbors. It is shown that with the proposed games, global optimization is achieved with local information. Specifically, the local altruistic game maximizes the network throughput and the local congestion game minimizes the network collision level. Also, the concurrent spatial adaptive play (C-SAP), which is an extension of the existing spatial adaptive play (SAP), is proposed to achieve the global optimum both autonomously as well as rapidly.
---
paper_title: Equilibrium Efficiency Improvement in MIMO Interference Systems: A Decentralized Stream Control Approach

paper_content:

We consider a multi-link MIMO interference system in which each link wishes to maximize its own mutual information by choosing its own signal vector, which leads to a multi-player game. We show the existence of a Nash equilibrium and obtain sufficient conditions for the uniqueness of equilibrium. We consider two decentralized link adjustment algorithms called best-response process (a.k.a. iterative water-filling) and gradient-play (an autonomous and non-cooperative version of the well-known gradient ascent algorithm). Under our uniqueness conditions, we establish the convergence of these algorithms to the unique equilibrium provided that the links use some inertia. To improve the efficiency of an equilibrium with respect to the total mutual information by imposing limits on the number of independent data streams, we present a stream control approach using linear transformation of the link covariance matrices. We then show how to decentralize our stream control approach by allowing the links to negotiate the limits on the number of independent data streams that they are willing to impose upon themselves. To achieve this, we introduce a variation of a learning algorithm called "adaptive play" that has desirable convergence properties in potential games with reduced computation.
---
paper_title: User-Demand-Aware Wireless Network Selection: A Localized Cooperation Approach

paper_content:

We study the network selection problem where multiple users with diverse user demands compete for access in wireless networks. Most existing network selection algorithms commonly suffer from the low efficiency of the social welfare, particulaly for distributed optimization approaches. Centralized optimization approaches can improve the efficiency, but they may incur much cost in network architecture, signaling, and computational complexity. We harvest the diverse user demands across users and propose a local improvement algorithm (LIA). Different from centralized approaches or distributed approaches, the key idea behind the LIA is introducing localized cooperation into networks who share users, called coupled network pair (CNP). Exploiting the spatial distribution of networks, the proposed algorithm decomposes global social welfare optimization into subproblems with low complexity, where each CNP cooperatively reassociates users with user demand awareness. Under a novel game formulation, we proved that the LIA can achieve promising performance. To speed up the convergence of the algorithm, we further exploit the spacial independence among CNPs and propose an enhanced LIA. Finally, simulations indicate that the proposed algorithms achieve much better performance with relatively short convergence time, compared with three distributed algorithms.
---
paper_title: Optimal Power Allocation and User Scheduling in Multicell Networks: Base Station Cooperation Using a Game-Theoretic Approach

paper_content:

This paper proposes a novel base station (BS) co- ordination approach for intercell interference mitigation in the orthogonal frequency-division multiple access based cellular net- works. Specifically, we first propose a new performance metric for evaluating end user's quality of experience (QoE), which jointly considers spectrum efficiency, user fairness, and service satisfaction. Interference graph is applied here to capture and analyze the interactions between BSs. Then, a QoE-oriented re- source allocation problem is formulated among BSs as a local cooperation game, where BSs are encouraged to cooperate with their peer nodes in the adjacent cells in user scheduling and power allocation. The existence of the joint-strategy Nash equilibrium (NE) has been proved, in which no BS player would unilaterally change its own strategy in user scheduling or power allocation. Furthermore, the NE in the formulated game is proved to lead to the global optimality of the network utility. Accordingly, we design an iterative searching algorithm to obtain the global op- timum (i.e., the best NE) with an arbitrarily high probability in a decentralized manner, in which only local information exchange is needed. Theoretical analysis and simulation results both validate the convergence and optimality of the proposed algorithm with fairness improvement.
---
paper_title: Optimal Base Station Sleeping in Green Cellular Networks: A Distributed Cooperative Framework Based on Game Theory

paper_content:

This paper proposes a distributed cooperative framework for improving the energy efficiency of green cellular networks. Based on the traffic load, neighboring base stations (BSs) cooperate to optimize the BS switching (sleeping) strategies so as to maximize the energy saving while guaranteeing users' minimal service requirements. The inter-BS cooperation is formulated following the principle of ecological self-organization. An interaction graph is defined to capture the network impact of the BS switching operation. Then, we formulate the problem of energy saving as a constrained graphical game , where each BS acts as a game player with the constraint of traffic load. The constrained graphical game is proved to be an exact constrained potential game. Furthermore, we prove the existence of a generalized Nash equilibrium (GNE), and the best GNE coincides with the optimal solution of total energy consumption minimization. Accordingly, we design a decentralized iterative algorithm to find the best GNE (i.e., the global optimum), where only local information exchange among the neighboring BSs is needed. Theoretical analysis and simulation results finally illustrate the convergence and optimality of the proposed algorithm.
---
paper_title: Distributed downlink resource allocation in cellular networks through spatial adaptive play

paper_content:

In this work, we develop mathematical and algorithmic tools for distributed resource allocation in downlink of mobile cellular networks. Our algorithms perform power allocation, subcarrier selection and base station association simultaneously. We aim to maximize the aggregate utility of all the users where users' utilities can be arbitrary increasing functions of their throughputs; this allows us to capture both elastic and inelastic traffics. Our solution is via framing the problem as a potential game among users. We propose a highly scalable, asynchronous algorithm that provably converges to a Nash equilibrium of this game. This algorithm requires only local measurements, limited communication between neighboring nodes and limited computation. This algorithm may at times stuck at a local maximum. To alleviate this problem, we propose an enhanced randomized algorithm based on spatial adaptive play that provably converges to a system optimal resource allocation. We also present simulation results to illustrate convergence and performance of the proposed algorithms.
---
paper_title: A Shapley Value Representation of Potential Games

paper_content:

In potential games, as considered by Monderer and Shapley (1996a, Games Econom. Behav.14, 124–143), each player's gain from a deviation is equal to the gain in a potential function. We prove that a game has a potential function if and only if its payoff functions coincide with the Shapley value of a particular class of cooperative games indexed by the set of strategy profiles. Also a potential function of a noncooperative potential game coincides with the potentials (cf. Hart and Mas-Colell, 1989, Econometrica57, 589–614) of cooperative games indexed by the strategy set. Journal of Economic Literature Classification Numbers: C71, C72.
---
paper_title: Congestion games with player-specific constants

paper_content:

We consider a special case of weighted congestion games with playerspecific latency functions where each player uses for each particular resource a fixed (non-decreasing) delay function together with a player-specific constant. For each particular resource, the resource-specific delay function and the playerspecific constant (for that resource) are composed by means of a group operation (such as addition or multiplication) into a player-specific latency function. We assume that the underlying group is a totally ordered abelian group. In this way, we obtain the class of weighted congestion games with player-specific constants; we observe that this class is contained in the new intuitive class of dominance weighted congestion games. We obtain the following results: Games on parallel links: - Every unweighted congestion game has a generalized ordinal potential. - There is a weighted congestion game with 3 players on 3 parallel links that does not have the Finite Best-Improvement Property. - There is a particular best-improvement cycle for general weighted congestion games with player-specific latency functions and 3 players whose outlaw implies the existence of a pure Nash equilibrium. This cycle is indeed outlawed for dominance weighted congestion games with 3 players - and hence for weighted congestion games with player-specific constants and 3 players. Network congestion games: For unweighted symmetric network congestion games with player-specific additive constants, it is PLS-complete to find a pure Nash equilibrium. Arbitrary (non-network) congestion games: Every weighted congestion game with linear delay functions and player-specific additive constants has a weighted potential.
---
paper_title: Graphical Congestion Games

paper_content:

We consider congestion games with linear latency functions in which each player is aware only of a subset of all the other players. This is modeled by means of a social knowledge graph G in which nodes represent players and there is an edge from i to j if i knows j. Under the assumption that the payoff of each player is affected only by the strategies of the adjacent ones, we first give a complete characterization of the games possessing pure Nash equilibria. Namely, if the social graph G is undirected, the game is an exact potential game and thus isomorphic to a classical congestion game. As a consequence, it always converges and possesses Nash equilibria. On the other hand, if G is directed an equilibrium is not guaranteed to exist, but the game is always convergent and an equilibrium can be found in polynomial time if G is acyclic, even if finding the best equilibrium remains an intractable problem. ::: ::: We then investigate the impact of the limited knowledge of the players on the performance of the game. More precisely, given a bound on the maximum degree of G, for the convergent cases we provide tight lower and upper bounds on the price of stability and asymptotically tight bounds on the price of anarchy. Such results are determined for four natural social cost functions: total and maximum presumed latencies, that is the ones the players believe to pay due to the fact that they are only aware of the existence of their neighbors, and total and maximum perceived latencies, i.e. actually experienced due to all (and not only the known) players using the same facilities. ::: ::: All the results are then extended to singleton congestion games.
---
paper_title: Pure Nash equilibria in player-specific and weighted congestion games

paper_content:

Unlike standard congestion games, weighted congestion games and congestion games with player-specific delay functions do not necessarily possess pure Nash equilibria. It is known, however, that there exist pure equilibria for both of these variants in the case of singleton congestion games, i. e., if the players' strategy spaces contain only sets of cardinality one. In this paper, we investigate how far such a property on the players' strategy spaces guaranteeing the existence of pure equilibria can be extended. We show that both weighted and player-specific congestion games admit pure equilibria in the case of matroid congestion games, i. e., if the strategy space of each player consists of the bases of a matroid on the set of resources. We also show that the matroid property is the maximal property that guarantees pure equilibria without taking into account how the strategy spaces of different players are interweaved. In the case of player-specific congestion games, our analysis of matroid games also yields a polynomial time algorithm for computing pure equilibria.
---
paper_title: Cooperative Control and Potential Games

paper_content:

We present a view of cooperative control using the language of learning in games. We review the game-theoretic concepts of potential and weakly acyclic games, and demonstrate how several cooperative control problems, such as consensus and dynamic sensor coverage, can be formulated in these settings. Motivated by this connection, we build upon game-theoretic concepts to better accommodate a broader class of cooperative control problems. In particular, we extend existing learning algorithms to accommodate restricted action sets caused by the limitations of agent capabilities and group based decision making. Furthermore, we also introduce a new class of games called sometimes weakly acyclic games for time-varying objective functions and action sets, and provide distributed algorithms for convergence to an equilibrium.
---
paper_title: A Shapley Value Representation of Potential Games

paper_content:

In potential games, as considered by Monderer and Shapley (1996a, Games Econom. Behav.14, 124–143), each player's gain from a deviation is equal to the gain in a potential function. We prove that a game has a potential function if and only if its payoff functions coincide with the Shapley value of a particular class of cooperative games indexed by the set of strategy profiles. Also a potential function of a noncooperative potential game coincides with the potentials (cf. Hart and Mas-Colell, 1989, Econometrica57, 589–614) of cooperative games indexed by the strategy set. Journal of Economic Literature Classification Numbers: C71, C72.
---
paper_title: Overview of collective intelligence

paper_content:

In this chapter an analysis of the behavior of an arbitrary (perhaps massive) collective of computational processes in terms of an associated “world” utility function is presented We concentrate on the situation where each process in the collective can be viewed as though it were striving to maximize its own private utility function. For such situations the central design issue is how to initialize and update the collective's structure, in particular the private utility functions, so as to induce the overall collective to behave in a way that has large values of the world utility. Traditional “team game” approaches to this problem simply set each private utility function equal to the world utility function. The “collective intelligence” (COIN) framework is a semiformal set of heuristics that have recently been used to construct private utility functions that in many experiments have resulted in world utility values up to orders of magnitude superior to that ensuing from use of the team game utility. In this chapter we introduce a formal mathematics for analyzing and designing collectives. We also use this mathematics to suggest new private utilities that should outperform the COIN heuristics in certain kinds of domains. In accompanying work we use that mathematics to explain previous experimental results concerning the superiority of COIN heuristics. In that accompanying work we also use the mathematics to make numerical predictions, some of which we then test. In this way these two papers establish the study of collectives as a proper science, involving theory, explanation of old experiments, prediction concerning new experiments, and engineering insights.
---
paper_title: Distributed Welfare Games

paper_content:

Game-theoretic tools are becoming a popular design choice for distributed resource allocation algorithms. A central component of this design choice is the assignment of utility functions to the individual agents. The goal is to assign each agent an admissible utility function such that the resulting game possesses a host of desirable properties, including scalability, tractability, and existence and efficiency of pure Nash equilibria. In this paper we formally study this question of utility design on a class of games termed distributed welfare games. We identify several utility design methodologies that guarantee desirable game properties irrespective of the specific application domain. Lastly, we illustrate the results in this paper on two commonly studied classes of resource allocation problems: “coverage” problems and “coloring” problems.
---
paper_title: Cooperative Control and Potential Games

paper_content:

We present a view of cooperative control using the language of learning in games. We review the game-theoretic concepts of potential and weakly acyclic games, and demonstrate how several cooperative control problems, such as consensus and dynamic sensor coverage, can be formulated in these settings. Motivated by this connection, we build upon game-theoretic concepts to better accommodate a broader class of cooperative control problems. In particular, we extend existing learning algorithms to accommodate restricted action sets caused by the limitations of agent capabilities and group based decision making. Furthermore, we also introduce a new class of games called sometimes weakly acyclic games for time-varying objective functions and action sets, and provide distributed algorithms for convergence to an equilibrium.
---
paper_title: Distributed Asynchronous Deterministic and Stochastic Gradient Optimization Algorithms

paper_content:

We present a model for asynchronous distributed computation and then proceed to analyze the convergence of natural asynchronous distributed versions of a large class of deterministic and stochastic gradient-like algorithms. We show that such algorithms retain the desirable convergence properties of their centralized counterparts, provided that the time between consecutive communications between processors plus communication delays are not too large.
---
paper_title: Convergence of cognitive radio networks

paper_content:

In this paper, we examine the conditions and behavior of several common convergence dynamics from game theory and show how they influence the structure of networks of cognitive radios. We then apply these to previously proposed distributed power control algorithms and describe how they impact network complexity.
---
paper_title: Best response dynamics and socially stable strategies

paper_content:

Abstract An evolutionarily stable strategy (Maynard Smith and Price, Nature (London) 246 (1973), 15–18) is a strategy which is robust against a tiny invasion of mutants. Best response dynamics is a dynamic process in which the frequency of a strategy increases only if it is a best response to the present strategy distribution. Gilboa and Matsui ( Econometrica 59 (1991), 859–867) proposed a stability concept directly derived from this dynamic process. Modifying the above two stability concepts, this paper shows the equivalence between the static concept and the dynamic one. Their set-valued versions always exist. Examples are given to see their usefulness in analyzing forward induction and preplay communication.
---
paper_title: Markov Approximation for Combinatorial Network Optimization

paper_content:

Many important network design problems are fundamentally combinatorial optimization problems. A large number of such problems, however, cannot readily be tackled by distributed algorithms. The Markov approximation framework studied in this paper is a general technique for synthesizing distributed algorithms. We show that when using the log-sum-exp function to approximate the optimal value of any combinatorial problem, we end up with a solution that can be interpreted as the stationary probability distribution of a class of time-reversible Markov chains. Selected Markov chains among this class yield distributed algorithms that solve the log-sum-exp approximated combinatorial network optimization problem. By examining three applications, we illustrate that the Markov approximation technique not only provides fresh perspectives to existing distributed solutions, but also provides clues leading to the construction of new distributed algorithms in various domains with provable performance. We believe the Markov approximation techniques will find applications in many other network optimization problems.
---
paper_title: The Statistical Mechanics of Strategic Interaction

paper_content:

I study strategic interaction among players who live on a lattice. Each player interacts directly with only a finite set of neighbors, but any two players indirectly interact through a finite chain of direct interactions. I examine various stochastic strategy revision processes, including (myopic) best response and stochastic choice. I discuss both stationary distributions and the limit behavior of these Markov processes. Stationary distributions are partially characterized, and the asymptotic behavior of stochastic choice for those processes whose choice rule is nearly best-response is related to equilibrium selection in symmetric 2 × 2 and n × n coordination games. Journal of Economic Literature Classification Number: C78.
---
paper_title: The logit-response dynamics

paper_content:

We develop a characterization of stochastically stable states for the logit-response learning dynamics in games, with arbitrary specification of revision opportunities. The result allows us to show convergence to the set of Nash equilibria in the class of best-response potential games and the failure of the dynamics to select potential maximizers beyond the class of exact potential games. We also study to which extent equilibrium selection is robust to the specification of revision opportunities. Our techniques can be extended and applied to a wide class of learning dynamics in games.
---
paper_title: GADIA: A Greedy Asynchronous Distributed Interference Avoidance Algorithm

paper_content:

In this paper, the problem of distributed dynamic frequency allocation is considered for a canonical communication network, which spans several networks such as cognitive radio networks and digital subscriber lines (DSLs). A greedy asynchronous distributed interference avoidance (GADIA) algorithm for horizontal spectrum sharing has been proposed that achieves performance close to that of a centralized optimal algorithm. The convergence of the GADIA algorithm to a near-optimal frequency allocation strategy is proved and several asymptotic performance bounds have been established for various spatial configurations of the network nodes. Furthermore, the near-equilibrium dynamics of the GADIA algorithm has been studied using the Glauber dynamics, by identifying the problem with the antiferromagnetic inhomogeneous long-range Potts model. Using the near-equilibrium dynamics and methods from stochastic analysis, the robustness of the algorithm with respect to time variations in the activity of network nodes is studied. These analytic results along with simulation studies reveal that the performance is close to that of an optimum centralized frequency allocation algorithm. Further simulation studies confirm that our proposed algorithm outperforms the iterative water-filling algorithm in the low signal-to-interference-plus-noise ratio (SINR) regime, in terms of achieved sum rate, complexity, convergence rate, and robustness to time-varying node activities.
---
paper_title: Revisiting log-linear learning: Asynchrony, completeness and payoff-based implementation

paper_content:

The theory of learning in games has sought to understand how and why equilibria emerge in non-cooperative games. Traditionally, social science literature develops descriptive game theoretic models for players, analyzes the limiting behavior, and generalizes the results for larger classes of games. Recently, there has been a significant amount of research seeking to understand these behavioral models not from a descriptive point of view, but rather from a prescriptive point of view [1]–[4]. The goal is to use these behavioral models as a prescriptive control approach in distributed multi-agent systems where the guaranteed limiting behavior would represent a desirable operating condition.
---
paper_title: Measurement-Based Self Organization of Interfering 802.11 Wireless Access Networks

paper_content:

The popularity of IEEE 802.11 WLANs has led to dense deployments in urban areas. High density leads to sub-optimal performance unless the interfering networks learn how to optimally use and share the spectrum. This paper proposes two fully distributed algorithms that allow (i) multiple interfering 802.11 access points to select their operating frequency in order to minimize interference, and (ii) users to choose the access point they attach to, in order to get their fair share of the whole network bandwidth. The proposed algorithms rely on Gibbs sampler, and do not require explicit coordination among the wireless devices. They only require the participating wireless nodes to measure local quantities such as interference and transmission delay. The algorithms are shown to lead to optimal bandwidth sharing, where optimality is defined according to the minimal potential delay. We analytically prove the convergence of the proposed algorithms, and study their performance by simulation.
---
paper_title: Adaptive channel allocation spectrum etiquette for cognitive radio networks

paper_content:

In this work, we propose a game theoretic framework to analyze the behavior of cognitive radios for distributed adaptive channel allocation. We define two different objective functions for the spectrum sharing games, which capture the utility of selfish users and cooperative users, respectively. Based on the utility definition for cooperative users, we show that the channel allocation problem can be formulated as a potential game, and thus converges to a deterministic channel allocation Nash equilibrium point. Alternatively, a no-regret learning implementation is proposed for both scenarios and it is shown to have similar performance with the potential game when cooperation is enforced, but with a higher variability across users. The no-regret learning formulation is particularly useful to accommodate selfish users. Non-cooperative learning games have the advantage of a very low overhead for information exchange in the network. We show that cooperation based spectrum sharing etiquette improves the overall network performance at the expense of an increased overhead required for information exchange
---
paper_title: An Interference-Minimization Potential Game for OFDMA-Based Distributed Spectrum Sharing Systems

paper_content:

Wireless orthogonal frequency-division multiple-access (OFDMA) networks, where distributed users can access the spectrum dynamically, offer great flexibility and the potential for the efficient utilization of scarce spectrum resources. Despite that, managing such large-scale networks while maintaining fair and efficient spectrum usage poses a great challenge, mainly due to cochannel interference from the spatially reusable subcarrier. This paper considers the problem of interference minimization in such a scenario from a game-theoretical viewpoint. A general framework that defines the distributed OFDMA-based spectrum access problem is presented. Next, our game-theoretical analysis shows that the proposed interference-minimizing utility function exhibits the properties of a potential game. Given a deterministic number of subcarriers by each player, there exists a pure-strategy Nash equilibrium solution, and therefore, convergence can be guaranteed via sequential best-response dynamics. Our simulation results verify the analysis, and at the same time, the fairness and optimality of the solutions obtained through the proposed game are examined.
---
paper_title: Joint Optimization of Transmission-Order Selection and Channel Allocation for Bidirectional Wireless Links—Part I: Game Theoretic Analysis

paper_content:

In this two-part paper, we consider a system consist- ing of bidirectional wireless links that interfere with each other, which has been the of focus of intensive research recently in emerging wireless systems like Device-to-Device (D2D) commu- nications underlaying cellular networks, heterogeneous networks, and small-cell networks. The problem is allocating the time re- sources (transmission orders) and frequency resources (channels) among the transmitters such that the overall network interference is minimized. Here, transmission order (TO) is a novel dimension for optimization. In Part I, we analyze the TO optimization prob- lem in the presence of channel allocation (CA), i.e., joint CA and the TO optimization problem from a game theoretic perspective, and prove that the joint optimization problem can be formulated as an exact potential game, which has at least one "pure strategy Nash Equilibrium" for any subset of the complete CA-TO action set and for any initial CA and TO conditions. We also show that the proposed joint CA and TO game is equal to the max-cut of a novel TO-dependent holistic system interference graph. In Part II, we present novel joint CA-TO algorithms and their performance analysis in D2D communications underlays.
---
paper_title: Joint Optimization of Transmission-Order Selection and Channel Allocation for Bidirectional Wireless Links—Part II: Algorithms

paper_content:

This is the second in a two-part series of papers on transmission order (TO) optimization in the presence of channel allocation (CA), i.e., joint optimization of the TO selection and CA problem, for interfering bidirectional wireless links. Part I of this paper thoroughly analyzes the joint optimization problem from a game theoretic perspective for a general deterministic setting. Here in Part II, we present novel distributed and centralized CA-TO algorithms, together with their performance analysis, for Device-to-Device (D2D) communications underlaying cellular net- works based on the findings in Part I of this paper. Here, TO is a novel dimension for optimization. In Part II, we propose and analyze novel two distributed and one centralized joint CA-TO al- gorithms. Our investigations show that: i) our algorithms contain many of the existing TO algorithms and CA algorithms as its spe- cial cases and can thus be considered as a general framework for the joint CA and TO optimization. The computer simulations for TDD-based D2D communications underlaying cellular network show that the proposed distributed and centralized joint CA-TO algorithms remarkably outperform the reference algorithms.
---
paper_title: Cross layer interference mitigation using a convergent two-stage game for ad hoc networks

paper_content:

In this paper, we concentrate on convergence issues of a two stage game namely on joint beamforming and channel allocation in an ad hoc network. Maximization of the received signal-to-interference-plus-noise (SINR) ratios between two communicating nodes under constant transmit power is considered. We propose a convergent sequential distortionless beamforming (SDRB) and cooperative channel allocation (CCA) algorithm which we call as SDRB_CCA, to mitigate the interference in the network. In this algorithm, a suboptimum beamforming algorithm is performed in PHY layer and a cooperative (or non-greedy) channel allocation is assigned based on the definition of potential games in MAC layer in an iterative manner. The payoff of each channel selection includes the interference received at each node as well as the interference that this selection will cause on the other nodes. Simulation results supported our analytical results in the sense that SDRB_CCA converges at the expense of decrease in average rate compared to the optimum joint iterative beamforming and greedy channel allocation (O_JIBGCA) algorithm especially in over-loaded scenarios.
---
paper_title: A stackelberg game for power control and channel allocation in cognitive radio networks

paper_content:

The ongoing growth in wireless communication continues to increase demand on the frequency spectrum. The current rigid frequency band allocation policy leads to a significant under-utilization of this scarce resource. However, recent policy changes by the Federal Communications Commission (FCC) and research directions suggested by the Defense Advanced Research Projects Agency (DARPA) have been focusing on wireless devices that can adaptively and intelligently adjust their transmission characteristics, which are known as cognitive radios. This paper suggests a game theoretical approach that allows master-slave cognitive radio pairs to update their transmission powers and frequencies simultaneously. This is shown to lead to an exact potential game, for which it is known that a particular update scheme converges to a Nash Equilibrium (NE). Next, a Stackelberg game model is presented for frequency bands where a licensed user has priority over opportunistic cognitive radios. We suggest a modification to the exact potential game discussed earlier that would allow a Stackelberg leader to charge a virtual price for communicating over a licensed channel. We investigate virtual price update algorithms for the leader and prove the convergence of a specific algorithm. Simulations performed in Matlab verify our convergence results and demonstrate the performance gains over alternative algorithms.
---
paper_title: Subcarrier assignment in multi-cell OFDMA systems via interference minimization game

paper_content:

Fair and efficient subcarrier assignment for an infrastructure-based cellular OFDMA network is a challenging problem due to interferences from neighboring cells. In this paper, we investigate this problem using potential game theory, where the utility function adopted is meant for minimizing the co-channel interferences among different players. Each of these players is considered to be a cell with a central base station (BS) and its multiple mobile stations (MS) in a downlink scenario. Under such formulation, we establish the potential game. Hence, a Nash equilibrium (NE) will be guaranteed for the proposed game, which can be achieved via certain strategy dynamics such as the best/better responses. We propose our iterative algorithm for obtaining the NEs and present numerical results to evaluate the performance of our game. Improvement in efficiency and fairness is observed in this study.
---
paper_title: Game Theory: Analysis of Conflict

paper_content:

Preface 1. Decision-Theoretic Foundations 1.1 Game Theory, Rationality, and Intelligence 1.2 Basic Concepts of Decision Theory 1.3 Axioms 1.4 The Expected-Utility Maximization Theorem 1.5 Equivalent Representations 1.6 Bayesian Conditional-Probability Systems 1.7 Limitations of the Bayesian Model 1.8 Domination 1.9 Proofs of the Domination Theorems Exercises 2. Basic Models 2.1 Games in Extensive Form 2.2 Strategic Form and the Normal Representation 2.3 Equivalence of Strategic-Form Games 2.4 Reduced Normal Representations 2.5 Elimination of Dominated Strategies 2.6 Multiagent Representations 2.7 Common Knowledge 2.8 Bayesian Games 2.9 Modeling Games with Incomplete Information Exercises 3. Equilibria of Strategic-Form Games 3.1 Domination and Ratonalizability 3.2 Nash Equilibrium 3.3 Computing Nash Equilibria 3.4 Significance of Nash Equilibria 3.5 The Focal-Point Effect 3.6 The Decision-Analytic Approach to Games 3.7 Evolution. Resistance. and Risk Dominance 3.8 Two-Person Zero-Sum Games 3.9 Bayesian Equilibria 3.10 Purification of Randomized Strategies in Equilibria 3.11 Auctions 3.12 Proof of Existence of Equilibrium 3.13 Infinite Strategy Sets Exercises 4. Sequential Equilibria of Extensive-Form Games 4.1 Mixed Strategies and Behavioral Strategies 4.2 Equilibria in Behavioral Strategies 4.3 Sequential Rationality at Information States with Positive Probability 4.4 Consistent Beliefs and Sequential Rationality at All Information States 4.5 Computing Sequential Equilibria 4.6 Subgame-Perfect Equilibria 4.7 Games with Perfect Information 4.8 Adding Chance Events with Small Probability 4.9 Forward Induction 4.10 Voting and Binary Agendas 4.11 Technical Proofs Exercises 5. Refinements of Equilibrium in Strategic Form 5.1 Introduction 5.2 Perfect Equilibria 5.3 Existence of Perfect and Sequential Equilibria 5.4 Proper Equilibria 5.5 Persistent Equilibria 5.6 Stable Sets 01 Equilibria 5.7 Generic Properties 5.8 Conclusions Exercises 6. Games with Communication 6.1 Contracts and Correlated Strategies 6.2 Correlated Equilibria 6.3 Bayesian Games with Communication 6.4 Bayesian Collective-Choice Problems and Bayesian Bargaining Problems 6.5 Trading Problems with Linear Utility 6.6 General Participation Constraints for Bayesian Games with Contracts 6.7 Sender-Receiver Games 6.8 Acceptable and Predominant Correlated Equilibria 6.9 Communication in Extensive-Form and Multistage Games Exercises Bibliographic Note 7. Repeated Games 7.1 The Repeated Prisoners Dilemma 7.2 A General Model of Repeated Garnet 7.3 Stationary Equilibria of Repeated Games with Complete State Information and Discounting 7.4 Repeated Games with Standard Information: Examples 7.5 General Feasibility Theorems for Standard Repeated Games 7.6 Finitely Repeated Games and the Role of Initial Doubt 7.7 Imperfect Observability of Moves 7.8 Repeated Wines in Large Decentralized Groups 7.9 Repeated Games with Incomplete Information 7.10 Continuous Time 7.11 Evolutionary Simulation of Repeated Games Exercises 8. Bargaining and Cooperation in Two-Person Games 8.1 Noncooperative Foundations of Cooperative Game Theory 8.2 Two-Person Bargaining Problems and the Nash Bargaining Solution 8.3 Interpersonal Comparisons of Weighted Utility 8.4 Transferable Utility 8.5 Rational Threats 8.6 Other Bargaining Solutions 8.7 An Alternating-Offer Bargaining Game 8.8 An Alternating-Offer Game with Incomplete Information 8.9 A Discrete Alternating-Offer Game 8.10 Renegotiation Exercises 9. Coalitions in Cooperative Games 9.1 Introduction to Coalitional Analysis 9.2 Characteristic Functions with Transferable Utility 9.3 The Core 9.4 The Shapkey Value 9.5 Values with Cooperation Structures 9.6 Other Solution Concepts 9.7 Colational Games with Nontransferable Utility 9.8 Cores without Transferable Utility 9.9 Values without Transferable Utility Exercises Bibliographic Note 10. Cooperation under Uncertainty 10.1 Introduction 10.2 Concepts of Efficiency 10.3 An Example 10.4 Ex Post Inefficiency and Subsequent Oilers 10.5 Computing Incentive-Efficient Mechanisms 10.6 Inscrutability and Durability 10.7 Mechanism Selection by an Informed Principal 10.8 Neutral Bargaining Solutions 10.9 Dynamic Matching Processes with Incomplete Information Exercises Bibliography Index
---
paper_title: Potential Game Approach for Self-Organized Interference Management in Closed Access Femtocell Networks

paper_content:

This paper proposes a game-theoretic approach for self-organized resource allocation in OFDMA femtocells with closed access configuration. The objective of the proposed scheme is to overcome the interference problem caused by co-channel operation of femtocells in an existing macrocell network using a self-organization capability of femto users. Inspired by the emerging cognitive radio technology, each femto user acts as an autonomous entity and attempts to select the most appropriate subset of resource blocks in a decentralized manner in order to mitigate the cross- and co-tier interference. Such a self-organized resource allocation scheme can be modeled as a potential game, which guarantees the convergence to a Nash equilibrium as long as distributed sequential play based on the best response strategy is adopted. Simulation results show that the proposed scheme improves the capacity of the femtocell network, while minimizing the performance degradation of the macrocell network.
---
paper_title: A Game-Theoretic Framework for Interference Coordination in OFDMA Relay Networks

paper_content:

Interference coordination, or interference-aware resource allocation, plays a key role in increasing resource utilization and improving cell throughput in orthogonal frequency-division multiple access (OFDMA) relay networks. In this paper, we develop a game-theoretic framework called the interference coordination game (ICG) to address this problem. To obtain the equilibrium of ICG and reduce the computational complexity, we decompose ICG into two subgames called the resource block assignment game (RBAG) and the power allocation game (PAG). The objective of the RBAG is to allocate resource block (RB) while avoiding interference. Based on RB assignment, we use the PAG to further reduce interferences and improve system payoff. As a higher system payoff can be accomplished by improving the individual players' payoff, each player can choose a best response to the others' action to implement system resource allocation while avoiding solving a complicated optimization problem. We theoretically prove the existence and uniqueness of equilibrium of ICG and conduct simulation experiments based on the model with realistic broadband channel propagation conditions to verify the analytical results and validate the effectiveness of ICG. In addition, numerical results show that our proposed interference coordination framework can guarantee that ICG converges to equilibrium and achieves better performance in terms of signal-to-interference-plus-noise ratio (SINR) distribution and system throughput compared with fractional frequency reuse scheme and schemes without interference coordination.
---
paper_title: Distributed cooperation among cognitive radios with complete and incomplete information

paper_content:

This paper proposes that secondary unlicensed users are allowed to opportunistically use the radio spectrum allocated to the primary licensed users, as long as they agree on facilitating the primary user communications by cooperating with them. The proposal is characterized by feasibility since the half-duplex option is considered, and incomplete knowledge of channel state information can be assumed. In particular, we consider two situations, where the users in the scenario have complete or incomplete knowledge of the surrounding environment. In the first case, we make the hypothesis of the existence of a Common Control Channel (CCC) where users share this information. In the second case, the hypothesis of the CCC is avoided, which improves the robustness and feasibility of the cognitive radio network. To model these schemes we make use of theory of exact and Bayesian potential games. We analyze the convergence properties of the proposed games, and we evaluate the outputs in terms of quality of service perceived by both primary and secondary users, showing that cooperation for cognitive radios is a promising framework and that the lack of complete information in the decision process only slightly reduces system performance.
---
paper_title: Interference Mitigation for Femtocell Networks Via Adaptive Frequency Reuse

paper_content:

The dense deployment of femtocells has brought new challenges for interference management. Flexible and efficient frequency reuse is one of promising approaches to tackling interference among femtocells. In this paper, we propose a semistatic intercell interference coordination (ICIC) scheme called adaptive frequency reuse (AFR). The proposed AFR scheme involves two algorithms, namely, primary subchannel self-configuration (PSC-SC), that served as ICIC, and interference-aware resource allocation, that served as intracell resource allocation. Compared with the no-ICIC scheme (i.e., Reuse 1), the proposed AFR scheme can achieve around 100% gain in terms of spectrum efficiency of cell-edge users with a minimal impact on the spectrum efficiency of cell-center users. Furthermore, the proposed PSC-SC algorithm is characteristic of low signaling overhead and fast convergence, which is very suitable for femtocell networks with constrained-capacity backhaul.
---
paper_title: Near-Potential Games: Geometry and Dynamics

paper_content:

Potential games are a special class of games for which many adaptive user dynamics converge to a Nash equilibrium. In this article, we study properties of near-potential games, that is, games that are close in terms of payoffs to potential games, and show that such games admit similar limiting dynamics. ::: We first focus on finite games in strategic form. We introduce a distance notion in the space of games and study the geometry of potential games and sets of games that are equivalent, with respect to various equivalence relations, to potential games. We discuss how, given an arbitrary game, one can find a nearby game in these sets. We then study dynamics in near-potential games by focusing on continuous-time perturbed best response dynamics. We characterize the limiting behavior of this dynamics in terms of the upper contour sets of the potential function of a close potential game and approximate equilibria of the game. Exploiting structural properties of approximate equilibrium sets, we strengthen our result and show that for games that are sufficiently close to a potential game, the sequence of mixed strategies generated by this dynamics converges to a small neighborhood of equilibria whose size is a function of the distance from the set of potential games. ::: In the second part of the article, we study continuous games and show that our approach for characterizing the limiting sets in near-potential games extends to continuous games. In particular, we consider continuous-time best response dynamics and a variant of it (where players update their strategies only if there is at least ε utility improvement opportunity) in near-potential games where the strategy sets are compact and convex subsets of a Euclidean space. We show that these update rules converge to a neighborhood of equilibria (or the maximizer of the potential function), provided that the potential function of the nearby potential game satisfies some structural properties. Our results generalize the known convergence results for potential games to near-potential games.
---
paper_title: Distributed interference control in OFDMA-based femtocells

paper_content:

This paper proposes a decentralized interference control scheme for an OFDMA (Orthogonal Frequency Division Multiple Access) cellular scenario where multiple macrocells and femtocells are deployed. In particular, we model the distributed resource allocation problem by means of a potential game, which is demonstrated to converge to a unique and pure Nash equilibrum. In this game, the femto base stations are the players, their actions are the resource blocks and the corresponding power levels to be allocated for downlink transmission, and the utility is designed to guarantee coexistence with the macro system, guaranteeing a fair tradeoff between femto and macro systems' performances. To do that, the utility function does not only consider the capacity of the femtocells, but also the different sources of inter-system interference: macrocell to femtocell, femtocell to femtocell, and femtocell to macrocell. The game is solved by applying a better response dynamic, which first selects the best resource blocks allocation policy for the femtousers, and then selects the most appropriate power levels for each resource block, through the solution of the corresponding convex optimization problem. Simulation results show that the introduction of femtocells in the scenario increases the total system capacity, and that the considered utility function provides an improvement in macro system performance of up to 40%, while reducing the femto capacity only up to 7%, with respect to the well known iterative waterfilling game.
---
paper_title: Potential game approach for spectrum sharing in distributed cognitive radio networks

paper_content:

In a spectrum sharing system, lower-priority users are allowed to spatially reuse the spectrum allocated to higher-priority users as long as they do not disrupt communications of the latter. Therefore, to improve spectrum utilization, an important requirement for the former users is to manage the interference and ensure that the latter users can maintain reliable communications. In the present paper, a game theoretic framework of joint channel selection and power allocation for spectrum sharing in distributed cognitive radio networks is proposed. First, a utility function that captures the cooperative behavior to manage the interference and the satisfaction level to improve the throughput of the lower-priority users is defined. Next, based on the defined utility function, the proposed framework can be formulated as a potential game; thus, it is guaranteed to converge to a Nash equilibrium when the best response dynamic is performed. Simulation results show the convergence of the proposed potential game and reveal that performance improvements in terms of network throughput of the lower-priority users and outage probability of the higher-priority users can be achieved by the introduction of an adaptive coefficient adjustment scheme in the proposed utility function at the expense of the convergence to the Nash equilibrium.
---
paper_title: Game Theoretic Max-logit Learning Approaches for Joint Base Station Selection and Resource Allocation in Heterogeneous Networks

paper_content:

This paper investigates the problem of joint base station selection and resource allocation in an orthogonal frequency division multiple access (OFDMA) heterogeneous cellular network. The original throughput maximization problem is NP-hard and we propose solving it by using game theoretic stochastic learning approaches. To this end, we first transform the original problem into a tractable form, which has a weighted utility function. Then we prove that an exact potential game applies and it exists the best Nash equilibria which is a near optimal solution of the original problem when an efficient solution method of the weights is employed. To obtain the optimal solution, we redesign the utility function by leveraging a state space to formulate the original problem into an ordinal state based potential game, which is proved that it exists a recurrent state equilibrium point that maximizes system throughput. Furthermore, we propose two different variants of Max-logit learning algorithm based on these two games respectively: one is a simultaneous learning algorithm with less information exchange, which achieves the best Nash equilibria point of the exact potential game and the other is an efficient learning algorithm for the ordinal state based potential game, which can converge to the global optimization solution. Finally, numerical results are given to validate that theoretical findings.
---
paper_title: A stackelberg game for power control and channel allocation in cognitive radio networks

paper_content:

The ongoing growth in wireless communication continues to increase demand on the frequency spectrum. The current rigid frequency band allocation policy leads to a significant under-utilization of this scarce resource. However, recent policy changes by the Federal Communications Commission (FCC) and research directions suggested by the Defense Advanced Research Projects Agency (DARPA) have been focusing on wireless devices that can adaptively and intelligently adjust their transmission characteristics, which are known as cognitive radios. This paper suggests a game theoretical approach that allows master-slave cognitive radio pairs to update their transmission powers and frequencies simultaneously. This is shown to lead to an exact potential game, for which it is known that a particular update scheme converges to a Nash Equilibrium (NE). Next, a Stackelberg game model is presented for frequency bands where a licensed user has priority over opportunistic cognitive radios. We suggest a modification to the exact potential game discussed earlier that would allow a Stackelberg leader to charge a virtual price for communicating over a licensed channel. We investigate virtual price update algorithms for the leader and prove the convergence of a specific algorithm. Simulations performed in Matlab verify our convergence results and demonstrate the performance gains over alternative algorithms.
---
paper_title: Potential Games for Energy-Efficient Resource Allocation in Multipoint-to-Multipoint CDMA Wireless Data Networks

paper_content:

Abstract The problem of noncooperative resource allocation in a multipoint-to-multipoint CDMA cellular network is considered in this paper. The considered scenario is general enough to represent several key instances of modern wireless networks such as a multicellular network, a peer-to-peer network (interference channel), and a wireless network equipped with femtocells. In particular, the problem of joint transmit waveforms adaptation, linear receiver design, and transmit power control is examined. Several utility functions to be maximized are considered, and, among them, we cite the received SINR, and the transmitter energy efficiency, which is measured in bit/J, and represents the number of successfully delivered bits for each energy unit used for transmission. Resorting to the theory of potential games, noncooperative games admitting Nash equilibria in multipoint-to-multipoint cellular networks regardless of the channel coefficient realizations are designed. Computer simulations confirm that the considered games are convergent, and show the huge benefits that resource allocation schemes can bring to the performance of wireless data networks.
---
paper_title: A Joint Game-Theoretic Interference Coordination Approach in Uplink Multi-Cell OFDMA Networks

paper_content:

In this paper, we present a joint game-theoretic approach to perform inter-cell interference coordination in uplink multi-cell orthogonal frequency division multiple access networks. The coordinated user scheduling and power allocation are considered simultaneously. We prove the existence of the joint-strategy Nash equilibrium (NE) in which both the user scheduling and power allocation strategy reach NE. Then, we design a distributed joint-strategy iterative algorithm to perform interference-aware resource allocation where only partial information exchange is involved. Simulation results demonstrate the effectiveness of the proposed algorithm.
---
paper_title: Interference avoidance in networks with distributed receivers

paper_content:

Direct extensions of distributed greedy interference avoidance (IA) techniques developed for centralized networks to networks with multiple distributed receivers (as in ad hoc networks) are not guaranteed to converge. Motivated by this fact, we develop a waveform adaptation (WA) algorithm framework for IA based on potential game theory. The potential game model ensures the convergence of the designed algorithms in distributed networks and leads to desirable network solutions. Properties of the game model are then exploited to design distributed implementations of the algorithm that involve limited feedback in the network. Finally, variations of IA algorithms including IA with respect to legacy systems and IA with combined transmit-power and WA adaptations are investigated.
---
paper_title: Distributed resource allocation in cognitive radio networks with a game learning approach to improve aggregate system capacity

paper_content:

This paper presents a game theoretic solution for joint channel allocation and power control in cognitive radio networks analyzed under the physical interference model. The objective is to find a distributed solution that maximizes the network utility, defined with different criteria, with limited information. The problem is addressed through a non-cooperative game based on local information. Although the existence of a pure Nash Equilibrium cannot be assured for this game, simulation results show that it exists with high probability and with a performance similar to that of a potential game, where each player requires overall network information. The obtained results are compared with a centralized heuristic genetic algorithm to show the correctness of the proposals. From this point, utility functions for the local game are modified to restrict the transmitted power to drive the solution to a more cooperative approach. To overcome the convergence limitations of the local game, no-regret learning algorithms are used to perform the joint channel and power allocation. These algorithms provide stable mixed strategies in any scenario with even better global performance. This opens an interesting perspective to develop realistic protocols based on the modeled interactions and increases the adaptability to perform efficient opportunistic spectrum access.
---
paper_title: A measurement study of interference modeling and scheduling in low-power wireless networks

paper_content:

Accurate interference models are important for use in transmission scheduling algorithms in wireless networks. In this work, we perform extensive modeling and experimentation on two 20-node TelosB motes testbeds -- one indoor and the other outdoor -- to compare a suite of interference models for their modeling accuracies. We first empirically build and validate the physical interference model via a packet reception rate vs. SINR relationship using a measurement driven method. We then similarly instantiate other simpler models, such as hop-based, range-based, protocol model, etc. The modeling accuracies are then evaluated on the two testbeds using transmission scheduling experiments. We observe that while the physical interference model is the most accurate, it is still far from perfect, providing a 90-percentile error about 20-25% (and 80 percentile error 7-12%), depending on the scenario. The accuracy of the other models is worse and scenario-specific. The second best model trails the physical model by roughly 12-18 percentile points for similar accuracy targets. Somewhat similar throughput performance differential between models is also observed when used with greedy scheduling algorithms. Carrying on further, we look closely into the the two incarnations of the physical model -- 'thresholded' (conservative, but typically considered in literature) and 'graded' (more realistic). We show via solving the one shot scheduling problem, that the graded version can improve `expected throughput' over the thresholded version by scheduling imperfect links.
---
paper_title: Multi-Channel Assignment in Wireless Sensor Networks: A Game Theoretic Approach

paper_content:

In this paper, we formulate multi-channel assignment in Wireless Sensor Networks (WSNs) as an optimization problem and show it is NP-hard. We then propose a distributed Game Based Channel Assignment algorithm (GBCA) to solve the problem. GBCA takes into account both the network topology information and transmission routing information. We prove that there exists at least one Nash Equilibrium in the channel assignment game. Furthermore, we analyze the sub-optimality of Nash Equilibrium and the convergence of the Best Response in the game. Simulation results are given to demonstrate that GBCA can reduce interference significantly and achieve satisfactory network performance in terms of delivery ratio, throughput, channel access delay and energy consumption.
---
paper_title: Game Theoretical Approach for Channel Allocation in Wireless Sensor and Actuator Networks

paper_content:

In this paper, multi-channel allocation in wireless sensor and actuator networks is formulated as an optimization problem which is NP-hard. In order to efficiently solve this problem, a distributed game based channel allocation (GBCA) Algorithm is proposed by taking into account both network topology and routing information. For both tree/forest routing and non-tree/forest routing scenarios, it is proved that there exists at least one Nash Equilibrium for the problem. Furthermore, the sub- optimality of Nash Equilibrium and the convergence of the Best Response dynamics are also analyzed. Simulation results demonstrate that GBCA significantly reduces the interference and dramatically improves the network performance in terms of delivery ratio, throughput, channel access delay, and energy consumption.
---
paper_title: Management of dominant interference in cognitive radio networks

paper_content:

A distributed channel allocation scheme aware of interference in cognitive radio networks is proposed. The objective of the proposed scheme is to minimize the number of dominant interference signals over a threshold instead of the total interference power. The proposed channel allocation can be treated by using game theory and proved to be a potential game, thus it is guaranteed to converge to a Nash equilibrium. In addition, the proposed channel allocation only requires the channel state of neighboring users while channel allocation minimizing the total interference power requires the channel state of all users. Simulation results reveal that the proposed channel allocation reduces both the required information exchange and the number of channel updates at a slight loss of network throughput.
---
paper_title: Distributed TV spectrum allocation for cognitive cellular network under game theoretical framework

paper_content:

This paper proposes efficient schemes for wireless cellular base stations to utilize TV white spectrum (such base stations referred to as white base stations - WBS), so that WBSes can provide good services to their end terminals without violating the incumbent TV services. In particular, we consider two complementary problems. On the one hand, given a set of TV stations and white base stations, maximum permitted transmit power levels on all channels for each base stations needs to be determined. By use of convex programming, we propose here an improved, centralized mechanism. On the other hand, once the maximum transmit powers are determined, each white base station needs to choose a channel with the maximal permitted power on that channel such that the resulting cell performance is improved. Allocating channels with nonidentical transmission power and asymmetric interference is formulated into congestion game for the first time, and an algorithm is derived thereafter which converges after a small number of iterations in simulation. However, the scheme requires geo information coupled with a radio map to decide at each WBS in a decentralized manner about the channel usage. We find that in comparison to several other decentralized schemes, our proposed approach first of all converges after a small number of iterations while on the other hand it is able to achieve the same network performance spending significantly lower transmit power.
---
paper_title: Performance of Distributed Dynamic Frequency Selection Schemes for Interference Reducing Networks

paper_content:

One of the more commonly envisioned algorithms for cognitive radios is spectrum filling via dynamic frequency selection. Applying the cognitive radio design framework proposed in [1], we formalize a low complexity distributed ad-hoc dynamic frequency sele ction algorithm that converges to near-minimal interference frequency re-use patterns. We then examine the performance of this algorithm in the presences of practical considerations such as intra-network policy variations and timing issues and show that while this leads to situations that violate the framework of [1], the steady-state and convergence properties of the framework are still preserved. 1. This work was made possible through the support basic research grant # N000140310629 from the Office of Naval Research, the National Science Foundation Integrated Graduate Education and Research Training (IGERT) sponsored Integrated Research and Education in Advanced Networking (IREAN) fellowship and the support of MPRG and Wireless @ Virginia Tech industrial affiliates.
---
paper_title: Measurement-Based Self Organization of Interfering 802.11 Wireless Access Networks

paper_content:

The popularity of IEEE 802.11 WLANs has led to dense deployments in urban areas. High density leads to sub-optimal performance unless the interfering networks learn how to optimally use and share the spectrum. This paper proposes two fully distributed algorithms that allow (i) multiple interfering 802.11 access points to select their operating frequency in order to minimize interference, and (ii) users to choose the access point they attach to, in order to get their fair share of the whole network bandwidth. The proposed algorithms rely on Gibbs sampler, and do not require explicit coordination among the wireless devices. They only require the participating wireless nodes to measure local quantities such as interference and transmission delay. The algorithms are shown to lead to optimal bandwidth sharing, where optimality is defined according to the minimal potential delay. We analytically prove the convergence of the proposed algorithms, and study their performance by simulation.
---
paper_title: GADIA: A Greedy Asynchronous Distributed Interference Avoidance Algorithm

paper_content:

In this paper, the problem of distributed dynamic frequency allocation is considered for a canonical communication network, which spans several networks such as cognitive radio networks and digital subscriber lines (DSLs). A greedy asynchronous distributed interference avoidance (GADIA) algorithm for horizontal spectrum sharing has been proposed that achieves performance close to that of a centralized optimal algorithm. The convergence of the GADIA algorithm to a near-optimal frequency allocation strategy is proved and several asymptotic performance bounds have been established for various spatial configurations of the network nodes. Furthermore, the near-equilibrium dynamics of the GADIA algorithm has been studied using the Glauber dynamics, by identifying the problem with the antiferromagnetic inhomogeneous long-range Potts model. Using the near-equilibrium dynamics and methods from stochastic analysis, the robustness of the algorithm with respect to time variations in the activity of network nodes is studied. These analytic results along with simulation studies reveal that the performance is close to that of an optimum centralized frequency allocation algorithm. Further simulation studies confirm that our proposed algorithm outperforms the iterative water-filling algorithm in the low signal-to-interference-plus-noise ratio (SINR) regime, in terms of achieved sum rate, complexity, convergence rate, and robustness to time-varying node activities.
---
paper_title: Interference Reducing Networks

paper_content:

When cognitive radios operate in a network, each link's adaptations impact the decisions of other cognitive radios which spawns an interactive decision processes. The existence of these interactive processes could potentially limit the deployment of cognitive radios as it is difficult to guarantee that the resulting behavior will avoid a tragedy of the commons, much less provide optimal performance. This paper proposes a novel design framework that ensures that cognitive radio interactions are beneficial and reduce sum network interference with each adaptation. Five different approaches to implementing algorithms that satisfy this framework are presented ? two of which rely on collaboration and three which permit autonomous adaptations.
---
paper_title: A Stochastic Game-Theoretic Approach for Interference Mitigation in Small Cell Networks

paper_content:

In this letter, we investigate the distributed channel selection for interference mitigation in small cell networks considering the random deployment and dynamic on–off activity. Game theory is adopted to analyze the distributed and interactive decision making, and the problem is formulated as an exact potential game, in which the Nash equilibrium (NE) minimizes the expected network interference, either globally or locally. Furthermore, we design a fully distributed, no-regret channel selection algorithm to find the NE solution in dynamic environment.
---
paper_title: Investigation on GADIA Algorithms for Interference Avoidance: A Game-Theoretic Perspective

paper_content:

In a recent paper (B. Babadi and V. Tarokh, "GADIA: A greedy asynchronous distributed interference avoidance algorithm", IEEE Trans. Inf. Theory, vol. 56, no. 12, pp. 6228-6252, 2010), two asynchronous distributed spectrum allocation algorithms, called the basic GADIA and the soft GADIA respectively, were proposed to solve the problem of interference avoidance for a canonical class of communication networks. The methodology proposed therein is constructive. In this letter, we re-investigate this problem from a game-theoretic perspective, and obtain some key incremental results in favor of the original paper.
---
paper_title: Distributed Channel Selection for Interference Mitigation in Dynamic Environment: A Game-Theoretic Stochastic Learning Solution

paper_content:

In this paper, we investigate the problem of distributed chan- nel selection for interference mitigation in a canonical communication network. The channel is assumed time-varying, and the active user set is considered dynamically variable due to the specific service requirement. This problem is formulated as an exact potential game, and the optimality property of the solution to this problem is first analyzed. Then, we design a low-complexity fully distributed no-regret learning algorithm for chan- nel adaptation in a dynamic environment, where each active player can independently and automatically update its action with no information exchange. The proposed algorithm is proven to converge to a set of correlated equilibria with a probability of 1. Finally, we conduct simula- tions to demonstrate that the proposed algorithm achieves near-optimal performance for interference mitigation in dynamic environments. Index Terms—Distributed channel allocation, dynamic environment, interference mitigation, no-regret learning, potential game.
---
paper_title: Joint dynamic frequency selection and power control for cognitive radio networks

paper_content:

In this paper, joint dynamic frequency selection and transmit power control problem with the goal of power minimization for a target SINR is investigated for cognitive radio networks. The optimization problem is formulated and three algorithms are proposed: A centralized algorithm based on graph coloring, and two distributed algorithms based on game theory; one for coordinated and the other for non-coordinated scenarios. Performance of the proposed algorithms in terms of power minimization and convergence speed is evaluated through simulations. Comparing the performance with the optimum solution, all three algorithms show near-optimum power minimization performance for the simulated scenarios. Based on these results, scenarios in which each algorithm is more appropriate to be used are identified.
---
paper_title: A game-theoretic framework for interference avoidance

paper_content:

Various iterative algorithms for interference avoidance (IA) in networks with co-located receivers, suitable for distributed implementation, have been proposed in the literature. In this paper, the IA problem is cast in a game-theoretic framework and is formulated as a potential game. This formulation accommodates previously proposed algorithms and, in addition, gives us a framework that enables the design of new distributed and convergent algorithms for IA including algorithms with nonidentical utility functions for the users. Two new convergence results for potential games are then derived. The first result establishes the convergence of a class of potential games to the global solution while following best response iterations and when noise is added. The second result establishes the convergence of potential games to the Nash equilibria of the game while following random better response iterations. The first result combined with the potential game formulation allows us to show that for a large class of network scenarios, arbitrarily small noise assures the convergence of best response IA algorithms, including the eigeniterations, to an arbitrarily small neighborhood of the globally optimal signature sequence set. The second result enables the design of reduced feedback mechanisms for IA that converge to desirable solutions.
---
paper_title: GADIA: A Greedy Asynchronous Distributed Interference Avoidance Algorithm

paper_content:

In this paper, the problem of distributed dynamic frequency allocation is considered for a canonical communication network, which spans several networks such as cognitive radio networks and digital subscriber lines (DSLs). A greedy asynchronous distributed interference avoidance (GADIA) algorithm for horizontal spectrum sharing has been proposed that achieves performance close to that of a centralized optimal algorithm. The convergence of the GADIA algorithm to a near-optimal frequency allocation strategy is proved and several asymptotic performance bounds have been established for various spatial configurations of the network nodes. Furthermore, the near-equilibrium dynamics of the GADIA algorithm has been studied using the Glauber dynamics, by identifying the problem with the antiferromagnetic inhomogeneous long-range Potts model. Using the near-equilibrium dynamics and methods from stochastic analysis, the robustness of the algorithm with respect to time variations in the activity of network nodes is studied. These analytic results along with simulation studies reveal that the performance is close to that of an optimum centralized frequency allocation algorithm. Further simulation studies confirm that our proposed algorithm outperforms the iterative water-filling algorithm in the low signal-to-interference-plus-noise ratio (SINR) regime, in terms of achieved sum rate, complexity, convergence rate, and robustness to time-varying node activities.
---
paper_title: Optimal distributed interference avoidance: potential game and learning

paper_content:

This article studies the problem of distributed interference avoidance (IA) through channel selection for distributed wireless networks, where mutual interference only occurs among nearby users. First, an interference graph is used to characterise the limited range of interference, and then the distributed IA problem is formulated as a graph colouring problem. Because solving the graph colouring problem is non-deterministic polynomial hard even in a centralised manner, the task of obtaining the optimal channel selection profile distributively is challenging. We formulate this problem as a channel selection game, which is proved to be an exact potential game with the weighted aggregate interference serving as the potential function. On the basis of this, a distributed learning algorithm is proposed to achieve the optimal channel selection profile that constitutes an optimal Nash equilibrium point of the channel selection game. The proposed learning algorithm is fully distributed because it needs information about neither the network topology nor the actions and the experienced interference of others. Simulation results show that the proposed potential game theoretic IA algorithm outperforms the existing algorithm because it minimises the aggregate weighted interference and achieves higher network rate. Copyright © 2012 John Wiley & Sons, Ltd.
---
paper_title: Database-Assisted Distributed Spectrum Sharing

paper_content:

According to FCC's ruling for white-space spectrum access, white-space devices are required to query a database to determine the spectrum availability. In this paper, we study the database-assisted distributed white-space access point (AP) network design. We first model the cooperative and non-cooperative channel selection problems among the APs as the system-wide throughput optimization and non-cooperative AP channel selection games, respectively, and design distributed AP channel selection algorithms that achieve system optimal point and Nash equilibrium, respectively. We then propose a state-based game formulation for the distributed AP association problem of the secondary users by taking the cost of mobility into account. We show that the state-based distributed AP association game has the finite improvement property, and design a distributed AP association algorithm that can converge to a state-based Nash equilibrium. Numerical results show that the algorithm is robust to the perturbation by secondary users' dynamical leaving and entering the system.
---
paper_title: Database-assisted Spectrum Access in Dynamic Networks: A Distributed Learning Solution

paper_content:

This paper investigates the problem of database-assisted spectrum access in dynamic TV white spectrum networks, in which the active user set is varying. Since there is no central controller and information exchange, it encounters dynamic and incomplete information constraints. To solve this challenge, we formulate a state-based spectrum access game and a robust spectrum access game. It is proved that the two games are ordinal potential games with the (expected) aggregate weighted interference serving as the potential functions. A distributed learning algorithm is proposed to achieve the pure strategy Nash equilibrium (NE) of the games. It is shown that the best NE is almost the same with the optimal solution and the achievable throughput of the proposed learning algorithm is very close to the optimal one, which validates the effectiveness of the proposed game-theoretic solution.
---
paper_title: Joint Channel Selection and Power Control in Infrastructureless Wireless Networks: A Multi-Player Multi-Armed Bandit Framework

paper_content:

This paper deals with the problem of efficient resource allocation in dynamic infrastructureless wireless networks. In a reactive interference-limited scenario, at each transmission trial, every transmitter selects a frequency channel from some common pool, together with a power level. As a result, for all transmitters, not only the fading gain, but the number and the power of interfering transmissions as well, vary over time. Due to the absence of a central controller and time varying network characteristics, it is highly inefficient for transmitters to acquire the global channel and network knowledge. Therefore, given no information, each transmitter selfishly intends to maximize its average reward, which is a function of the channel quality, as well as the joint selection profile of all transmitters. This scenario is modeled as an adversarial multiplayer multiarmed bandit game, where players attempt to minimize their so-called regret, while, at the network side, achieving equilibrium in some sense. Based on this model and to solve the resource allocation problem, in this paper, we develop two joint power level and channel selection strategies. We prove that the gap between the average rewards achieved by our approaches and that based on the best fixed strategy converges to zero asymptotically. Moreover, the empirical joint frequencies of the game converge to the set of correlated equilibria, which is characterized for two relaxed versions of the designed game.
---
paper_title: A game-theoretic framework for interference avoidance

paper_content:

Various iterative algorithms for interference avoidance (IA) in networks with co-located receivers, suitable for distributed implementation, have been proposed in the literature. In this paper, the IA problem is cast in a game-theoretic framework and is formulated as a potential game. This formulation accommodates previously proposed algorithms and, in addition, gives us a framework that enables the design of new distributed and convergent algorithms for IA including algorithms with nonidentical utility functions for the users. Two new convergence results for potential games are then derived. The first result establishes the convergence of a class of potential games to the global solution while following best response iterations and when noise is added. The second result establishes the convergence of potential games to the Nash equilibria of the game while following random better response iterations. The first result combined with the potential game formulation allows us to show that for a large class of network scenarios, arbitrarily small noise assures the convergence of best response IA algorithms, including the eigeniterations, to an arbitrarily small neighborhood of the globally optimal signature sequence set. The second result enables the design of reduced feedback mechanisms for IA that converge to desirable solutions.
---
paper_title: Joint Channel and Power Allocation in Wireless Mesh Networks: A Game Theoretical Perspective

paper_content:

This paper addresses the throughput maximization problem in wireless mesh networks. For the case of cooperative access points, we present a negotiation-based throughput maximization algorithm which adjusts the operating channel and power level among access points automatically, from a game-theoretical perspective. We show that this algorithm converges to the optimal channel and power assignment which yields the maximum overall throughput with arbitrarily high probability. Moreover, we analyze the scenario where access points belong to different regulation entities and hence non-cooperative. The long- term behavior and corresponding performance are investigated and the analytical results are verified by simulations.
---
paper_title: Near-Potential Games: Geometry and Dynamics

paper_content:

Potential games are a special class of games for which many adaptive user dynamics converge to a Nash equilibrium. In this article, we study properties of near-potential games, that is, games that are close in terms of payoffs to potential games, and show that such games admit similar limiting dynamics. ::: We first focus on finite games in strategic form. We introduce a distance notion in the space of games and study the geometry of potential games and sets of games that are equivalent, with respect to various equivalence relations, to potential games. We discuss how, given an arbitrary game, one can find a nearby game in these sets. We then study dynamics in near-potential games by focusing on continuous-time perturbed best response dynamics. We characterize the limiting behavior of this dynamics in terms of the upper contour sets of the potential function of a close potential game and approximate equilibria of the game. Exploiting structural properties of approximate equilibrium sets, we strengthen our result and show that for games that are sufficiently close to a potential game, the sequence of mixed strategies generated by this dynamics converges to a small neighborhood of equilibria whose size is a function of the distance from the set of potential games. ::: In the second part of the article, we study continuous games and show that our approach for characterizing the limiting sets in near-potential games extends to continuous games. In particular, we consider continuous-time best response dynamics and a variant of it (where players update their strategies only if there is at least ε utility improvement opportunity) in near-potential games where the strategy sets are compact and convex subsets of a Euclidean space. We show that these update rules converge to a neighborhood of equilibria (or the maximizer of the potential function), provided that the potential function of the nearby potential game satisfies some structural properties. Our results generalize the known convergence results for potential games to near-potential games.
---
paper_title: Opportunistic Spectrum Access in Cognitive Radio Networks: Global Optimization Using Local Interaction Games

paper_content:

We investigate the problem of achieving global optimization for distributed channel selections in cognitive radio networks (CRNs), using game theoretic solutions. To cope with the lack of centralized control and local influences, we propose two special cases of local interaction game to study this problem. The first is local altruistic game, in which each user considers the payoffs of itself as well as its neighbors rather than considering itself only. The second is local congestion game, in which each user minimizes the number of competing neighbors. It is shown that with the proposed games, global optimization is achieved with local information. Specifically, the local altruistic game maximizes the network throughput and the local congestion game minimizes the network collision level. Also, the concurrent spatial adaptive play (C-SAP), which is an extension of the existing spatial adaptive play (SAP), is proposed to achieve the global optimum both autonomously as well as rapidly.
---
paper_title: Opportunistic Spectrum Access Using Partially Overlapping Channels: Graphical Game and Uncoupled Learning

paper_content:

This article investigates the problem of distributed channel selection in opportunistic spectrum access (OSA) networks with partially overlapping channels (POC) using a game-theoretic learning algorithm. Compared with traditional non-overlapping channels (NOC), POC can increase the full-range spectrum utilization, mitigate interference and improve the network throughput. However, most existing POC approaches are centralized, which are not suitable for distributed OSA networks. We formulate the POC selection problem as an interference mitigation game. We prove that the game has at least one pure strategy NE point and the best pure strategy NE point minimizes the aggregate interference in the network. We characterize the achievable performance of the game by presenting an upper bound for aggregate interference of all NE points. In addition, we propose a simultaneous uncoupled learning algorithm with heterogeneous exploration rates to achieve the pure strategy NE points of the game. Simulation results show that the heterogeneous exploration rates lead to faster convergence speed and the throughput improvement gain of the proposed POC approach over traditional NOC approach is significant. Also, the proposed uncoupled learning algorithm achieves satisfactory performance when compared with existing coupled and uncoupled algorithms.
---
paper_title: Variable-Width Channel Allocation for Access Points: A Game-Theoretic Perspective

paper_content:

Channel allocation is a crucial concern in variable-width wireless local area networks. This work aims to obtain the stable and fair nonoverlapped variable-width channel allocation for selfish access points (APs). In the scenario of single collision domain, the channel allocation problem reduces to a channel-width allocation problem, which can be formulated as a noncooperative game. The Nash equilibrium (NE) of the game corresponds to a desired channel-width allocation. A distributed algorithm is developed to achieve the NE channel-width allocation that globally maximizes the network utility. A punishment-based cooperation self-enforcement mechanism is further proposed to ensure that the APs obey the proposed scheme. In the scenario of multiple collision domains, the channel allocation problem is formulated as a constrained game. Penalty functions are introduced to relax the constraints and the game is converted into a generalized ordinal potential game. Based on the best response and randomized escape, a distributed iterative algorithm is designed to achieve a desired NE channel allocation. Finally, computer simulations are conducted to validate the effectiveness and practicality of the proposed schemes.
---
paper_title: Common control channel assignment in cognitive radio networks using potential game theory

paper_content:

In a cognitive radio network, it is indispensable to assign common control channels for group operations of the secondary users of the spectrum. The assignment requires that multiple secondary users establish the least amount of frequency channels among them while each chooses a channel that has minimum interference to its nearby primary users. We model this problem as a strategic game and design its utility function such that the game is a potential game. A set of pure Nash equilibria are found by locating the local optima of the potential function. We develop sequential and asynchronous updates of game players' strategies using the best response dynamic. In order for the search to escape the local optimum and reach the global optimum of the potential function, we adopt simulated annealing in the sequential and asynchronous updates of the strategies. The optimal assignment of the common control channel is obtained accordingly and the convergence property is analyzed for these updating schemes.
---
paper_title: Centralized-distributed Spectrum Access for Small Cell Networks: A Cloud-based Game Solution

paper_content:

By employing the advances in wireless cloud technologies, this letter establishes a centralized-distributed optimization architecture for spectrum access in small cell networks. In the centralized aspect, the spectrum access problem is solved in the cloud. In the distributed aspect, the problem is solved by a game-theoretic solution, aiming to address the challenges of heavy computation complexity caused by the densely deployed small cells. The properties of the game, including the existence of pure Nash equilibrium and the achievable lower bound, are rigorously proved and analyzed. Furthermore, a cloud-assisted best response learning algorithm with low computational complexity is proposed, which converges to the global or local optima of the aggregate interference level of the small cell network. It is shown that the cloud-assisted algorithm converges rapidly and is scalable when increasing the number of small cells. Finally, simulation results are presented to validate the proposed cloud-based centralized-distributed solution.
---
paper_title: A potential game approach for uplink resource allocation in a multichannel wireless access network

paper_content:

We consider a resource allocation problem in a multichannel wireless access system being shared by several users for uplink transfer of elastic traffic. Each user can allocate its resources (e.g., radios, antennas or power) to one or more of the carriers. In this network scenario we consider a problem of noncooperative allocation of resources by the users, with each user's objective being to maximize its own utility. We apply the theory of potential games to solve this problem by transforming it into an equivalent global optimization one. We obtain structural properties of the equilibrium policies using tools from Schur concave stochastic orders. Finally, we propose a totally distributed algorithm that converges to a Nash Equilibrium of the system.
---
paper_title: A Bayesian Learning Automata-Based Distributed Channel Selection Scheme for Cognitive Radio Networks

paper_content:

We consider a scenario where multiple Secondary Users SUs operate within a Cognitive Radio Network CRN which involves a set of channels, where each channel is associated with a Primary User PU. We investigate two channel access strategies for SU transmissions. In the first strategy, the SUs will send a packet directly without operating Carrier Sensing Medium Access/Collision Avoidance CSMA/CA whenever a PU is absent in the selected channel. In the second strategy, the SUs implement CSMA/CA to further reduce the probability of collisions among co-channel SUs. For each strategy, the channel selection problem is formulated and demonstrated to be a so-called "Potential" game, and a Bayesian Learning Automata BLA has been incorporated into each SU so to play the game in such a manner that the SU can adapt itself to the environment. The performance of the BLA in this application is evaluated through rigorous simulations. These simulation results illustrate the convergence of the SUs to the global optimum in the first strategy, and to a Nash Equilibrium NE point in the second.
---
paper_title: Opportunistic Spectrum Access with Spatial Reuse: Graphical Game and Uncoupled Learning Solutions

paper_content:

This article investigates the problem of distributed channel selection for opportunistic spectrum access systems, where multiple cognitive radio (CR) users are spatially located and mutual interference only emerges between neighboring users. In addition, there is no information exchange among CR users. We first propose a MAC-layer interference minimization game, in which the utility of a player is defined as a function of the number of neighbors competing for the same channel. We prove that the game is a potential game with the optimal Nash equilibrium (NE) point minimizing the aggregate MAC-layer interference. Although this result is promising, it is challenging to achieve a NE point without information exchange, not to mention the optimal one. The reason is that traditional algorithms belong to coupled algorithms which need information of other users during the convergence towards NE solutions. We propose two uncoupled learning algorithms, with which the CR users intelligently learn the desirable actions from their individual action-utility history. Specifically, the first algorithm asymptotically minimizes the aggregate MAC-layer interference and needs a common control channel to assist learning scheduling, and the second one does not need a control channel and averagely achieves suboptimal solutions.
---
paper_title: Proportional and double imitation rules for spectrum access in cognitive radio networks

paper_content:

Abstract In this paper, we tackle the problem of opportunistic spectrum access in large-scale cognitive radio networks, where the unlicensed Secondary Users (SUs) access the frequency channels partially occupied by the licensed Primary Users (PUs). Each channel is characterized by an availability probability unknown to the SUs. We apply population game theory to model the spectrum access problem and develop distributed spectrum access policies based on imitation, a behavior rule widely applied in human societies consisting of imitating successful behaviors. We develop two imitation-based spectrum access policies based on the basic Proportional Imitation (PI) rule and the more advanced Double Imitation (DI) rule given that a SU can only imitate the other SUs operating on the same channel. A systematic theoretical analysis is presented for both policies on the induced imitation dynamics and the convergence properties of the proposed policies to the Nash equilibrium. Simple and natural, the proposed imitation-based spectrum access policies can be implemented distributedly based on solely local interactions and thus is especially suited in decentralized adaptive learning environments as cognitive radio networks.
---
paper_title: Opportunistic Spectrum Access in Unknown Dynamic Environment: A Game-Theoretic Stochastic Learning Solution

paper_content:

We investigate the problem of distributed channel selection using a game-theoretic stochastic learning solution in an opportunistic spectrum access (OSA) system where the channel availability statistics and the number of the secondary users are apriori unknown. We formulate the channel selection problem as a game which is proved to be an exact potential game. However, due to the lack of information about other users and the restriction that the spectrum is time-varying with unknown availability statistics, the task of achieving Nash equilibrium (NE) points of the game is challenging. Firstly, we propose a genie-aided algorithm to achieve the NE points under the assumption of perfect environment knowledge. Based on this, we investigate the achievable performance of the game in terms of system throughput and fairness. Then, we propose a stochastic learning automata (SLA) based channel selection algorithm, with which the secondary users learn from their individual action-reward history and adjust their behaviors towards a NE point. The proposed learning algorithm neither requires information exchange, nor needs prior information about the channel availability statistics and the number of secondary users. Simulation results show that the SLA based learning algorithm achieves high system throughput with good fairness.
---
paper_title: Joint Power and Channel Minimization in Topology Control: A Cognitive Network Approach

paper_content:

Wireless topology control is the process of structuring the connectivity between network nodes to achieve some network-wide goal. This paper presents a cognitive network approach to achieving the objectives of power and spectrum management. We cast the problem as a two phased non-cooperative game and use the properties of potential game theory to ensure the existence of, and convergence to, a desirable Nash equilibrium. Although this is a multi-objective optimization and the spectrum management problem is NP-hard, this selfish cognitive network constructs a topology that minimizes the maximum transmission power while simultaneously using, on average, less than 12% extra spectrum, as compared to the ideal solution.
---
paper_title: Distributed Spectrum Access with Spatial Reuse

paper_content:

Efficient distributed spectrum sharing mechanism is crucial for improving the spectrum utilization. The spatial aspect of spectrum sharing, however, is less understood than many other aspects. In this paper, we generalize a recently proposed spatial congestion game framework to design efficient distributed spectrum access mechanisms with spatial reuse. We first propose a spatial channel selection game to model the distributed channel selection problem with fixed user locations. We show that the game is a potential game, and develop a distributed learning mechanism that converges to a Nash equilibrium only based on users' local observations. We then formulate the joint channel and location selection problem as a spatial channel selection and mobility game, and show that it is also a potential game. We next propose a distributed strategic mobility algorithm, jointly with the distributed learning mechanism, that can converge to a Nash equilibrium.
---
paper_title: Database-Assisted Distributed Spectrum Sharing

paper_content:

According to FCC's ruling for white-space spectrum access, white-space devices are required to query a database to determine the spectrum availability. In this paper, we study the database-assisted distributed white-space access point (AP) network design. We first model the cooperative and non-cooperative channel selection problems among the APs as the system-wide throughput optimization and non-cooperative AP channel selection games, respectively, and design distributed AP channel selection algorithms that achieve system optimal point and Nash equilibrium, respectively. We then propose a state-based game formulation for the distributed AP association problem of the secondary users by taking the cost of mobility into account. We show that the state-based distributed AP association game has the finite improvement property, and design a distributed AP association algorithm that can converge to a state-based Nash equilibrium. Numerical results show that the algorithm is robust to the perturbation by secondary users' dynamical leaving and entering the system.
---
paper_title: Linearly coupled communication games

paper_content:

This paper discusses a special type of multi-user communication scenario, in which users' utilities are linearly impacted by their competitors' actions. We explicitly characterize the Nash equilibrium and Pareto boundary of the achievable utility region. To improve the performance in the non-cooperative scenarios, we investigate the properties of an alternative solution concept named conjectural equilibrium, in which individual users compensate for their lack of information by forming internal beliefs about their competitors. The global convergence of the best response and Jacobi update dynamics that achieve various conjectural equilibria are analyzed. It is shown that the Pareto boundaries of the investigated linearly coupled games can be sustained as stable conjectural equilibria if the belief functions are properly initialized. The investigated models apply to a variety of realistic applications encountered in the multiple access design, including wireless random access and flow control.
---
paper_title: Congestion games with player-specific constants

paper_content:

We consider a special case of weighted congestion games with playerspecific latency functions where each player uses for each particular resource a fixed (non-decreasing) delay function together with a player-specific constant. For each particular resource, the resource-specific delay function and the playerspecific constant (for that resource) are composed by means of a group operation (such as addition or multiplication) into a player-specific latency function. We assume that the underlying group is a totally ordered abelian group. In this way, we obtain the class of weighted congestion games with player-specific constants; we observe that this class is contained in the new intuitive class of dominance weighted congestion games. We obtain the following results: Games on parallel links: - Every unweighted congestion game has a generalized ordinal potential. - There is a weighted congestion game with 3 players on 3 parallel links that does not have the Finite Best-Improvement Property. - There is a particular best-improvement cycle for general weighted congestion games with player-specific latency functions and 3 players whose outlaw implies the existence of a pure Nash equilibrium. This cycle is indeed outlawed for dominance weighted congestion games with 3 players - and hence for weighted congestion games with player-specific constants and 3 players. Network congestion games: For unweighted symmetric network congestion games with player-specific additive constants, it is PLS-complete to find a pure Nash equilibrium. Arbitrary (non-network) congestion games: Every weighted congestion game with linear delay functions and player-specific additive constants has a weighted potential.
---
paper_title: Competitive scheduling in wireless collision channels with correlated channel state

paper_content:

We consider a wireless collision channel, shared by a finite number of mobile users who transmit to a common base station. Each user wishes to optimize its individual network utility that incorporates a natural tradeoff between throughput and power. The channel quality of every user is affected by global and time-varying conditions at the base station, which are manifested to all users in the form of a common channel state. Assuming that all users employ stationary, state-dependent transmission strategies, we investigate the properties of the Nash equilibrium of the resulting game between users. While the equilibrium performance can be arbitrarily bad (in terms of aggregate utility), we bound the efficiency loss at the best equilibrium as a function of a technology-related parameter. Under further assumptions, we show that sequential best-response dynamics converge to an equilibrium point in finite time, and discuss how to exploit this property for better network usage.
---
paper_title: Potential game for joint channel and power allocation in cognitive radio networks

paper_content:

Presented is a game theoretic solution for joint channel and power allocation in cognitive radio networks. This issue has been previously addressed, but the proposed games assume a global knowledge of the players' strategies, which make the solution not scalable. In contrast, here the problem is formulated as a potential game only requiring local information. The obtained results are compared with a metaheuristic genetic algorithm to show the correctness of the proposal.
---
paper_title: Distributed Learning-Based Spectrum Allocation with Noisy Observations in Cognitive Radio Networks

paper_content:

This paper studies the medium access design for secondary users (SUs) from a game-theoretic learning perspective. In consideration of the random return of primary users (PUs), a distributed SU access approach is presented based on an adaptive carrier sense multiple access (CSMA) scheme, in which each SU accesses multiple idle frequency slots of a licensed frequency band with adaptive activity factors. The problem of finding optimal activity factors of SUs is formulated as a potential game, and the existence, feasibility, and optimality of Nash equilibrium (NE) are analyzed. Furthermore, to achieve NEs of the formulated game, learning-based algorithms are developed in which each SU independently adjusts its activity factors. Convergence properties of best-response dynamics and log-linear dynamics are studied. Subsequently, by learning other SUs' behavior from locally available information, the convergence with probability of one to an arbitrarily small neighborhood of the globally optimal solution is investigated by both analysis and simulation.
---
paper_title: Distributed learning algorithms for spectrum sharing in spatial random access networks

paper_content:

We consider distributed optimization over orthogonal collision channels in spatial multi-channel ALOHA networks. Users are spatially distributed and each user is in the interference range of a few other users. Each user is allowed to transmit over a subset of the shared channels with a certain attempt probability. We study both the non-cooperative and cooperative settings. In the former, the goal of each user is to maximize its own rate irrespective of the utilities of other users. In the latter, the goal is to achieve proportionally fair rates among users. We develop simple distributed learning algorithms to solve these problems. The efficiencies of the proposed algorithms are demonstrated via both theoretical analysis and simulation results.
---
paper_title: Exploiting User Demand Diversity in Heterogeneous Wireless Networks

paper_content:

Radio resource management (RRM) is crucial for improving resource utilization in heterogeneous wireless networks. Existing work attempts to exploit the network diversity to gain throughput improvement for users, which, however, neglects the impact of user demand on RRM. Armed with the idea that the ultimate goal of communications is to serve users with personalized demand, we introduce another dimension of potential performance gain, user demand diversity gain. This gain derives from the elaborate matching between user demand and radio resource, which can not be directly attained in existing throughput-centric optimization due to users' blindness in maximizing throughput. Aiming at obtaining this gain, we propose the user demand-centric optimization, where users seek to maximize quality of experience (QoE), instead of throughput. This shift enables us to propose a novel game formulation, QoE game. We derive the condition on the existence of the QoE equilibrium, validate the user demand diversity gain and propose a distributed QoE equilibrium learning algorithm. Finally, a cloud assisted learning framework is proposed to accommodate the learning algorithm with significantly reduced cost. Simulation results validate the existence of user demand diversity gain and the effectiveness of the proposed learning algorithm in improving the system efficiency and QoE fairness.
---
paper_title: Game Theoretic Aspects of the Multi-Channel ALOHA Protocol in Cognitive Radio Networks

paper_content:

In this paper we consider the problem of distributed throughput maximization of cognitive radio networks with the multi-channel ALOHA medium access protocol. First, we characterize the Nash Equilibrium Points (NEPs) of the network when users solve an unconstrained rate maximization (i.e., the total transmission probability equals one). Then, we focus on constrained rate maximization, where user rates are subject to a total transmission probability constraint. We propose a simple best-response algorithm that solves the constrained rate maximization, where each user updates its strategy using its local channel state information (CSI) and by monitoring the channel utilization. We prove the convergence of the proposed algorithm using the theory of potential games. Furthermore, we show that the network approaches a unique equilibrium as the number of users increases. Then, we formulate the problem of choosing the access probability as a leader-followers Stackelberg game, where a single user is chosen to be the leader to manage the network. We show that a fully distributed setup can be applied to approximately optimize the network throughput for a large number of users. Finally, we extend the model to the case where primary and secondary users co-exist in the same frequency band.
---
paper_title: New economic perspectives for resource allocation in wireless networks

paper_content:

The economic approaches of potential game theory and bargaining theory are applied to the area of power control in CDMA wireless networks. These perspectives help identify suitable equilibrium points, and algorithms that can be shown to converge to them. The bargaining approach also suggests an iterative method for the simultaneous routing and resource allocation problem.
---
paper_title: Game theoretic analysis of a network of cognitive radios

paper_content:

Cognitive radio is an enhancement on traditional software radio design where observations of the operating environment are combined with knowledge of the radio's available hardware and software capabilities to form decisions as to how to modify the radio's behavior to produce a desired level of performance. This paper addresses how the insertion of cognitive radio technology into a network will impact performance and demonstrates how techniques from game theory can be used to analyze the network as a first step of shaping the decisions of the radios to achieve optimal network performance.
---
paper_title: Power Control for Uplink Transmission With Mobile Users

paper_content:

In this paper, we introduce an uplink transmission model with mobile users, where each user maximizes his/her utility to achieve the best performance. We propose a power allocation scheme for each mobile user when all channel information is available. Moreover, we illustrate that one user would expect to predict the aggregate interference to maximize the utility when the channel information is incomplete. It is shown that this approach forms a game with incomplete information. We demonstrate the prediction rules that can help the mobile users dynamically adjust predictions and apply the Kalman filter to tackle measurement noises. We also illustrate the theoretical bound for the difference between the utility with prediction and that with complete information. Moreover, applying dynamic programming from control theory, we give a dynamic power allocation scheme based on the predictions. Simulation results indicate that our power allocation scheme with complete information and dynamic power allocation with predictions give better performance compared with the scheme with even power allocation. In addition, results under our dynamic power allocation scheme are close to those under the power allocation with complete information.
---
paper_title: CDMA uplink power control as a noncooperative game

paper_content:

We present a game-theoretic treatment of distributed power control in CDMA wireless systems. We make use of the conceptual framework of noncooperative game theory to obtain a distributed and market-based control mechanism. We address not only the power control problem, but also pricing and allocation of a single resource among several users. A cost function is introduced as the difference between pricing and utility functions, and the existence of a unique Nash equilibrium is established. Furthermore, two update algorithms, namely parallel update and random update, are shown to be globally stable under specific conditions. Convergence properties and robustness of each algorithm are also studied through extensive simulations.
---
paper_title: Efficient power control via pricing in wireless data networks

paper_content:

A major challenge in the operation of wireless communications systems is the efficient use of radio resources. One important component of radio resource management is power control, which has been studied extensively in the context of voice communications. With the increasing demand for wireless data services, it is necessary to establish power control algorithms for information sources other than voice. We present a power control solution for wireless data in the analytical setting of a game theoretic framework. In this context, the quality of service (QoS) a wireless terminal receives is referred to as the utility and distributed power control is a noncooperative power control game where users maximize their utility. The outcome of the game results in a Nash (1951) equilibrium that is inefficient. We introduce pricing of transmit powers in order to obtain Pareto improvement of the noncooperative power control game, i.e., to obtain improvements in user utilities relative to the case with no pricing. Specifically, we consider a pricing function that is a linear function of the transmit power. The simplicity of the pricing function allows a distributed implementation where the price can be broadcast by the base station to all the terminals. We see that pricing is especially helpful in a heavily loaded system.
---
paper_title: Convergence of cognitive radio networks

paper_content:

In this paper, we examine the conditions and behavior of several common convergence dynamics from game theory and show how they influence the structure of networks of cognitive radios. We then apply these to previously proposed distributed power control algorithms and describe how they impact network complexity.
---
paper_title: Normalized nash equilibrium for power allocation in femto base stations in heterogeneous network

paper_content:

We consider heterogeneous networks with multiple femtocells and macrocells. Femto-base stations (femto-BS) are constrained to allocate transmitting powers such that the total interference at each macro-user terminal (macro-UT) is below a given threshold. We formulate a power allocation problem as a concave game with femto-BSs as players and multiple macro-UTs enforcing coupled constraints. Equilibrium selection is based on the concept of normalized Nash equilibrium (NNE). When the interference at a femto-user terminal (femto-UT) from adjacent femto-BSs is negligible, for any strictly concave nondecreasing utility the NNE is unique and the NNE is the solution of a concave potential game. We also propose a distributed algorithm which converges to the unique NNE. When the interference is not negligible, an NNE may not be unique and the computation of NNE has exponential complexity. We introduce the concept of weakly normalized Nash equilibrium (WNNE) which keeps the most of NNEs' interesting properties but, in contrast to the latter, the WNNE can be determined with low complexity. We show the usefulness of the WNNE concept for the relevant case of Shannon capacity as femto-BS's utility.
---
paper_title: Near-Optimal Power Control in Wireless Networks: A Potential Game Approach

paper_content:

We study power control in a multi-cell CDMA wireless system whereby self-interested users share a common spectrum and interfere with each other. Our objective is to design a power control scheme that achieves a (near) optimal power allocation with respect to any predetermined network objective (such as the maximization of sum-rate, or some fairness criterion). To obtain this, we introduce the potential-game approach that relies on approximating the underlying noncooperative game with a "close" potential game, for which prices that induce an optimal power allocation can be derived. We use the proximity of the original game with the approximate game to establish through Lyapunov-based analysis that natural user-update schemes (applied to the original game) converge within a neighborhood of the desired operating point, thereby inducing near-optimal performance in a dynamical sense. Additionally, we demonstrate through simulations that the actual performance can in practice be very close to optimal, even when the approximation is inaccurate. As a concrete example, we focus on the sum-rate objective, and evaluate our approach both theoretically and empirically.
---
paper_title: Joint power control and component carrier assignment scheme in heterogeneous network with carrier aggregation

paper_content:

A distributed interference coordination scheme is proposed to alleviate cross-tier and inner-tier interference in heterogeneous network (HetNet), consisting of a power control strategy based on game theory to acquire both Nash equilibrium among femtocells and Stackelberg equilibrium between femtocells and macrocells. Component carrier assignment is the other interference coordination dimension for HetNet with carrier aggregation. The proposed method is a two-dimensional interference coordination scheme combining power control and component carrier assignment. The simulation results demonstrate the effectiveness and improvement of the proposed scheme.
---
paper_title: Resource Allocation in Cognitive Radio Networks: A Comparison Between Game Theory Based and Heuristic Approaches

paper_content:

Cognitive Radio (CR) approach can be considered as a promising and suitable solution to solve in an efficient and flexible way the increasing and continuous demand of services and radio resources. This paper shows the potential benefits of the adoption of a cognitive radio strategy to the coexistence problem. Two different approaches have been considered: the first one is based on the Game Theory while the second one is formalized as a constrained maximum search and represent the optimum solution. The Game theory approach, suitable for a distributed implementation, provides performances comparable to the heuristic one which is a centralized optimization problem. The paper analyzes the performances of both approaches in terms of secondary rates and spectral efficiency provided by the secondary system.
---
paper_title: Equilibria of Channel Selection Games in Parallel Multiple Access Channel

paper_content:

In this article, the parallel multiple access channel is studied under the assumption that transmitters maximize their individual spectral efficiency by selfishly tuning their power allocation policy. Two particular scenarios are studied: (a) transmitters are allowed to use all the available channels; and (b) transmitters are constrained to use a single channel. Both scenarios are modeled by one-shot games and the corresponding sets of Nash equilibria (NE) are fully characterized under the assumption that the receiver treads the multiple access interference as noise. In both cases, the set of NE is non-empty. In the case in which transmitters use a single channel, an upper bound of the cardinality of the NE set is provided in terms of the number of transmitters and number of channels. In particular, it is shown that in fully loaded networks, the sum spectral efficiency at the NE in scenario (a) is at most equal to the sum spectral efficiency at the NE in scenario (b). A formal proof of this observation, known in general as a Braess paradox, is provided in the case of two transmitters and two channels. In general scenarios, we conjecture that the same effect holds as long as the network is kept fully loaded, as shown by numerical examples. Moreover, the price of anarchy and the price of stability in both games are also studied. Interestingly, under certain conditions on the channel gains, Pareto optimality can be achieved at some NE if and only if the number of channels equals or exceeds the number of transmitters. Finally, simulations are presented to verify the theoretical results.
---
paper_title: Dense femtocell networks power self-optimization: an exact potential game approach

paper_content:

Femtocell is regarded as a promising technology to enhance indoor coverage and improve network capacity. However, highly dense and self-organized femtocells in urban environment will result in serious inter-femtocell interference. To solve this problem, this paper proposes a distributed power self-optimization scheme for the downlink operation of dense femtocell networks. First, a novel convex pricing mechanism is presented to price the transmit power of femtocells and construct the utility function of femtocells. Then, a noncooperative game framework for power self-optimization of femtocells in dense femtocell networks is established on the basis of the exact potential game theory, which is demonstrated to converge to a pure and unique Nash equilibrium. Finally, combined with firefly algorithm, an effective power self-optimization algorithm with guaranteed convergence is proposed to achieve the Nash equilibrium of the proposed game. With practical LTE parameters and a 3GPP dual-strip femtocell model, simulation results show that the proposed game with convex pricing mechanism increases the femtocell network throughput by 7% and reduces the average transmit power of femtocells by 50% in dense femtocell networks, with respect to the compared schemes. Copyright © 2014 John Wiley & Sons, Ltd.
---
paper_title: Distributed Learning Policies for Power Allocation in Multiple Access Channels

paper_content:

We analyze the problem of distributed power allocation for orthogonal multiple access channels by considering a continuous non-cooperative game whose strategy space represents the users' distribution of transmission power over the network's channels. When the channels are static, we find that this game admits an exact potential function and this allows us to show that it has a unique equilibrium almost surely. Furthermore, using the game's potential property, we derive a modified version of the replicator dynamics of evolutionary game theory which applies to this continuous game, and we show that if the network's users employ a distributed learning scheme based on these dynamics, then they converge to equilibrium exponentially quickly. On the other hand, a major challenge occurs if the channels do not remain static but fluctuate stochastically over time, following a stationary ergodic process. In that case, the associated ergodic game still admits a unique equilibrium, but the learning analysis becomes much more complicated because the replicator dynamics are no longer deterministic. Nonetheless, by employing results from the theory of stochastic approximation, we show that users still converge to the game's unique equilibrium. ::: Our analysis hinges on a game-theoretical result which is of independent interest: in finite player games which admit a (possibly nonlinear) convex potential function, the replicator dynamics (suitably modified to account for nonlinear payoffs) converge to an eps-neighborhood of an equilibrium at time of order O(log(1/eps)).
---
paper_title: Joint Power and Bandwidth Allocation for Amplify-and-Forward Cooperative Communications Using Stackelberg Game

paper_content:

The amplify-and-forward (AF) cooperative communication scheme is modeled using the Stackelberg market framework, where a relay is willing to sell its resources, power, and bandwidth to multiple users to maximize its revenue. The relay determines the prices for relaying the users' information, depending on its available resources and the users' demands. Subsequently, each user maximizes its own utility function by determining the optimum power and bandwidth to buy from the relay. The utility function of the user is formulated as a joint concave function in power and bandwidth. The existence and uniqueness of the Nash equilibrium (NE) are investigated using the concavity of the utility function and the exact potential game associated with the proposed utility function. The NE solution can be obtained in a centralized manner, which requires full knowledge of all channel gains of all users, which may be difficult to obtain in practice. In this sense, a distributed algorithm can be applied to obtain power and bandwidth allocations with minimum information exchange between the relay and the users. Similarly, the optimum prices for the power and bandwidth can also be obtained in a distributed manner. The convergence of the algorithms is investigated using the Jacobian matrix at the NE. Numerical simulations are used to verify the validation of the proposed framework.
---
paper_title: The Waterfilling Game-Theoretical Framework for Distributed Wireless Network Information Flow

paper_content:

We present a general game-theoretical framework for power allocation in the downlink of distributed wireless small-cell networks, where multiple access points (APs) or small base stations send independent coded network information to multiple mobile terminals (MTs) through orthogonal channels. In such a game-theoretical study, a central question is whether a Nash equilibrium (NE) exists, and if so, whether the network operates efficiently at the NE. For independent continuous fading channels, we prove that the probability of a unique NE existing in the game is equal to 1. Furthermore, we show that this power allocation problem can be studied as a potential game, and hence efficiently solved. In order to reach the NE, we propose a distributed waterfilling-based algorithm requiring very limited feedback. The convergence behavior of the proposed algorithm is discussed. Finally, numerical results are provided to investigate the price of anarchy or inefficiency of the NE.
---
paper_title: Distributed Resource Allocation Based on Game Theory in Multi-cell OFDMA Systems

paper_content:

A game theoretic solution for distributed uplink resource allocation in multi-cell OFDMA systems is presented in this paper. Convergence rule and steady state characterization are analyzed with potential game. Simulation results show that the proposed non-cooperative potential game algorithm for dynamic subcarrier and power allocation can converge to Nash Equilibrium (NE) quickly and achieve higher energy efficiency compared with pure iterative water-filling algorithm.
---
paper_title: Joint Access Point Selection and Power Allocation for Uplink Wireless Networks

paper_content:

We consider the distributed uplink resource allocation problem in a multi-carrier wireless network with multiple access points (APs). Each mobile user can optimize its own transmission rate by selecting a suitable AP and by controlling its transmit power. Our objective is to devise suitable algorithms by which mobile users can jointly perform these tasks in a distributed manner. Our approach relies on a game theoretic formulation of the joint power control and AP selection problem. In the proposed game, each user is a player with an associated strategy containing a discrete variable (the AP selection decision) and a continuous vector (the power allocation among multiple channels). We provide characterizations of the Nash Equilibrium of the proposed game. We present a novel algorithm named Joint Access Point Selection and Power Allocation (JASPA) and its various extensions (with different update schedules) that allow the users to efficiently optimize their rates. Finally, we study the properties of the proposed algorithms as well as their performance via extensive simulations.
---
paper_title: A multi-cell adaptive resource allocation scheme based on potential game for ICIC in LTE-A

paper_content:

Intercell interference coordination in Third Generation Partnership Project long-term evolution-advanced system has received much attention both from the academia and the standardization communities. Moreover, the network architecture of long-term evolution-advanced system is modified to take into account coordinated transmission. In this article, we study the dynamic resource allocation problem and potential game theory and propose a multicell adaptive distributed resource allocation algorithm based on potential game. The allocation process is divided into two steps; subchannel is allocated first, and then, transmitted power is optimized dynamically according to a novel pricing factor. Besides, existence and uniqueness of Nash equilibrium of the proposed game model are assured. As a result, intercell interference is well coordinated. Simulation results show that transmitted power is saved efficiently and system fairness is improved to a large extent, accompanied with good performance gain of total and cell-edge throughputs. Copyright © 2013 John Wiley & Sons, Ltd.
---
paper_title: On the Base Station Selection and Base Station Sharing in Self-Configuring Networks

paper_content:

We model the interaction of several radio devices aiming to obtain wireless connectivity by using a set of base stations (BS) as a non-cooperative game. Each radio device aims to maximize its own spectral efficiency (SE) in two different scenarios: First, we let each player to use a unique BS (BS selection) and second, we let them to simultaneously use several BSs (BS Sharing). In both cases, we show that the resulting game is an exact potential game. We found that the BS selection game posses multiple Nash equilibria (NE) while the BS sharing game posses a unique one. We provide fully decentralized algorithms which always converge to a NE in both games. We analyze the price of anarchy and the price of stability for the case of BS selection. Finally, we observed that depending on the number of transmitters, the BS selection technique might provide a better global performance (network spectral efficiency) than BS sharing, which suggests the existence of a Braess type paradox.
---
paper_title: Learning distributed power allocation policies in MIMO channels

paper_content:

In this paper1, we study the discrete power allocation game for the fast fading multiple-input multiple-output multiple access channel. Each player or transmitter chooses its own transmit power policy from a certain finite set to optimize its individual transmission rate. First, we prove the existence of at least one pure strategy Nash equilibrium. Then, we investigate two learning algorithms that allow the players to converge to either one of the NE states or to the set of correlated equilibria. At last, we compare the performance of the considered discrete game with the continuous game in [7].
---
paper_title: Game Theoretic Multimode Precoding Strategy Selection for MIMO Multiple Access Channels

paper_content:

This paper is concerned with decentralized selection of multimode precoding strategy for multiple-input multiple-output (MIMO) multiple access channels. We formulate it as a discrete noncooperative game. This game is shown to possess at least one pure strategy Nash equilibrium (NE) and the optimal strategy profile which maximizes the sum rate constitutes a pure strategy NE. Then we propose a decentralized algorithm based on learning automata to achieve the NE. A repeated mechanism is introduced to improve the sum rate performance and a mechanism for adapting step size is designed to control the convergence speed. Simulation results show that the proposed algorithm, which only requires limited feedback, can achieve near optimal or optimal sum rate performance.
---
paper_title: Energy Efficient Spectrum Sharing Strategy Selection for Cognitive MIMO Interference Channels

paper_content:

In this paper, we propose a promising discrete game-theoretic framework for distributed energy efficient discrete spectrum sharing strategy selection (i.e., joint discrete power control and multimode precoding strategy selection) with limited feedback for cognitive MIMO interference channels. Given the competitive nature, the secondary users are assumed to be selfish and noncooperative, each of whom attempts to maximize its individual energy efficiency under a minimum data rate constraint and an interference power constraint. A mechanism for shutting down links is proposed to reduce interference and save energy. A payoff function is designed to guarantee the feasibility of the pure strategy Nash equilibrium with no need to know the infeasible strategy profiles (a spectrum sharing strategy profile is said to be feasible if the stated constraints are satisfied; otherwise, the spectrum sharing strategy profile is said to be infeasible, i.e., they may not satisfy the interference power constraint and minimum data rate constraint) in advance. We then investigate the existence and the feasibility of the pure strategy Nash equilibrium, and further devise a pricing-based distributed algorithm for spectrum strategy selection. The proposed algorithm is proved to converge to a feasible pure strategy Nash equilibrium under specific conditions. Moreover, by studying the relationship between our proposed game and the social optimum, we find that the pricing mechanism can result in Pareto improvement and lead to better convergence for the proposed distributed algorithm. Numerical results show that our designed algorithm significantly outperforms the random selection algorithm and the pricing mechanism has a dramatic effect in improving the system performance.
---
paper_title: Game-Theoretic Opportunistic Spectrum Sharing Strategy Selection for Cognitive MIMO Multiple Access Channels

paper_content:

This paper studies opportunistic spectrum sharing strategy (i.e., quantized precoding strategy) selection for cognitive multiple-input multiple-output multiple access channels with limited feedback under interference power constraint and maximum transmission stream number constraint. We put forward a game-theoretic framework to model the precoding strategy selection behaviors of the secondary users under the specified constraints. First, we prove the formulated discrete game is a potential game which possesses at least one feasible pure strategy Nash equilibrium. The feasibility and optimality of the Nash equilibrium are also analyzed. Then we prove that the solution to the sum rate maximization problem constitutes a feasible pure strategy Nash equilibrium of our formulated game. Furthermore, we design two algorithms. The iterative precoding strategy selection algorithm based on the best response rule is designed to attain a feasible Nash equilibrium. The modified algorithm is designed to improve the sum rate performance. Simulation results show that our designed algorithms can achieve optimal or near optimal sum rate performance with low complexity.
---
paper_title: Relay Selection and Discrete Power Control for Cognitive Relay Networks via Potential Game

paper_content:

In this paper, we study the joint relay selection and discrete power control problem for cognitive relay networks via a game-theoretic approach subject to the interference power con- straint at the primary receivers and the total available power con- straint for the secondary relays. The problem is formulated as a noncooperative game where the achievable rate of the cognitive relay network is used to design a common utility. This game is shown to be a potential game which possesses at least one pure strategy Nash equilibrium (NE) and an optimal strategy profile that maximizes the rate of cognitive relay network constitutes a pure strategy NE of our proposed game.We provethat undersome mild conditions, our proposed game can guarantee the feasibility of a pure strategy NE without advance knowledge of infeasible strategyprofiles. Moreover, wefind that the price of anarchy (PoA) of our proposed game is equal to 1 under some conditions. In order to achieve the pure strategy NE, we design a centralized iterative algorithm and a decentralized stochastic learning algorithm based on learning automata. The convergence and the complexity of our designed algorithms are discussed. It is shown that our designed algorithms can achieve optimal or near-optimal rate performance with low complexity.
---
paper_title: Linear Precoding Game for MIMO MAC With Dynamic Access Point Selection

paper_content:

This paper examines a non-cooperative game in precoding design for MIMO multiple-access channels with dynamic access point (AP) selection. This game is first shown to be a potential game, where the potential function is the sum rate achieved by successive interference cancellation. Due to the mixed-integer nature of the optimization variable, it is challenging to directly characterize the maximum of the potential function, which are closely related to the Nash equilibrium (NE) of the game. Instead, we establish the existence and achievability of the maximum through non-decreasing and upperbounded properties of the potential function as a direct result of our proposed update scheme. A distributed algorithm is designed where each player selfishly optimizes its AP selection and linear precoding strategy in a sequential manner. Convergence is a by-product of the established properties of the potential function which are materialized by an iterative waterfilling algorithm. Numerical results show that the algorithm is able to reach fast convergence and provides a system sum rate nearing that of the optimal centralized solution.
---
paper_title: Effect of Selfish Node Behavior on Efficient Topology Design

paper_content:

The problem of topology control is to assign per-node transmission power such that the resulting topology is energy efficient and satisfies certain global properties such as connectivity. The conventional approach to achieve these objectives is based on the fundamental assumption that nodes are socially responsible. We examine the following question: if nodes behave in a selfish manner, how does it impact the overall connectivity and energy consumption in the resulting topologies? We pose the above problem as a noncooperative game and use game-theoretic analysis to address it. We study Nash equilibrium properties of the topology control game and evaluate the efficiency of the induced topology when nodes employ a greedy best response algorithm. We show that even when the nodes have complete information about the network, the steady-state topologies are suboptimal. We propose a modified algorithm based on a better response dynamic and show that this algorithm is guaranteed to converge to energy-efficient and connected topologies. Moreover, the node transmit power levels are more evenly distributed, and the network performance is comparable to that obtained from centralized algorithms.
---
paper_title: Analyzing Selfish Topology Control in Multi-Radio Multi-Channel Multi-Hop Wireless Networks

paper_content:

Typically, topology control is perceived as a per-node transmit power control process that achieves certain network-level objectives. We take an alternative approach of controlling the topology of a network purely by assigning channels to multiple radio interfaces on nodes. Specifically, we exploit the synergy between topology control and channel allocation to reduce the overall interference in multi-radio multi-channel wireless ad hoc networks. ::: ::: We formulate channel assignment as a non-cooperative game, with nodes selecting low interference channels while maintaining some degree of network connectivity. This game is shown to be a potential game, which ensures the existence of, and convergence to, a Nash Equilibrium (NE). Next, we evaluate the performance of NE topologies with respect to interference and connectivity objectives. By quantifying the impact of channel availability on interference performance, we illuminate the tradeoff between interference reduction that can be achieved by distributing interference over multiple channels and the cost of having additional channels. Finally, we study the spectral occupancy of steady state topologies, and show that despite the non-cooperative behavior, the NE topologies achieve load balancing.
---
paper_title: Topology control of dynamic networks in the presence of local and global constraints

paper_content:

Formation flying (FF) is a critical element in NASA's future deep-space missions. Terrestrial Planet Finder (TPF), NASA's first space-based mission to directly observe planets outside our own solar system, will rely on FF to achieve the functionality and benefits of a large instrument using multiple lower cost smaller spacecraft. Many key network design problems for such FF missions can be formulated as optimization problems with local and global constraints. We develop a topology control algorithm that can be used for many network problems in the presence of local constraints, such as collision avoidance, and global constraints, such as network connectivity. The presence of contradictory objectives in topology control problems motivated a game-theoretic approach. We demonstrated that a game-theoretic technique could provide a framework for design and analysis of many topology control problems in dynamic networks. In particular, the problem of motion planning for formation reconfiguration in the presence of constraints on network connectivity and inter-spacecraft collisions is studied.
---
paper_title: Virtual Game-Based Energy Balanced Topology Control Algorithm for Wireless Sensor Networks

paper_content:

In topology control (TC), game theory is an efficient approach to analyze the conflicting objectives of nodes to enable the topology with certain global properties in the presence of selfish nodes. But in many existing game-based TC algorithms, every node has to make others aware of its changes by transmitting the control information repeatedly, which results in much unnecessary energy waste and network lifetime reduction. To solve the problem, the concept of virtual game is introduced, which virtualizes the game process to avoid the repeated information exchange in the game process. In addition, considering that unbalanced distribution of energy consumption also restricts the network lifetime, a distributed Virtual Game-based Energy Balanced TC algorithm (VGEB) with incomplete information is proposed, which is mathematically analyzed. The analysis results show that the TC virtual game is a potential game and the virtual game algorithm can converge to the state of Nash Equilibrium, which is Pareto Optimal. Moreover, VGEB can easily construct the topology with a low information complexity of O(n) and the induced topology can maintain the network connectivity, where n is the number of nodes in network. Simulation results demonstrate that VGEB can effectively balance the nodes' energy consumption, greatly reduce the energy waste in the game process and has many other attractive topological features.
---
paper_title: Topology control in wireless ad hoc and sensor networks

paper_content:

Topology Control (TC) aims at tuning the topology of highly dynamic networks to provide better control over network resources and to increase the efficiency of communication. Recently, many TC protocols have been proposed. The protocols are designed for preserving connectivity, minimizing energy consumption, maximizing the overall network coverage or network capacity. Each TC protocol makes different assumptions about the network topology, environment detection resources, and control capacities. This circumstance makes it extremely difficult to comprehend the role and purpose of each protocol. To tackle this situation, a taxonomy for TC protocols is presented throughout this paper. Additionally, some TC protocols are classified based upon this taxonomy.
---
paper_title: A QoS-Based Topology Control Algorithm for Underwater Wireless Sensor Networks

paper_content:

The topology control techniques of underwater wireless sensor networks and terrestrial wireless sensor networks are significantly different because of the particularity of underwater environments and acoustic communication. In this paper, an underwater wireless sensor network model was constructed, and six universal topology control objectives were concluded. The QoS topology control problem was mapped into an ordinal potential game model, and a distributed strategy adjustment algorithm for nodes was designed accordingly. The strategy vector resulting from the algorithm converges to the Nash equilibrium; minor complexity and preferable approximate ratios can be represented by the algorithm as well. The performance of the algorithm was analyzed through simulation experiments which indicate a well-constructed topology. Every objective was upgraded when model parameters were set suitable.
---
paper_title: Distributed Cooperative Control Algorithm for Topology Control and Channel Allocation in Multi-radio Multi-channel Wireless Sensor Network: From a Game Perspective

paper_content:

With the development of wireless communication technology, the spectrum resource is becoming more and more scarce, which results in the increase of network co-interference and then incurs the increase of data retransmission probability. Hence, the single channel based algorithms are facing a myriad of challenges. Moreover, reducing the energy consumption and prolonging the network lifetime is the key issue for wireless sensor network. In order to alleviate the interference while reducing and balancing the energy consumption, we tend to design a multi-radio multi-channel algorithm that joint the topology control and channel allocation. Firstly, we study the interactions between topology control and channel allocation, which lay the basis for the further reduction of transmission power and interference. We take account of the radio power, node residual energy and node interference to construct a cooperative control game model of topology and channel allocation. This game model has proven to guarantee the existence of Nash equilibrium. And then based on this game model, a distributed Cooperative Control Algorithm of Topology and Channel allocation (CCATC) is developed, which can converge to Nash Equilibrium and preserve the network connectivity. Furthermore, the simulation results demonstrate that CCATC can not only greatly reduce the interference but also prolong the network lifetime by balancing the energy consumption of nodes. The reduction of interference comes with the improvement of network throughput. Besides, CCATC has many other attractive features such as the higher channel utilization, the better robustness, the fairer channel allocation and the less end-to-end delay.
---
paper_title: Topology control algorithm for underwater wireless sensor networks using GPS-free mobile sensor nodes

paper_content:

Underwater wireless sensor networks (UWSNs) have been developed for underwater applications, such as resource exploration, pollution monitoring, and tactical surveillance. The topology control techniques of UWSNs and terrestrial wireless sensor networks are significantly different because of the particularity of underwater environments and acoustic communication, such as mobility pattern, propagation delay and energy consumption. Due to multifarious factors of underwater environments, node mobility becomes a non-negligible issue. However, GPS may not be feasible because of the limitations of satellite coverage or obstructions in adverse underwater environments. In particular, anchored sensor nodes towed by wires are prone to offset around their static positions, causing each node to move within a spherical crown surface (spherical crown mobility pattern). Nevertheless, most previous studies have not focused on this specific mobility pattern. In the current paper, a mobility model for UWSNs nodes is constructed, and three representative topology control objectives are attained. A distributed radius determination algorithm is designed for the mobility-based topology control problem. Results of theoretic analysis prove that the proposed algorithm is convergent, and it has preferable approximate ratios and polynomial complexity. Performance of the algorithm is analyzed through simulation experiments, which indicate a well-constructed topology. Every objective can still be upgraded without the dynamic location information of mobile nodes.
---
paper_title: The price of ignorance: distributed topology control in cognitive networks

paper_content:

In a cognitive network, autonomous and adaptive radios select their operating parameters to achieve individual and network-wide goals. The effectiveness of these adaptations depends on the amount of knowledge about the state of the network that is available to the radios. We examine the price of ignorance in topology control in a cognitive network with power- and spectral-efficiency objectives. We propose distributed algorithms that, if radios possess global knowledge, minimize both the maximum transmit power and the spectral footprint of the network. We show that while local (as opposed to global) knowledge has little effect on the maximum transmission power used by the network, it has a significant effect on the spectral performance. Furthermore, we show that due to the high cost of maintaining network knowledge for highly dynamic networks, the cost/performance tradeoff makes it advantageous for radios to operate under some degree of local knowledge, rather than global knowledge.We also propose distributed algorithms for power and frequency adaptations as radios join or leave the network, and assess how partial knowledge impacts the performance of these adaptations.
---
paper_title: Cooperative topology control with adaptation for improved lifetime in wireless ad hoc networks

paper_content:

Topology control algorithms allow each node in a wireless multi-hop network to adjust the power at which it makes its transmissions and choose the set of neighbors with which it communicates directly, while preserving global goals such as connectivity or coverage. This allows each node to conserve energy and contribute to increasing the lifetime of the network. Previous work on topology control has largely used an approach based on considering only the energy costs across links without considering the amount of energy available on a node. Further, previous work has largely used a static approach where the topology is determined at the beginning of the network's life and does not incorporate the varying rates of energy consumption at different nodes. In this paper, we address these weaknesses and introduce a new topology control algorithm that dynamically adapts to current energy levels at nodes. The algorithm, called Cooperative Topology Control with Adaptation (CTCA), employs a game-theoretic approach that maps the problem of maximizing the network's lifetime into an ordinal potential game. This allows a node running the CTCA algorithm to make a sacrifice by increasing its transmission power if it can help reduce energy consumption at another node with a smaller lifetime. We prove the existence of a Nash equilibrium for the game. Our simulation results indicate that the CTCA algorithm extends the life of a network by more than 50% compared to the best previouslyknown algorithm.
---
paper_title: Controlling Connectivity of Dynamic Graphs

paper_content:

The control of mobile networks of multiple agents raises fundamental and novel problems in controlling the structure of the resulting dynamic graphs. In this paper, we consider the problem of controlling a network of agents so that the resulting motion always preserves various connectivity properties. In particular, we consider preserving k-hop connectivity, where agents are allowed to move while maintaining connections to agents that are no more than k-hops away. The connectivity constraint is translated to constrains on individual agent motion by considering the dynamics of the adjacency matrix and related constructs from algebraic graph theory. As special cases, we obtain motion constraints that can preserve the exact structure of the initial dynamic graph, or may simply preserve the usual notion connectivity while the structure of the graph changes over time. We conclude by illustrating various interesting problems that can be achieved while preserving connectivity constraints.
---
paper_title: Revenue-maximizing pricing and capacity expansion in a many-users regime

paper_content:

We consider a network where each user is charged a fixed price per unit of bandwidth used, but where there is no congestion-dependent pricing. However, the transmission rate of each user is assumed to be a function of network congestion (like TCP), and the price per unit bandwidth. We are interested in answering the following question: how should the network choose the price to maximize its overall revenue? To obtain a tractable solution, we consider a single link accessed by many users where the capacity is increased in proportion to the number of users. We show the following result: as the number of users increases, the optimal price per unit bandwidth charged by the service provider may increase or decrease depending upon the bandwidth of the link. However, for all values of the link capacity, the service provider's revenue per unit bandwidth increases and the overall performance of each user (measured in terms of a function of its throughput, the network congestion and the cost incurred by the user for bandwidth usage) improves. Since the revenue per unit bandwidth increases, it provides an incentive for the service provider to increase the available bandwidth in proportion to the number of users.
---
paper_title: Non-Cooperative Spectrum Access in Cognitive Radio Networks: a Game Theoretical Model

paper_content:

Cognitive radio networks provide the capability to share the wireless channel with licensed (primary) users in an opportunistic manner. Primary users have a license to operate in a certain spectrum band; their access can only be controlled by the primary operator and is not affected by any other unlicensed (secondary) user. On the other hand, secondary users (SUs) have no spectrum license, and they attempt to exploit the spectral gaps left free by primary users. This work studies the spectrum access problem in cognitive radio networks from a game theoretical perspective. The problem is modeled as a non-cooperative spectrum access game where secondary users access simultaneously multiple spectrum bands left available by primary users, optimizing their objective function which takes into account the congestion level observed on the available spectrum bands. As a key innovative feature with respect to existing works, we model accurately the interference between SUs, capturing the effect of spatial reuse. Furthermore, we consider both non-elastic and elastic user traffic, to model real-time as well as data transfer applications. Finally, we consider an alternative formulation of the spectrum access problem, where players use replicator dynamics to adjust their strategies, and we derive convergence conditions to Nash equilibrium points. We demonstrate the existence of the Nash equilibrium, and derive equilibrium flow settings. Finally, we provide numerical results of the proposed spectrum access game in several cognitive radio scenarios, and study the impact of the interference between SUs on the game efficiency. Our results indicate that the congestion cost functions we propose in this paper lead to small gaps between Nash equilibria and optimal solutions in all the considered network scenarios, thus representing a starting point for designing pricing mechanisms so as to obtain a socially optimal use of the network.
---
paper_title: Convergence of synchronous and asynchronous greedy algorithms in a multiclass telecommunications environment

paper_content:

The Nash equilibrium point for optimum flow control in a noncooperative multiclass environment is studied. Convergence properties of synchronous and asynchronous greedy algorithms are investigated in the case where several users compete for the resources of a single queue using power as their performance criterion. A proof of the convergence of a synchronous greedy algorithm for the n users case is given, and the necessary and sufficient conditions for the convergence of asynchronous greedy algorithms are obtained. Another important contribution is the introduction to the literature and the extension of a not very widely known theorem for the convergence of Gauss-Seidel algorithms in the linear systems theory. >
---
paper_title: A game theoretic perspective to flow control in telecommunication networks

paper_content:

Abstract Multiple classes of traffic with differing and often conflicting requirements arise in an integrated telecommunications environment as users share the limited existing resources. In this paper, a game theoretic perspective is presented and analysed as the appropriate framework for the study of the flow control problem. Using the notion of power as the performance criterion, we compare a network—Pareto optimal solution—with two user optimal solutions—Nash and Stackelberg equilibria. The appropriateness of each solution is discussed given the operating characteristics of the system. A proposed greedy algorithm is shown to converge to the Nash equilibrium.
---
paper_title: Gateway Congestion Control Survey

paper_content:

The growth of network intensive Internet applications has made gateway congestion control a high priority. The IETF Performance and Congestion Control Working Group surveyed and reviewed gateway congestion control and avoidance approaches. The purpose of this paper is to present our review of the congestion control approaches, as a way of encouraging new discussion and experimentation. Included in the survey are Source Quench, Random Drop, Congestion Indication (DEC Bit), and Fair Queueing. The task remains for Internet implementors to determine and agree on the most effective mechanisms for controlling gateway congestion.
---
paper_title: Distributed wireless information flow allocation in multiple access networks

paper_content:

We present a general framework for distributed wireless information flow allocation problem in multiple access networks, where the end users (EUs) can seek wireless flows from multiple access points (APs). We aim to minimize the power consumption while satisfying each EU's minimum data rate requirement but not violating peak power constraint of each AP and interference constraint monitored by regulatory agents. Toward this end, we model the flow allocation problem as a game which is proved to be a best-response potential game. Then based on potential game theory, we show the existence and uniqueness of Nash equilibrium in the formulated game. Moreover, we demonstrate that the Nash equilibrium is actually the globally optimal solution to our problem. Besides, we propose two distributed algorithms along with convergence analysis for the network to obtain the Nash equilibrium. Meanwhile, we reveal the interesting layered structure of the problem in question. Extensive numerical results are conducted to demonstrate the benefits obtained by flow allocation, as well as the effectiveness of our proposed algorithms.
---
paper_title: A packet dropping-based incentive mechanism for M/M/1 queues with selfish users

paper_content:

We study a novel game theoretic incentive mechanism design problem for network congestion control in the context of selfish users sending data through a single store-and-forward router (a.k.a. “server” in this work). The scenario is modeled as an M/M/1 queueing game with each user (a.k.a. “player”) aiming to optimize a tradeoff between throughput and delay in a selfish distributed manner. We first show that the original game has an inefficient unique Nash Equilibrium (NE). In order to improve the outcome efficiency, we propose an incentivizing packet dropping scheme that can be easily implemented at the server. We then show that if the packet dropping scheme is a function of the sum of arrival rates, we have a modified M/M/1 queueing game that is an ordinal potential game with a unique NE. In particular, for a linear packet dropping scheme, which is similar to the Random Early Detection (RED) algorithm used with TCP, we show that there exists a unique Nash Equilibrium. For this scheme, the social welfare (expressed either as the summation of utilities of all players or log summation of utilities of all players) at the equilibrium point can be arbitrarily close to the social welfare at the global optimal point. Finally, we show that the simple best response dynamic converges to this unique efficient Nash Equilibrium.
---
paper_title: Equilibrium, games, and pricing in transportation and telecommunications networks

paper_content:

Network equilibrium models that have traditionally been used for transportation planning have penetrated in recent years to other scientific fields. These models have recently been introduced in the telecommunication networks literature, as well as in the field of game theory. Researchers in the latter fields are not always aware of the very rich literature on equilibrium models outside of their application area. On the other hand, researchers that have used network equilibrium models in transportation may not be aware of new application areas of their tools. The aim of this paper is to present some central research issues and tools in network equilibria and pricing that could bring closer the three mentioned research communities.
---
paper_title: A game-theoretic framework for congestion control in general topology networks

paper_content:

We study control of congestion in general topology communication networks within a fairly general mathematical framework that utilizes noncooperative game theory. We consider a broad class of cost functions, composed of pricing and utility functions, which capture various pricing schemes along with varying behavior and preferences for individual users. We prove the existence and uniqueness of a Nash equilibrium under mild convexity assumptions on the cost function, and show that the Nash equilibrium is the optimal solution of a particular "system problem". Furthermore, we prove the global stability of a simple gradient algorithm and its convergence to the equilibrium point. Thus, we obtain a distributed, market-based, end-to-end framework that addresses congestion control, pricing and resource allocation problems for a large class of of communication networks. As a byproduct, we obtain a congestion control scheme for combinatorially stable ad hoc networks by specializing the cost function to a specific form. Finally, we present simulation studies that explore the effect of the cost function parameters on the equilibrium point and the robustness of the gradient algorithm to variations in time delay and to link failures.
---
paper_title: Game theoretic rate control for mobile devices

paper_content:

Modern mobile devices offer increased connectivity to heterogeneous wireless networks such as WiFi and 3G. These networks typically exhibit high variability in their characteristics, which poses extra challenges to applications developed to run over them. To address this issue, we propose a game-theoretic rate control scheme for mobile devices. In this noncooperative game formulation of the system the users are assumed the to be selfish in terms of their resource (bandwidth) requests. The information requirements within the model are then simplified by exploiting the available bandwidth measurements provided by a tool called Zeus we developed for this purpose. The formulation is shown to be a potential game, admitting a unique Nash equilibrium. Furthermore, the resulting distributed gradient update algorithm is shown to converge globally. The validity of the model is verified through numerical analysis run on real data, collected by Zeus from different wireless networks.
---
paper_title: Cooperative Control and Potential Games

paper_content:

We present a view of cooperative control using the language of learning in games. We review the game-theoretic concepts of potential and weakly acyclic games, and demonstrate how several cooperative control problems, such as consensus and dynamic sensor coverage, can be formulated in these settings. Motivated by this connection, we build upon game-theoretic concepts to better accommodate a broader class of cooperative control problems. In particular, we extend existing learning algorithms to accommodate restricted action sets caused by the limitations of agent capabilities and group based decision making. Furthermore, we also introduce a new class of games called sometimes weakly acyclic games for time-varying objective functions and action sets, and provide distributed algorithms for convergence to an equilibrium.
---
paper_title: Sensor Networks and Cooperative Control

paper_content:

This paper provides a tutorial-style overview of sensor networks from a systems and control theory perspective. We identify key sensor network design and operational control problems and present solution approaches that have been proposed to date. These include deployment, routing, scheduling and power control. In the case of mobile nodes, a sensor network is called upon to perform a “mission”. We present solution approaches to two types of missions both involving stochastic mission spaces and cooperative control: reward maximization missions and coverage control missions. We conclude by outlining some fundamental research questions related to sensor networks and the convergence of communication, computing and control.
---
paper_title: Cooperative Control and Potential Games

paper_content:

We present a view of cooperative control using the language of learning in games. We review the game-theoretic concepts of potential and weakly acyclic games, and demonstrate how several cooperative control problems, such as consensus and dynamic sensor coverage, can be formulated in these settings. Motivated by this connection, we build upon game-theoretic concepts to better accommodate a broader class of cooperative control problems. In particular, we extend existing learning algorithms to accommodate restricted action sets caused by the limitations of agent capabilities and group based decision making. Furthermore, we also introduce a new class of games called sometimes weakly acyclic games for time-varying objective functions and action sets, and provide distributed algorithms for convergence to an equilibrium.
---
paper_title: ENERGY EFFICIENT COVERAGE PROBLEMS IN WIRELESS Ad Hoc SENSOR NETWORKS

paper_content:

Coverage is a typical problem in wireless sensor networks to fulfil the issued sensing tasks. In general, sensing coverage represents how well an area is monitored by sensors. The quality of a sensor network can be reflected by the levels of coverage and connectivity that it offers. The coverage problem has been studied extensively, especially when combined with connectivity and energy efficiency. Constructing a connected fully covered, and energy efficient sensor network is valuable for real world applications due to the limited resources of sensor nodes. In this paper, we survey recent contributions addressing energyefficient coverage problems in the context of static WASNs, networks in which sensor nodes do not move once they are deployed and present in some detail of the algorithms, assumptions, and results. A comprehensive comparison among these approaches is given from the perspective of design objectives, assumptions, algorithm attributes and related results.
---
paper_title: Efficient Routing Algorithms for Multiple Vehicles With no Explicit Communications

paper_content:

In this paper, we consider a class of dynamic vehicle routing problems, in which a number of mobile agents in the plane must visit target points generated over time by a stochastic process. It is desired to design motion coordination strategies in order to minimize the expected time between the appearance of a target point and the time it is visited by one of the agents. We propose control strategies that, while making minimal or no assumptions on communications between agents, provide the same level of steady-state performance achieved by the best known decentralized strategies. In other words, we demonstrate that inter-agent communication does not improve the efficiency of such systems, but merely affects the rate of convergence to the steady state. Furthermore, the proposed strategies do not rely on the knowledge of the details of the underlying stochastic process. Finally, we show that our proposed strategies yield an efficient, pure Nash equilibrium in a game theoretic formulation of the problem, in which each agent's objective is to maximize the expected value of the ldquotime spent alonerdquo at the next target location. Simulation results are presented and discussed.
---
paper_title: DISTRIBUTED COVERAGE GAMES FOR ENERGY-AWARE MOBILE SENSOR NETWORKS

paper_content:

Inspired by current challenges in data-intensive and energy-limited sensor networks, we formulate a coverage optimization problem for mobile sensors as a (constrained) repeated multiplayer game. Each sensor tries to optimize its own coverage while minimizing the processing/energy cost. The sensors are subject to the informational restriction that the environmental distribution function is unknown a priori. We present two distributed learning algorithms where each sensor only remembers its own utility values and actions played during the last plays. These algorithms are proven to be convergent in probability to the set of (constrained) Nash equilibria and global optima of a certain coverage performance metric, respectively. Numerical examples are provided to verify the performance of our proposed algorithms.
---
paper_title: Target-Based Weapon Target Assignment Problems

paper_content:

In this chapter we consider a class of non-linear assignment problems collectively referred to as Target-based Weapon Target Assignment (WTA). The Target-based Weapon Target Assignment problem considers optimally assigning M weapons to N targets so that the total expected damage to the targets is maximized. We use the term target-based to distinguish these problems from those that are asset-based, that is problems where weapons are assigned to targets such that the value of a group of assets is maximized supposing that the targets themselves are missiles engaging the assets. The asset-based problem is most pertinent to strategic ballistic missile defense problems whereas the target-based problems apply to offensive conventional warfare types of problems. Previous surveys of WTA problems were made by Matlin [Matlin, 1970] and Eckler and Burr [Eckler and Burr, 1972] the first on offensive, target based problems and the second primarily about defensive, asset based problems.
---
paper_title: Autonomous vehicle-target assignment: a game theoretical formulation

paper_content:

We consider an autonomous vehicle-target assignment problem where a group of vehicles are expected to optimally assign themselves to a set of targets. We introduce a game-theoretical formulation of the problem in which the vehicles are viewed as self-interested decision makers. Thus, we seek the optimization of a global utility function through autonomous vehicles that are capable of making individually rational decisions to optimize their own utility functions. The first important aspect of the problem is to choose the utility functions of the vehicles in such a way that the objectives of the vehicles are localized to each vehicle yet aligned with a global utility function. The second important aspect of the problem is to equip the vehicles with an appropriate negotiation mechanism by which each vehicle pursues the optimization of its own utility function. We present several design procedures and accompanying caveats for vehicle utility design. We present two new negotiation mechanisms, namely, "generalized regret monitoring with fading memory and inertia" and "selective spatial adaptive play," and provide accompanying proofs of their convergence. Finally, we present simulations that illustrate how vehicle negotiations can consistently lead to near-optimal assignments provided that the utilities of the vehicles are designed appropriately.
---
paper_title: Energy-efficient target coverage in wireless sensor networks

paper_content:

A critical aspect of applications with wireless sensor networks is network lifetime. Power-constrained wireless sensor networks are usable as long as they can communicate sensed data to a processing node. Sensing and communications consume energy, therefore judicious power management and sensor scheduling can effectively extend network lifetime. To cover a set of targets with known locations when ground access in the remote area is prohibited, one solution is to deploy the sensors remotely, from an aircraft. The lack of precise sensor placement is compensated by a large sensor population deployed in the drop zone, that would improve the probability of target coverage. The data collected from the sensors is sent to a central node (e.g. cluster head) for processing. In this paper we propose un efficient method to extend the sensor network life time by organizing the sensors into a maximal number of set covers that are activated successively. Only the sensors from the current active set are responsible for monitoring all targets and for transmitting the collected data, while all other nodes are in a low-energy sleep mode. By allowing sensors to participate in multiple sets, our problem formulation increases the network lifetime compared with related work [M. Cardei et al], that has the additional requirements of sensor sets being disjoint and operating equal time intervals. In this paper we model the solution as the maximum set covers problem and design two heuristics that efficiently compute the sets, using linear programming and a greedy approach. Simulation results are presented to verify our approaches.
---
paper_title: Distributed lifetime-maximized target coverage game

paper_content:

Wireless sensor nodes are usually densely deployed to completely cover (monitor) a set of targets. Consequently, redundant sensor nodes that are not currently needed in the covering task can be powered off to conserve energy. These sensors can take over the covering task later to prolong network lifetime. The coverage problem, concerns picking up a set of working sensors that collectively meet the coverage requirements. The problem is complicated by the possibility that targets may have different coverage requirements while sensor nodes may have different amounts of energy. This article proposes a game-theoretic approach to the coverage problem, where each sensor autonomously decides its state with a simple rule based on local information. We give rigorous proofs to show stability, correctness, and efficiency of the proposed game. Implementation variants of the game consider specific issues, such as game convergence time and different amounts of sensor energy. Simulation results show significant improvement in network lifetime by the proposed approach when compared with representative alternatives.
---
paper_title: Optimality and Complexity of Pure Nash Equilibria in the Coverage Game

paper_content:

In this paper, we investigate the coverage problem in wireless sensor networks using a game theory method. We assume that nodes are randomly scattered in a sensor field and the goal is to partition these nodes into K sets. At any given time, nodes belonging to only one of these sets actively sense the field. A key challenge is to achieve this partition in a distributed manner with purely local information and yet provide near optimal coverage. We appropriately formulate this coverage problem as a coverage game and prove that the optimal solution is a pure Nash equilibrium. Then, we design synchronous and asynchronous algorithms, which converge to pure Nash equilibria. Moreover, we analyze the optimality and complexity of pure Nash equilibria in the coverage game. We prove that, the ratio between the optimal coverage and the worst case Nash equilibrium coverage, is upper bounded by 2 - 1/m+1 (m is the maximum number of nodes, which cover any point, in the Nash equilibrium solution s*). We prove that finding pure Nash equilibria in the general coverage game is PLS-complete, i.e. "as hard as that of finding a local optimum in any local search problem with efficient computable neighbors". Finally, via extensive simulations, we show that, the Nash equilibria coverage performance is very close to the optimal coverage and the convergence speed is sublinear. Even under the noisy environment, our algorithms can still converge to the pure Nash equilibria.
---
paper_title: Collaborative Sensing in a Distributed PTZ Camera Network

paper_content:

The performance of dynamic scene algorithms often suffers because of the inability to effectively acquire features on the targets, particularly when they are distributed over a wide field of view. In this paper, we propose an integrated analysis and control framework for a pan, tilt, zoom (PTZ) camera network in order to maximize various scene understanding performance criteria (e.g., tracking accuracy, best shot, and image resolution) through dynamic camera-to-target assignment and efficient feature acquisition. Moreover, we consider the situation where processing is distributed across the network since it is often unrealistic to have all the image data at a central location. In such situations, the cameras, although autonomous, must collaborate among themselves because each camera's PTZ parameter entails constraints on the others. Motivated by recent work in cooperative control of sensor networks, we propose a distributed optimization strategy, which can be modeled as a game involving the cameras and targets. The cameras gain by reducing the error covariance of the tracked targets or through higher resolution feature acquisition, which, however, comes at the risk of losing the dynamic target. Through the optimization of this reward-versus-risk tradeoff, we are able to control the PTZ parameters of the cameras and assign them to targets dynamically. The tracks, upon which the control algorithm is dependent, are obtained through a consensus estimation algorithm whereby cameras can arrive at a consensus on the state of each target through a negotiation strategy. We analyze the performance of this collaborative sensing strategy in active camera networks in a simulation environment, as well as a real-life camera network.
---
paper_title: Game theoretic cooperative control of PTZ visual sensor networks for environmental change monitoring

paper_content:

In this paper, we investigate cooperative environmental monitoring for Pan-Tilt-Zoom(PTZ) visual sensor networks based on game theoretic cooperative control. In particular, we focus on one of the key goals of the monitoring task, i.e. monitoring environmental changes from a normal state. For this purpose, this paper first presents a novel formulation of the optimal environmental monitoring problem reflecting the above objective and characteristics of vision sensors. Then, the optimization problem is reduced to a potential game with potential function equal to the formulated objective function through an existing utility design technique, where the designed utility is shown to be computable through local computation and communication. We finally present a payoff-based learning algorithm, which refines [18] so that the sensors eventually take the potential function maximizes with high probability and local action constraints are dealt with. Finally, we run experiments on a testbed in order to demonstrate the effectiveness of the presented approach.
---
paper_title: $N$-Person Card Game Approach for Solving SET $K$-COVER Problem in Wireless Sensor Networks

paper_content:

Solutions to SET K-COVER problem can prolong the lifetime of wireless sensor networks (WSNs) by partitioning the sensors into sets. In this paper, a novel purely distributed method for solving SET K-COVER problem is introduced based on the game theory, in which we consider the SET K-COVER problem as a noncooperative N-person card game. The sensors in WSN are considered as the players, the cover sets chosen by N sensors are considered as the strategies, and the sensing area covered alone is considered as the payoff function for each sensor. After the gaming process, the best strategies that all of the players have chosen constitute the Nash equilibrium. In addition, we analyze the effects of the initial strategies on the gaming result and propose a solution to avoid this effect in order to obtain a better coverage performance. We also extend the optimality of Nash equilibrium in the coverage game to a more general case. Besides that, the analysis of the convergence performance and the message complexity of the proposed algorithm are also presented. Extensive simulations have been conducted to show the superiority of the proposed algorithm in convergence, robustness, and coverage, comparing with the random, K-COVER, and synchronous Nash equilibria convergence algorithms. Finally, based on the results from real experiments on both small- and large-scale WSNs, we conclude that the proposed algorithm can be applied in real application environment and is also of good performance in both convergence and coverage. Furthermore, we also provide the comparisons between results from simulations and real experiments when some practical issues are considered.
---
paper_title: Game-Theoretic Based Distributed Scheduling Algorithms for Minimum Coverage Breach in Directional Sensor Networks

paper_content:

A directional sensor network, where a lot of sensors are intensively and randomly deployed, is able to enhance coverage performances, since working directions can be partitioned into different K covers which are activated in a round-robin fashion. In this paper, we consider the problem of direction set K-Cover for minimum coverage breach in directional sensor networks. First, we formulate the problem as a game called direction scheduling game (DSG), which we prove as a potential game. Thus, the existence of pure Nash equilibria can be guaranteed, and the optimal coverage is a pure Nash equilibrium, since the potential function of DSGs is consistent with the coverage objective function of the underlying network. Second, we propose the synchronous and asynchronous game-theoretic based distributed scheduling algorithms, which we prove to converge to pure Nash equilibria. Third, we present the explicit bounds on the coverage performance of the proposed algorithms by theoretical analysis of the algorithms’ coverage performance. Finally, we show experimental results and conclude that the Nash equilibria can provide a near-optimal and well-balanced solution.
---
paper_title: Non-cooperative code design in radar networks: a game-theoretic approach

paper_content:

A network of radars sharing the same frequency band, and using properly coded waveforms to improve features attractive from the radar point of view is considered in this article. Non-cooperative games aimed at code design for maximization of the signal-to-interference plus noise ratio (SINR) of each active radar are presented. Code update strategies are proposed, and, resorting to the theory of potential games, the existence of Nash equilibria is analytically proven. In particular, we propose non-cooperative code update procedures for the cases in which a matched filter, a minimum integrated sidelobe level filter, and a minimum peak to sidelobe level filter are used at the receiver. The case in which the received data contain a non-negligible Doppler shift is also analyzed. Experimental results confirm that the proposed procedures reach an equilibrium in few iterations, as well as that the SINR values at the equilibrium are largely superior to those in the case in which classical waveforms are used and no optimization of the radar code is performed.
---
paper_title: Collusion of operators in wireless spectrum markets

paper_content:

The liberalization of wireless spectrum markets has been envisioned as a method for improving mobile communication services and accommodating the increasing traffic volumes of wireless users. It has been assumed that competition among operators will foster optimal utilization of wireless spectrum and ensure the provision of cost-efficient wireless services to users. However, spectrum markets often function inefficiently due to collusion of the operators. Although it is illegal and detrimental to users, such phenomena are often observed in real life as, for example, in the form of implicit price fixing. This results in a de-facto monopoly in the spectrum market to the detriment of the users. In this paper, we consider a general wireless spectrum market where a set of operators sell bandwidth to a large population of users. We use an evolutionary game model to capture the user dynamics in the presence of limited market information and analyze the interaction of the operators using coalitional game theory. We define a partition formation game in order to rigorously study the conditions that render the grand coalition (emergence of monopoly) stable under various stability notions. The results obtained provide a foundation for effective measures against operator collusion by altering the underlying motivations rather than fighting against the symptoms through law enforcement.
---
paper_title: Demand side management for Wind Power Integration in microgrid using dynamic potential game theory

paper_content:

We propose a novel demand side management method to tackle the intermittency in wind power generation. Our focus is on an isolated microgrid with one wind turbine, one fast-responding conventional generator, and several users. Users act as independent decision makers in shaping their own load profiles. Using dynamic potential game theory, we analyze and coordinate the interactions among users to efficiently utilize the available renewable and conventional energy resources to minimize the total energy cost in the system. We further model the inter-temporal variations of the available wind power as a Markov chain based on field data. Using techniques from dynamic potential game theory, we first derive closed-form expressions for the best responses for the users that participate in demand side management. Then, we investigate the efficiency of the constructed game model at the equilibrium. Finally, the system performance is assessed using computer simulation. In particular, our proposed scheme saves 38% generation cost compared with the case without demand side management.
---
paper_title: Multipath Wireless Network Coding: A Population Game Perspective

paper_content:

We consider wireless networks in which multiple paths are available between each source and destination. We allow each source to split traffic among all of its available paths, and ask the question: how do we attain the lowest possible number of transmissions per unit time to support a given traffic matrix? Traffic bound in opposite directions over two wireless hops can utilize the ``reverse carpooling'' advantage of network coding in order to decrease the number of transmissions used. We call such coded hops as ``hyper-links''. With the reverse carpooling technique longer paths might be cheaper than shorter ones. However, there is a prisoners dilemma type situation among sources -- the network coding advantage is realized only if there is traffic in both directions of a shared path. We develop a two-level distributed control scheme that decouples user choices from each other by declaring a hyper- link capacity, allowing sources to split their traffic selfishly in a distributed fashion, and then changing the hyper-link capacity based on user actions. We show that such a controller is stable, and verify our analytical insights by simulation.
---
paper_title: Network Selection in Cognitive Heterogeneous Networks Using Stochastic Learning

paper_content:

Coexistence of multiple radio access technologies (RATs) is a promising paradigm to improve spectral efficiency. This letter presents a game-theoretic network selection scheme in a cognitive heterogeneous networking environment with time-varying channel availability. We formulate the network selection problem as a noncooperative game with secondary users (SUs) as the players, and show that the game is an ordinal potential game (OPG). A decentralized, stochastic learning-based algorithm is proposed where each SU's strategy progressively evolves toward the Nash equilibrium (NE) based on its own action-reward history, without the need to know actions in other SUs. The convergence properties of the proposed algorithm toward an NE point are theoretically and numerically verified. The proposed algorithm demonstrates good throughput and fairness performances in various network scenarios.
---
paper_title: Network Selection and Resource Allocation Games for Wireless Access Networks

paper_content:

Wireless access networks are often characterized by the interaction of different end users, communication technologies, and network operators. This paper analyzes the dynamics among these "actorsa by focusing on the processes of wireless network selection, where end users may choose among multiple available access networks to get connectivity, and resource allocation, where network operators may set their radio resources to provide connectivity. The interaction among end users is modeled as a noncooperative congestion game, where players (end users) selfishly select the access network that minimizes their perceived selection cost. A method based on mathematical programming is proposed to find Nash equilibria and characterize their optimality under three cost functions, which are representative of different technological scenarios. System level simulations are then used to evaluate the actual throughput and fairness of the equilibrium points. The interaction among end users and network operators is then assessed through a two-stage multileader/multifollower game, where network operators (leaders) play in the first stage by properly setting the radio resources to maximize their users, and end users (followers) play in the second stage the aforementioned network selection game. The existence of exact and approximated subgame perfect Nash equilibria of the two-stage game is thoroughly assessed and numerical results are provided on the "qualitya of such equilibria.
---
paper_title: A game-theoretic approach for balancing the tradeoffs between data availability and query delay in multi-hop cellular networks

paper_content:

In this paper, the selfish caching problem in multi-hop cellular networks (MCNs) is formulated as a non-cooperative game: data caching game. Towards balancing the tradeoffs between data availability and query delay in MCNs, an incentive mechanism based upon a payment model is set up for data caching game. The data caching game is proved to be a potential game. Thus, for the game, pure Nash equilibra can be obtained and the best response dynamics converge to a pure Nash equilibrium. Moreover, by properly setting the payoff distribution rule, caching proxies have incentive to or not to cache the same data to some extent. Thereby, the performance of data availability and query delay can be tuned in an adjustable-way, which results in a desirable service performance that service provider intends to achieve.
---
paper_title: Game Theoretical Model and Existence of Win-Win Situation for Femtocell Networks

paper_content:

In recent years, the femtocell plays an important role in wireless networks not only for its spectrum reuse but also for its low power consumption. However, there exists several critical issues that need to be investigated, especially for the interferences between the macrocells and the femtocells. Two major access policies are considered in the femtocell network, including the closed access mode and the open access mode. The closed access mode only permits authorized subscribers to utilize the femtocells; while all users are allowed to connect to the femtocell by adopting the open access mode. The closed access will intuitively be advantageous to the femtocell subscribers, however, it has shown that interference from the macrocell to the femtocell can be mitigated by using the open access mode. In this paper, a cell selection game is theoretically modeled to formulate the behaviors of the nonsubscribers who have the opportunities to connect to the femtocells. The distinct connection manners of nonsubscribers to access the macrocells and the femtocells are modeled as the primary users and cognitive users, respectively. Considering the channel capacity of femtocell as the utility function of this game, the existence of a pure strategy Nash equilibrium is illustrated to provide the win-win situation between the subscribers and nonsubscribers.
---
paper_title: On Distributed Localization for Road Sensor Networks: A Game Theoretic Approach

paper_content:

Road sensor network is an important part of vehicle networks system and is critical for many intelligent automobile scenarios, such as vehicle safety monitoring and transportation efficiency supporting. Localization of sensors is an active and crucial issue to most applications of road sensor network. Generally, given some anchor nodes’ positions and certain pairwise distance measurements, estimating the positions of all nonanchor nodes embodies a nonconvex optimization problem. However, due to the small number of anchor nodes and low sensor node connectivity degree in road sensor networks, the existing localization solutions are ineffective. In order to tackle this problem, a novel distributed localization method based on game theory for road sensor networks is proposed in this paper. Formally, we demonstrate that our proposed localization game is a potential game. Furthermore, we present several techniques to accelerate the convergence to the optimal solution. Simulation results demonstrate the effectiveness of our proposed algorithm.
---
paper_title: Peering Equilibrium Multipath Routing: A Game Theory Framework for Internet Peering Settlements

paper_content:

It is generally admitted that interdomain peering links represent nowadays the main bottleneck of the Internet, particularly because of lack of coordination between providers, which use independent and "selfish" routing policies. We are interested in identifying possible "light" coordination strategies that would allow carriers to better control their peering links while preserving their independence and respective interests. We propose a robust multipath routing coordination framework for peering carriers, which relies on the multiple-exit discriminator (MED) attribute of Border Gateway Protocol (BGP) as signaling medium. Our scheme relies on a game theory modeling, with a non-cooperative potential game considering both routing and congestions costs. Peering equilibrium multipath (PEMP) coordination policies can be implemented by selecting Pareto-superior Nash equilibria at each carrier. We compare different PEMP policies to BGP Multipath schemes by emulating a realistic peering scenario. Our results show that the routing cost can be decreased by roughly 10% with PEMP. We also show that the stability of routes can be significantly improved and that congestion can be practically avoided on the peering links. Finally, we discuss practical implementation aspects and extend the model to multiple players highlighting the possible incentives for the resulting extended peering framework.
---
paper_title: Decentralized Computation Offloading Game For Mobile Cloud Computing

paper_content:

Mobile cloud computing is envisioned as a promising approach to augment computation capabilities of mobile devices for emerging resource-hungry mobile applications. In this paper, we propose a game theoretic approach for achieving efficient computation offloading for mobile cloud computing. We formulate the decentralized computation offloading decision making problem among mobile device users as a decentralized computation offloading game. We analyze the structural property of the game and show that the game always admits a Nash equilibrium. We then design a decentralized computation offloading mechanism that can achieve a Nash equilibrium of the game and quantify its efficiency ratio over the centralized optimal solution. Numerical results demonstrate that the proposed mechanism can achieve efficient computation offloading performance and scale well as the system size increases.
---
paper_title: Pricing Games for Distributed Cooperative Transmission

paper_content:

Two pricing games are derived for distributed rate allocation in two cooperative transmission schemes, in which source nodes are assigned orthogonal channels. In the first game, the source nodes multiplex the data streams of the outgoing links through superposition coding. In the second game, the source nodes perform time-division multiplexing over their outgoing links. At the Nash equilibrium of both games, the total transmission power is minimized. Based on both games, we propose distributed and adaptive implementations. Simulation results illustrate the significant improvement of power consumption over direct transmission and the high convergence rate of our proposed algorithms.
---
paper_title: A New Decomposition Method for Multiuser DC-Programming and Its Applications

paper_content:

We propose a novel decomposition framework for the distributed optimization of Difference Convex (DC)-type nonseparable sum-utility functions subject to coupling convex constraints. A major contribution of the paper is to develop for the first time a class of (inexact) best-response-like algorithms with provable convergence, where a suitably convexified version of the original DC program is iteratively solved. The main feature of the proposed successive convex approximation method is its decomposability structure across the users, which leads naturally to distributed algorithms in the primal and/or dual domain. The proposed framework is applicable to a variety of multiuser DC problems in different areas, ranging from signal processing, to communications and networking. As a case study, in the second part of the paper we focus on two examples, namely: i) a novel resource allocation problem in the emerging area of cooperative physical layer security and ii) and the renowned sum-rate maximization of MIMO Cognitive Radio networks. Our contribution in this context is to devise a class of easy-to-implement distributed algorithms with provable convergence to stationary solution of such problems. Numerical results show that the proposed distributed schemes reach performance close to (and sometimes better than) that of centralized methods.
---
paper_title: Femtocell Access Strategies in Heterogeneous Networks using a Game Theoretical Framework

paper_content:

In recent years, femtocell plays an important role in wireless networks not only for its spectrum reuse but also for its low power consumption. However, there exist several critical issues that need to be investigated, especially for the interferences between the macrocell BSs (mBSs) and femtocell BSs (fBSs). The level of interference mainly depends on the access strategies of fBSs. Two major access policies are considered in femtocell network, including the closed access mode and open access mode. The closed access mode only permits authorized subscribers to utilize the fBS; while all users are allowed to connect to the fBS by adopting the open access mode. Closed access will intuitively be advantageous to the femtocell subscribers, however, interference from the fBS to mBS's users can become severe in the closed access mode than in open access mode. System performance of the entire heterogeneous network (HetNet) can be improved if fBS is operated in the open access mode. In order to relax the inflexible access strategies, hybrid access policy is considered in this paper which allows nonsubscribers to possess limited connections to the fBS. Two cell selection games for distinct scenarios are theoretically modeled to formulate the behaviors of nonsubscribers, and the existences of pure strategy Nash equilibria are also proven under feasible utility functions. From the perspectives of subscribers, HetNet system, and operator, numerical results suggest the adoption of hybrid access mode to provide higher flexibility for the performance enhancement.
---
paper_title: Evolutionary dynamics and potential games in non-cooperative routing

paper_content:

We consider a routing problem in a network with a general topology. Considering a link cost which is linear in the link flow, we obtain a unique Nash equilibrium and show that the non-cooperative game can be expressed as a potential game. We establish various convergence and stability properties of of the equilibrium related to the routing problem being a potential game. We then consider the routing problem in the framework of a population game and study the evolution of the size of the populations when the replicator dynamics is used.
---
paper_title: Energy-efficient routing for correlated data in wireless sensor networks

paper_content:

In this paper, we investigate the reduction in the total energy consumption of wireless sensor networks using multi-hop data aggregation by constructing energy-efficient data aggregation trees. We propose an adaptive and distributed routing algorithm for correlated data gathering and exploit the data correlation between nodes using a game theoretic framework. Routes are chosen to minimize the total energy expended by the network using best response dynamics to local data. The cost function that is used for the proposed routing algorithm takes into account energy, interference and in-network data aggregation. The iterative algorithm is shown to converge in a finite number of steps. Simulations results show that multi-hop data aggregation can significantly reduce the total energy consumption in the network.
---
paper_title: Uplink power control and base station association in multichannel cellular networks

paper_content:

A combined base station association and power control problem is studied for the uplink of multichannel multicell cellular networks, in which each channel is used by exactly one cell (i.e., base station). A distributed association and power update algorithm is proposed and shown to converge to a Nash equilibrium of a noncooperative game. We consider network models with discrete mobiles (yielding an atomic congestion game), as well as a continuum of mobiles (yielding a population game). We find that the equilibria need not be Pareto efficient, nor need they be system optimal. To address the lack of system optimality, we propose pricing mechanisms. It is shown that these mechanisms can be implemented in a distributed fashion.
---
paper_title: The price of selfishness in network coding

paper_content:

We introduce a game theoretic framework for studying a restricted form of network coding in a general wireless network. The network is fixed and known, and the system performance is measured as the number of wireless transmissions required to meet n unicast demands. Game theory is here employed as a tool for improving distributed network coding solutions. We propose a framework that allows each unicast session to independently adjust his routing decision in response to local information. Specifically, we model the interactions of the unicast sessions as a noncooperative game. This approach involves designing both local cost functions and decision rules for the unicast sessions so that the resulting collective behavior achieves a desirable system performance in a shared network environment. We propose a family of cost functions and compare the performance of the resulting distributed algorithms to the best performance that could be found and implemented using a centralized controller. We focus on the performance of stable solutions - where stability here refers to a form of Nash equilibrium defined below. Results include bounds on the bestand worst-case stable solutions as compared to the optimal centralized solution. Results in learning in games prove that the best-case stable solution can be learned by self-interested players with probability approaching 1.
---
paper_title: Resource Allocation for Multiuser Improved AF Cooperative Communication Scheme

paper_content:

Joint power and bandwidth allocation of an improved amplify and forward (AF) cooperative communication scheme is proposed to utilize the spectrum efficiently. Each user adapts to a mixed strategy transmission using frequency division multiplexing (FDM), where part of the data is transmitted using AF relaying with diversity, and the other part is transmitted using direct transmission without diversity. The resource allocation problem aimed at maximizing the sum rate of a multi-user up-link scenario using the improved scheme is formulated. Both flat and frequency-selective fading channels are addressed. The resource allocation problem of the power and bandwidth profiles is non-convex and difficult to solve. In this sense, a two-step iterative algorithm is proposed, which alternates between solving either power allocation sub-problem for a given bandwidth profile or a bandwidth allocation sub-problem for a given power profile. The convergence and optimality of the proposed algorithm are discussed using game theory framework. Numerical simulations show the merits of the proposed improved AF cooperative communication scheme and the proposed iterative algorithm.
---
paper_title: Distributed Demand Management in Smart Grid with a Congestion Game

paper_content:

In this paper we propose distributed load management in smart grid infrastructures to control the power demand at peak hours, by means of dynamic pricing strategies. The distributed solution that we propose is based on a network congestion game, which can be demonstrated to converge in a finite number of steps to a pure Nash equilibrium solution. We take advantage of the remarkable property of congestion games, according to which they are equivalent to potential games. We define a potential function characterized by a meaningful physical interpretation, so that we obtain the favorable result that the optimal local solution of each selfish consumer is also the solution of a global objective. We evaluate this approach for managing both the demand and the grid load and we show that load control can be effectively achieved implementing a distributed solution, which significantly reduce the signaling burden over the network.
---
paper_title: Two-dimensional route switching in cognitive radio networks: a game-theoretical framework

paper_content:

In cognitive radio networks (CRNs), secondary users (SUs) can flexibly access primary users' (PUs') idle spectrum bands, but such spectrum opportunities are dynamic due to PUs' uncertain activity patterns. In a multihop CRN consisting of SUs as relays, such spectrum dynamics will further cause the invalidity of predetermined routes. In this paper, we investigate spectrum-mobility-incurred route-switching problems in both spatial and frequency domains for CRNs, where spatial switching determines which relays and links should be reselected and frequency switching decides which channels ought to be reassigned to the spatial routes. The proposed route-switching scheme not only avoids conflicts with PUs but also mitigates spectrum congestion. Meanwhile, tradeoffs between routing costs and channel switching costs are achieved. We further formulate the route-switching problem as the Route-Switching Game, which is shown to be a potential game and has a pure Nash equilibrium (NE). Accordingly, efficient algorithms for finding the NE and the $\epsilon $ –NE are proposed. Then, we extend the proposed game to the incomplete-information scenario and provide a method to compute the Bayesian NE. Finally, we prove that the price of anarchy of the proposed game has a deterministic upper bound.
---
paper_title: Multipath Wireless Network Coding: An Augmented Potential Game Perspective

paper_content:

We consider wireless networks in which multiple paths are available between each source and destination. We allow each source to split traffic among all of its available paths, and we ask the question: How do we attain the lowest possible number of transmissions per unit time to support a given traffic matrix? Traffic bound in opposite directions over two wireless hops can utilize the “reverse carpooling” advantage of network coding in order to decrease the number of transmissions used. We call such coded hops “hyper-links.” With the reverse carpooling technique, longer paths might be cheaper than shorter ones. However, there is a peculiar situation among sources-the network coding advantage is realized only if there is traffic in both directions of a shared path. We consider the problem of routing with network coding by selfish agents (the sources) as a potential game and develop a method of state-space augmentation in which additional agents (the hyper-links) decouple sources' choices from each other by declaring a hyper-link capacity, allowing sources to split their traffic selfishly in a distributed fashion, and then changing the hyper-link capacity based on user actions. Furthermore, each hyper-link has a scheduling constraint in terms of the maximum number of transmissions allowed per unit time. We show that our two-level control scheme is stable and verify our analytical insights by simulation.
---
paper_title: A social group utility maximization framework with applications in database assisted spectrum access

paper_content:

In this paper, we develop a social group utility maximization (SGUM) framework for cooperative networking that takes into account both social relationships and physical coupling among users. Specifically, instead of maximizing its individual utility or the overall network utility, each user aims to maximize its social group utility that hinges heavily on its social ties with other users. We show that this framework provides rich modeling flexibility and spans the continuum space between non-cooperative game and network utility maximization (NUM) - two traditionally disjoint paradigms for network optimization. Based on this framework, we study an important application in database assisted spectrum access. We formulate the distributed spectrum access problem among white-space users with social ties as a SGUM game. We show that the game is a potential game and always admits a social-aware Nash equilibrium. We also design a distributed spectrum access algorithm that can achieve the social-aware Nash equilibrium of the game and quantify its performance gap. We evaluate the performance of the SGUM solution using real social data traces. Numerical results demonstrate that the performance gap between the SGUM solution and the NUM (social welfare optimal) solution is at most 15%.
---
paper_title: Game-Based Broadcast over Reliable and Unreliable Wireless Links in Wireless Multihop Networks

paper_content:

This paper addresses the minimum transmission broadcast problem in wireless networks and presents efficient solutions, including an optimal broadcast scheme and a distributed game-based algorithm. Distinct from related work in the literature which typically assumes wireless links are reliable, we address the issue of broadcasting over both reliable wireless links and unreliable wireless links. Our main contributions are as follows: We first formulate the minimum transmission broadcast problems over reliable links and over unreliable links as two mixed integer linear programming (MILP) problems, respectively. This way, optimal broadcast schemes can be easily obtained using any existing MILP solver, for small-scale networks. For large-scale networks, we propose a distributed game-based algorithm and prove that the game-based algorithm achieves Nash Equilibrium. Using simulation, we confirm that compared with existing algorithms in the literature and optimal solutions obtained by our MILP techniques, the proposed game-based algorithm performs very well in terms of delivery ratio, the number of transmissions, and convergence speed.
---
paper_title: Reconciling the Overlay and Underlay Tussle

paper_content:

In the presence of multiple overlays and underlays, the emerging global network behavior is the result of interactions of self-serving overlay routing decisions and independent underlay management actions. It is crucial for network operators, service, and content providers to have a good grasp of the underlying principles in order to better design and manage current and future networks and services. In this paper, we describe special game scenarios wherein the interaction of noncooperative overlays and underlays in multidomain networks can result in an operable global configuration in linear time and the overall convergence is polynomial in the unweighed case. For weighted games, we find that weighted Shapley potential can achieve linear time convergence to an operable state. Furthermore, we analyze the interaction of overlays and underlays as a two-stage congestion game and recommend simple operational guidelines to ensure global stability. We further explore the use of Shapley value as an enabler of mutual cooperation in an otherwise competitive environment. Our simulation results confirm our findings and demonstrate its effectiveness in general networks.
---
paper_title: Efficient inter-domain traffic engineering with transit-edge hierarchical routing

paper_content:

The relentless growth of Internet, which has resulted in the increase of routing table sizes, requires consideration and new direction to address Internet scalability and resiliency. A possible direction is to move away from the flat legacy Internet routing to hierarchical routing, and introduce two-level hierarchical routing between edge networks and across transit networks. In this way, there is also an opportunity to separate the routing locator from the terminal identifier, to better manage IP mobility and mitigate important routing security issues. In this paper, we study the extended traffic engineering capabilities arising in a transit-edge hierarchical routing, focusing on those multi-homed edge networks (e.g., Cloud/content providers) that aim at increasing their Internet resiliency experience. We model the interaction between distant independent edge networks exchanging large traffic volumes using game theory, with the goal of seeking efficient edge-to-edge load-balancing solutions. The proposed traffic engineering framework relies on a non-cooperative potential game, built upon locator and path ranking costs, that indicates efficient equilibrium solution for the edge-to-edge load-balancing coordination problem. Simulations on real instances show that in comparison to the available standard protocols such as BGP and LISP, we can achieve a much higher degree of resiliency and stability.
---

Title: A Comprehensive Survey of Potential Game Approaches to Wireless Networks

Section 1: Introduction
Description 1: Introduce the topic and provide an overview of potential game approaches in wireless networks.

Section 2: Game-Theoretic Framework
Description 2: Define the strategic form game and discuss concepts such as best response and Nash equilibrium.

Section 3: Potential Games
Description 3: Explain key definitions and properties of potential games and identify and design exact and ordinal potential games.

Section 4: Learning Algorithms
Description 4: Discuss various learning algorithms that facilitate the convergence of potential games to Nash equilibrium.

Section 5: Channel Assignment in TX-RX Pair Model
Description 5: Examine channel assignment problems and interference management in the TX-RX pair model.

Section 6: Joint Transmission Power and Channel Allocation
Description 6: Explore joint transmission power and channel allocation schemes and potential games.

Section 7: Primary-Secondary Scenario and Heterogeneous Networks
Description 7: Address interference management in primary-secondary systems and heterogeneous networks.

Section 8: Channel Assignment to Manage the Number of Interference Signals
Description 8: Discuss models that minimize the number of interference signals in channel assignments.

Section 9: Channel Assignment to Enhance SINR and Capacity
Description 9: Investigate potential games that enhance signal-to-interference-plus-noise ratio (SINR) and capacity.

Section 10: Channel Assignment in Interference Graphs
Description 10: Analyze channel assignments using interference graphs to reduce interference.

Section 11: Channel Assignment to Enhance Throughput in Collision Channels
Description 11: Examine methods to enhance throughput in collision channels through potential games.

Section 12: Transmission Power Assignment to Enhance Throughput
Description 12: Discuss transmission power control to maximize throughput in multiple-access channels.

Section 13: Transmission Power Assignment for Connectivity
Description 13: Discuss topology control strategies for maintaining network connectivity while reducing energy consumption.

Section 14: Flow and Congestion Control in Fluid Networks
Description 14: Explore potential game formulations for flow and congestion control in networks.

Section 15: Arrival Rate Control for M/M/1 Queues
Description 15: Investigate approaches to control arrival rates to optimize throughput and delay in queuing models.

Section 16: Sensor Deployment for Connectivity and Coverage
Description 16: Discuss potential game approaches for sensor deployment to ensure connectivity and coverage.

Section 17: Channel Assignment to Enhance Coverage for Immobile Sensors
Description 17: Examine channel assignment strategies for enhancing the coverage area of immobile sensors.

Section 18: Conclusions
Description 18: Summarize the survey findings and discuss the implications and potential future directions for potential game approaches in wireless networks.

Section 19: Acknowledgments
Description 19: Acknowledge any support or contributions received during the research.