Bottleneck Routing Games in Communication Networks

We consider routing games where the performance of each user is dictated by the worst (bottleneck) element it employs. We are given a network, finitely many (selfish) users, each associated with a positive flow demand, and a load-dependent performance function for each network element; the social (i.e., system) objective is to optimize the performance of the worst element in the network (i.e., the network bottleneck). Although we show that such "bottleneck" routing games appear in a variety of practical scenarios, they have not been considered yet. Accordingly, we study their properties, considering two routing scenarios, namely when a user can split its traffic over more than one path (splittable bottleneck game) and when it cannot (unsplittable bottleneck game). First, we prove that, for both splittable and unsplittable bottleneck games, there is a (not necessarily unique) Nash equilibrium. Then, we consider the rate of convergence to a Nash equilibrium in each game. Finally, we investigate the efficiency of the Nash equilibria in both games with respect to the social optimum; specifically, while for both games we show that the price of anarchy is unbounded, we identify for each game conditions under which Nash equilibria are socially optimal.     

Multiradio Channel Allocation in Multihop Wireless Networks

Channel allocation was extensively investigated in the framework of cellular networks, but it was rarely studied in the wireless ad hoc networks, especially in the multihop networks. In this paper, we study the competitive multiradio multichannel allocation problem in multihop wireless networks in detail. We first analyze that the static noncooperative game and Nash equilibrium (NE) channel allocation scheme are not suitable for the multihop wireless networks. Thus, we model the channel allocation problem as a hybrid game involving both cooperative game and noncooperative game. Within a communication session, it is cooperative; and among sessions, it is noncooperative. We propose the min-max coalition-proof Nash equilibrium (MMCPNE) channel allocation scheme in the game, which aims to maximize the achieved data rates of communication sessions. We analyze the existence of MMCPNE and prove the necessary conditions for MMCPNE. Furthermore, we propose several algorithms that enable the selfish players to converge to MMCPNE. Simulation results show that MMCPNE outperforms NE and coalition-proof Nash equilibrium (CPNE) schemes in terms of the achieved data rates of multihop sessions and the throughput of whole networks due to cooperation gain.     

WiFi access point pricing as a dynamic game

We study the economic interests of a wireless access point owner and his paying client, and model their interaction as a dynamic game. The key feature of this game is that the players have asymmetric information - the client knows more than the access provider. We find that if a client has a "web browser" utility function (a temporal utility function that grows linearly), it is a Nash equilibrium for the provider to charge the client a constant price per unit time. On the other hand, if the client has a "file transferor" utility function (a utility function that is a step function), the client would be unwilling to pay until the final time slot of the file transfer. We also study an expanded game where an access point sells to a reseller,which in turn sells to a mobile client and show that if the client has a web browser utility function, that constant price is a Nash equilibrium of the three player game. Finally, we study a two player game in which the access point does not know whether he faces a web browser or file transferor type client, and show conditions for which it is not a Nash equilibrium for the access point to maintain a constant price.     

A Price Based Decentralized Rate Selection in IEEE 802.11 Based WLANS

We consider the problem of decentralized rate selection in IEEE 802.11 wireless local area networks (WLANs). Owing to the decentralized nature of WLANs, we formulate the current problem of rate selection as a non-cooperative game where individual users (players) of a WLAN can pick their actions from a finite set of physical layer modulation rates. The utility of each user is the difference of throughput and a cost incurred due to the price imposed by the access point. We prove the resulting non-cooperative game to be supermodular, and hence has at least one pure strategy Nash equilibrium, that is contained in a set bounded by the smallest and largest Nash equilibria. We also prove the smallest and largest Nash equilibria to be non-decreasing functions of the price and the smallest Nash equilibrium to be Pareto-dominant. We present an algorithm to compute the best response of each user asynchronously, that converges almost surely to the smallest Nash equilibrium of the game. Next we extend our price based approach to the multi-channel case and prove the resulting game to be supermodular in the special case of two channels. Our simulation results demonstrate the improvement in overall network throughput with appropriate tuning of the price.     

Min-Cost Selfish Multicast With Network Coding

The single-source min-cost multicast problem, which can be framed as a convex optimization problem with the use of network codes and convex increasing edge costs is considered. A decentralized approach to this problem is presented by Lun, Ratnakar for the case where all users cooperate to reach the global minimum. Further, the cost for the scenario where each of the multicast receivers greedily routes its flows is analyzed and the existence of a Nash equilibrium is proved. An allocation rule by which edge cost at each edge is allocated to flows through that edge is presented. We prove that under our pricing rule, the flow cost at user equilibrium is the same as the min-cost. This leads to the construction of a selfish flow-steering algorithm for each receiver, which is also globally optimal. Further, the algorithm is extended for completely distributed flow adaptation at nodes in the network to achieve globally minimal cost in steady state. Analogous results are also presented for the case of multiple multicast sessions     

