Multicast network design game on a ring

DOI10.1007/978-3-319-26626-8_32zbMATH Open1474.91024OpenAlexW2219066727MaRDI QIDQ3467862FDOQ3467862

Authors: Akaki Mamageishvili, Matúš Mihalák 

Publication date: 5 February 2016

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Abstract: In this paper we study quality measures of different solution concepts for the multicast network design game on a ring topology. We recall from the literature a lower bound of 4/3 and prove a matching upper bound for the price of stability, which is the ratio of the social costs of a best Nash equilibrium and of a general optimum. Therefore, we answer an open question posed by Fanelli et al. in [12]. We prove an upper bound of 2 for the ratio of the costs of a potential optimizer and of an optimum, provide a construction of a lower bound, and give a computer-assisted argument that it reaches $2$ for any precision. We then turn our attention to players arriving one by one and playing myopically their best response. We provide matching lower and upper bounds of 2 for the myopic sequential price of anarchy (achieved for a worst-case order of the arrival of the players). We then initiate the study of myopic sequential price of stability and for the multicast game on the ring we construct a lower bound of 4/3, and provide an upper bound of 26/19. To the end, we conjecture and argue that the right answer is 4/3.

Full work available at URL: https://arxiv.org/abs/1507.04222

Recommendations

• Improved bounds on equilibria solutions in the network design game
• The ring design game with fair cost allocation
• On the price of stability of undirected multicast games
• Minimizing Rosenthal potential in multicast games
• The Price of Nash Equilibria in Multicast Transmissions Games

zbMATH Keywords

Nash equilibriumring topologynetwork design gamepotential-optimum price of stability/anarchymyopic sequential price of stability/anarchyprice of stability/anarchy

Mathematics Subject Classification ID

Games involving graphs (91A43)

Cites Work

• The Price of Stability for Network Design with Fair Cost Allocation
• Computing on an anonymous ring
• The curse of simultaneity
• 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
• When ignorance helps: graphical multicast cost sharing games
• Nash equilibria with minimum potential in undirected broadcast games
• Improved lower bounds on the price of stability of undirected network design games
• The ring design game with fair cost allocation
• Call control in rings
• Improving the \(H _{k }\)-bound on the price of stability in undirected Shapley network design games
• On the sequential price of anarchy of isolation games
• An \(H _{n/2}\) upper bound on the price of stability of undirected network design games

Cited In (3)

• The price of anarchy and stability in general noisy best-response dynamics
• Improved bounds on equilibria solutions in the network design game
• The ring design game with fair cost allocation

Uses Software

• CGAL

This page was built for publication: Multicast network design game on a ring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3467862)