Improved lower bounds on the price of stability of undirected network design games

DOI10.1007/s00224-012-9411-6zbMath1273.90168OpenAlexW1992071237MaRDI QIDQ2392248

Ioannis Caragiannis, Gianpiero Monaco, Vittorio Bilò, Angelo Fanelli

Publication date: 1 August 2013

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-012-9411-6

Mathematics Subject Classification ID

Applications of graph theory (05C90) Network design and communication in computer systems (68M10) Applications of game theory (91A80) Combinatorial optimization (90C27)

Related Items (14)

Multicast Network Design Game on a Ring ⋮ On the Price of Stability of Undirected Multicast Games ⋮ Unnamed Item ⋮ The price of stability for undirected broadcast network design with fair cost allocation is constant ⋮ The ring design game with fair cost allocation ⋮ Designing cost-sharing methods for Bayesian games ⋮ Improved bounds on equilibria solutions in the network design game ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ A Characterization of Undirected Graphs Admitting Optimal Cost Shares ⋮ The Price of Stability of Weighted Congestion Games ⋮ The Price of Stability of Weighted Congestion Games ⋮ Enforcing efficient equilibria in network design games via subsidies ⋮ A unifying approximate potential for weighted congestion games ⋮ On the sequential price of anarchy of isolation games

Cites Work

• Unnamed Item
• Network design with weighted players
• An \(O(\frac{\log n}{\log \log n})\) upper bound on the price of stability for undirected Shapley network design games
• A class of games possessing pure-strategy Nash equilibria
• The Price of Stability for Network Design with Fair Cost Allocation
• On the Price of Stability for Undirected Network Design
• Tight Bounds for Selfish and Greedy Load Balancing
• On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
• On the Value of Coordination in Network Design
• Algorithms, games, and the internet
• Algorithms – ESA 2005

This page was built for publication: Improved lower bounds on the price of stability of undirected network design games