BAD'16 Poster

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 two-player normal-form games. Should we understand this to mean that the computational challenge is genuinely hard? In this talk, I explain PPAD, what PPAD-completeness means for equilibrium computation, and possible ways to escape the worst-case hardness. Following the PPAD-completeness 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 polynomial-time approximation scheme. I also discuss recent work suggesting that a quasi-polynomial time algorithm is the best thing we can hope to achieve.


  The University of Bristol   EPSRC