On the Value of Coordination in Network Design

DOI10.1137/070701376zbMath1191.68025OpenAlexW2007583146MaRDI QIDQ3654377

Susanne Albers

Publication date: 6 January 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070701376

zbMATH Keywords

coalitionprice of anarchyprice of stabilitystrong Nash equilibriumShapley cost sharing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Special types of economic equilibria (91B52) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Games involving graphs (91A43) Applications of game theory (91A80) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Agent technology and artificial intelligence (68T42)

Related Items

Optimal cost sharing for capacitated facility location games ⋮ How to split the costs and charge the travellers sharing a ride? Aligning system's optimum with users' equilibrium ⋮ Cost-sharing scheduling games on restricted unrelated machines ⋮ When ignorance helps: graphical multicast cost sharing games ⋮ Collusion in atomic splittable routing games ⋮ Improved lower bounds on the price of stability of undirected network design games ⋮ Computing pure Nash and strong equilibria in bottleneck congestion games ⋮ Nash equilibria with minimum potential in undirected broadcast games ⋮ Timing matters: online dynamics in broadcast games ⋮ Strategic cooperation in cost sharing games ⋮ On the Price of Stability of Undirected Multicast Games ⋮ The price of stability for undirected broadcast network design with fair cost allocation is constant ⋮ Approximate strong equilibria in job scheduling games with two uniformly related machines ⋮ The ring design game with fair cost allocation ⋮ Strong stability of Nash equilibria in load balancing games ⋮ Minimizing Rosenthal potential in multicast games ⋮ Non-cooperative facility location and covering games ⋮ Competitive cost sharing with economies of scale ⋮ Bayesian ignorance ⋮ Cost-sharing games in real-time scheduling systems ⋮ Cost-sharing games in real-time scheduling systems ⋮ The Price of Stability of Weighted Congestion Games ⋮ Balancing Load via Small Coalitions in Selfish Ring Routing Games ⋮ The Price of Stability of Weighted Congestion Games ⋮ Some anomalies of farsighted strategic behavior ⋮ Enforcing efficient equilibria in network design games via subsidies