{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,7]],"date-time":"2024-07-07T16:31:12Z","timestamp":1720369872837},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,4,13]],"date-time":"2015-04-13T00:00:00Z","timestamp":1428883200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2015,6,23]]},"abstract":"\n We introduce a network creation game in which each player (vertex) has a fixed budget to establish links to other players. In this model, each link has a unit price, and each agent tries to minimize its cost, which is either its eccentricity or its total distance to other players in the underlying (undirected) graph of the created network. Two versions of the game are studied: In the MAX version, the cost incurred to a vertex is the maximum distance between the vertex and other vertices, and, in the SUM version, the cost incurred to a vertex is the sum of distances between the vertex and other vertices. We prove that in both versions pure Nash equilibria exist, but the problem of finding the best response of a vertex is NP-hard. We take the social cost of the created network to be its diameter, and next we study the maximum possible diameter of an equilibrium graph with\n n<\/jats:italic>\n vertices in various cases. When the sum of players\u2019 budgets is\n n<\/jats:italic>\n \u2212 1, the equilibrium graphs are always trees, and we prove that their maximum diameter is \u0398(\n n<\/jats:italic>\n ) and \u0398(log\u2009\n n<\/jats:italic>\n ) in MAX and SUM versions, respectively. When each vertex has a unit budget (i.e., can establish a link to just one vertex), the diameter of any equilibrium graph in either version is \u0398(1). We give examples of equilibrium graphs in the MAX version, such that all vertices have positive budgets and yet the diameter is \u03a9(\u221alog\n n<\/jats:italic>\n ). This interesting (and perhaps counterintuitive) result shows that increasing the budgets may increase the diameter of equilibrium graphs and hence deteriorate the network structure. Then we prove that every equilibrium graph in the SUM version has diameter 2\n \n O<\/jats:italic>\n (\u221alog\n n<\/jats:italic>\n )\n <\/jats:sup>\n . Finally, we show that if the budget of each player is at least\n k<\/jats:italic>\n , then every equilibrium graph in the SUM version is\n k<\/jats:italic>\n -connected or has a diameter smaller than 4.\n <\/jats:p>","DOI":"10.1145\/2701615","type":"journal-article","created":{"date-parts":[[2015,4,14]],"date-time":"2015-04-14T12:32:19Z","timestamp":1429014739000},"page":"1-25","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["A Bounded Budget Network Creation Game"],"prefix":"10.1145","volume":"11","author":[{"given":"Shayan","family":"Ehsani","sequence":"first","affiliation":[{"name":"Sharif University of Technology, Stanford, CA, USA"}]},{"given":"Saber Shokat","family":"Fadaee","sequence":"additional","affiliation":[{"name":"Sharif University of Technology, Boston, MA, USA"}]},{"given":"Mohammadamin","family":"Fazli","sequence":"additional","affiliation":[{"name":"Sharif University of Technology, Tehran, Iran"}]},{"given":"Abbas","family":"Mehrabian","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}]},{"given":"Sina Sadeghian","family":"Sadeghabad","sequence":"additional","affiliation":[{"name":"Sharif University of Technology, ON, Canada"}]},{"given":"Mohammadali","family":"Safari","sequence":"additional","affiliation":[{"name":"Sharif University of Technology, Tehran, Iran"}]},{"given":"Morteza","family":"Saghafian","sequence":"additional","affiliation":[{"name":"Sharif University of Technology, Tehran, Iran"}]}],"member":"320","published-online":{"date-parts":[[2015,4,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109568"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771478"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.09.028"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35311-6_6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1050.0127"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_45"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2050805.2050833"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073833"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281142"},{"key":"e_1_2_1_11_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2005. Graph Theory ( 3 rd ed.). Graduate Texts in Mathematics, Vol. 173 . Springer-Verlag , Berlin. Reinhard Diestel. 2005. Graph Theory (3rd ed.). Graduate Texts in Mathematics, Vol. 173. Springer-Verlag, Berlin.","edition":"3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872088"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988788"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/647064.714876"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(79)90044-1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1571644"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900)","author":"Johnson David S.","year":"2000","unstructured":"David S. Johnson , Maria Minkoff , and Steven Phillips . 2000 . The prize collecting Steiner tree problem: Theory and practice . In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 760--769. David S. Johnson, Maria Minkoff, and Steven Phillips. 2000. The prize collecting Steiner tree problem: Theory and practice. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900). Society for Industrial and Applied Mathematics, Philadelphia, PA, 760--769."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486185"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764891.1764944"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400774"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129787"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1929237.1929261"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_60"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497321432"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.97.16.9340"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2701615","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T18:44:24Z","timestamp":1672425864000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2701615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,13]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,6,23]]}},"alternative-id":["10.1145\/2701615"],"URL":"http:\/\/dx.doi.org\/10.1145\/2701615","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,13]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}