Query Complexity of Approximate Equilibria in Anonymous Games

摘要: We study the computation of equilibria two-strategy anonymous games, via algorithms that may proceed a sequence adaptive queries to game's payoff function, assumed be unknown initially. The general topic we consider is query complexity, is, how many are necessary or sufficient compute an exact approximate Nash equilibrium. We show cannot found query-efficient algorithms. also give example 2-strategy, 3-player game does not have any equilibrium in rational numbers. Our main result new randomized algorithm finds $$On^{-1/4}$$-approximate querying $$\tilde{O}n^{3/2}$$ payoffs and runs time $$\tilde{O}n^{3/2}$$. This improves on running pre-existing for first one obtain inverse polynomial approximation poly-time. this can used get efficient PTAS. Furthermore, prove $$\varOmega n \log {n}$$ must queried order find $$\epsilon $$-well-supported equilibrium, even by