Nash equilibria with minimum potential in undirected broadcast games

DOI10.1016/J.TCS.2013.02.031MaRDI QIDQ390911zbMATH OpenOpenAlexFDO

Authors Yasushi Kawase, Kazuhisa Makino

Publication date 9 January 2014

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

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

zbMATH Keywords

potential gameprice of anarchyprice of stabilitynetwork design game

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Noncooperative games (91A10) Games involving graphs (91A43)

Recommendations

• Nash equilibria with minimum potential in undirected broadcast games
• The price of stability for undirected broadcast network design with fair cost allocation is constant
• On approximate Nash equilibria in network design
• An \(H _{n/2}\) upper bound on the price of stability of undirected network design games
• An \(O(\frac{\log n}{\log \log n})\) upper bound on the price of stability for undirected Shapley network design games

Cites work

• A class of games possessing pure-strategy Nash equilibria
• An \(O(\frac{\log n}{\log \log n})\) upper bound on the price of stability for undirected Shapley network design games
• Designing network protocols for good equilibria
• Improved lower bounds on the price of stability of undirected network design games
• Nash equilibria with minimum potential in undirected broadcast games
• Near-optimal network design with selfish agents
• On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
• On the value of coordination in network design
• Potential functions and the inefficiency of equilibria
• Potential games
• Robust Equilibria of Potential Games
• The Price of Stability for Network Design with Fair Cost Allocation
• The complexity of pure Nash equilibria
• The statistical mechanics of strategic interaction
• Worst-case equilibria

Cited in

(10)

• Nash equilibria with minimum potential in undirected broadcast games
• On the price of stability of undirected multicast games
• The Price of Nash Equilibria in Multicast Transmissions Games
• The price of anarchy and stability in general noisy best-response dynamics
• Tighter bounds on the inefficiency ratio of stable equilibria in load balancing games
• Multicast network design game on a ring
• Improved bounds on equilibria solutions in the network design game
• Surrogate optimization for \(p\)-norms
• The ring design game with fair cost allocation
• Timing matters: online dynamics in broadcast games

This page was built for publication: Nash equilibria with minimum potential in undirected broadcast games

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