Smoothed Complexity of 2-player Nash Equilibria
Offered By: IEEE via YouTube
Course Description
Overview
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.
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
Tags
Related Courses
Automata TheoryStanford University via edX Introduction to Computational Thinking and Data Science
Massachusetts Institute of Technology via edX 算法设计与分析 Design and Analysis of Algorithms
Peking University via Coursera How to Win Coding Competitions: Secrets of Champions
ITMO University via edX Introdução à Ciência da Computação com Python Parte 2
Universidade de São Paulo via Coursera