More Web Proxy on the site http://driver.im/

research-article

Public Access

Knapsack Voting for Participatory Budgeting

Authors:

Anilesh K. Krishnaswamy,

Sukolsak Sakshuwong,

Tanja AitamurtoAuthors Info & Claims

ACM Transactions on Economics and Computation (TEAC), Volume 7, Issue 2

Article No.: 8, Pages 1 - 27

https://doi.org/10.1145/3340230

Published: 29 July 2019 Publication History

All formats PDF

Abstract

We address the question of aggregating the preferences of voters in the context of participatory budgeting. We scrutinize the voting method currently used in practice, underline its drawbacks, and introduce a novel scheme tailored to this setting, which we call “Knapsack Voting.” We study its strategic properties—we show that it is strategy-proof under a natural model of utility (a dis-utility given by the ℓ₁ distance between the outcome and the true preference of the voter) and “partially” strategy-proof under general additive utilities. We extend Knapsack Voting to more general settings with revenues, deficits, or surpluses and prove a similar strategy-proofness result. To further demonstrate the applicability of our scheme, we discuss its implementation on the digital voting platform that we have deployed in partnership with the local government bodies in many cities across the nation. From voting data thus collected, we present empirical evidence that Knapsack Voting works well in practice.

References

[1]

Francisco J. André, M. Alejandro Cardenete, and Carlos Romero. 2010. Designing Public Policies: An Approach Based on Multi-criteria Analysis and Computable General Equilibrium Modeling. Vol. 642. Springer Science 8 Business Media.

Digital Library

[2]

Kenneth J. Arrow. 2012. Social Choice and Individual Values. Vol. 12. Yale University Press.

[3]

Salvador Barberà, Faruk Gul, and Ennio Stacchetti. 1993. Generalized median voter schemes and committees. J. Econ. Theory 61, 2 (1993), 262--289.

[4]

Salvador Barberà, Jordi Massó, and Alejandro Neme. 1997. Voting under constraints. J. Econ. Theory 76, 2 (1997), 298--321.

[5]

Gerdus Benade, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. 2017. Preference elicitation for participatory budgeting. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI’17). 376--382.

Digital Library

[6]

Sanjai Bhagat and James A. Brickley. 1984. Cumulative voting: The value of minority shareholder voting rights. J. Law Econ. 27, 2 (1984), 339--365.

[7]

Duncan Black. 1948. The decisions of a committee using a special majority. Econometrica 16, 3 (1948), 245--261.

[8]

Kim C. Border and James S. Jordan. 1983. Straightforward elections, unanimity and phantom voters. Rev. Econ. Stud. 50, 1 (1983), 153--170.

[9]

Steven J. Brams. 1990. Constrained approval voting: A voting system to elect a governing board. Interfaces 20, 5 (1990), 67--80.

Digital Library

[10]

Steven J. Brams. 1993. Approval voting and the good society. PEGS Newslett. 3, 1 (1993), 10--14.

[11]

Steven J. Brams and Peter C. Fishburn. 1978. Approval Voting. Vol. 72. Cambridge University Press. 831--847 pages.

[12]

Steven J. Brams and Peter C. Fishburn. 2002. Voting procedures, Ch. 4 in the Handbook of Social Choice and Welfare, Vol. 1 (2002).

[13]

Eric Budish. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Pol. Econ. 119, 6 (2011), 1061--1103.

[14]

Yves Cabannes. 2004. Participatory budgeting: A significant contribution to participatory democracy. Environ. Urban. 16, 1 (2004), 27--46.

[15]

Donald E. Campbell and Jerry S. Kelly. 2000. Weak independence and veto power. Econ. Lett. 66, 2 (2000), 183--189.

[16]

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2016. The unreasonable fairness of maximum Nash welfare. In Proceedings of the 2016 ACM Conference on Economics and Computation. ACM, 305--322.

Digital Library

[17]

Vince Conitzer, Markus Brill, and Rupert Freeman. 2015. Crowdsourcing societal tradeoffs. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1213--1217.

Digital Library

[18]

Vincent Conitzer and Tuomas Sandholm. 2012. Common voting rules as maximum likelihood estimators. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI'05). 145--152.

Digital Library

[19]

Varsha Dani. 2017. Truthful and near-optimal mechanisms for welfare maximization in participatory budgeting. (unpublished).

