Computer Science – Computer Science and Game Theory
Scientific paper
2011-03-14
Computer Science
Computer Science and Game Theory
32 pages, 10 figures, 23rd British Combinatorial Conference
Scientific paper
PPAD refers to a class of computational problems for which solutions are guaranteed to exist due to a specific combinatorial principle. The most well-known such problem is that of computing a Nash equilibrium of a game. Other examples include the search for market equilibria, and envy-free allocations in the context of cake-cutting. A problem is said to be complete for PPAD if it belongs to PPAD and can be shown to constitute one of the hardest computational challenges within that class. In this paper, I give a relatively informal overview of the proofs used in the PPAD-completeness results. The focus is on the mixed Nash equilibria guaranteed to exist by Nash's theorem. I also give an overview of some recent work that uses these ideas to show PSPACE-completeness for the computation of specific equilibria found by homotopy methods. I give a brief introduction to related problems of searching for market equilibria.
No associations
LandOfFree
A Survey of PPAD-Completeness for Computing Nash Equilibria 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 Survey of PPAD-Completeness for Computing Nash Equilibria, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Survey of PPAD-Completeness for Computing Nash Equilibria will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-259874