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

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A tight characterization of strategic games with a unique equilibrium'. Together they form a unique fingerprint.

  • Cite this