Explore the communication complexity of Nash equilibrium in potential games through this 27-minute IEEE conference talk. Delve into the intricacies of congestion games and potential games as presenters Yakov Babichenko and Aviad Rubinstein discuss known concepts, challenges in proving hardness, and recent advancements in the field. Gain insights into the proof structure, including potential limitation games, classical proof structures, and control embedding techniques. Enhance your understanding of game theory and computational complexity in this informative presentation.
Communication Complexity of Nash Equilibrium in Potential Games
Overview
Syllabus
Introduction
Potential games
Congestion games
What is known
Talk
Why proving hardness
Results
Result
Proof structure
Potential limitation game
Classical proof structure
Control embedding
Recent progress
Taught by
IEEE FOCS: Foundations of Computer Science
