Timing matters: online dynamics in broadcast games
From MaRDI portal
Publication:2190382
DOI10.1007/978-3-030-04612-5_6zbMATH Open1443.91072arXiv1611.07745OpenAlexW3161990778MaRDI QIDQ2190382FDOQ2190382
Authors: Shuchi Chawla, Joseph (Seffi) Naor, Debmalya Panigrahi, Mohit Singh, Seeun William Umboh 
Publication date: 18 June 2020
Abstract: A central question in algorithmic game theory is to measure the inefficiency (ratio of costs) of Nash equilibria (NE) with respect to socially optimal solutions. The two established metrics used for this purpose are price of anarchy (POA) and price of stability (POS), which respectively provide upper and lower bounds on this ratio. A deficiency of these metrics, however, is that they are purely existential and shed no light on which of the equilibrium states are reachable in an actual game, i.e., via natural game dynamics. This is particularly striking if these metrics differ significantly, such as in network design games where the exponential gap between the best and worst NE states originally prompted the notion of POS in game theory (Anshelevich et al., FOCS 2002). In this paper, we make progress toward bridging this gap by studying network design games under natural game dynamics. First we show that in a completely decentralized setting, where agents arrive, depart, and make improving moves in an arbitrary order, the inefficiency of NE attained can be polynomially large. This implies that the game designer must have some control over the interleaving of these events in order to force the game to attain efficient NE. We complement our negative result by showing that if the game designer is allowed to execute a sequence of improving moves to create an equilibrium state after every batch of agent arrivals or departures, then the resulting equilibrium states attained by the game are exponentially more efficient, i.e., the ratio of costs compared to the optimum is only logarithmic. Overall, our two results establish that in network games, the efficiency of equilibrium states is dictated by whether agents are allowed to join or leave the game in arbitrary states, an observation that might be useful in analyzing the dynamics of other classes of games with divergent POS and POA bounds.
Full work available at URL: https://arxiv.org/abs/1611.07745
Recommendations
Cites Work
- A class of games possessing pure-strategy Nash equilibria
- Potential games
- The Price of Stability for Network Design with Fair Cost Allocation
- A Shapley value representation of potential games
- On the existence of pure Nash equilibria in weighted congestion games
- Congestion games with player-specific payoff functions
- The complexity of pure Nash equilibria
- Dynamic Steiner Tree Problem
- On the value of coordination in network design
- Network design with weighted players
- Circumventing the price of anarchy: leading dynamics to good behavior
- A general approach to online network optimization problems
- Strong equilibrium in congestion games
- On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
- An \(O(\frac{\log n}{\log \log n})\) upper bound on the price of stability for undirected Shapley network design games
- On the price of stability for undirected network design
- Nash equilibria with minimum potential in undirected broadcast games
- Title not available (Why is that?)
- Online node-weighted Steiner tree and related problems
- The ring design game with fair cost allocation
- On-line generalized Steiner problem
- Exact price of anarchy for polynomial congestion games
- Online constrained forest and prize-collecting network design
- Near-optimal online algorithms for prize-collecting Steiner problems
- Online Node-weighted Steiner Forest and Extensions via Disk Paintings
- On the price of stability of undirected multicast games
- LAST but not least: online spanners for buy-at-bulk
- Timing matters: online dynamics in broadcast games
- Computing equilibria for a service provider game with (Im)perfect information
- Online Buy-at-Bulk Network Design
Cited In (2)
This page was built for publication: Timing matters: online dynamics in broadcast games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2190382)
