• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

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.