Anarchy Is Free in Network Creation

DOI10.1007/978-3-319-03536-9_17zbMath1342.68036arXiv1307.3113OpenAlexW2178671672MaRDI QIDQ2938033

Ariel Levavi, Linus Hamilton, Po-Shen Loh, Ronald L. Graham

Publication date: 13 January 2015

Published in: Lecture Notes in Computer Science, ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.3113

zbMATH Keywords

network formationextremal graph theoryprice of anarchyalgorithmic game theorynetwork creation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Noncooperative games (91A10) Network design and communication in computer systems (68M10) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Internet topics (68M11) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

Tree Nash Equilibria in the Network Creation Game, On network formation games with heterogeneous players and basic network creation games, On the tree conjecture for the network creation game

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The price of anarchy in network creation games is (mostly) constant
• On a network creation game
• The price of anarchy in network creation games
• Near-optimal network design with selfish agents
• On nash equilibria for a network creation game
• Algorithms, games, and the internet
• The price of selfish behavior in bilateral network formation
• The price of anarchy is independent of the network topology