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

详细信息    查看全文

• 作者：Endre Boros^a ; ^{boros@rutcor.rutgers.edu} ; Khaled Elbassioni^b ; ^{elbassio@mpi-sb.mpg.de} ; Vladimir Gurvich^a ; ^{gurvich@rutcor.rutgers.edu} ; Kazuhisa Makino^c ; ^{makino@mist.i.u-tokyo.ac.jp}
• 关键词：Chess- and Backgammon-like games ; Nash equilibrium ; Subgame perfect ; Improvement cycle ; Best reply ; Stochastic game ; Perfect information ; Position ; Move ; Random move
• 刊名：Discrete Mathematics
• 出版年：2012
• 出版时间：28 February, 2012
• 年：2012
• 卷：312
• 期：4
• 页码：772-788
• 全文大小：719 K

文摘

We consider -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 , in addition to the standard outcomes formed by the terminal positions. (For example, in the case of Chess or Backgammon and is a draw.) These outcomes are ranked arbitrarily by 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?is ranked as the worst one by all players; (iv) ; (v) and the payoff is zero-sum.