Learning in Games with Dynamic Population

on YouTube ↗48m

" summary

Analyzes repeated congestion/auction games where a fraction of players randomly leave each round (replacement probability p) and shows learning still yields low social cost if learning uses 1+epsilon multiplicative regret and mild recency discounting. Model assumes worst-case replacements, shows regret scales with number K of major changes, gives guarantees when p is roughly 1/log n (so many repeats per player). Empirical fit uses 5–10% human-like epsilon, and a stable approximate optimum is built (greedy+rounding) with constant-factor loss that makes the bounds robust.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 2:09Large population games: traffic routing
3. 3:59Repeated games
4. 7:08Examples of price of anarchy bounds
5. 7:47Repeated game that is (slowly) changing Lykouris, Syrgkanis, T.
6. 11:01Learning in Repeated Game
7. 13:28No-regret without stability: learning
8. 14:39Outcome of no-regret learning in a fixed game
9. 20:24Quality of Learning Outcome
10. 23:33Proof Technique: Smoothness (Roughgarden'09)
11. 27:06Learning and price of anarchy
12. 29:15Need for adaptive learning
13. 30:11Adapting result to dynamic populations
14. 31:49Change in Optimum Solution
15. 35:54Result (Lykouris, Syrgkanis, T'16)
16. 38:32Stable Optimum in Matching
17. 40:02Stable Solutions
18. 41:45Sample Application