skip to main content
10.1145/872035.872088acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

On a network creation game

Published: 13 July 2003 Publication History

Abstract

We introduce a novel game that models the creation of Internet-like networks by selfish node-agents without central design or coordination. Nodes pay for the links that they establish, and benefit from short paths to all destinations. We study the Nash equilibria of this game, and prove results suggesting that the "price of anarchy" [4] in this context (the relative cost of the lack of coordination) may be modest. Several interesting: extensions are suggested.

References

[1]
A. Czumaj, P. Krysta, and B. Vöcking. Selfish traffic allocation for server farms. In Proc. of 2002 STOC, pages 287--296. ACM, May 2002.
[2]
M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. In Proc. of 1999 SIGCOMM, pages 251--262. ACM, September 1999.
[3]
J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker. A bgp-based mechanism for lowest-cost routing. In Proc. of 2002 PODC, pages 173--182. ACM, July 2002.
[4]
E. Koutsoupias and C. H. Papadimitriou. Worst-case equilibria. Lecture Notes in Computer Science, 1563:404--413, 1999.
[5]
M. Mavronikolas and P. Spirakis. The price of selfish routing. In Proc. of 2001 STOC, pages 510--519. ACM, July 2001.
[6]
T. Roughgarden. Selfish Routing. PhD thesis, Cornell University, 2002.
[7]
T. Roughgarden and E. Tardos. How bad is selfish routing? In Proc. of 2000 FOCS, pages 93--102. IEEE, November 2000.

Cited By

View all
  • (2024)Equilibria, Efficiency, and Inequality in Network Formation for Hiring and OpportunityProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673451(347-371)Online publication date: 8-Jul-2024
  • (2024)Pricing for Efficient Traffic Exchange at IXPsIEEE/ACM Transactions on Networking10.1109/TNET.2023.333635232:3(2053-2068)Online publication date: Jun-2024
  • (2024)The Diameter of Sum Basic Equilibria GamesTheoretical Computer Science10.1016/j.tcs.2024.114807(114807)Online publication date: Aug-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing
July 2003
380 pages
ISBN:1581137087
DOI:10.1145/872035
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2003

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Nash equilibria
  2. distributed network design
  3. game-theoretic models
  4. price of anarchy

Qualifiers

  • Article

Conference

PODC03
Sponsor:

Acceptance Rates

PODC '03 Paper Acceptance Rate 51 of 226 submissions, 23%;
Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)86
  • Downloads (Last 6 weeks)1
Reflects downloads up to 15 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Equilibria, Efficiency, and Inequality in Network Formation for Hiring and OpportunityProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673451(347-371)Online publication date: 8-Jul-2024
  • (2024)Pricing for Efficient Traffic Exchange at IXPsIEEE/ACM Transactions on Networking10.1109/TNET.2023.333635232:3(2053-2068)Online publication date: Jun-2024
  • (2024)The Diameter of Sum Basic Equilibria GamesTheoretical Computer Science10.1016/j.tcs.2024.114807(114807)Online publication date: Aug-2024
  • (2024)Network creation with homophilic agentsSocial Choice and Welfare10.1007/s00355-024-01562-xOnline publication date: 5-Nov-2024
  • (2023)Temporal network creation gamesProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/279(2511-2519)Online publication date: 19-Aug-2023
  • (2023)The Impact of Cooperation in Bilateral Network CreationProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594588(321-331)Online publication date: 19-Jun-2023
  • (2023)Lightning Creation Games2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00037(1-11)Online publication date: Jul-2023
  • (2023)On Dynamics of Basic Network Creation Games with Non-Uniform Communication Interest2023 Eleventh International Symposium on Computing and Networking Workshops (CANDARW)10.1109/CANDARW60564.2023.00023(86-92)Online publication date: 27-Nov-2023
  • (2023)Social Distancing Network CreationAlgorithmica10.1007/s00453-022-01089-685:7(2087-2130)Online publication date: 12-Jan-2023
  • (2023)Port Capacity Leasing Games at Internet Exchange PointsGame Theory for Networks10.1007/978-3-031-23141-4_19(251-262)Online publication date: 8-Jan-2023
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media