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

08/11/2021
by   Vladimir Gurvich, et al.
0

In 1975 the first author proved that every finite tight two-person game form g is Nash-solvable, that is, for every payoffs u and w of two players the obtained game (g;u,w), in normal form, has a Nash equilibrium (NE) in pure strategies. This result was extended in several directions; here we strengthen it further. We construct two special NE realized by a lexicographically safe (lexsafe) strategy of one player and a best response of the other. 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 such that size of g is exponential in size || of . We assume that game form g = g() generated by is tight and that an arbitrary win-lose game (g;u,w) (in which payoffs u and w are zero-sum and take only values ± 1) can be solved, in time polynomial in ||. These assumptions allow us to construct an algorithm computing two (one for each player) lexsafe NE in time polynomial in ||. We consider four types of oracles known in the literature and show that all four satisfy the above assumptions.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset