Improving the \(H_k\)-bound on the price of stability in undirected Shapley network design games

DOI10.1016/j.tcs.2014.10.037zbMath1303.91056OpenAlexW2027154380MaRDI QIDQ476904

Andreas Emil Feldmann, Max Klimm, Matúš Mihalák, Yann Disser

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.10.037

zbMATH Keywords

price of stabilitypotential-optimal price of anarchypotential-optimal price of stabilityundirected Shapley network design game

Mathematics Subject Classification ID

Games involving graphs (91A43) Applications of game theory (91A80)

Related Items (5)

Further Results on Capacitated Network Design Games ⋮ Unnamed Item ⋮ Improved bounds on equilibria solutions in the network design game ⋮ A Characterization of Undirected Graphs Admitting Optimal Cost Shares ⋮ Efficient Black-Box Reductions for Separable Cost Sharing

Cites Work

• Unnamed Item
• An \(O(\frac{\log n}{\log \log n})\) upper bound on the price of stability for undirected Shapley network design games
• Potential games
• The statistical mechanics of best-response strategy revision
• A class of games possessing pure-strategy Nash equilibria
• Nash Equilibria with Minimum Potential in Undirected Broadcast Games
• Improved Lower Bounds on the Price of Stability of Undirected Network Design Games
• The Price of Stability for Network Design with Fair Cost Allocation
• On the Price of Stability for Undirected Network Design
• On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations

This page was built for publication: Improving the \(H_k\)-bound on the price of stability in undirected Shapley network design games