On Nash equilibria and improvement cycles in pure positional strategies for Chess-like and Backgammon-like n-person games

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

We consider n-person positional games with perfect information modeled by finite directed graphs that may have directed cycles, assuming that all infinite plays form a single outcome c, in addition to the standard outcomes a 1,⋯,a m formed by the terminal positions. (For example, in the case of Chess or Backgammon n=2 and c is a draw.) These m+1 outcomes are ranked arbitrarily by n players. We study existence of (subgame perfect) Nash equilibria and improvement cycles in pure positional strategies and provide a systematic case analysis assuming one of the following conditions: (i) there are no random positions; (ii) there are no directed cycles; (iii) the ïnfinite outcome" c is ranked as the worst one by all n players; (iv) n=2; (v) n=2 and the payoff is zero-sum.

Original languageEnglish (US)
Pages (from-to)772-788
Number of pages17
JournalDiscrete Mathematics
Volume312
Issue number4
DOIs
StatePublished - Feb 28 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Best reply
  • Chess- and Backgammon-like games
  • Improvement cycle
  • Move
  • Nash equilibrium
  • Perfect information
  • Position
  • Random move
  • Stochastic game
  • Subgame perfect

Fingerprint

Dive into the research topics of 'On Nash equilibria and improvement cycles in pure positional strategies for Chess-like and Backgammon-like n-person games'. Together they form a unique fingerprint.

Cite this