{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:12:59Z","timestamp":1750219979594,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T00:00:00Z","timestamp":1648684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>\n            We study the problem of designing cost-sharing mechanisms for combinatorial domains. Suppose that multiple items or services are available to be shared among a set of interested agents. The outcome of a mechanism in this setting consists of an assignment, determining for each item the set of players who are granted service, together with respective payments. Although there are several works studying specialized versions of such problems, there has been almost no progress for general combinatorial cost-sharing domains until recently [\n            <jats:xref ref-type=\"bibr\">9<\/jats:xref>\n            ]. Still, many questions about the interplay between strategyproofness, cost recovery, and economic efficiency remain unanswered.\n          <\/jats:p>\n          <jats:p>\n            The main goal of our work is to further understand this interplay in terms of budget balance and social cost approximation. Towards this, we provide a refinement of cross-monotonicity (which we term\n            <jats:italic>trace-monotonicity<\/jats:italic>\n            ) that is applicable to iterative mechanisms. The trace here refers to the order in which players become finalized. On top of this, we also provide two parameterizations (complementary to a certain extent) of cost functions, which capture the behavior of their average cost-shares.\n          <\/jats:p>\n          <jats:p>\n            Based on our trace-monotonicity property, we design an Iterative Ascending Cost-Sharing Mechanism, which is applicable to the combinatorial cost-sharing setting with symmetric submodular valuations. Using our first cost function parameterization, we identify conditions under which our mechanism is weakly group-strategyproof,\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( O(1) \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -budget-balanced, and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( O(H_n) \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -approximate with respect to the social cost. Furthermore, we show that our mechanism is budget-balanced and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( H_n \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -approximate if both the valuations and the cost functions are symmetric submodular; given existing impossibility results, this is best possible.\n          <\/jats:p>\n          <jats:p>\n            Finally, we consider general valuation functions and exploit our second parameterization to derive a more fine-grained analysis of the Sequential Mechanism introduced by Moulin. This mechanism is budget balanced by construction, but in general, only guarantees a poor social cost approximation of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( n \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . We identify conditions under which the mechanism achieves improved social cost approximation guarantees. In particular, we derive improved mechanisms for fundamental cost-sharing problems, including Vertex Cover and Set Cover.\n          <\/jats:p>","DOI":"10.1145\/3505586","type":"journal-article","created":{"date-parts":[[2022,4,8]],"date-time":"2022-04-08T09:06:33Z","timestamp":1649408793000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Cost Sharing over Combinatorial Domains"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4733-7885","authenticated-orcid":false,"given":"Georgios","family":"Birmpas","sequence":"first","affiliation":[{"name":"Sapienza University of Rome, Rome, Lazio, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1855-141X","authenticated-orcid":false,"given":"Evangelos","family":"Markakis","sequence":"additional","affiliation":[{"name":"Athens University of Economics and Business, Athens, Attica, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1923-4902","authenticated-orcid":false,"given":"Guido","family":"Sch\u00e4fer","sequence":"additional","affiliation":[{"name":"Centrum Wiskunde &amp; Informatica (CWI) and University of Amsterdam, Amsterdam, North Holland, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2022,4,8]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48433-3_4"},{"key":"e_1_3_3_3_2","first-page":"20:1\u201320:17","volume-title":"Proceedings of the 27th European Symposium on Algorithms","author":"Birmpas Georgios","year":"2019","unstructured":"Georgios Birmpas, Evangelos Markakis, and Guido Schaefer. 2019. Cost sharing over combinatorial domains: Complement-free cost functions and beyond. In Proceedings of the 27th European Symposium on Algorithms. 20:1\u201320:17."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79309-0_31"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70918-3_57"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_11"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2004.08.004"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2017.03.008"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3331041.3331046"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373715"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00085-9"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0047-2727(76)90049-9"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0781-1"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69311-6_19"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/90.650144"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1177\/109114217400200205"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.06.005"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s003550050145"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00004200"},{"key":"e_1_3_3_23_2","volume-title":"Proceedings of the Aggregation and Revelation of Preferences","author":"Roberts Kevin","year":"1979","unstructured":"Kevin Roberts. 1979. The characterization of implementable choice rules. In Proceedings of the Aggregation and Revelation of Preferences. Jean Jacques Laffont (Ed.), Amsterdam: North Holland."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538907"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01770069"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1029\/WR018i003p00463"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3505586","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3505586","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:24Z","timestamp":1750182564000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3505586"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,31]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3505586"],"URL":"https:\/\/doi.org\/10.1145\/3505586","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2022,3,31]]},"assertion":[{"value":"2021-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}