{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T13:52:08Z","timestamp":1770990728908,"version":"3.50.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,6,28]],"date-time":"2016-06-28T00:00:00Z","timestamp":1467072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Research Grant PRIN 2010 ARS TechnoMedia"},{"name":"Italian Ministry of Education, University, and Research"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2016,6,28]]},"abstract":"<jats:p>\n            Network creation games have been extensively studied, both by economists and computer scientists, due to their versatility in modeling individual-based community formation processes. These processes, in turn, are the theoretical counterpart of several economics, social, and computational applications on the Internet. In their several variants, these games model the tension of a player between the player\u2019s two antagonistic goals: to be as close as possible to the other players and to activate a cheapest possible set of links. However, the generally adopted assumption is that players have a\n            <jats:italic>common and complete<\/jats:italic>\n            information about the ongoing network, which is quite unrealistic in practice. In this article, we consider a more compelling scenario in which players have only limited information about the network in whicy they are embedded. More precisely, we explore the game-theoretic and computational implications of assuming that players have a complete knowledge of the network structure only up to a given radius\n            <jats:italic>k<\/jats:italic>\n            , which is one of the most qualified\n            <jats:italic>local-knowledge models<\/jats:italic>\n            used in distributed computing. In this respect, we define a suitable equilibrium concept, and we provide a comprehensive set of upper and lower bounds to the price of anarchy for the entire range of values of\n            <jats:italic>k<\/jats:italic>\n            and for the two classic variants of the game, namely, those in which a player\u2019s cost\u2014besides the activation cost of the owned links\u2014depends on the maximum\/sum of all distances to the other nodes in the network, respectively. These bounds are assessed through an extensive set of experiments.\n          <\/jats:p>","DOI":"10.1145\/2938426","type":"journal-article","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T11:59:22Z","timestamp":1468929562000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Locality-Based Network Creation Games"],"prefix":"10.1145","volume":"3","author":[{"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Sassari, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luciano","family":"Gual\u00e0","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cTor Vergata\u201d, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leucci","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi dell\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi dell\u2019Aquila, and Istituto di Analisi dei Sistemi ed Informatica (CNR), Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,7,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771478"},{"key":"e_1_2_1_2_1","volume-title":"24th Annual Congress of the European Economic Association and 63rd Econometric Society European Meeting (EEC\/ESEM\u201909)","author":"Ballester Pla Pablo C.","unstructured":"Pablo C. Ballester Pla , Giovanni Ponti , and Marco J . van der Leij. 2009. Bounded rationality and incomplete information in network games . Presented at the 24th Annual Congress of the European Economic Association and 63rd Econometric Society European Meeting (EEC\/ESEM\u201909) . Pablo C. Ballester Pla, Giovanni Ponti, and Marco J. van der Leij. 2009. Bounded rationality and incomplete information in network games. Presented at the 24th Annual Congress of the European Economic Association and 63rd Econometric Society European Meeting (EEC\/ESEM\u201909)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35311-6_29"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09620-9_17"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35311-6_6"},{"key":"e_1_2_1_6_1","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s B\u00e9la","unstructured":"B\u00e9la Bollob\u00e1s . 2004. Extremal Graph Theory . Courier Dover Publications , Mineola, NY . B\u00e9la Bollob\u00e1s. 2004. Extremal Graph Theory. Courier Dover Publications, Mineola, NY."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1980522.1980524"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281142"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989523"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs","volume":"6","author":"Erd\u0151s Paul","year":"1959","unstructured":"Paul Erd\u0151s and Alfr\u00e9d R\u00e9nyi . 1959 . On random graphs . Publicationes Mathematicae Debrecen 6 , 290 -- 291 . Paul Erd\u0151s and Alfr\u00e9d R\u00e9nyi. 1959. On random graphs. Publicationes Mathematicae Debrecen 6, 290--291.","journal-title":"Publicationes Mathematicae Debrecen"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872088"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03536-9_17"},{"key":"e_1_2_1_13_1","volume-title":"Retrieved","author":"Optimization Gurobi","year":"2014","unstructured":"Gurobi Optimization . 2014 . Gurobi optimizer reference manual. (2014) . Retrieved May 27, 2016 from http:\/\/www.gurobi.com. Gurobi Optimization. 2014. Gurobi optimizer reference manual. (2014). Retrieved May 27, 2016 from http:\/\/www.gurobi.com."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.005"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1996.0108"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486185"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.04.013"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1995-00569-0"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35311-6_11"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03536-9_10"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_60"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9459-y"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2938426","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2938426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:38:20Z","timestamp":1750282700000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2938426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,28]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,6,28]]}},"alternative-id":["10.1145\/2938426"],"URL":"https:\/\/doi.org\/10.1145\/2938426","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,28]]},"assertion":[{"value":"2014-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}