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