{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:46:42Z","timestamp":1767340002941,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,6,1]],"date-time":"2009-06-01T00:00:00Z","timestamp":1243814400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-04-1-0725N00014-01-1-0795"],"award-info":[{"award-number":["N00014-04-1-0725N00014-01-1-0795"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["W911NF-05-1-0224"],"award-info":[{"award-number":["W911NF-05-1-0224"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p>In a cost-sharing problem, several participants with unknown preferences vie to receive some good or service, and each possible outcome has a known cost. A cost-sharing mechanism is a protocol that decides which participants are allocated a good and at what prices. Three desirable properties of a cost-sharing mechanism are: incentive-compatibility, meaning that participants are motivated to bid their true private value for receiving the good; budget-balance, meaning that the mechanism recovers its incurred cost with the prices charged; and economic efficiency, meaning that the cost incurred and the value to the participants are traded off in an optimal way. These three goals have been known to be mutually incompatible for thirty years. Nearly all the work on cost-sharing mechanism design by the economics and computer science communities has focused on achieving two of these goals while completely ignoring the third.<\/jats:p>\n          <jats:p>We introduce novel measures for quantifying efficiency loss in cost-sharing mechanisms and prove simultaneous approximate budget-balance and approximate efficiency guarantees for mechanisms for a wide range of cost-sharing problems, including all submodular and Steiner tree problems. Our key technical tool is an exact characterization of worst-case efficiency loss in Moulin mechanisms, the dominant paradigm in cost-sharing mechanism design.<\/jats:p>","DOI":"10.1145\/1538902.1538907","type":"journal-article","created":{"date-parts":[[2009,6,30]],"date-time":"2009-06-30T13:10:17Z","timestamp":1246367417000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["Quantifying inefficiency in cost-sharing mechanisms"],"prefix":"10.1145","volume":"56","author":[{"given":"Tim","family":"Roughgarden","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mukund","family":"Sundararajan","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,7,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"]]Andelman N. Feldman M. and Mansour Y. 2009. Strong price of anarchy. Games Econ. Behav. (http:\/\/pluto.huji.ac.il\/~mfeldman\/papers\/coalition_full.pdf).  ]]Andelman N. Feldman M. and Mansour Y. 2009. Strong price of anarchy. Games Econ. Behav. (http:\/\/pluto.huji.ac.il\/~mfeldman\/papers\/coalition_full.pdf).","DOI":"10.1016\/j.geb.2008.03.005"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0899-8256(03)00176-3"},{"key":"e_1_2_1_3_1","first-page":"399","article-title":"Hardness of approximations. In Approximation Algorithms for NP-Hard Problems, D. S. Hochbaum, Ed. PWS Publishing Company","volume":"10","author":"Arora S.","year":"1997","journal-title":"Chapter"},{"volume-title":"Proceedings of the 7th International Joint Conference on Autonomous Agents and Multi-agent Systems (AAMAS). 943--950","author":"Bachrach Y.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3114179.3114334"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11758471_19"},{"key":"e_1_2_1_7_1","unstructured":"]]Borodin A. and El-Yaniv R. 1998. Online Computation and Competitive Analysis. Cambridge University Press Cambridge.   ]]Borodin A. and El-Yaniv R. 1998. Online Computation and Competitive Analysis. Cambridge University Press Cambridge."},{"volume":"4393","volume-title":"Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science","author":"Brenner J.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_11"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2603"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1062104.1700886"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79309-0_29"},{"key":"e_1_2_1_14_1","first-page":"233","article-title":"Optimum branchings. J. Res. NBS","volume":"71","author":"Edmonds J.","year":"1967","journal-title":"Ser. B"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00085-9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1754"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/570810.570812"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-2727(76)90049-9"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Gupta A.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118787.3119259"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/1911054"},{"key":"e_1_2_1_22_1","unstructured":"]]Hartline J. D. 2003. Optimization in the private value model: Competitive analysis applied to auction design. Ph.D. dissertation University of Washington.   ]]Hartline J. D. 2003. Optimization in the private value model: Competitive analysis applied to auction design. Ph.D. dissertation University of Washington."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1361192.1361201"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380825"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/060658448"},{"key":"e_1_2_1_26_1","unstructured":"]]Juarez R. 2007. Group strategyproof cost sharing: the role of indifferences. http:\/\/www2.hawaii.edu\/~ruben\/gsp1.pdf.  ]]Juarez R. 2007. Group strategyproof cost sharing: the role of indifferences. http:\/\/www2.hawaii.edu\/~ruben\/gsp1.pdf."},{"volume-title":"Operational Research Proceedings KOI. 43--48","author":"Kent K.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585268"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646408"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.033"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2004.00503.x"},{"key":"e_1_2_1_32_1","unstructured":"]]Mas-Colell A. Whinston M. D. and Green J. R. 1995. Microeconomic Theory. Oxford University Press.  ]]Mas-Colell A. Whinston M. D. and Green J. R. 1995. Microeconomic Theory. Oxford University Press."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250912"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"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.1561\/0400000002"},{"key":"e_1_2_1_38_1","unstructured":"]]Osborne M. J. and Rubinstein A. 1994. A Course in Game Theory. MIT Press Cambridge.  ]]Osborne M. J. and Rubinstein A. 1994. A Course in Game Theory. MIT Press Cambridge."},{"volume-title":"Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS). ACM","year":"2003","author":"P\u00e1l M.","key":"e_1_2_1_39_1"},{"volume-title":"Aggregation and Revelation of Preferences","author":"Roberts K.","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132528"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72792-7_35"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1538902.1538907","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1538902.1538907","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:53Z","timestamp":1750278413000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1538902.1538907"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1145\/1538902.1538907"],"URL":"https:\/\/doi.org\/10.1145\/1538902.1538907","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2009,6]]},"assertion":[{"value":"2007-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}