Designing Network Protocols for Good Equilibria
Authors:
- Ho-Lin ChenHCHo-Lin Chen
- Tim RoughgardenTRTim Roughgarden
- Gregory ValiantGVGregory Valiant
- 1 January 2010
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 39 (5) , 1799-1832
Abstract
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.Keywords
This publication has 53 references indexed in Scilit:
- The stable paths problem and interdomain routingIEEE/ACM Transactions on Networking, 2002
- Stable Internet routing without global coordinationIEEE/ACM Transactions on Networking, 2001
- A Noncooperative Model of Network FormationEconometrica, 2000
- Optimization flow control. I. Basic algorithm and convergenceIEEE/ACM Transactions on Networking, 1999
- Charging and rate control for elastic trafficEuropean Transactions on Telecommunications, 1997
- Balancing minimum spanning trees and shortest-path treesAlgorithmica, 1995
- Potential, Value, and ConsistencyEconometrica, 1989
- On weighted Shapley valuesInternational Journal of Game Theory, 1987
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973
- The network equilibrium problem in integersNetworks, 1973