Nash-solvable two-person symmetric cycle game forms

A two-person positional game form gg (with perfect information and without moves of chance) is modeled by a finite directed graph (digraph) whose vertices and arcs are interpreted as positions and moves, respectively. All simple directed cycles of this digraph together with its terminal positions form the set AA of the outcomes. Each non-terminal position jj is controlled by one of two players i∈I={1,2}i∈I={1,2}. A strategy xixi of a player i∈Ii∈I involves selecting a move (j,j′)(j,j′) in each position jj controlled by ii. We restrict both players to their pure positional strategies; in other words, a move (j,j′)(j,j′) in a position jj is deterministic (not random) and it can depend only on jj (not on preceding positions or moves or on their numbers). For every pair of strategies (x1,x2)(x1,x2), the selected moves uniquely define a play, that is, a directed path form a given initial position j0j0 to an outcome (a directed cycle or terminal vertex). This outcome a∈Aa∈A is the result of the game corresponding to the chosen strategies, a=a(x1,x2)a=a(x1,x2). Furthermore, each player i∈I={1,2}i∈I={1,2} has a real-valued utility function uiui over AA. Standardly, a game form gg is called Nash-solvable if for every u=(u1,u2)u=(u1,u2) the obtained game (g,u)(g,u) has a Nash equilibrium (in pure positional strategies).A digraph (and the corresponding game form) is called symmetric if (j,j′)(j,j′) is its arc whenever (j′,j)(j′,j) is. In this paper we obtain necessary and sufficient conditions for Nash-solvability of symmetric cycle two-person game forms and show that these conditions can be verified in linear time in the size of the digraph.

► Game forms are modeled by directed graphs whose directed cycles are treated as the outcomes. ► We study Nash-solvability, i.e., existence of a Nash equilibrium for any payoff. ► We restrict ourselves by two-person game forms and symmetric graphs. ► In the considered case we obtain necessary and sufficient conditions of Nash-solvability.