On Nash equilibria for multicast transmissions in ad-hoc wireless networks

We study a multicast game in ad-hoc wireless networks in which a source sends the same message or service to a set of receiving stations via multi-hop communications and the overall transmission cost is divided among the receivers according to given cost sharing methods. We assume that each receiver gets a certain utility from the transmission and enjoys a benefit equal to the difference between his utility and the shared cost he is asked to pay. Assuming a selfish and rational behavior, each user is willing to receive the transmission if and only if his shared cost does not exceed his utility. Moreover, given the strategies of the other users, he wants to select a strategy of minimum shared cost. A Nash equilibrium is a solution in which no user can increase his benefit by choosing to adopt a different strategy. We consider the following reasonable cost sharing methods: egalitarian, semi-egalitarian next-hop-proportional, path-proportional, egalitarian-path-proportional and Shapley value. We prove that, while the first five cost sharing methods in general do not admit a Nash equilibrium, the Shapley value yields games always converging to a Nash equilibrium. We then turn our attention to the special case in which the receivers’ set R is part of the input (that is only the stations belonging to R have a positive utility which is set equal to infinity) and show that in such a case also the egalitarian and the egalitarian-path-proportional methods yield convergent games. In such a framework, we show that the price of anarchy is unbounded for the game yielded by the egalitarian method and provide matching upper and lower bounds for the price of anarchy of the other two convergent games with respect to two different global cost functions, that is the overall cost of the power assignment, that coincides with the sum of all the shared costs, and the maximum shared cost paid by the receivers. Finally, in all cases we show that finding the best Nash equilibrium is computationally intractable, that is NP-hard. Vittorio Bilò received the degree in Computer Science and the Ph.D. degree in Computer Science at the University of L’Aquila in 2001 and 2005 respectively. He is currently an assistant professor at the Department of Mathematics “Ennio De Giorgi” of the University of Lecce. His research interests include algorithms and computational complexity, communication problems in interconnection networks and game theoretical issues in non-cooperative networks. Michele Flammini received the degree in Computer Science at the University of L’Aquila in 1990 and the Ph.D. degree in Computer Science at the University of Rome “La Sapienza” in 1995. He is full professor at the Computer Science Department of the University of L’Aquila since March 2005. His research interests include algorithms and computational complexity, game theory, communication problems in interconnection networks and routing. He has authored and co-authored more than 70 papers in his fields of interest published in the most reputed international conferences and journals. Giovanna Melideo received the Laurea degree in computer science in 1997 from the University of L’Aquila (Italy) and the Ph.D. degree in computer engineering in 2001 from the University of Rome “La Sapienza”. From November 1999 to February 2000 she was visitor at IRISA/INRIA, University of Rennes 1, Rennes (France) in the ADP group. She was research fellow from June to October 2001 at the University of L’Aquila, where she is currently an assistant professor in the Computer Science Department. Her research interests include algorithms and complexity, algorithmic game theory, wireless networks, models for information integration and cooperative information systems, certification and security in e-service, distributed protocols and dependability. She has been a member of the scientific and organizing committee of the IFIP international workshop on Certification and Security in E-Services (CSES 2002), Montreal, Canada. Luca Moscardelli received the degree in Computer Science at the University of L’Aquila in 2004. He is currently a Ph.D. student in Computer Science at the University of L’Aquila. His current research interests include optimization problems in social and communication networks, and the analysis of the interaction between selfish agents in non-cooperative networks.     

Virtual path bandwidth allocation in multiuser networks

We consider a multiuser network that is shared by noncooperative users. Each user sets up virtual paths that optimize its own selfish performance measure. This measure accounts for the guaranteed call level quality of service, as well as for the cost incurred for reserving the resource. The interaction among the user strategies is formalized as a noncooperative game. We show that the game has a unique Nash equilibrium and that it possesses a certain fairness property. We investigate the dynamics of this game and prove convergence to the Nash equilibrium of both a Gauss-Seidel scheme and a Jacobi scheme. We extend our study to various general network topologies. Finally, the formal results and some extensions thereof are tested by emulating the schemes on an experimental network     

Cooperative Game Theory and the Gaussian Interference Channel

