Timing Matters: Online Dynamics in Broadcast Games

摘要

This article studies the equilibrium states that can be reached in a network design game via natural game dynamics. First, we show that an arbitrarily interleaved sequence of arrivals and departures of players can lead to a polynomially inefficient solution at equilibrium. This implies that the central controller must have some control over the timing of agent arrivals and departures to ensure efficiency of the system at equilibrium. Indeed,we give a complementary result showing that if the central controller is allowed to restore equilibrium after every set of arrivals/departures via improving moves, then the eventual equilibrium states reached have exponentially better efficiency.