Candidate talk: Computing Nash Equilibria

Опубликовано 6 сентября 2016, 16:57

In view of the recent hardness results for mixed Nash equilibria, there has been increased interest in computing approximate equilibrium points, albeit progress has been slow. We will overview the hardness results and present recent developments on the subject, in particular, algorithms which achieve constant factor approximations for 2-player games, and a quasi-polynomial time approximation scheme for the multi-player setting. Next, we will consider a very natural and important class of games, the anonymous games, in which, like in certain auction settings, a player is oblivious to the identities of the other players. These games or variants are often appealing models for games of many players even so because the description size that they require is polynomial in the number of players -as opposed to exponential that a game in standard form would require. We will present a polynomial time approximation scheme for the anonymous setting and surprising connections with Stein's method in probability theory.