Computing a Nash equilibrium is a hard problem (PPAD-complete, shown by Daskalakis, Goldberg and Papadimitriou in 2006): it is not NP-complete because a solution always exists by Nash's theorem, but it is at least as hard as any problem whose solution is guaranteed to exist; unwinding Nash's Kakutani fixed-point existence proof yields an algorithm that may follow an exponentially long trail before reaching the equilibrium.
factualpending
Speaker
Scott AaronsonEvidence Quote
“if you try to actually unwind the existence proof into an actual algorithm to calculate the equilibrium then what you get is an algorithm that ends up taking exponential points”
Created: 6/13/2026, 7:00:25 PM
Your notes
Loading notes...