Potential games and competitive scheduling in wireless networks

This thesis studies a game theoretic model for scheduling transmissions among multiple self-interested users in a wireless network with fading. Our model involves a finite number of mobile users transmitting to a common base station under time-varying channel conditions. A distinguishing feature of our model is the assumption that the channel quality of each user is affected by global and time-varying conditions at the base station, resulting in each user observing a common channel state. Each user chooses a transmission policy that maximizes its utility function, which captures a natural trade-off between throughput and power. The transmission policy specifies how transmissions should be scheduled as a function of the time-varying common channel state observed by each user. We make three main contributions. First, we establish the existence of a Nash equilibrium of this game and characterize the set of equilibria. We investigate the efficiency properties of these equilibria, and study a related aggregate utility maximization problem, to serve as a benchmark for the performance of the equilibria. We quantify the efficiency loss in the game comparing the optimal solution of the aggregate utility maximization problem, to the best and worst equilibria in terms of the aggregate utility. We show that the performance of the worst equilibrium can be arbitrarily bad (in terms of the aggregate utility), but the efficiency loss of the best equilibrium can be bounded as a function of a technology-related parameter. Our second contribution is to study various distributed mechanisms to reach an equilibrium of this game.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2009

Author dc:creator

• Candogan, Utku Ozan

Advisor dc:contributor.advisor

• Asŭman Ozdaglar̀ and Pablo Parrilo.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/53206

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/53206