{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T14:19:22Z","timestamp":1775744362115,"version":"3.50.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T00:00:00Z","timestamp":1744243200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            Budget-feasible procurement has been a major paradigm in mechanism design since its introduction by Singer [\n            <jats:xref ref-type=\"bibr\">28<\/jats:xref>\n            ]. An auctioneer (buyer) with a strict budget constraint is interested in buying goods or services from a group of strategic agents (sellers). In many scenarios, it makes sense to allow the auctioneer to only partially buy what an agent offers, e.g., an agent might have multiple copies of an item to sell, might offer multiple levels of a service, or may be available to perform a task for any fraction of a specified time interval. Nevertheless, the focus of the related literature has been on settings in which each agent\u2019s services are either fully acquired or not at all. A reason for this is that in settings with partial allocations, such as the ones mentioned, there are strong inapproximability results (see, e.g., Anari et\u00a0al. [\n            <jats:xref ref-type=\"bibr\">5<\/jats:xref>\n            ], Chan and Chen [\n            <jats:xref ref-type=\"bibr\">10<\/jats:xref>\n            ]). Under the mild assumption of being able to afford each agent entirely, we are able to circumvent such results. We design a polynomial-time, deterministic, truthful, budget-feasible,\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((2+\\sqrt {3})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -approximation mechanism for the setting in which each agent offers multiple levels of service and the auctioneer has a valuation function that is separable concave, i.e., it is the sum of concave functions. We then use this result to design a deterministic, truthful, and budget-feasible\n            <jats:italic>O<\/jats:italic>\n            (1)-approximation mechanism for the setting in which any fraction of a service can be acquired, again for separable concave objectives. For the special case in which the objective is the sum of linear valuation functions, we improve the best known approximation ratio for the problem from\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((3+\\sqrt {5})\/2\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            (by Klumper and Sch\u00e4fer [\n            <jats:xref ref-type=\"bibr\">19<\/jats:xref>\n            ]) to 2. This establishes a separation between this setting and its indivisible counterpart.\n          <\/jats:p>","DOI":"10.1145\/3723883","type":"journal-article","created":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T10:20:59Z","timestamp":1742293259000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Partial Allocations in Budget-Feasible Mechanism Design: Bridging Multiple Levels of Service and Divisible Agents"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4341-5439","authenticated-orcid":false,"given":"Georgios","family":"Amanatidis","sequence":"first","affiliation":[{"name":"Athens University of Economics and Business, Athens, Greece and Archimedes \/ Athena RC, Athens, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2375-5313","authenticated-orcid":false,"given":"Sophie","family":"Klumper","sequence":"additional","affiliation":[{"name":"Centrum Wiskunde en Informatica, Amsterdam, Netherlands and University of Amsterdam, Amsterdam, Netherlands"}]},{"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, Greece and Archimedes \/ Athena RC, Athens, Greece and Input Output (IOG), Athens, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1923-4902","authenticated-orcid":false,"given":"Guido","family":"Sch\u00e4fer","sequence":"additional","affiliation":[{"name":"Centrum Wiskunde en Informatica, Amsterdam, Netherlands and University of Amsterdam, Amsterdam, Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5924-3620","authenticated-orcid":false,"given":"Artem","family":"Tsikiridis","sequence":"additional","affiliation":[{"name":"Centrum Wiskunde en Informatica, Amsterdam, Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2025,4,10]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1007\/978-3-662-54110-4_29","volume-title":"Proceedings of Web and Internet Economics: 12th International Conference (WINE\u201916)","author":"Amanatidis Georgios","year":"2016","unstructured":"Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. 2016. Coverage, matching, and beyond: New results on budgeted mechanism design. In Proceedings of Web and Internet Economics: 12th International Conference (WINE\u201916). 414\u2013428."},{"key":"e_1_3_3_3_2","first-page":"1","volume-title":"Proceedings of Web and Internet Economics: 13th International Conference (WINE\u201917)","author":"Amanatidis Georgios","year":"2017","unstructured":"Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. 2017. On budget-feasible mechanism design for symmetric submodular objectives. In Proceedings of Web and Internet Economics: 13th International Conference (WINE\u201917). Springer, 1\u201315."},{"key":"e_1_3_3_4_2","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1145\/3328526.3329622","volume-title":"Proceedings of the 2019 ACM Conference on Economics and Computation (EC\u201919)","author":"Amanatidis Georgios","year":"2019","unstructured":"Georgios Amanatidis, Pieter Kleer, and Guido Sch\u00e4fer. 2019. Budget-feasible mechanism design for non-monotone submodular objectives: Offline and online. In Proceedings of the 2019 ACM Conference on Economics and Computation (EC\u201919). 901\u2013919."},{"key":"e_1_3_3_5_2","series-title":"Lecture Notes in Computer Science","first-page":"Berlin, 41\u201358","volume-title":"Proceedings of the 9th International Conference on Web and Internet Economics, WINE\u201923)","volume":"14","author":"Amanatidis Georgios","year":"2023","unstructured":"Georgios Amanatidis, Sophie Klumper, Evangelos Markakis, Guido Sch\u00e4fer, and Artem Tsikiridis. 2023. Partial allocations in budget-feasible mechanism design: Bridging multiple levels of service and divisible agents. In Proceedings of the 9th International Conference on Web and Internet Economics, WINE\u201923), Jugal Garg, Max Klimm, and Yuqing Kong (Eds.). Lecture Notes in Computer Science, Vol. 14,413). Springer-Verlag, Berlin, 41\u201358."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2017.1693"},{"issue":"1","key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"113","DOI":"10.22574\/jmid.2022.12.004","article-title":"Characterization of incentive compatible single-parameter mechanisms revisited","volume":"7","author":"Apt Krzysztof R.","year":"2022","unstructured":"Krzysztof R. Apt and Jan Heering. 2022. Characterization of incentive compatible single-parameter mechanisms revisited. The Journal of Mechanism and Institution Design 7, 1 (2022), 113\u2013129.","journal-title":"The Journal of Mechanism and Institution Design"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875583"},{"key":"e_1_3_3_9_2","first-page":"2940","volume-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022","author":"Balkanski Eric","year":"2022","unstructured":"Eric Balkanski, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi Tan. 2022. Deterministic budget-feasible clock auctions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. 2940\u20132963."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1067275"},{"key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-319-13129-0_7","volume-title":"Web and Internet Economics: 10th International Conference, WINE 2014, Proceedings","author":"Chan Hau","year":"2014","unstructured":"Hau Chan and Jing Chen. 2014. Truthful multi-unit procurements with budgets. In Web and Internet Economics: 10th International Conference, WINE 2014, Proceedings. 89\u2013105."},{"key":"e_1_3_3_12_2","first-page":"685","volume-title":"Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA\u201911)","author":"Chen Ning","year":"2011","unstructured":"Ning Chen, Nick Gravin, and Pinyan Lu. 2011. On the approximability of budget feasible mechanisms. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA\u201911). 685\u2013699."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993615"},{"key":"e_1_3_3_14_2","first-page":"279","volume-title":"Proceedings of the 23rd International Conference on World Wide Web (WWW\u201914","author":"Goel Gagan","year":"2014","unstructured":"Gagan Goel, Afshin Nikzad, and Adish Singla. 2014. Allocating tasks to workers with matching constraints: Truthful mechanisms for crowdsourcing markets. In Proceedings of the 23rd International Conference on World Wide Web (WWW\u201914). 279\u2013280."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3417746"},{"key":"e_1_3_3_16_2","volume-title":"37th Conference on Neural Information Processing Systems","author":"Han Kai","year":"2023","unstructured":"Kai Han, You Wu, He Huang, and Shuang Cui. 2023. Triple eagle: Simple, fast and practical budget-feasible mechanisms. In 37th Conference on Neural Information Processing Systems. 33894\u201333911."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(95)00009-9"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583477"},{"key":"e_1_3_3_19_2","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/978-3-030-04612-5_17","volume-title":"Proceedings of Web and Internet Economics: 14th International Conference (WINE\u201918)","author":"Jalaly Pooya","year":"2018","unstructured":"Pooya Jalaly and \u00c9va Tardos. 2018. Simple and efficient budget feasible mechanisms for monotone submodular valuations. In Proceedings of Web and Internet Economics: 14th International Conference (WINE\u201918). 246\u2013263."},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/978-3-031-15714-1_5","volume-title":"Proceedings of Algorithmic Game Theory: 15th International Symposium (SAGT\u201922)","author":"Klumper Sophie","year":"2022","unstructured":"Sophie Klumper and Guido Sch\u00e4fer. 2022. Budget feasible mechanisms for procurement auctions with divisible agents. In Proceedings of Algorithmic Game Theory: 15th International Symposium (SAGT\u201922). 78\u201393."},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/978-3-319-59250-3_30","volume-title":"Proceedings of Integer Programming and Combinatorial Optimization: 19th International Conference (IPCO\u201917)","author":"Leonardi Stefano","year":"2017","unstructured":"Stefano Leonardi, Gianpiero Monaco, Piotr Sankowski, and Qiang Zhang. 2017. Budget feasible mechanisms on matroids. In Proceedings of Integer Programming and Combinatorial Optimization: 19th International Conference (IPCO\u201917). 368\u2013379."},{"issue":"2","key":"e_1_3_3_22_2","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s10458-022-09563-9","article-title":"Budget feasible mechanisms for facility location games with strategic facilities","volume":"36","author":"Li Minming","year":"2022","unstructured":"Minming Li, Chenhao Wang, and Mengqi Zhang. 2022. Budget feasible mechanisms for facility location games with strategic facilities. Autonomous Agents and Multi-Agent Systems 36, 2 (2022), 35.","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"e_1_3_3_23_2","first-page":"8132","volume-title":"Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI\u201924)","author":"Liu Xiang","year":"2024","unstructured":"Xiang Liu, Hau Chan, Minming Li, and Weiwei Wu. 2024. Budget feasible mechanisms: A survey. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI\u201924), Kate Larson (Ed.). International Joint Conferences on Artificial Intelligence Organization, 8132\u20138141. Survey Track."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/98124"},{"issue":"5","key":"e_1_3_3_25_2","doi-asserted-by":"crossref","first-page":"22\u2013es","DOI":"10.1145\/1284320.1284321","article-title":"Adwords and generalized online matching","volume":"54","author":"Mehta Aranyak","year":"2007","unstructured":"Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. 2007. Adwords and generalized online matching. Journal of the ACM (JACM) 54, 5 (2007), 22\u2013es.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_3_3_27_2","volume-title":"15th Innovations in Theoretical Computer Science Conference (ITCS\u201924)","author":"Neogi Rian","year":"2024","unstructured":"Rian Neogi, Kanstantsin Pashkovich, and Chaitanya Swamy. 2024. Budget-feasible mechanism design: Simpler, better mechanisms and general payment constraints. In 15th Innovations in Theoretical Computer Science Conference (ITCS\u201924). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik. 84:1\u201384:22."},{"key":"e_1_3_3_28_2","volume-title":"14th Innovations in Theoretical Computer Science Conference (ITCS\u201923)","author":"Rubinstein Aviad","year":"2023","unstructured":"Aviad Rubinstein and Junyao Zhao. 2023. Beyond worst-case budget-feasible mechanism design. In 14th Innovations in Theoretical Computer Science Conference (ITCS\u201923). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_3_29_2","first-page":"765","volume-title":"Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS\u201910)","author":"Singer Yaron","year":"2010","unstructured":"Yaron Singer. 2010. Budget feasible mechanisms. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS\u201910). 765\u2013774."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3723883","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3723883","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:00Z","timestamp":1750295940000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3723883"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,10]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3723883"],"URL":"https:\/\/doi.org\/10.1145\/3723883","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,10]]},"assertion":[{"value":"2024-01-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}