Timing Matters: Online Dynamics in Broadcast Games
Conference Paper
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.
Full Text
Duke Authors
Cited Authors
- Chawla, S; Naor, JS; Panigrahi, D; Singh, M; Umboh, SW
Published Date
- May 1, 2021
Published In
Volume / Issue
- 9 / 2
Electronic International Standard Serial Number (EISSN)
- 2167-8383
International Standard Serial Number (ISSN)
- 2167-8375
Digital Object Identifier (DOI)
- 10.1145/3434425
Citation Source
- Scopus