Nash-solvable two-person symmetric cycle game forms

摘要

A two-person positional game form 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 of the outcomes. Each non-terminal position j is controlled by one of two players i∈I=1,2. A strategy ~(xi) of a player i∈I involves selecting a move (j,j′) in each position j controlled by i. We restrict both players to their pure positional strategies; in other words, a move (j,j′) in a position j is deterministic (not random) and it can depend only on j (not on preceding positions or moves or on their numbers). For every pair of strategies (x_1,x_2), the selected moves uniquely define a play, that is, a directed path form a given initial position j~0 to an outcome (a directed cycle or terminal vertex). This outcome a∈A is the result of the game corresponding to the chosen strategies, a=a(x_1,x_2). Furthermore, each player i∈I=1,2 has a real-valued utility function u_i over A. Standardly, a game form g is called Nash-solvable if for every u=(u _1,u_2) the obtained game (g,u) has a Nash equilibrium (in pure positional strategies). A digraph (and the corresponding game form) is called symmetric if (j,j′) is its arc whenever (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.