{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:29:35Z","timestamp":1759847375857,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,2,3]],"date-time":"2016-02-03T00:00:00Z","timestamp":1454457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1016885 and CCF-1215965"],"award-info":[{"award-number":["CCF-1016885 and CCF-1215965"]}]},{"name":"ONR PECASE"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2016,2,3]]},"abstract":"<jats:p>We consider network cost-sharing games with nonanonymous cost functions, where the cost of each edge is a submodular function of its users, and this cost is shared using the Shapley value. Nonanonymous cost functions model asymmetries between the players, which can arise from different bandwidth requirements, durations of use, services needed, and so on.<\/jats:p>\n          <jats:p>\n            These games can possess multiple Nash equilibria of wildly varying quality. The goal of this article is to identify well-motivated equilibrium refinements that admit good worst-case approximation bounds. Our primary results are tight bounds on the cost of strong Nash equilibria and potential function minimizers in network cost-sharing games with nonanonymous cost functions, parameterized by the set\n            <jats:italic>C<\/jats:italic>\n            of allowable submodular cost functions.\n          <\/jats:p>\n          <jats:p>\n            These two worst-case bounds coincide for every set\n            <jats:italic>C<\/jats:italic>\n            , and equal the\n            <jats:italic>summability<\/jats:italic>\n            parameter introduced in Roughgarden and Sundararajan [2009] to characterize efficiency loss in a family of cost-sharing mechanisms. Thus, a single parameter simultaneously governs the worst-case inefficiency of network cost-sharing games (in two incomparable senses) and cost-sharing mechanisms. This parameter is always at most the\n            <jats:italic>k<\/jats:italic>\n            th Harmonic number\n            <jats:italic>\n              H\n              <jats:italic>\n                <jats:sub>k<\/jats:sub>\n              <\/jats:italic>\n            <\/jats:italic>\n            \u2248 ln\n            <jats:italic>k<\/jats:italic>\n            , where\n            <jats:italic>k<\/jats:italic>\n            is the number of players, and is constant for many function classes of interest.\n          <\/jats:p>","DOI":"10.1145\/2841228","type":"journal-article","created":{"date-parts":[[2016,2,3]],"date-time":"2016-02-03T16:29:01Z","timestamp":1454516941000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Network Cost-Sharing without Anonymity"],"prefix":"10.1145","volume":"4","author":[{"given":"Tim","family":"Roughgarden","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA"}]},{"given":"Okke","family":"Schrijvers","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}]}],"member":"320","published-online":{"date-parts":[[2016,2,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/070701376"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680096"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a004"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_54"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"R. J. Aumann. 1959. Acceptable points in general cooperative n-person games. Contributions to the Theory of Games 4 (1959) 287--324.  R. J. Aumann. 1959. Acceptable points in general cooperative n-person games. Contributions to the Theory of Games 4 (1959) 287--324.","DOI":"10.1515\/9781400882168-018"},{"volume":"8768","volume-title":"Lecture Notes in Computer Science","author":"Bachrach Y.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219265911002824"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9411-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"V. Bil\u00f2 M. Flammini G. Monaco and L. Moscardelli. 2013. Some anomalies of farsighted strategic behavior. In Approximation and Online Algorithms. Vol. 7846. Springer Berlin 229--241.  V. Bil\u00f2 M. Flammini G. Monaco and L. Moscardelli. 2013. Some anomalies of farsighted strategic behavior. In Approximation and Online Algorithms. Vol. 7846. Springer Berlin 229--241.","DOI":"10.1007\/978-3-642-38016-7_19"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"V. Bil\u00f2 M. Flammini and L. Moscardelli. 2014. The price of stability for undirected broadcast network design with fair cost allocation is constant. Games and Economic Behavior (2014).  V. Bil\u00f2 M. Flammini and L. Moscardelli. 2014. The price of stability for undirected broadcast network design with fair cost allocation is constant. Games and Economic Behavior (2014).","DOI":"10.1109\/FOCS.2013.74"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1993.1023"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378544"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2007.070813"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9128-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/08072721X"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.101.6.2562"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_24"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12450-1_8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.07.002"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872088"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_53"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482553"},{"volume-title":"Econometrica: Journal of the Econometric Society","year":"1989","author":"Hart S.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0592"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"M. O. Jackson. 2008. Social and Economic Networks. Princeton.   M. O. Jackson. 2008. Social and Economic Networks. Princeton.","DOI":"10.1515\/9781400833993"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"K. Jain and M. Mahdian. 2007. Cost sharing. Algorithmic Game Theory (2007) 385--410.  K. Jain and M. Mahdian. 2007. Cost sharing. Algorithmic Game Theory (2007) 385--410.","DOI":"10.1017\/CBO9780511800481.017"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01756292"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Y. Kawase and K. Makino. 2013. Nash equilibria with minimum potential in undirected broadcast games. Theoretical Computer Science 482 (April 2013) 33--47.  Y. Kawase and K. Makino. 2013. Nash equilibria with minimum potential in undirected broadcast games. Theoretical Computer Science 482 (April 2013) 33--47.","DOI":"10.1016\/j.tcs.2013.02.031"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2781678"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482562"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.04.015"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0095"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003550050145"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00004200"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090242"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538907"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_8"},{"key":"e_1_2_1_40_1","unstructured":"L. S. Shapley. 1953. Additive and Non-Additive Set Functions. Ph.D. dissertation. Department of Mathematics Princeton University.  L. S. Shapley. 1953. Additive and Non-Additive Set Functions. Ph.D. dissertation. Department of Mathematics Princeton University."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.2307\/2950588"},{"volume-title":"Internet and Network Economics","author":"Syrgkanis V.","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"\u00c9. Tardos and T. Wexler. 2007. Network formation games and the potential function method. In Algorithmic Game Theory. Cambridge University Press Chapter 19 487--516.  \u00c9. Tardos and T. Wexler. 2007. Network formation games and the potential function method. In Algorithmic Game Theory. Cambridge University Press Chapter 19 487--516.","DOI":"10.1017\/CBO9780511800481.021"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0567"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2841228","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2841228","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:53:47Z","timestamp":1750222427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2841228"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,3]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2,3]]}},"alternative-id":["10.1145\/2841228"],"URL":"https:\/\/doi.org\/10.1145\/2841228","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2016,2,3]]},"assertion":[{"value":"2014-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}