Timing matters: Online dynamics in broadcast games

Other Article

This paper 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 in order 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, 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

  • January 1, 2018

Published In

Volume / Issue

  • 11316 LNCS /

Start / End Page

  • 80 - 95

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783030046118

Digital Object Identifier (DOI)

  • 10.1007/978-3-030-04612-5_6

Citation Source

  • Scopus