A Caltech Library Service

Designing Network Protocols for Good Equilibria

Chen, Ho-Lin and Roughgarden, Tim and Valiant, Gregory (2010) Designing Network Protocols for Good Equilibria. SIAM Journal on Computing, 39 (5). pp. 1799-1832. ISSN 0097-5397.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Designing and deploying a network protocol determines the rules by which end users interact with each other and with the network. We consider the problem of designing a protocol to optimize the equilibrium behavior of a network with selfish users. We consider network cost-sharing games, where the set of Nash equilibria depends fundamentally on the choice of an edge cost-sharing protocol. Previous research focused on the Shapley protocol, in which the cost of each edge is shared equally among its users. We systematically study the design of optimal cost-sharing protocols for undirected and directed graphs, single-sink and multicommodity networks, and different measures of the inefficiency of equilibria. Our primary technical tool is a precise characterization of the cost-sharing protocols that induce only network games with pure-strategy Nash equilibria. We use this characterization to prove, among other results, that the Shapley protocol is optimal in directed graphs and that simple priority protocols are essentially optimal in undirected graphs.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2010 Society for Industrial and Applied Mathematics. Received by the editors June 16, 2008; accepted for publication (in revised form) September 24, 2009; published electronically January 22, 2010. An extended abstract of this paper appeared in the Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 2008. We thank Anupam Gupta for helpful discussions during the early stages of this research, David Easley for suggesting the model with outside options, and two anonymous referees for their useful comments.
Subject Keywords:network design, cost sharing, price of anarchy, game theory, Nash equilibrium
Issue or Number:5
Classification Code:AMS subject classifications: 68Q25, 68W25, 90B10, 91A43
Record Number:CaltechAUTHORS:20100525-110741585
Persistent URL:
Official Citation:Designing Network Protocols for Good Equilibria Ho-Lin Chen, Tim Roughgarden, and Gregory Valiant, SIAM J. Comput. 39, 1799 (2010), DOI:10.1137/08072721X
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:18425
Deposited By: Ruth Sustaita
Deposited On:25 May 2010 20:20
Last Modified:03 Oct 2019 01:42

Repository Staff Only: item control page