Timeline for Simple proof of the existence of Nash equilibria for 2-person games?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S May 6, 2019 at 17:09 | history | edited | Alex M. | CC BY-SA 4.0 |
The link was no longer functioning, so it has been replaced with an archived version
|
| S May 6, 2019 at 17:09 | history | suggested | Victoria M | CC BY-SA 4.0 |
The link was no longer functioning, so it has been replaced with an archived version
|
| May 6, 2019 at 16:48 | review | Suggested edits | |||
| S May 6, 2019 at 17:09 | |||||
| Mar 9, 2013 at 2:07 | comment | added | Rabee Tourky | @John Baes the computational complexity relationship between 2NASH and finding a fixed point has recently been establishment in the literature on PPAD complexity classes. Google PPAD 2-Nash | |
| Mar 8, 2013 at 19:50 | comment | added | John Baez | Thanks, Rabee Tourky! Unfortunately I don't know linear programming, but it's probably at work behind this elementary proof that Nash equilibria exist for finite 2-player zero-sum games: johncarlosbaez.wordpress.com/2013/03/07/game-theory-part-19 This is based on Andrew Colman's 1982 book Game Theory and its Applications in the Social and Biological Sciences. | |
| Mar 8, 2013 at 19:46 | comment | added | John Baez | Thanks, Michael Greinecker! Since Milnor gave 3-page proof of the Brouwer fixed-point theorem using just multivariable calculus and a wee bit of analysis (people.ucsc.edu/~lewis/Math208/hairyball.pdf), I'm not convinced proving it from the existence of Nash equilibria by taking a limit as a finite game converges to an infinite one implies that the existence of Nash equilibria for finite 2-person games is 'just as hard' as the Brouwer fixed-point theorem. There still could be an easy proof for finite games. But still, all this is very interesting! | |
| Feb 19, 2013 at 18:27 | comment | added | Michael Greinecker | @Rabee He explains how to prove the general result from existence for finite games using narrow convergence. That's not really practical for classroom use, but should convince mathematicians. | |
| Feb 14, 2013 at 4:51 | comment | added | Rabee Tourky | @Michael Greinecker the game in that blog site is not a finite game. | |
| Feb 14, 2013 at 4:49 | comment | added | Rabee Tourky | @John Baez existence of a Nash equilibrium for two person finite zero sum games is a linear programming problem. The existence of symmetric equilibrium for a two person finite game with symmetric payoff matrices that are symmetric is a quadratic programming problem. The general case is a general fixed point problem. Recently, two person Nash equilibrium has been shown to be PPAD complete in computational economics. That means you can reduce the problem in polynomial time to Sperner's lemma with $2^n$ many vertices as strategies. | |
| Feb 12, 2013 at 7:50 | comment | added | Michael Greinecker | Here is what seems to amount to a simplified version of the argument that shows how one can prove the Brouwer fixed point theorem from the existence of Nash equilibria in two player games (modulo a limiting compactness argument): theoryclass.wordpress.com/2012/01/05/… | |
| Feb 12, 2013 at 1:13 | comment | added | John Baez | Thanks! There's a lot of nice history in this paper. And I guess you wouldn't say any proof of the existence of a Nash equilibrium for two person finite zero sum games is a proof of Kakutani's fixed point theorem? The trick in this paper seems to involve taking $A$ arbitrary, $B = I$. | |
| Feb 12, 2013 at 0:42 | history | answered | Rabee Tourky | CC BY-SA 3.0 |