Potential games are a subclass of noncooperative games that bear some special properties and are often exploited in wireless network designs. In this chapter, we first introduce the concept of potential games and give definitions of different types of potential games. Then, we provide some important results and properties of potential games. After that, we introduce three algorithms to achieve Nash equilibrium of a potential game. Next, this chapter will show how to apply potential game theory to design efficient algorithms for wireless network optimization. One application of potential game theory is to study the power control problem in wireless networks. Another example is the multimode precoding design in multi-input multi-output multiple access channels. We also show how to apply potential games for joint resource allocation in a relay network where multiple users can conduct bidirectional communications through a relay node over multiple available channels.
TopIntroduction
Noncooperative game theory constitutes a powerful framework for analyzing conflicts among interacting decision-makers, usually called players, each of whom wishes to maximize his own payoff (Monderer & Shapley, 1996a; Myerson, 1991; MacKenzie & DaSilva, 2007; Hossain, Niyato, & Han, 2009; Saraydar, Mandayam, & Goodman, 2002). Such a framework has been widely applied to designing wireless networks, where users compete limited resources and meanwhile generate interference to each other. By formulating a network design as a noncooperative game, one can devise proper algorithms to achieve the solution of the game, i.e., the Nash equilibrium, at which no player wishes to unilaterally change his strategy. However, the overall network performance may not be improved at a Nash equilibrium due to selfish behaviors of players.
Potential games (Monderer & Shapley, 1996a) are a subclass of noncooperative games with nice properties that can lead to an enhancement of global performance at the equilibrium point. Particularly, in potential games, the incentive of all players to change their strategies can be expressed in a single global function, called potential function. That is, players in a potential game can serve the greater good by furthering their own interests. Consequently, each user’s selfish optimization would contribute to optimizing the potential function, thus improving the global system performance, which is particularly important from a whole network perspective.
In light of global optimality improvement, potential games have received great attention and have been introduced to transmission designs in, for example, multiple access or interference channels. When using potential games in wireless networks, an important issue is to devise distributed algorithms, using local information and processing abilities, to reach a Nash equilibrium of the potential game. The property of potential game can guarantee the convergence of local search algorithms, of which two algorithms, namely, best response dynamic and better response dynamic, are most commonly used. Combined with appropriate learning mechanisms, these local search algorithms can achieve globally optimal or nearly globally optimal performance.
Potential games has been used to study the wireless networks in many previous works. For examples, the authors proposed a game theoretic framework for the power control problem in wireless networks based on potential game in the work of Scutari, Barbarossa, & Palomar, (2006). The work of Ai, Srinivasan, & Tham, (2008) applied potential game theory to study the coverage game in wireless sensor networks. The work of Menon, MacKenzie, Buehrer, & Reed, (2009) established a potential game theoretic framework for the interference avoidance in wireless communication systems. Xu, Wang, Wu, Anpalagan, & Yao, (2012) used potential game theory to study the opportunistic spectrum access in cognitive radio networks. Zhong, Chen, Jin, & Wong, (2014) formulated the relay selection and discrete power control problem for cognitive relay systems as a potential game and analyze the price of anarchy of the proposed game. Uykan & Jantti, (2014). analyzed the transmission order (TO) optimization problem 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. Among existing works, one important application of potential game theory is to design proper resource allocation strategies for wireless networks.
In this chapter, we will introduce the concept and definition of potential game, important properties of potential game, and algorithms to achieve Nash equilibrium of potential game. Then, we would use three examples to show applications of potential game theory in wireless networks. The first one is the application of potential games to a power control problem (Scutari, Barbarossa, & Palomar, 2006), the second one is the multimode precoding design in multi-input multi-output (MIMO) multiple access channels (Zhong, Xu, Tao, & Cai, 2010), and the third one is the joint resource management for multi-channel dual-mode relay networks.