Stability and Learning in Repeated Games

Explore the complexities of stability and learning in repeated games through this Richard M. Karp Distinguished Lecture delivered by Éva Tardos from Cornell University. Delve into the research community's understanding of strategic user behavior's impact on outcomes in games like traffic routing and online auctions. Examine how these findings extend to repeated games when players employ no-regret learning. Investigate the limitations of these results, particularly in packet routing and online auctions where game states evolve based on previous outcomes. Learn about the stability guarantees in simple routing games with increased server capacity and the potential shortcomings of no-regret learning in such environments. Gain insights into network-flow algorithms, selfish routing efficiency, and the interface between algorithms and incentives from a renowned expert in the field.

Intro
Example 1: traffic routing
No-regret without stability: learning (Hannan consistency)
No-regret learning as a behavioral model?
Quality of Learning Outcomes: Price Anarchy No-regret as a behavioral assumption
Social Welfare of Learning Outcomes
Large population games: traffic routing
No-regret as a model of learning?
Simple Model of Queuing
Selfish Queuing: Price of Anarchy
Theorem 1 Proof Idea (using no regret)
Extra Technical Details
Price of Anarchy: Proof Sketch