The price of anarchy in network creation games
We study Nash equilibria in the setting of network creation games introduced recently by Fabrikant, Luthra, Maneva, Papadimitriou, and Shenker. In this game we have a set of selfish node players, each creating some incident links, and the goal is to minimize α times the cost of the created links plu...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121367 |
| _version_ | 1826200055265099776 |
|---|---|
| author | Demaine, Erik D Hajiaghayi, MohammadTaghi Mahini, Hamid Zadimoghaddam, Morteza |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D Hajiaghayi, MohammadTaghi Mahini, Hamid Zadimoghaddam, Morteza |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | We study Nash equilibria in the setting of network creation games introduced recently by Fabrikant, Luthra, Maneva, Papadimitriou, and Shenker. In this game we have a set of selfish node players, each creating some incident links, and the goal is to minimize α times the cost of the created links plus sum of the distances to all other players. Fabrikant et al. proved an upper bound O(√α) on the price of anarchy: the relative cost of the lack of coordination. Albers, Eilts, Even-Dar, Mansour, and Roditty show that the price of anarchy is constant for α = O(√n) and for α ≥ 12n[lgn], and that the price of anarchy is 15(1 + (min{α/n, n 2/alpha;}) 1/3) for any α. The latter bound shows the first sublinear worst-case bound, O(n 1/3), for all α. But no better bound is known for α between ω(√n) and o(nlgn). Yet α ≈ n is perhaps the most interesting range, for it corresponds to considering the average distance (instead of the sum of distances) to other nodes to be roughly on par with link creation (effectively dividing α by n). In this article, we prove the first o(n ε) upper bound for general α, namely 2 (√lgn). We also prove a constant upper bound for α = O(n 1-ε) for any fixed ε ≤ 0, substantially reducing the range of α for which constant bounds have not been obtained. Along the way, we also improve the constant upper bound by Albers et al. (with the lead constant of 15) to 6 for α < (n/2) 1/2 and to 4 for α < (n/2) 1/3. Next we consider the bilateral network variant of Corbo and Parkes, in which links can be created only with the consent of both endpoints and the link price is shared equally by the two. Corbo and Parkes show an upper bound of O(√α) and a lower bound of Ω(lgα) for α ≤ n. In this article, we show that in fact the upper bound O(√α) is tight for α ≤ n, by proving a matching lower bound of Ω(√α). For α > n, we prove that the price of anarchy is Θ(n/√α). Finally we introduce a variant of both network creation games, in which each player desires to minimize α times the cost of its created links plus the maximum distance (instead of the sum of distances) to the other players. This variant of the problem is naturally motivated by considering the worst case instead of the average case. Interestingly, for the original (unilateral) game, we show that the price of anarchy is at most 2 for α ≥ n, O(min{4√lgn, (n/α) 1/3}) for 2√lgn ≥ α ≥ n, and O(n 2/α) for α > 2√lgn. For the bilateral game, we prove matching upper and lower bounds of Θ(n/α+1) for α ≤ n, and an upper bound of 2 for α > n. |
| first_indexed | 2024-09-23T11:30:16Z |
| format | Article |
| id | mit-1721.1/121367 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:30:16Z |
| publishDate | 2019 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1213672022-09-27T19:59:20Z The price of anarchy in network creation games Demaine, Erik D Hajiaghayi, MohammadTaghi Mahini, Hamid Zadimoghaddam, Morteza Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science We study Nash equilibria in the setting of network creation games introduced recently by Fabrikant, Luthra, Maneva, Papadimitriou, and Shenker. In this game we have a set of selfish node players, each creating some incident links, and the goal is to minimize α times the cost of the created links plus sum of the distances to all other players. Fabrikant et al. proved an upper bound O(√α) on the price of anarchy: the relative cost of the lack of coordination. Albers, Eilts, Even-Dar, Mansour, and Roditty show that the price of anarchy is constant for α = O(√n) and for α ≥ 12n[lgn], and that the price of anarchy is 15(1 + (min{α/n, n 2/alpha;}) 1/3) for any α. The latter bound shows the first sublinear worst-case bound, O(n 1/3), for all α. But no better bound is known for α between ω(√n) and o(nlgn). Yet α ≈ n is perhaps the most interesting range, for it corresponds to considering the average distance (instead of the sum of distances) to other nodes to be roughly on par with link creation (effectively dividing α by n). In this article, we prove the first o(n ε) upper bound for general α, namely 2 (√lgn). We also prove a constant upper bound for α = O(n 1-ε) for any fixed ε ≤ 0, substantially reducing the range of α for which constant bounds have not been obtained. Along the way, we also improve the constant upper bound by Albers et al. (with the lead constant of 15) to 6 for α < (n/2) 1/2 and to 4 for α < (n/2) 1/3. Next we consider the bilateral network variant of Corbo and Parkes, in which links can be created only with the consent of both endpoints and the link price is shared equally by the two. Corbo and Parkes show an upper bound of O(√α) and a lower bound of Ω(lgα) for α ≤ n. In this article, we show that in fact the upper bound O(√α) is tight for α ≤ n, by proving a matching lower bound of Ω(√α). For α > n, we prove that the price of anarchy is Θ(n/√α). Finally we introduce a variant of both network creation games, in which each player desires to minimize α times the cost of its created links plus the maximum distance (instead of the sum of distances) to the other players. This variant of the problem is naturally motivated by considering the worst case instead of the average case. Interestingly, for the original (unilateral) game, we show that the price of anarchy is at most 2 for α ≥ n, O(min{4√lgn, (n/α) 1/3}) for 2√lgn ≥ α ≥ n, and O(n 2/α) for α > 2√lgn. For the bilateral game, we prove matching upper and lower bounds of Θ(n/α+1) for α ≤ n, and an upper bound of 2 for α > n. National Science Foundation (U.S.) (grant number ITR ANI-0205445) Danish National Research Foundation. Center for Massive Data Algorithmics 2019-06-19T18:09:27Z 2019-06-19T18:09:27Z 2012-04 2019-06-19T14:46:47Z Article http://purl.org/eprint/type/JournalArticle 1549-6325 https://hdl.handle.net/1721.1/121367 Demaine, Erik D., MohammadTaghi Hajiaghayi, Hamid Mahini and Morteza Zadimoghaddam. "The Price of Anarchy in Network Creation Games." ACM Transactions on Algorithms, 8 (2) April 2012, Article No. 13. en 10.1145/2151171.2151176 ACM Transactions on Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Demaine, Erik D Hajiaghayi, MohammadTaghi Mahini, Hamid Zadimoghaddam, Morteza The price of anarchy in network creation games |
| title | The price of anarchy in network creation games |
| title_full | The price of anarchy in network creation games |
| title_fullStr | The price of anarchy in network creation games |
| title_full_unstemmed | The price of anarchy in network creation games |
| title_short | The price of anarchy in network creation games |
| title_sort | price of anarchy in network creation games |
| url | https://hdl.handle.net/1721.1/121367 |
| work_keys_str_mv | AT demaineerikd thepriceofanarchyinnetworkcreationgames AT hajiaghayimohammadtaghi thepriceofanarchyinnetworkcreationgames AT mahinihamid thepriceofanarchyinnetworkcreationgames AT zadimoghaddammorteza thepriceofanarchyinnetworkcreationgames AT demaineerikd priceofanarchyinnetworkcreationgames AT hajiaghayimohammadtaghi priceofanarchyinnetworkcreationgames AT mahinihamid priceofanarchyinnetworkcreationgames AT zadimoghaddammorteza priceofanarchyinnetworkcreationgames |