DIMACS TR: 2008-13
Nash-solvable bidirected cyclic two-person game forms
Authors: Endre Boros, Vladimir Gurvich, Kazuhisa Makino and Wei Shao
We consider cyclic positional games of two players. Let G=(V,E) be a directed graph (digraph) and P: V = V1 U V2 U Vt be a partition of its vertices (positions) in three subsets: V1 and V2 are positions of players 1 and 2, respectively, and Vt are the terminal positions. Directed edges going from a position j in V1 (respectively, j in V2) are called the moves of player 1 (respectively, 2).
Furthermore, j in Vt if and only if the out-degree of j is 0. Given a digraph G = (V,E), a partition
P : V = V1 U V2 U Vt, and also an initial position j0 in V1 U V2, the triplet (G, P, j0) is called a positional cyclic game form.
Name "cyclic" is motivated as follows.
A mapping x1 (respectively, x2) that assigns a move (j,j') to each position j in V1 (respectively, j in V2) is called a (positional) strategy of player 1 (respectively, 2).
Each pair of strategies x = (x1, x2) uniquely defines a play, that is, a directed path
that begins in the initial position j0 and either ends in a terminal position j in Vt
or results in a simple directed cycle (dicycle) c in C = C(G).
The obtained mapping g = g(G,P,j0): X1 * X2 --> Vt U C is called the normal cyclic game form
corresponding to (G,P,j0).
Utility functions of players 1 and 2 are defined by two arbitrary mappings:
u1 : Vt U C --> R and u2 : Vt U C --> R.
A game form g = g(G,P,j0) is called Nash-solvable if for every utility functions u = (u1, u2)
the obtained normal form game (g,u) has at least one Nash equilibrium in pure strategies.
In this paper we characterize Nash-solvable cyclic game forms g(G,P,j0) whose digraphs
are bidirected, that is, (j,j') in E if and only if (j',j) in E.
We derive this characterization from an old general criterion:
a two-person game form g is Nash-solvable if and only if it is tight.
Paper Available at:
DIMACS Home Page