[20]

Nelson Dias. 2014. Hope for democracy: 25 years of participatory budgeting worldwide. www.in-loco.pt.

[21]

John Duggan and Thomas Schwartz. 2000. Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized. Soc. Choice Welfare 17, 1 (2000), 85--93.

[22]

Brandon Fain, Ashish Goel, and Kamesh Munagala. 2016. The core of the participatory budgeting problem. In Proceedings of the International Conference on Web and Internet Economics. Springer, 384--399.

Digital Library

[23]

Rupert Freeman, David M Pennock, Dominik Peters, and Jennifer Wortman Vaughan. 2019. Truthful aggregation of budget proposals. arXiv preprint arXiv:1905.00457 (2019).

Digital Library

[24]

Ernesto Ganuza and Gianpaolo Baiocchi. 2012. The power of ambiguity: How participatory budgeting travels the globe. J. Publ. Delib. 8, 2 (2012), 8.

[25]

Nikhil Garg, Vijay Kamble, Ashish Goel, David Marn, and Kamesh Munagala. 2017. Collaborative optimization for collective decision-making in continuous spaces. In Proceedings of the 26th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 617--626.

Digital Library

[26]

Allan Gibbard. 1973. Manipulation of voting schemes: A general result. Econometrica 41, 4 (1973), 587--601.

[27]

Nam Wook Kim, Jonghyuk Jung, Eun-Young Ko, Songyi Han, Chang Won Lee, Juho Kim, and Jihee Kim. 2016. Budgetmap: Engaging taxpayers in the issue-driven classification of a government budget. In Proceedings of the 19th ACM Conference on Computer-Supported Cooperative Work 8 Social Computing. ACM, 1028--1039.

Digital Library

[28]

Christian Klamler, Ulrich Pferschy, and Stefan Ruzika. 2012. Committee selection under weight constraints. Math. Soc. Sci. 64, 1 (2012), 48--56.

[29]

Jonathan Levin and Barry Nalebuff. 1995. An introduction to vote-counting schemes. J. Econ. Perspect. 9, 1 (1995), 3--26.

[30]

Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce. ACM, 125--131.

Digital Library

[31]

Tyler Lu and Craig Boutilier. 2011. Budgeted social choice: From consensus to personalized decision making. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI’11). 280--286.

Digital Library

[32]

Hervé Moulin. 1980. On strategy-proofness and single peakedness. Public Choice 35, 4 (1980), 437--455.

[33]

K. Nehring and Clemens Puppe. 2002. Strategy-proof social choice on single-peaked domains: Possibility, impossibility and the space between. Unpublished, Department of Economics, University of California at Davis.

[34]

Richard G. Niemi. 1984. The problem of strategic behavior under approval voting. Am. Pol. Sci. Rev. 78, 4 (1984), 952--958.

[35]

Carole Pateman. 2012. Participatory democracy revisited. Perspect. Pol. 10, 1 (2012), 7--19.

[36]

Participatory Budgeting Project (PBP). 2016. Where has it worked? Retrieved from http://www.participatorybudgeting.org/about-participatory-budgeting/where-has-it-worked/.

[37]

Ariel D. Procaccia, Sashank J. Reddi, and Nisarg Shah. 2012. A maximum likelihood approach for selecting sets of alternatives. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI'12). 695--704.

Digital Library

[38]

Mark Allen Satterthwaite. 1975. Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. J. Econ. Theory 10, 2 (1975), 187--217.

[39]

Aaron Schneider and Ben Goldfrank. 2002. Budgets and ballots in Brazil: Participatory budgeting from the city to the state. Working Paper Series 149 (2002). Institute of Development Studies, Brighton, UK.

[40]

Graham Smith. 2009. Democratic Innovations: Designing Institutions for Citizen Participation. Cambridge University Press, Cambridge.

[41]

H. Peyton Young. 1974. An axiomatization of Borda’s rule. J. Econ. Theory 9, 1 (1974), 43--52.

[42]

H. Peyton Young. 1988. Condorcet’s theory of voting. Am. Pol. Sci. Rev. 82, 4 (1988), 1231--1244.

Cited By