In this paper we discuss the use of cooperative game theory for analyzing interference channels. We extend our previous work, to games with N players as well as frequency selective channels and joint TDM/FDM strategies. We show that the Nash bargaining solution can be computed using convex optimization techniques. We also show that the same results are applicable to interference channels where only statistical knowledge of the channel is available. Moreover, for the special case of two player 2 × K frequency selective channel (with K frequency bins) we provide an O(K log/sub 2/K) complexity algorithm for computing the Nash bargaining solution under mask constraint and using joint FDM/TDM strategies. Simulation results are also provided.     

A non-cooperative quality optimization game for scalable video delivery over MANETs

Non-cooperative game theory has found many important applications in engineering. In networking research community, this theory has been adopted to represent the selfish behaviour of the network users. In video transmission over Mobile Ad hoc NETworks (MANETs), video sources try to optimize their perceived video quality unilaterally. On the other hand, network providers try to set some prices on the scarce network resources such that their associated income is maximized. In the current paper, a non-cooperative quality game framework has been introduced in which by exploiting a related quality metric, scalable video users try to optimize their perceived quality in a distributed manner. The existence of a Nash Equilibrium (NE) has been proved and the stability of the distributed resource allocation strategy has been investigated. In the proposed resource assignment game, the utility functions of all competing scalable video sources converge to some optimal value which is dictated by the resulting Nash equilibrium in the allocated rates. In this optimal point, no player (video source) can enhance its utility unilaterally without compromising other players’ utility. The assigned rates in the game can be considered as rate-feedbacks for on-line rate adaptation of a moderate scalable video encoder such as H.264/MPEG4 AVC. Some numerical analysis have been presented to validate the theoretical results and to verify the claims.     

Game theory in signal processing and communications [From the Guest Editors]

Game theory is a branch of mathematics aimed at the modeling and understanding of resource conflict problems. Essentially, the theory splits into two branches: noncooperative and cooperative game theory. The distinction between the two is whether or not the players in the game can make joint decisions regarding the choice of strategy. Noncooperative game theory is closely connected to minimax optimization and typically results in the study of various equilibria, most notably the Nash equilibrium. Cooperative game theory examines how strictly rational (selfish) actors can benefit from voluntary cooperation by reaching bargaining agreements. Another distinction is between static and dynamic game theory, where the latter can be viewed as a combination of game theory and optimal control. In general, the theory provides a structured approach to many important problems arising in signal processing and communications, notably resource allocation and robust transceiver optimization. Recent applications also occur in other emerging fields, such as cognitive radio, spectrum sharing, and in multihop-sensor and adhoc networks.     

拥塞高速数据通信网优化控制模型

针对多信源——信宿高速数据通信网，引入N用户非零和微分对策优化控制路由模型。通信网中每个用户(决策者)，通过决策瞬时队列、路由及通信流量速率，使优化指标(损耗函数)达到最小；给出了反馈Nash平衡解的充要条件，并进行讨论。     

Joint random access and power control game in ad hoc networks with noncooperative users

We consider a distributed joint random access and power control scheme for interference management in wireless ad hoc networks. To derive decentralized solutions that do not require any cooperation among the users, we formulate this problem as noncooperative joint random access and power control game, in which each user minimizes its average transmission cost with a given rate constraint. Using supermodular game theory, the existence and uniqueness of Nash equilibrium are established. Furthermore, we present an asynchronous distributed algorithm to compute the solution of the game based on myopic best response updates, which converges to Nash equilibrium globally. Finally, a link admission algorithm is carried out to guarantee the reliability of the active users. Performance evaluations via simulations show that the game-theoretical based cross-layer design achieves high performance in terms of energy consumption and network stability.     

Optimality and Complexity of Pure Nash Equilibria in the Coverage Game

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.     

Competitive Pricing for Spectrum Sharing in Cognitive Radio Networks: Dynamic Game, Inefficiency of Nash Equilibrium, and Collusion

