Game Theory for CompetitiveAd-Hoc Communications

May 1, 2009

Many communication systems of interest contain multiple uncoordinated users that share a common medium (e.g., wireless ad-hoc networks). These systems can be mathematically modeled as the so-called interference channel, for which the capacity region is still unknown. In these scenarios, centralized solutions are to be avoided and distributed algorithms play a central role. In fact, in many cases, the right model is to consider selfish users that compete with each other for the resources. Game theory is the right framework to study such competitive networks of users, leading to the concept of Nash equilibrium (NE) as solution of the game. This results in fully distributed algorithms with no signaling required among the users. Within the context of game theory, there are three main aspects to be studied: i) existence of NE, ii) uniqueness of NE, and iii) development of practical distributed algorithms with provable convergence to the NE.
    This problem has been studied since 2001 by different researchers in the frequency-selective case. Among other things, we provide the state-of-the-art conditions for convergence of a class of iterative algorithms that contain as special cases the popular sequential iterative waterfilling algorithms as well as the novel asynchronous iterative waterfilling algorithm (more realistic in practice). We then extend the analysis to the MIMO case which provides a unified view of the problem. As a side result, we provide a novel interpretation of the (MIMO) waterfilling operator as a projection onto a proper convex set (this result is in fact fundamental to prove contraction mapping and convergence of algorithms).

Papers