DIMACS TR: 2008-13

Nash-solvable bidirected cyclic two-person game forms



Authors: Endre Boros, Vladimir Gurvich, Kazuhisa Makino and Wei Shao

ABSTRACT

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: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2008/2008-13.pdf
DIMACS Home Page