On Nash-solvability of chess-like games

In 2003, Boros and Gurvich proved that a chess-likes game has a Nash equilibrium (NE) in pure stationary strategies if (A) the number n of players is at most 2, or (B) the number p of terminals is at most 2 and (C) any infinite play is worse than each terminal for every player. In the talk we strengthen the bound in (B) replacing p <= 2 by p <= 3, provided (C) still holds. On the other hand, we construct an NE-free four-person chess-like game with five terminals, which has a unique cycle, but does not satisfy (C). It remains open whether an NE-free example exists for n = 3, or for 2 < p < 4, or for some n > 3 and p > 4 provided (C) holds.

Joint work with E. Boros, V. Oudalov, and R. Rand.

http://rutcor.rutgers.edu/pub/rrr/reports2014/09_2014.pdf

http://arxiv.org/pdf/1411.0349.pdf