IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2206.05966.html

Coordinating Monetary Contributions in Participatory Budgeting

Author

Listed:
  • Haris Aziz
  • Sujit Gujar
  • Manisha Padala
  • Mashbat Suzuki
  • Jeremy Vollen

Abstract

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 classical 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.

Suggested Citation

  • Haris Aziz & Sujit Gujar & Manisha Padala & Mashbat Suzuki & Jeremy Vollen, 2022. "Coordinating Monetary Contributions in Participatory Budgeting," Papers 2206.05966, arXiv.org, revised Feb 2023.
    • Handle: RePEc:arx:papers:2206.05966
    as

    Download full text from publisher

    File URL: https://arxiv.org/pdf/2206.05966
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Hervé Moulin & Scott Shenker, 2001. "Strategyproof sharing of submodular costs:budget balance versus efficiency," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 18(3), pages 511-533.
    2. Brandl, Florian & Brandt, Felix & Greger, Matthias & Peters, Dominik & Stricker, Christian & Suksompong, Warut, 2022. "Funding public projects: A case for the Nash product rule," Journal of Mathematical Economics, Elsevier, vol. 99(C).
    3. Ohseto, Shinji, 2000. "Characterizations of Strategy-Proof Mechanisms for Excludable versus Nonexcludable Public Projects," Games and Economic Behavior, Elsevier, vol. 32(1), pages 51-66, July.
    4. Edith Elkind & Piotr Faliszewski & Piotr Skowron & Arkadii Slinko, 2017. "Properties of multiwinner voting rules," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(3), pages 599-632, March.
    5. Hervé Moulin, 1994. "Serial Cost-Sharing of Excludable Public Goods," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 61(2), pages 305-325.
    6. Dobzinski, Shahar & Mehta, Aranyak & Roughgarden, Tim & Sundararajan, Mukund, 2018. "Is Shapley cost sharing optimal?," Games and Economic Behavior, Elsevier, vol. 108(C), pages 130-138.
    7. Zubrickas, Robertas, 2014. "The provision point mechanism with refund bonuses," Journal of Public Economics, Elsevier, vol. 120(C), pages 231-234.
    8. repec:wbk:wbpubs:6640 is not listed on IDEAS
    9. D. Marc Kilgour, 2016. "Approval elections with a variable number of winners," Theory and Decision, Springer, vol. 81(2), pages 199-211, August.
    10. repec:wbk:wbpubs:6639 is not listed on IDEAS
    11. Eugene L. Lawler, 1979. "Fast Approximation Algorithms for Knapsack Problems," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 339-356, November.
    12. Vitalik Buterin & Zoë Hitzig & E. Glen Weyl, 2019. "A Flexible Design for Funding Public Goods," Management Science, INFORMS, vol. 65(11), pages 5171-5187, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Shichijo, Tatsuhiro & Fukuda, Emiko, 2021. "Cost-sharing mechanism for excludable goods with generalized non-rivalry," Journal of Economic Theory, Elsevier, vol. 193(C).
    2. Shinji Ohseto, 2010. "Serial Mechanisms For The Provision Of An Excludable Public Good," The Japanese Economic Review, Japanese Economic Association, vol. 61(4), pages 507-516, December.
    3. Kazuhiko Hashimoto & Hiroki Saitoh, 2016. "Strategy-proof rules for an excludable public good," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 46(4), pages 749-766, April.
    4. Kazuhiko Hashimoto & Kohei Shiozawa, 2018. "Strategy-Proofness and Efficiency of Probabilistic Mechanisms for Excludable Public Good," Working Papers e118, Tokyo Center for Economic Research.
    5. Hervé Moulin & Yves Sprumont, 2007. "Fair allocation of production externalities : recent results," Revue d'économie politique, Dalloz, vol. 117(1), pages 7-36.
    6. Dobzinski, Shahar & Mehta, Aranyak & Roughgarden, Tim & Sundararajan, Mukund, 2018. "Is Shapley cost sharing optimal?," Games and Economic Behavior, Elsevier, vol. 108(C), pages 130-138.
    7. Minghui Lai & Weili Xue & Qian Hu, 2019. "An Ascending Auction for Freight Forwarder Collaboration in Capacity Sharing," Transportation Science, INFORMS, vol. 53(4), pages 1175-1195, July.
    8. Olszewski, Wojciech, 2004. "Coalition strategy-proof mechanisms for provision of excludable public goods," Games and Economic Behavior, Elsevier, vol. 46(1), pages 88-114, January.
    9. Mackenzie, Andrew & Trudeau, Christian, 2023. "On Groves mechanisms for costly inclusion," Theoretical Economics, Econometric Society, vol. 18(3), July.
    10. Massó, Jordi & Nicolò, Antonio & Sen, Arunava & Sharma, Tridib & Ülkü, Levent, 2015. "On cost sharing in the provision of a binary and excludable public good," Journal of Economic Theory, Elsevier, vol. 155(C), pages 30-49.
    11. David McCune & Erin Martin & Grant Latina & Kaitlyn Simms, 2023. "A Comparison of Sequential Ranked-Choice Voting and Single Transferable Vote," Papers 2306.17341, arXiv.org.
    12. Aardal, Karen & van den Berg, Pieter L. & Gijswijt, Dion & Li, Shanfei, 2015. "Approximation algorithms for hard capacitated k-facility location problems," European Journal of Operational Research, Elsevier, vol. 242(2), pages 358-368.
    13. Tobias Harks & Martin Hoefer & Anja Schedel & Manuel Surek, 2021. "Efficient Black-Box Reductions for Separable Cost Sharing," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 134-158, February.
    14. Deb, Rajat & Razzolini, Laura & Seo, Tae Kun, 2003. "Strategy-proof cost sharing, ability to pay and free provision of an indivisible public good," Mathematical Social Sciences, Elsevier, vol. 45(2), pages 205-227, April.
    15. Nir Halman & Giacomo Nannicini, 2025. "Fully Polynomial Time Approximation Schemes for Robust Multistage Decision Making," INFORMS Journal on Computing, INFORMS, vol. 37(5), pages 1306-1327, September.
    16. Daria Dzyabura & Srikanth Jagabathula, 2018. "Offline Assortment Optimization in the Presence of an Online Channel," Management Science, INFORMS, vol. 64(6), pages 2767-2786, June.
    17. Xiaohui Bei & Xinhang Lu & Warut Suksompong, 2021. "Truthful Cake Sharing," Papers 2112.05632, arXiv.org, revised Feb 2022.
    18. Alfredo Valencia-Toledo & Juan Vidal-Puga, 2020. "Reassignment-proof rules for land rental problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(1), pages 173-193, March.
    19. Hines Jr., James R., 2000. "What is benefit taxation?," Journal of Public Economics, Elsevier, vol. 75(3), pages 483-492, March.
    20. Balireddi, Sindhura & Uhan, Nelson A., 2012. "Cost-sharing mechanisms for scheduling under general demand settings," European Journal of Operational Research, Elsevier, vol. 217(2), pages 270-277.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2206.05966. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: https://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.