2021/08/11 by Gurvich, Vladimir, Naumova, Mariya
#Combinatorics (math.CO) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.05469
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 \cO such that size of g is exponential in size |\cO| of \cO. We assume that game form g = g(\cO) generated by \cO is tight and that an arbitrary \em 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 |\cO|. These assumptions allow us to construct an algorithm computing two (one for each player) lexsafe NE in time polynomial in |\cO|. We consider four types of oracles known in the literature and show that all four satisfy the above assumptions.