skip to main content
10.5555/1347082.1347176acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article

Designing networks with good equilibria

Published: 20 January 2008 Publication History

Abstract

In a network with selfish users, designing and deploying a protocol determines the rules of the game by which end users interact with each other and with the network. We study the problem of designing a protocol to optimize the equilibrium behavior of the induced network game. 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, different classes of cost-sharing methods, and different measures of the inefficiency of equilibria. One of our main technical tools is a complete characterization of the uniform cost-sharing protocols---protocols that are designed without foreknowledge of or assumptions on the network in which they will be deployed. We use this characterization result to identify the optimal uniform protocol in several scenarios: for example, the Shapley protocol is optimal in directed graphs, while the optimal protocol in undirected graphs, a simple priority scheme, has exponentially smaller worst-case price of anarchy than the Shapley protocol. We also provide several matching upper and lower bounds on the best-possible performance of non-uniform cost-sharing protocols.

References

[1]
S. Albers, S. Eilts, E. Even-Dar, Y. Mansour, and L. Roditty. On Nash equilibria for a network creation game. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 89--98, 2006.
[2]
E. Anshelevich, A. Dasgupta, J. Kleinberg, É. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. In Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pages 295--304, 2004.
[3]
E. Anshelevich, A. Dasgupta, É. Tardos, and T. Wexler. Near-optimal network design with selfish agents. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pages 511--520, 2003.
[4]
B. Awerbuch, Y. Azar, and Y. Bartal. On-line generalized Steiner problem. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 68--74, 1996.
[5]
V. Bala and S. Goyal. A non-cooperative model of network formation. Econometrica, 68(5):1181--1229, 2000.
[6]
M. Charikar, H. Karloff, C. Mathieu, J. Naor, and M. Saks. Best response dynamics in multicast cost sharing. Manuscript, 2007.
[7]
C. Chekuri, J. Chuzhoy, L. Lewin-Eytan, J. Naor, and A. Orda. Non-cooperative multicast and facility location games. In 7th Annual ACM Conference on Electronic Commerce (EC), pages 72--81, 2006.
[8]
H. Chen and T. Roughgarden. Network design with weighted players. In Proceedings of the 18th ACM Symposium on Parallelism in Algorithms and Architextures (SPAA), pages 28--37, 2006.
[9]
G. Christodoulou, E. Koutsoupias, and A. Nanavati. Coordination mechanisms. In Proceedings of the 31st Annual International Colloquium on Automata, Languages, and Programming (ICALP), volume 3142 of Lecture Notes in Computer Science, pages 345--357, 2004.
[10]
R. Cole, Y. Dodis, and T. Roughgarden. Pricing network edges for heterogeneous selfish users. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pages 521--530, 2003.
[11]
J. Corbo and D. C. Parkes. The price of selfish behavior in bilateral network formation games. In Proceedings of the 24th ACM Symposium on Principles of Distributed Computing (PODC), pages 99--107, 2005.
[12]
A. Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou, and S. J. Shenker. On a network creation game. In Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), pages 347--351, 2003.
[13]
A. Fabrikant and C. H. Papadimitriou. The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008. To appear.
[14]
A. Fiat, H. Kaplan, M. Levy, S. Olonetsky, and R. Shabo. On the price of stability for designing undirected networks with fair cost allocations. In Proceedings of the 33rd Annual International Colloquium on Automata, Languages, and Programming (ICALP), volume 4051 of Lecture Notes in Computer Science, pages 608--618, 2006.
[15]
L. K. Fleischer, K. Jain, and M. Mahdian. Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pages 277--285, 2004.
[16]
L. Gao and J. Rexford. Stable Internet routing without global coordination. IEEE/ACM Transactions on Networking, 9(6):681--692, 2001.
[17]
A. Goel and D. Estrin. Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 499--505, 2003.
[18]
M. X. Goemans, V. Mirrokni, and A. Vetta. Sink equilibria and convergence. In Proceedings of the 46th Annual Symposium on Foundations of Computer Science (FOCS), pages 142--151, 2005.
[19]
T. Griffin, F. B. Shepherd, and G. Wilfong. The stable paths problem and interdomain routing. IEEE/ACM Transactions on Networking, 10(1):232--243, 2002.
[20]
A. Gupta, M. T. Hajiaghayi, and H. Räcke. Oblivious network design. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 970--979, 2006.
[21]
M. Imase and B. M. Waxman. Dynamic Steiner tree problem. SIAM Journal on Discrete Mathematics, 4(3):369--384, 1991.
[22]
N. Immorlica, L. Li, V. S. Mirrokni, and A. S. Schulz. Coordination mechanisms for selfish scheduling. In Proceedings of the First Annual International Workshop on Internet and Network Economics (WINE), volume 3828 of Lecture Notes in Computer Science, pages 55--69, 2005.
[23]
M. O. Jackson. A survey of models of network formation: Stability and efficiency. In G. Demange and M. Wooders, editors, Group Formation in Economics; Networks, Clubs, and Coalitions, chapter 1. Cambridge University Press, 2005.
[24]
V. Jacobson. Congestion avoidance and control. In Proceedings of SIGCOMM, pages 314--329, 1988.
[25]
K. Jain and V. V. Vazirani. Applications of approximation algorithms to cooperative games. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 364--372, 2001.
[26]
L. Jia, G. Lin, G. Noubir, R. Rajaraman, and R. Sundaram. Universal approximations for TSP, Steiner tree, and set cover. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 386--395, 2005.
[27]
R. Johari and J. N. Tsitsiklis. Efficiency of scalar-parameterized mechanisms. Submitted, 2007.
[28]
E. Kalai and D. Samet. On weighted Shapley values. International Journal of Game Theory, 16(3):205--222, 1987.
[29]
G. Karakostas and S. G. Kolliopoulos. Edge pricing of multicommodity networks for heterogeneous selfish users. In Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pages 268--276, 2004.
[30]
F. P. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunications, 8(1):33--37, 1997.
[31]
E. Koutsoupias and C. H. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1563 of Lecture Notes in Computer Science, pages 404--413, 1999.
[32]
V. S. Anil Kumar and M. V. Marathe. Improved results for Stackelberg scheduling strategies. In Proceedings of the 29th Annual International Colloquium on Automata, Languages, and Programming (ICALP), volume 2380 of Lecture Notes in Computer Science, pages 776--787, 2002.
[33]
S. H. Low and D. E. Lapsley. Optimization flow control I: Basic algorithm and convergence. IEEE/ACM Transactions on Networking, 7(6):861--874, 1999.
[34]
J. Matoušek. Lectures on Discrete Geometry. Springer, 2002.
[35]
D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, 14(1):124--143, 1996.
[36]
T. Moscibroda, S. Schmid, and R. Wattenhofer. On the topologies formed by selfish peers. In Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC), pages 133--142, 2006.
[37]
H. Moulin and S. Shenker. Strategyproof sharing of submodular costs: Budget balance versus efficiency. Economic Theory, 18(3):511--533, 2001.
[38]
J. F. Nash. Equilibrium points in N-person games. Proceedings of the National Academy of Science, 36(1):48--49, 1950.
[39]
N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1/2):166--196, 2001.
[40]
M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
[41]
Y. Rekhter, T. Li, and S. Hares. A border gateway protocol 4 (BGP-4). Network Working Group Request for Comments 4271, January 2006.
[42]
R. W. Rosenthal. A class of games possessing purestrategy Nash equilibria. International Journal of Game Theory, 2(1):65--67, 1973.
[43]
R. W. Rosenthal. The network equilibrium problem in integers. Networks, 3(1):53--59, 1973.
[44]
T. Roughgarden. Stackelberg scheduling strategies. SIAM Journal on Computing, 33(2):332--350, 2004.
[45]
C. Swamy. The effectiveness of Stackelberg strategies and tolls for network congestion games. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1133--1142, 2007.
[46]
K. Varadhan, R. Govindan, and D. Estrin. Persistent route oscillations in inter-domain routing. Computer Networks, 32(1):1--16, 2000.
[47]
V. V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
January 2008
1289 pages
  • Program Chair:
  • Shang-Hua Teng

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

  • Research-article

