## 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 language | English (US) |
---|---|

Pages (from-to) | 772-788 |

Number of pages | 17 |

Journal | Discrete Mathematics |

Volume | 312 |

Issue number | 4 |

DOIs | |

State | Published - 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