A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium

Details A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium

2010-07-22

arxiv.org/abs/1007.3886v1

Computer Science

Computer Science and Game Theory

21 pages

Scientific paper

We present a direct reduction from k-player games to 2-player games that preserves approximate Nash equilibrium. Previously, the computational equivalence of computing approximate Nash equilibrium in k-player and 2-player games was established via an indirect reduction. This included a sequence of works defining the complexity class PPAD, identifying complete problems for this class, showing that computing approximate Nash equilibrium for k-player games is in PPAD, and reducing a PPAD-complete problem to computing approximate Nash equilibrium for 2-player games. Our direct reduction makes no use of the concept of PPAD, thus eliminating some of the difficulties involved in following the known indirect reduction.

Affiliated with

Also associated with

No associations

Rating

A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium 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 A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-612521