Computing Nash Equilibria: Approximation and Smoothed Complexity

Details Computing Nash Equilibria: Approximation and Smoothed Complexity Computing Nash Equilibria: Approximation and Smoothed Complexity

2006-02-11

arxiv.org/abs/cs/0602043v2

Computer Science

Computational Complexity

Scientific paper

We show that the BIMATRIX game does not have a fully polynomial-time approximation scheme, unless PPAD is in P. In other words, no algorithm with time polynomial in n and 1/\epsilon can compute an \epsilon-approximate Nash equilibrium of an n by nbimatrix game, unless PPAD is in P. Instrumental to our proof, we introduce a new discrete fixed-point problem on a high-dimensional cube with a constant side-length, such as on an n-dimensional cube with side-length 7, and show that they are PPAD-complete. Furthermore, we prove, unless PPAD is in RP, that the smoothed complexity of the Lemke-Howson algorithm or any algorithm for computing a Nash equilibrium of a bimatrix game is polynomial in n and 1/\sigma under perturbations with magnitude \sigma. Our result answers a major open question in the smoothed analysis of algorithms and the approximation of Nash equilibria.

Affiliated with

Also associated with

No associations

Rating

Computing Nash Equilibria: Approximation and Smoothed Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing Nash Equilibria: Approximation and Smoothed Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Nash Equilibria: Approximation and Smoothed Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-211038