Timing matters: Online dynamics in broadcast games
Publication
, Other
Chawla, S; Naor, JS; Panigrahi, D; Singh, M; Umboh, SW
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 2018
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.
Duke Scholars
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
Publication Date
January 1, 2018
Volume
11316 LNCS
Start / End Page
80 / 95
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Chawla, S., Naor, J. S., Panigrahi, D., Singh, M., & Umboh, S. W. (2018). Timing matters: Online dynamics in broadcast games. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). https://doi.org/10.1007/978-3-030-04612-5_6
Chawla, S., J. S. Naor, D. Panigrahi, M. Singh, and S. W. Umboh. “Timing matters: Online dynamics in broadcast games.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), January 1, 2018. https://doi.org/10.1007/978-3-030-04612-5_6.
Chawla S, Naor JS, Panigrahi D, Singh M, Umboh SW. Timing matters: Online dynamics in broadcast games. Vol. 11316 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2018. p. 80–95.
Chawla, S., et al. “Timing matters: Online dynamics in broadcast games.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11316 LNCS, 1 Jan. 2018, pp. 80–95. Scopus, doi:10.1007/978-3-030-04612-5_6.
Chawla S, Naor JS, Panigrahi D, Singh M, Umboh SW. Timing matters: Online dynamics in broadcast games. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2018. p. 80–95.
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
Publication Date
January 1, 2018
Volume
11316 LNCS
Start / End Page
80 / 95
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences