New decision-making paradigms addressing the requirements of flexibility, adaptability and intelligence are needed for future wireless networks. Moreover, mutual interactions should be captured when all the devices are autonomous and smart. Game theory is a powerful tool to study such interactions. However, since it is a branch of applied mathematic and mainly studied in economic, some featured challenges should be addressed when applied in wireless networks. This chapter bridges game theory and practical wireless applications, by focusing on the incomplete, dynamic and uncertain information constraints. Four kinds of distributed learning algorithms including stochastic learning automata, payoff-based log-linear learning, learning by trial and error, and no-regret learning are discussed. The learning procedures and basic theoretical results are presented, and their applications in wireless networks are reviewed. Contrastive analysis on environment dynamics, solution concepts, synchrony, convergence, and convergent results is discussed, and some future research directions are given.
Top1. Introduction And Background
With the explosive increase in wireless transmission demands, traditional static and pre-determined decision approaches can not meet the requirements of flexibility, adaptability and intelligence for the terminals (users). Cognitive radio has established an innovative framework for smart communication systems which adapt to dynamic environment by observing the environment, making intelligent decisions and reconfiguring the hardware (Haykin, 2005; Mitola & Maguire Jr, 1999). With the great success of cognitive radio, autonomous decision-making has been regarded as a promising approach for future wireless communication networks, in which the devices are required to be autonomous and smart. Basically, mutual interaction should be well addressed when all the devices are autonomous and smart. In particular, the interactions may include competition, collision, interference and coordination. Game theory is a powerful tool to study the interactions among multiple autonomous decision-makers and has been extensively applied in wireless communication networks, e.g., power control (Saraydar, Mandayam, & Goodman, 2002), medium access control (Cui, Chen, & Low, 2008), channel assignment (Nie & Comaniciu, 2006), rooting selection (Kannan & Iyengar, 2004) and many other wireless applications. In game-theoretic solutions, equilibria are the desirable and stable outcomes, in which no decision-maker is willing to change its strategy unilaterally.
For game-theoretic solutions, there are three key steps: designing the game model, identifying the existence of equilibria and finding them. Since game theory is a branch of applied mathematic and was mainly studied in the field of economic, some new challenges with regard to information constraints should be addressed when it is applied to wireless communication networks. However, the most existing studies in the literature did not consider the featured information constraints in wireless communication networks, which may not be suitable for practical applications. The purpose of this chapter is to bridge game theory and practical wireless applications, by taking into account the un-neglectable information constraints in wireless communication networks, which are mainly classified into the following three categories:
- ●
Incomplete: a decision-maker only has partial information about the environment; in addition, it only knows the individual information but knows nothing about other users.
- ●
Dynamic: the system states/ variables are time-varying.
- ●
Uncertain: the observations are not equal to the real values, e.g., the observed values are corrupted by noise.
For presentation, we denote the above as IDU information constraints. IDU information constraints are common in wireless communications, some examples are: 1) in a multi-channel access system, a user only has information of a small part of channels rather than that of all channels due to hardware limitation, 2) in a distributed spectrum access system, a user does not know the strategies of other users, 3) in cognitive radio networks, the channel occupation of the primary users are always time-varying, 4) the observations may be corrupted by noise.
Learning is a powerful approach to cope with the above information constraints. Specifically, it is characterized by having the ability to adjust current strategy based on the history information. Therefore, learning and game models can be naturally integrated to provide efficient solutions for practical wireless decision problems.
In this chapter, a comprehensive survey of learning algorithms of equilibria with IDU information constraints is presented. For each kind of learning algorithm, the learning procedure is firstly presented. Then, its properties in terms of convergence and optimality are analyzed, and the existing studies on distributed learning of equilibria in wireless communication networks are surveyed and compared.