TY - JOUR

T1 - Games to induce specified equilibria

AU - Ganchev, Antoniy

AU - Narayanan, Lata

AU - Shende, Sunil

N1 - Funding Information:
I Research supported by NSERC, Canada. A preliminary version appears in the Proceedings of the 2nd International Workshop on Internet & Network Economics∗ Correspondingauthor.Tel.:+15148482424.(WINE2006). E-mail addresses: a_ganche@cs.concordia.ca (A. Ganchev), lata@cs.concordia.ca (L. Narayanan), shende@crab.rutgers.edu (S. Shende).

PY - 2008/12/28

Y1 - 2008/12/28

N2 - Media access protocols in wireless networks require each contending node to wait for a backoff time, chosen randomly from a fixed range, before attempting to transmit on a shared channel. However, nodes acting in their own selfish interest may not follow the protocol. In this paper, a static version of the problem is modeled as a strategic game played by non-cooperating, rational players (the nodes). The objective is to design a game which exhibits a unique, a priori mixed-strategy Nash equilibrium. In the context of the media access problem, the equilibrium of the game would correspond to nodes choosing backoff times randomly from a given range of values, according to the given distribution. We consider natural variations of the problems concerning the number of actions available to the players and show that it is possible to design such a game when there are at least two players that each have the largest number of possible actions among all players. In contrast, we show that if there are exactly two players with different number of actions available to them, then it becomes impossible to design a strategic game with a unique such Nash equilibrium.

AB - Media access protocols in wireless networks require each contending node to wait for a backoff time, chosen randomly from a fixed range, before attempting to transmit on a shared channel. However, nodes acting in their own selfish interest may not follow the protocol. In this paper, a static version of the problem is modeled as a strategic game played by non-cooperating, rational players (the nodes). The objective is to design a game which exhibits a unique, a priori mixed-strategy Nash equilibrium. In the context of the media access problem, the equilibrium of the game would correspond to nodes choosing backoff times randomly from a given range of values, according to the given distribution. We consider natural variations of the problems concerning the number of actions available to the players and show that it is possible to design such a game when there are at least two players that each have the largest number of possible actions among all players. In contrast, we show that if there are exactly two players with different number of actions available to them, then it becomes impossible to design a strategic game with a unique such Nash equilibrium.

UR - http://www.scopus.com/inward/record.url?scp=55949084830&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=55949084830&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2008.06.011

DO - 10.1016/j.tcs.2008.06.011

M3 - Article

AN - SCOPUS:55949084830

VL - 409

SP - 341

EP - 350

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 3

ER -