A tight characterization of strategic games with a unique equilibrium

Antoniy Ganchev, Lata Narayanan, Sunil Shende

Research output: Contribution to journalArticle

Abstract

We consider the problem of designing a strategic game (i.e. the utilities) for a set of players where distinct players may have sets of actions with possibly different cardinalities. Furthermore, for each player, a full-support probability distribution on its action set is apriori specified. The goal is to ensure that this pre-specified profile of distributions is the unique Nash equilibrium for the game. One motivation for our problem comes from exponential backoff shared-media access protocols in wireless networks: a static version of protocol compliance can be modeled as an instance of the problem. Building on results from an earlier paper, we provide a tight characterization of the conditions under which such a strategic game may be constructed. Our results not only establish the exact relationship that must hold between the cardinalities of the players' action sets but also provide the players' utilities for the desired unique equilibrium to be achieved.

Original languageEnglish (US)
Pages (from-to)37-50
Number of pages14
JournalTheoretical Computer Science
Volume481
DOIs
StatePublished - Apr 15 2013

Fingerprint

Game
Network protocols
Probability distributions
Cardinality
Wireless networks
Nash Equilibrium
Compliance
Wireless Networks
Probability Distribution
Distinct
Relationships
Profile

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

@article{1c649a938ba442b0bf0a7e5547c7e8ce,
title = "A tight characterization of strategic games with a unique equilibrium",
abstract = "We consider the problem of designing a strategic game (i.e. the utilities) for a set of players where distinct players may have sets of actions with possibly different cardinalities. Furthermore, for each player, a full-support probability distribution on its action set is apriori specified. The goal is to ensure that this pre-specified profile of distributions is the unique Nash equilibrium for the game. One motivation for our problem comes from exponential backoff shared-media access protocols in wireless networks: a static version of protocol compliance can be modeled as an instance of the problem. Building on results from an earlier paper, we provide a tight characterization of the conditions under which such a strategic game may be constructed. Our results not only establish the exact relationship that must hold between the cardinalities of the players' action sets but also provide the players' utilities for the desired unique equilibrium to be achieved.",
author = "Antoniy Ganchev and Lata Narayanan and Sunil Shende",
year = "2013",
month = "4",
day = "15",
doi = "10.1016/j.tcs.2013.02.008",
language = "English (US)",
volume = "481",
pages = "37--50",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

A tight characterization of strategic games with a unique equilibrium. / Ganchev, Antoniy; Narayanan, Lata; Shende, Sunil.

In: Theoretical Computer Science, Vol. 481, 15.04.2013, p. 37-50.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A tight characterization of strategic games with a unique equilibrium

AU - Ganchev, Antoniy

AU - Narayanan, Lata

AU - Shende, Sunil

PY - 2013/4/15

Y1 - 2013/4/15

N2 - We consider the problem of designing a strategic game (i.e. the utilities) for a set of players where distinct players may have sets of actions with possibly different cardinalities. Furthermore, for each player, a full-support probability distribution on its action set is apriori specified. The goal is to ensure that this pre-specified profile of distributions is the unique Nash equilibrium for the game. One motivation for our problem comes from exponential backoff shared-media access protocols in wireless networks: a static version of protocol compliance can be modeled as an instance of the problem. Building on results from an earlier paper, we provide a tight characterization of the conditions under which such a strategic game may be constructed. Our results not only establish the exact relationship that must hold between the cardinalities of the players' action sets but also provide the players' utilities for the desired unique equilibrium to be achieved.

AB - We consider the problem of designing a strategic game (i.e. the utilities) for a set of players where distinct players may have sets of actions with possibly different cardinalities. Furthermore, for each player, a full-support probability distribution on its action set is apriori specified. The goal is to ensure that this pre-specified profile of distributions is the unique Nash equilibrium for the game. One motivation for our problem comes from exponential backoff shared-media access protocols in wireless networks: a static version of protocol compliance can be modeled as an instance of the problem. Building on results from an earlier paper, we provide a tight characterization of the conditions under which such a strategic game may be constructed. Our results not only establish the exact relationship that must hold between the cardinalities of the players' action sets but also provide the players' utilities for the desired unique equilibrium to be achieved.

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

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

U2 - 10.1016/j.tcs.2013.02.008

DO - 10.1016/j.tcs.2013.02.008

M3 - Article

AN - SCOPUS:84875828833

VL - 481

SP - 37

EP - 50

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -