On Nash-solvability of finite n-person deterministic graphical games; Catch 22
share
We consider finite n-person deterministic graphical (DG) games. These games are modelled by finite directed graphs (digraphs) G which may have directed cycles and, hence, infinite plays. Yet, it is assumed that all these plays are equivalent and form a single outcome c, while the terminal vertices V_T = {a_1, …, a_p} form p remaining outcomes. We study the existence of Nash equilibria (NE) in pure stationary strategies. It is known that NE exist when n=2 and may fail to exist when n > 2. Yet, the question becomes open for n > 2 under the following extra condition: (C) For each of n players, c is worse than each of p terminal outcomes. In other words, all players are interested in terminating the play, which is a natural assumption. Moreover, Nash-solvability remains open even if we replace (C) by a weaker condition: (C22) There exist no two players for whom c is better than (at least) two terminal outcomes. We conjecture that such two players exist in each NE-free DG game, or in other words, that (C22) implies Nash-solvability, for all n. Recently, the DG games were extended to a wider class of the DG multi-stage (DGMS) games, whose outcomes are the strongly connected components (SCC) of digraph G. Merging all outcomes of a DGMS game that correspond to its non-terminal SCCs we obtain a DG game. Clearly, this operation respects Nash-solvability (NS). Basic conditions and conjectures related to NS can be extended from the DG to DGMS games: in both cases NE exist if n=2 and may fail to exist when n > 2; furthermore, we modify conditions (C) and (C22) to adapt them for the DGMS games. Keywords: n-person deterministic graphical (multi-stage) games, Nash equilibrium, Nash-solvability, pure stationary strategy, digraph, directed cycle, strongly connected component.
READ FULL TEXT