Candidate talk: Computing Nash Equilibria

121 views · Published 6 September 2016 · 1:18:56 · Indexed 27 October 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

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.

More from this channel