Conference

SODA08
Sponsor:
SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms
January 20 - 22, 2008
California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2015)How egalitarian are Nash equilibria in network cost-sharing games?Operations Research Letters10.1016/j.orl.2015.08.00643:6(564-566)Online publication date: 1-Nov-2015
  • (2013)Distributed Welfare GamesOperations Research10.1287/opre.1120.113761:1(155-168)Online publication date: 1-Jan-2013
  • (2011)A Nash bargaining solution for cooperative network formation gamesProceedings of the 10th international IFIP TC 6 conference on Networking - Volume Part I10.5555/2008780.2008810(307-318)Online publication date: 9-May-2011
  • (2011)An architectural view of game theoretic controlACM SIGMETRICS Performance Evaluation Review10.1145/1925019.192502638:3(31-36)Online publication date: 3-Jan-2011
  • (2010)Stackelberg strategies for network design gamesProceedings of the 6th international conference on Internet and network economics10.5555/1940179.1940198(222-233)Online publication date: 13-Dec-2010
  • (2010)Socially-aware network design gamesProceedings of the 29th conference on Information communications10.5555/1833515.1833524(41-45)Online publication date: 14-Mar-2010
  • (2010)Non-cooperative facility location and covering gamesTheoretical Computer Science10.1016/j.tcs.2010.02.005411:16-18(1855-1876)Online publication date: 1-Mar-2010
  • (2010)When ignorance helpsTheoretical Computer Science10.1016/j.tcs.2009.10.007411:3(660-671)Online publication date: 1-Jan-2010
  • (2009)Efficient coordination mechanisms for unrelated machine schedulingProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496859(815-824)Online publication date: 4-Jan-2009
  • (2009)Covering GamesProceedings of the 5th International Workshop on Internet and Network Economics10.1007/978-3-642-10841-9_18(184-195)Online publication date: 9-Dec-2009

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media