Improved bounds on equilibria solutions in the network design game

DOI10.1007/s00182-017-0600-zzbMath1418.91101OpenAlexW2768332442MaRDI QIDQ1757081

Simone Montemezzani, Akaki Mamageishvili, Matúš Mihalák

Publication date: 28 December 2018

Published in: International Journal of Game Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00182-017-0600-z

zbMATH Keywords

Nash equilibriumprice of stabilityring topologynetwork design gamepotential-optimum price of stability/anarchy

Mathematics Subject Classification ID

Applications of graph theory (05C90) Games involving graphs (91A43) Games involving topology, set theory, or logic (91A44) (n)-person games, (n>2) (91A06)

Related Items

Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions

Uses Software

• CGAL

Cites Work

• Nash equilibria with minimum potential in undirected broadcast games
• The ring design game with fair cost allocation
• Improving the \(H_k\)-bound on the price of stability in undirected Shapley network design games
• When ignorance helps: graphical multicast cost sharing games
• Call control in rings
• An \(O(\frac{\log n}{\log \log n})\) upper bound on the price of stability for undirected Shapley network design games
• Potential games
• The price of stability for undirected broadcast network design with fair cost allocation is constant
• The logit-response dynamics
• On the sequential price of anarchy of isolation games
• Improved lower bounds on the price of stability of undirected network design games
• A class of games possessing pure-strategy Nash equilibria
• The curse of simultaneity
• 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
• Computing on an anonymous ring