Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles

Discrete Applied Mathematics. 2023. Vol. 340. P. 53–68.

Gurvich V., Naumova M.

In 1975 the first author proved that every finite tight two-person game form g is Nashsolvable,
that is, for every payoffs u and w of two players the obtained normal form game
(g; u,w) has a Nash equilibrium (NE) in pure strategies. Several proofs of this theorem
were obtained later. Here we strengthen the result and give a new proof, which is shorter
than previous ones. We show that game (g; u,w) has two types of NE, realized by a
lexicographically safe (lexsafe) strategy of one player and some special best response of
the other. The proof is constructive, we obtain a polynomial algorithm computing these
lexsafe NE. This is trivial when game form g is given explicitly. Yet, in applications g is
frequently realized by an oracle O such that size of g is exponential in the size |O| of
O. We assume that game form g = g(O) generated by O is tight and that an arbitrary
±1 game (g; u0,w0) (in which payoffs u0 and w0 are zero-sum and take only values ±1)
can be solved in time polynomial in |O|. These assumptions allow us to compute two
(one for each player) lexsafe NE in time polynomial in |O|. These NE may coincide. We
consider four types of oracles known in the literature and show that all four satisfy the
above assumptions.

Keywords: Nash equilibrium, Game form, Nash-solvability, Tightness, game in normal and in positional form, Deterministic graphical game structure, Monotone bargaining, Veto voting, Jordan game

Publication based on the results of: Mathematical methods inthe studies of definitional complexity, computational complexity and formal language (2023)