On Nash-solvability in pure stationary strategies of the deterministic n-person games with perfect information and mean or total effective cost

Discrete Applied Mathematics. 2014. Vol. 167. P. 131–143.

Gurvich V., Oudalov V.

We study existence of Nash equilibria (NE) in pure stationary strategies in n$-person\; positional\; games\; with\; no\; moves\; of\; chance,\; with\; perfect\; information,\; and\; with\; the\; mean\; or\; total\; effective\; cost\; function.$

We construct a NE-free three-person game with positive local costs, thus disproving the conjecture suggested in Boros and Gurvich (2003). Still, the following four problems remain open: Whether NE exist in all two-person games with total effective costs such that

(I) all local costs are strictly positive or (II) there are no dicycles of the total cost zero?

Whether NE exist in all n$-person\; games\; with\; the\; terminal\; (transition-free)\; cost\; functions,\; provided\; all\; dicycles\; form\; a\; unique\; outcome$c$and$

(III) assuming that c$is\; worse\; than\; any\; terminal\; outcome$or (IV) without this assumption?

For n=3$the\; case\; (I)\; (and\; hence\; (II))\; is\; answered\; in\; the\; negative.\; This\; is\; the\; main\; result\; of\; the\; present\; paper.\; For$n=2$the\; case\; (IV)\; (and\; hence\; (III))\; was\; answered\; in\; the\; positive\; earlier.$

We briefly survey the above and some other negative and positive results on Nash-solvability in pure stationary strategies for the games under consideration.

Keywords: Nash equilibrium, Stochastic games, Chess-like games