Rey SEndriss U(2025)Epistemic selection of costly alternatives: the case of participatory budgetingAutonomous Agents and Multi-Agent Systems10.1007/s10458-024-09677-239:1Online publication date: 1-Jun-2025
https://dl.acm.org/doi/10.1007/s10458-024-09677-2
Sreedurga GDastani MSichman JAlechina NDignum V(2024)Hybrid Participatory Budgeting: Divisible, Indivisible, and BeyondProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663200(2480-2482)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663200
Faliszewski PJaneczko ŁKaczmarczyk ALisowski GSkowron PSzufa SDastani MSichman JAlechina NDignum V(2024)Strategic Cost Selection in Participatory BudgetingProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663125(2255-2257)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663125
Show More Cited By

Index Terms

Knapsack Voting for Participatory Budgeting

Recommendations

Optimized Distortion and Proportional Fairness in Voting
EC '22: Proceedings of the 23rd ACM Conference on Economics and Computation

A voting rule decides on a probability distribution over a set of m alternatives, based on rankings of those alternatives provided by agents. We assume that agents have cardinal utility functions over the alternatives, but voting rules have access to ...
Coordinating Monetary Contributions in Participatory Budgeting
Algorithmic Game Theory
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 discrete participatory budgeting model as a ...
Welfare vs. Representation in Participatory Budgeting
AAMAS '22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems

Participatory budgeting (PB) is a democratic process for allocating funds to projects based on the votes of members of the community. Different rules have been used to aggregate participants' votes.

A recent paper by Lackner and Skowron [12] studied the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Economics and Computation

ACM Transactions on Economics and Computation Volume 7, Issue 2

May 2019

170 pages

ISSN:2167-8375

EISSN:2167-8383

DOI:10.1145/3340299

Editors:
David Pennock
Microsoft
,
Ilya Segal
Stanford University

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2019

Accepted: 01 May 2019

Revised: 01 November 2018

Received: 01 April 2017

Published in TEAC Volume 7, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

59
Total Citations
View Citations
2,106
Total Downloads

Downloads (Last 12 months)448
Downloads (Last 6 weeks)72

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rey SEndriss U(2025)Epistemic selection of costly alternatives: the case of participatory budgetingAutonomous Agents and Multi-Agent Systems10.1007/s10458-024-09677-239:1Online publication date: 1-Jun-2025
https://dl.acm.org/doi/10.1007/s10458-024-09677-2
Sreedurga GDastani MSichman JAlechina NDignum V(2024)Hybrid Participatory Budgeting: Divisible, Indivisible, and BeyondProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663200(2480-2482)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663200
Faliszewski PJaneczko ŁKaczmarczyk ALisowski GSkowron PSzufa SDastani MSichman JAlechina NDignum V(2024)Strategic Cost Selection in Participatory BudgetingProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663125(2255-2257)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663125
Serramia MLopez-Sanchez MRodriguez-Aguilar JMoretti SDastani MSichman JAlechina NDignum V(2024)Value Alignment in Participatory BudgetingProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663030(1692-1700)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663030
Köppe MKoutecký MSornat KTalmon NDastani MSichman JAlechina NDignum V(2024)Fine-Grained Liquid Democracy for Cumulative BallotsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662958(1029-1037)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662958
Böttcher LKlingebiel R(2024)Organizational Selection of InnovationOrganization Science10.1287/orsc.2023.17357Online publication date: 19-Sep-2024
https://doi.org/10.1287/orsc.2023.17357
Balcan MDeblasio DDick TKingsford CSandholm TVitercik E(2024)How Much Data Is Sufficient to Learn High-Performing Algorithms?Journal of the ACM10.1145/367627871:5(1-58)Online publication date: 29-Jul-2024
https://dl.acm.org/doi/10.1145/3676278
Yang JHausladen CPeters DPournaras EHnggli Fricker RHelbing D(2024)Designing Digital Voting Systems for Citizens: Achieving Fairness and Legitimacy in Participatory BudgetingDigital Government: Research and Practice10.1145/36653325:3(1-30)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3665332
Gelauff LGoel A(2024)Opinion Change or Differential Turnout: Changing Opinions on the Austin Police Department in a Budget Feedback ProcessDigital Government: Research and Practice10.1145/36648225:3(1-32)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3664822
Cui SHan KTang SLi FLuo JBaeza-Yates RBonchi F(2024)Fairness in Streaming Submodular Maximization Subject to a Knapsack ConstraintProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671778(514-525)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671778
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents