Главная
Study mode:
on
1
Intro
2
Pause and Reflect
3
Question for today
4
Big Picture
5
Smoothed Analysis
6
Smoothed Algorithmica
7
Hardness of Approximation
8
Finding a Nash Equilibrium
9
Quick work on PPAD
10
Back to Nash
11
Algorithms for Nash
12
Smoothed Nash
13
Outline
14
Proof Overview
15
Reduction Step 1: Padding Alice
16
Reduction Step 2: Zero-sum noise
17
Full Reduction
18
Key facts about Nash equlibria
19
Large support
20
Small lz norm
21
concentration
22
Recap: Analysis in 3 steps
23
Conclusion
Description:
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.

Smoothed Complexity of 2-player Nash Equilibria

IEEE
Add to list