

Bristol Algorithms Days 2016 Workshop on Efficient Algorithms and Lower Bounds
2  3 February 2016

Approximate Nash equilibrium computation
Paul Goldberg
Nash equilibrium computation is complete for the complexity class PPAD, even for twoplayer normalform games. Should we understand this to mean that the computational challenge is genuinely hard? In this talk, I explain PPAD, what PPADcompleteness means for equilibrium computation, and possible ways to escape the worstcase hardness. Following the PPADcompleteness results, attention turned to the complexity of computing approximate Nash equilibria. In an approximate equilibrium, the usual "no incentive to deviate" requirement is replaced with "bounded incentive to deviate", where a parameter epsilon denotes a limit on any player's incentive to deviate. I review some of the progress that was made, and reasons to hope for a polynomialtime approximation scheme. I also discuss recent work suggesting that a quasipolynomial time algorithm is the best thing we can hope to achieve.
Back
 