Nash-solvable two-person symmetric cycle game forms
A two-person positional game form g g (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 A A of the outcomes. Each non-terminal position j j is controlled by one of two players i?I={1,2} i ? I = { 1 , 2 } . A strategy xi x i of a player i?I i ? I involves selecting a move (j,j?) ( j , j ? ) in each position j j controlled by i i . We restrict both players to their pure positional strategies; in other words, a move (j,j?) ( j , j ? ) in a position j j is deterministic (not random) and it can depend only on j j (not on preceding positions or moves or on their numbers). For every pair of strategies (x1,x2) ( x 1 , x 2 ) , the selected moves uniquely define a play, that is, a directed path form a given initial position j0 j 0 to an outcome (a directed cycle or terminal vertex). This outcome a?A a ? A is the result of the game corresponding to the chosen strategies, a=a(x1,x2) a = a ( x 1 , x 2 ) . Furthermore, each player i?I={1,2} i ? I = { 1 , 2 } has a real-valued utility function ui u i over A A . Standardly, a game form g g is called Nash-solvable if for every u=(u1,u2) u = ( u 1 , u 2 ) 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.
cycle game game form positional game nash equilibrium tight game form nash-solvable game form game in normal form mean-payoff game