A Caltech Library Service

Improved Bounds on the Price of Stability in Network Cost Sharing Games

Lee, Euiwoong and Ligett, Katrina (2013) Improved Bounds on the Price of Stability in Network Cost Sharing Games. In: EC '13 Proceedings of the fourteenth ACM conference on Electronic commerce. ACM , New York, NY, pp. 607-620. ISBN 978-1-4503-1962-1.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We study the price of stability in undirected network design games with fair cost sharing. Our work provides multiple new pieces of evidence that the true price of stability, at least for special subclasses of games, may be a constant. We make progress on this long-outstanding problem, giving a bound of O(log log log n) on the price of stability of undirected broadcast games (where n is the number of players). This is the first progress on the upper bound for this problem since the O(log log n) bound of [Fiat et al. 2006] (despite much attention, the known lower bound remains at 1.818, from [Bilò et al. 2010]). Our proofs introduce several new techniques that may be useful in future work. We provide further support for the conjectured constant price of stability in the form of a comprehensive analysis of an alternative solution concept that forces deviating players to bear the entire costs of building alternative paths. This solution concept includes all Nash equilibria and can be viewed as a relaxation thereof, but we show that it preserves many properties of Nash equilibria. We prove that the price of stability in multicast games for this relaxed solution concept is Θ(1), which may suggest that similar results should hold for Nash equilibria. This result also demonstrates that the existing techniques for lower bounds on the Nash price of stability in undirected network design games cannot be extended to be super-constant, as our relaxation concept encompasses all equilibria constructed in them.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Ligett, Katrina0000-0003-2780-6656
Additional Information:Copyright ©2013 ACM. EL is supported by the Samsung Foundation. KL gratefully acknowledges the generous support of the Charles Lee Powell Foundation. The authors would like to thank Federico Echenique, Amos Fiat, Bobby Kleinberg, and Rob van Stee for their useful suggestions and comments.
Funding AgencyGrant Number
Samsung FoundationUNSPECIFIED
Charles Lee Powell FoundationUNSPECIFIED
Subject Keywords:Theory, Algorithms, Economics, Network Design, Price of Stability
Classification Code:F.2.0 [ Theory of Computation ]: Analysis of Algorithms and Problem Complexity
Record Number:CaltechAUTHORS:20131009-110149445
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:41810
Deposited By: Kristin Buxton
Deposited On:09 Oct 2013 21:14
Last Modified:10 Nov 2021 04:34

Repository Staff Only: item control page