We address the problem of spectrum pricing in a cognitive radio network where multiple primary service providers compete with each other to offer spectrum access opportunities to the secondary users. By using an equilibrium pricing scheme, each of the primary service providers aims to maximize its profit under quality of service (QoS) constraint for primary users. We formulate this situation as an oligopoly market consisting of a few firms and a consumer. The QoS degradation of the primary services is considered as the cost in offering spectrum access to the secondary users. For the secondary users, we adopt a utility function to obtain the demand function. With a Bertrand game model, we analyze the impacts of several system parameters such as spectrum substitutability and channel quality on the Nash equilibrium (i.e., equilibrium pricing adopted by the primary services). We present distributed algorithms to obtain the solution for this dynamic game. The stability of the proposed dynamic game algorithms in terms of convergence to the Nash equilibrium is studied. However, the Nash equilibrium is not efficient in the sense that the total profit of the primary service providers is not maximized. An optimal solution to gain the highest total profit can be obtained. A collusion can be established among the primary services so that they gain higher profit than that for the Nash equilibrium. However, since one or more of the primary service providers may deviate from the optimal solution, a punishment mechanism may be applied to the deviating primary service provider. A repeated game among primary service providers is formulated to show that the collusion can be maintained if all of the primary service providers are aware of this punishment mechanism, and therefore, properly weight their profits to be obtained in the future.     

Competitive flow control in general multi-node multi-link communication networks

In this paper, we consider the flow control in a general multi-node multi-link communication network with competing users. Each user has a source node, a destination node, and an existing route for its data flow over any set of links in the network from its source to its destination node. The flow rate for each user is a control variable that is determined by optimizing a user-specific utility function which combines maximizing the flow rate and minimizing the network congestion for that user. A preference parameter in the utility function allows each user to adjust the trade-off between these two objectives. Since all users share the same network resources and are only interested in optimizing their own utility functions, the Nash equilibrium of game theory represents a reasonable solution concept for this multi-user general network. The existence and uniqueness of such an equilibrium is therefore very important for the network to admit an enforceable flow configuration. In this paper, we derive an expression for the Nash equilibrium and prove its uniqueness. We illustrate the results with an example and discuss some properties and observations related to the network performance when in the Nash equilibrium. Copyright © 2007 John Wiley & Sons, Ltd.     

基于博弈论的无线传感网络节点攻防优化

针对无线传感器网络各节点在安全需求与资源消耗上存在的矛盾,提出一种基于博弈论的无线传感网络节点优化博弈模型.首先,通过分析网络节点中攻击方的攻击代价与防守方的防守开销,基于博弈论分析攻防双方的效用函数并构造攻防博弈模型;其次,根据网络节点中攻防双方选择的不同行动策略,结合信息论技术将攻防双方抽象成随机变量,并设计博弈信...     

Competition Versus Cooperation on the MISO Interference Channel

We consider the problem of coordinating two competing multiple-antenna wireless systems (operators) that operate in the same spectral band. We formulate a rate region which is achievable by scalar coding followed by power allocation and beamforming. We show that all interesting points on the Pareto boundary correspond to transmit strategies where both systems use the maximum available power. We then argue that there is a fundamental need for base station cooperation when performing spectrum sharing with multiple transmit antennas. More precisely, we show that if the systems do not cooperate, there is a unique Nash equilibrium which is inefficient in the sense that the achievable rate is bounded by a constant, regardless of the available transmit power. An extension of this result to the case where the receivers use successive interference cancellation (SIC) is also provided. Next we model the problem of agreeing on beamforming vectors as a non-transferable utility (NTU) cooperative gametheoretic problem, with the two operators as players. Specifically we compute numerically the Nash bargaining solution, which is a likely resolution of the resource conflict assuming that the players are rational. Numerical experiments indicate that selfish but cooperating operators may achieve a performance which is close to the maximum-sum-rate bound.     

认知MIMO系统中波束成形和功率的联合控制博弈算法

针对认知MIMO系统中波束成形和功率的联合优化问题,建立了非合作可分离对策联合博弈模型,提出了新的代价函数,根据KT条件证明了该模型中的各个子博弈均存在最优纳什均衡,从而得到联合博弈存在最优纳什均衡的结论,并提出了新的交替迭代算法。仿真结果表明,该算法有较快的收敛速度;同时,在动态环境下,算法也能达到最优纳什均衡,具有较好的稳定性。     

Electricity Consumption Scheduling with Consumers' Comfort and Preference in Smart Grid

A game theory based scheduling method for household electricity consumption in smart grid is proposed in this paper.A non-cooperative game model is employed during the scheduling.All household consumers compete with each other and control their loads to maximize their payoffs.For solving the scheduling problem,we formulate the Utility optimization (UO) model,in which the electricity cost reduction and the improvement of consumers' comfort and preference are considered simultaneously.The System optimization (SO) model only minimizes the electricity cost when scheduling the consumers' electricity consumption.Then we compare and analyze the two models in numerical simulation.The existence and the uniqueness of Nash equilibrium for proposed game model are proved.Simulation results show that the UO model provides an effective scheduling approach to achieve higher comfort and preference and at the same time decrease the energy cost.