{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T06:51:15Z","timestamp":1765176675008,"version":"3.46.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,7,9]],"date-time":"2025-07-09T00:00:00Z","timestamp":1752019200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,9]],"date-time":"2025-07-09T00:00:00Z","timestamp":1752019200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001773","name":"University of New South Wales","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001773","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We formalize a framework for coordinating funding and selecting projects, the costs of which are shared among agents with quasi-linear utility functions and individual budgets. Our model contains the discrete participatory budgeting model as a special case, while capturing other useful scenarios. We propose several important axioms and objectives and study how well they can be simultaneously satisfied. We show that whereas welfare maximization admits an FPTAS, welfare maximization subject to a natural and very weak participation requirement leads to a strong inapproximability. This result is bypassed if we consider some natural restricted valuations, namely laminar single-minded valuations and symmetric valuations. Our analysis for the former restriction leads to the discovery of a new class of tractable instances for the Set Union Knapsack problem, a classical problem in combinatorial optimization.<\/jats:p>","DOI":"10.1007\/s10458-025-09715-7","type":"journal-article","created":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T09:22:42Z","timestamp":1752139362000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Coordinating monetary contributions in participatory budgeting"],"prefix":"10.1007","volume":"39","author":[{"given":"Haris","family":"Aziz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sujit","family":"Gujar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manisha","family":"Padala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mashbat","family":"Suzuki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeremy","family":"Vollen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,9]]},"reference":[{"issue":"2","key":"9715_CR1","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1080\/15427951.2004.10129086","volume":"1","author":"A Archer","year":"2004","unstructured":"Archer, A., Papadimitriou, C., Talwar, K., et al. (2004). An approximate truthful mechanism for combinatorial auctions with single parameter agents. Internet Mathematics,1(2), 129\u2013150.","journal-title":"Internet Mathematics"},{"key":"9715_CR2","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.dam.2013.12.015","volume":"169","author":"A Arulselvan","year":"2014","unstructured":"Arulselvan, A. (2014). A note on the set union knapsack problem. Discrete Applied Mathematics,169, 214\u2013218.","journal-title":"Discrete Applied Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Aziz, H. (2020). Strategyproof multi-item exchange under single-minded dichotomous preferences. Autonomous Agents and Multi-Agent Systems,34(1).","key":"9715_CR3","DOI":"10.1007\/s10458-019-09426-w"},{"doi-asserted-by":"crossref","unstructured":"Aziz, H., & Ganguly, A. (2021). Participatory funding coordination: Model, axioms and rules. In: International conference on algorithmic decision theory, lecture notes in computer science, vol. 13023. Springer, pp. 409\u2013423.","key":"9715_CR4","DOI":"10.1007\/978-3-030-87756-9_26"},{"key":"9715_CR5","volume-title":"Pathways between Social Science and Computational Social Science: Theories","author":"H Aziz","year":"2020","unstructured":"Aziz, H., & Shah, N. (2020). Participatory budgeting: Models and approaches. In T. Rudas & P. G\u00e1bor (Eds.), Pathways between Social Science and Computational Social Science: Theories. Methods and Interpretations: Springer."},{"unstructured":"Aziz, H., Lee, B. E., & Talmon, N. (2018). Proportionally representative participatory budgeting: Axioms and algorithms. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pp. 23\u201331.","key":"9715_CR6"},{"doi-asserted-by":"crossref","unstructured":"Birmpas, G., Courcoubetis, C., Giotis, I., et al. (2015). Cost-Sharing Models in Participatory Sensing. In: Hoefer, M. (ed) Algorithmic game theory, vol. 9347. Springer, pp. 43\u201356.","key":"9715_CR7","DOI":"10.1007\/978-3-662-48433-3_4"},{"key":"9715_CR8","first-page":"1","volume-title":"27th Annual European Symposium on Algorithms, ESA 2019","author":"G Birmpas","year":"2019","unstructured":"Birmpas, G., Markakis, E., & Sch\u00e4fer, G. (2019). Cost sharing over combinatorial domains: Complement-free cost functions and beyond. 27th Annual European Symposium on Algorithms, ESA 2019 (pp. 1\u201317). Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH: Dagstuhl Publishing."},{"doi-asserted-by":"crossref","unstructured":"Brandl, F., Brandt, F., Greger, M., et al. (2022). Funding public projects: A case for the nash product rule. Journal of Mathematical Economics,99","key":"9715_CR9","DOI":"10.1016\/j.jmateco.2021.102585"},{"doi-asserted-by":"crossref","unstructured":"Brandt, F., Greger, M., Segal-Halevi, E., et al. (2023). Balanced donor coordination. arXiv:2305.10286.","key":"9715_CR10","DOI":"10.1145\/3580507.3597729"},{"unstructured":"Br\u00e2nzei, S., Lv, Y., & Mehta, R. (2016). To give or not to give: Fair division for single minded valuations. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. AAAI Press, New York, New York, USA, IJCAI\u201916, pp. 123\u2013129.","key":"9715_CR11"},{"issue":"11","key":"9715_CR12","doi-asserted-by":"publisher","first-page":"5171","DOI":"10.1287\/mnsc.2019.3337","volume":"65","author":"V Buterin","year":"2019","unstructured":"Buterin, V., Hitzig, Z., & Weyl, E. G. (2019). A Flexible Design for Funding Public Goods. Management Science,65(11), 5171\u20135187.","journal-title":"Management Science"},{"doi-asserted-by":"crossref","unstructured":"Chen, J., Lackner, M., & Maly, J. (2022). Participatory budgeting with donations and diversity constraints. In: Proceedings of the AAAI conference on artificial intelligence, pp. 9323\u20139330.","key":"9715_CR13","DOI":"10.1609\/aaai.v36i9.21163"},{"issue":"4","key":"9715_CR14","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1016\/j.jcss.2004.04.012","volume":"69","author":"N Chen","year":"2004","unstructured":"Chen, N., Deng, X., & Sun, X. (2004). On complexity of single-minded auction. Journal of Computer and System Sciences,69(4), 675\u2013687.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Damle, S., Moti, M. H., Chandra, P., et al. (2019). Civic crowdfunding for agents with negative valuations and agents with asymmetric beliefs. In: Proceedings of the 28th international joint conference on artificial intelligence, pp. 208\u2013214.","key":"9715_CR15","DOI":"10.24963\/ijcai.2019\/30"},{"issue":"2","key":"9715_CR16","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1287\/opre.5.2.266","volume":"5","author":"GB Dantzig","year":"1957","unstructured":"Dantzig, G. B. (1957). Discrete-Variable Extremum Problems. Operations Research,5(2), 266\u2013288. https:\/\/doi.org\/10.1287\/opre.5.2.266","journal-title":"Operations Research"},{"doi-asserted-by":"crossref","unstructured":"Devanur, N. R., Goldner, K., Saxena, R. R., et al. (2020). Optimal mechanism design for single-minded agents. In: Proceedings of the 21st ACM conference on economics and computation, pp. 193\u2013256.","key":"9715_CR17","DOI":"10.1145\/3391403.3399454"},{"doi-asserted-by":"crossref","unstructured":"Dobzinski, S., & Ovadia, S. (2017). Combinatorial cost sharing. In: Proceedings of the 2017 ACM conference on economics and computation, pp. 387\u2013404.","key":"9715_CR18","DOI":"10.1145\/3033274.3085141"},{"doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Mehta, A., Roughgarden, T., et al. (2018). Is shapley cost sharing optimal? Games and Economic Behavior,108, 130\u2013138. Special Issue in Honor of Lloyd Shapley: Seven Topics in Game Theory","key":"9715_CR19","DOI":"10.1016\/j.geb.2017.03.008"},{"doi-asserted-by":"crossref","unstructured":"Elkind, E., Faliszewski, P., Skowron, P., et al. (2017). Properties of multiwinner voting rules. Social Choice and Welfare.","key":"9715_CR20","DOI":"10.1007\/s00355-017-1026-z"},{"key":"9715_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H: Freeman."},{"issue":"2","key":"9715_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3340230","volume":"7","author":"A Goel","year":"2019","unstructured":"Goel, A., Krishnaswamy, A. K., Sakshuwong, S., et al. (2019). Knapsack voting for participatory budgeting. ACM Transactions on Economics and Computation (TEAC),7(2), 1\u201327.","journal-title":"ACM Transactions on Economics and Computation (TEAC)"},{"issue":"6","key":"9715_CR23","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1002\/1520-6750(199410)41:6<833::AID-NAV3220410611>3.0.CO;2-Q","volume":"41","author":"O Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Nehme, D., & Yu, G. (1994). Note: On the set-union knapsack problem. Naval Research Logistics (NRL),41(6), 833\u2013842.","journal-title":"Naval Research Logistics (NRL)"},{"key":"9715_CR24","volume-title":"Incentives in Public Decision-Making,","author":"JR Green","year":"1979","unstructured":"Green, J. R., & Laffont, J. J. (1979). Incentives in Public Decision-Making, (Vol. 1). North-Holland."},{"key":"9715_CR25","doi-asserted-by":"publisher","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T Groves","year":"1973","unstructured":"Groves, T. (1973). Incentives in teams. Econometrica,41, 617\u2013631.","journal-title":"Econometrica"},{"key":"9715_CR26","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.future.2017.05.044","volume":"78","author":"Y He","year":"2018","unstructured":"He, Y., Xie, H., Wong, T. L., et al. (2018). A novel binary artificial bee colony algorithm for the set-union knapsack problem. Future Generation Computer Systems,78, 77\u201386.","journal-title":"Future Generation Computer Systems"},{"doi-asserted-by":"crossref","unstructured":"Hershkowitz, D. E., Kahng, A., Peters, D., et al. (2021). District-fair participatory budgeting. In: Proceedings of the AAAI conference on artificial intelligence, pp. 5464\u20135471.","key":"9715_CR27","DOI":"10.1609\/aaai.v35i6.16688"},{"doi-asserted-by":"crossref","unstructured":"Hoefer, M., & Kesselheim, T. (2012). Secondary spectrum auctions for symmetric and submodular bidders. In: Proceedings of the 13th ACM conference on electronic commerce, pp. 657\u2013671.","key":"9715_CR28","DOI":"10.1145\/2229012.2229062"},{"doi-asserted-by":"crossref","unstructured":"Jain, P., Sornat, K., & Talmon, N. (2020). Participatory budgeting with project interactions. In: Proceedings of the twenty-ninth international conference on international joint conferences on artificial intelligence, pp. 386\u2013392.","key":"9715_CR29","DOI":"10.24963\/ijcai.2020\/54"},{"issue":"2","key":"9715_CR30","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s11238-016-9535-2","volume":"81","author":"DM Kilgour","year":"2016","unstructured":"Kilgour, D. M. (2016). Approval elections with a variable number of winners. Theory and Decision,81(2), 199\u2013211.","journal-title":"Theory and Decision"},{"issue":"4","key":"9715_CR31","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"EL Lawler","year":"1979","unstructured":"Lawler, E. L. (1979). Fast approximation algorithms for knapsack problems. Mathematics of Operations Research,4(4), 339\u2013356.","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"9715_CR32","doi-asserted-by":"publisher","first-page":"305","DOI":"10.2307\/2297983","volume":"61","author":"H Moulin","year":"1994","unstructured":"Moulin, H. (1994). Serial cost-sharing of excludable public goods. The Review of Economic Studies,61(2), 305\u2013325.","journal-title":"The Review of Economic Studies"},{"unstructured":"Nehme-Haily, D. A. (1995). The set-union knapsack problem. PhD thesis, The University of Texas at Austin.","key":"9715_CR33"},{"issue":"1","key":"9715_CR34","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1006\/game.1999.0755","volume":"32","author":"S Ohseto","year":"2000","unstructured":"Ohseto, S. (2000). Characterizations of strategy-proof mechanisms for excludable versus nonexcludable public projects. Games and Economic Behavior,32(1), 51\u201366.","journal-title":"Games and Economic Behavior"},{"issue":"2","key":"9715_CR35","doi-asserted-by":"publisher","first-page":"233","DOI":"10.7155\/jgaa.00186","volume":"13","author":"U Pferschy","year":"2009","unstructured":"Pferschy, U., & Schauer, J. (2009). The Knapsack Problem with Conflict Graphs. J Graph Algorithms Appl,13(2), 233\u2013249.","journal-title":"J Graph Algorithms Appl"},{"doi-asserted-by":"crossref","unstructured":"Samuelson, P. A. (1954). The pure theory of public expenditure. The review of economics and statistics, pp 387\u2013389.","key":"9715_CR36","DOI":"10.2307\/1925895"},{"doi-asserted-by":"crossref","unstructured":"Shah, A. (2007). Participatory budgeting. World Bank Publications.","key":"9715_CR37","DOI":"10.1596\/978-0-8213-6923-4"},{"unstructured":"Stolicki, D., Szufa, S., & Talmon, N. (2020). Pabulib: A Participatory Budgeting Library. arXiv:2012.06539 [cs].","key":"9715_CR38"},{"doi-asserted-by":"crossref","unstructured":"Talmon, N., & Faliszewski, P. (2019). A framework for approval-based budgeting methods. In: Proceedings of the AAAI conference on artificial intelligence, pp. 2181\u20132188.","key":"9715_CR39","DOI":"10.1609\/aaai.v33i01.33012181"},{"key":"9715_CR40","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V. V. (2001). Approximation Algorithms. Springer."},{"unstructured":"Vries, M. S. D., Nemec, J., & \u0160pa\u010dek, D. (eds) (2020). International Trends in Participatory Budgeting: Between Trivial Pursuits and Best Practices. Springer.","key":"9715_CR41"},{"unstructured":"Wagner, J., & Meir, R. (2021). A vcg adaptation for participatory budgeting.","key":"9715_CR42"},{"unstructured":"Wang, G., Guo, R., Sakurai, Y., et al. (2021). Mechanism design for public projects via neural networks. In: Proceedings of the 20th international conference on autonomous agents and multi-agent systems, pp. 1380\u20131388.","key":"9715_CR43"},{"key":"9715_CR44","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1016\/j.future.2019.07.062","volume":"101","author":"Z Wei","year":"2019","unstructured":"Wei, Z., & Hao, J. K. (2019). Iterated two-phase local search for the Set-Union Knapsack Problem. Future Generation Computer Systems,101, 1005\u20131017.","journal-title":"Future Generation Computer Systems"},{"unstructured":"Yan, X., & Chen, Y. (2021). Optimal crowdfunding design. In: Proceedings of the 20th international conference on autonomous agents and multi-agent systems, pp. 1704\u20131706.","key":"9715_CR45"},{"key":"9715_CR46","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.jpubeco.2014.10.006","volume":"120","author":"R Zubrickas","year":"2014","unstructured":"Zubrickas, R. (2014). The provision point mechanism with refund bonuses. Journal of Public Economics,120, 231\u2013234.","journal-title":"Journal of Public Economics"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-025-09715-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-025-09715-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-025-09715-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T06:46:52Z","timestamp":1765176412000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-025-09715-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,9]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["9715"],"URL":"https:\/\/doi.org\/10.1007\/s10458-025-09715-7","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"type":"print","value":"1387-2532"},{"type":"electronic","value":"1573-7454"}],"subject":[],"published":{"date-parts":[[2025,7,9]]},"assertion":[{"value":"16 June 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"Springer journals and proceedings:\n                      \n                      Nature Portfolio journals:\n                      \n                      Scientific Reports\n                      :\n                      \n                      BMC journals:","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Editorial Policies for:"}}],"article-number":"34"}}