Smoothed Complexity of 2-player Nash Equilibria

Smoothed Complexity of 2-player Nash Equilibria

IEEE FOCS: Foundations of Computer Science via YouTube Direct link

Intro

1 of 23

1 of 23

Intro

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

Smoothed Complexity of 2-player Nash Equilibria

Automatically move to the next video in the Classroom when playback concludes

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

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.