2021/11/11 by Vladimir Gurvich, Gurvich, Vladimir
Decision Sciences · Economics, Econometrics and Finance · #91A05 #91A06 #91A18 #Combinatorics (math.CO) #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2111.06278
openalex publication_date 2021/11/11 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
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 VT = \a1, …, ap\ 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.