Timing Matters: Online Dynamics in Broadcast Games
summary
Broadcast broadcast-game with Shapley cost sharing can hit worst-case Nash gaps of Θ(n) but best equilibria are constant-factor. This work shows arbitrary interleavings of arrivals/departures and selfish moves can produce poly(n)-bad equilibria, while if every arrival/departure is followed by an algorithmic sequence of improving moves that restores equilibrium the worst-case approximation to the MST is O(log n). Analysis uses a decreasing potential function, multi-scale dual-fitting (disjoint balls) and a charging invariant fixed by targeted improving moves.
AI-written summary · about
chapters (9)
- 0:00Start
- 3:11Broadcast game
- 11:07Price of Stability Or, quality of the best equilibrium
- 25:23Ques: Can "natural" dynamics lead to a good equilibrium?
- 32:20Key ideas for the upper bound
- 34:23Dual fitting basics
- 37:19Avoiding overcharging
- 39:55Invariant on overcharges
- 41:27Summary
related talks
24mAsymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
20mThe Complexity of Infinite-Horizon General-Sum Stochastic Games
31mNear-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
27mComputation Over the Noisy Broadcast Channel with Malicious Parties
31mBroadcast Optimal Multi-Party Computation
58mThe Communication Complexity Landscape of Information-theoretic MPC
30mOptimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
19mDeterministic Dynamic Matching In Worst-Case Update Time