Explore the concept of smoothed complexity in 2-player Nash Equilibria through this 24-minute IEEE conference talk. Delve into topics such as smoothed analysis, algorithmic hardness of approximation, and algorithms for Nash equilibria. Learn about the proof overview, including reduction steps, key facts about Nash equilibria, and analysis techniques. Gain insights from speakers Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, and Aviad Rubinstein as they discuss the intricacies of game theory and computational complexity.
Overview
Syllabus
Intro
Pause and Reflect
Question for today
Big Picture
Smoothed Analysis
Smoothed Algorithmica
Hardness of Approximation
Finding a Nash Equilibrium
Quick work on PPAD
Back to Nash
Algorithms for Nash
Smoothed Nash
Outline
Proof Overview
Reduction Step 1: Padding Alice
Reduction Step 2: Zero-sum noise
Full Reduction
Key facts about Nash equlibria
Large support
Small lz norm
concentration
Recap: Analysis in 3 steps
Conclusion
Taught by
IEEE FOCS: Foundations of Computer Science
