Iterative local voting for collective decision-making in continuous spaces

DOI10.1613/JAIR.1.11358MaRDI QIDQ3120424zbMATH OpenOpenAlexFDO

Authors Nikhil Garg, Vijay Kamble, Ashish Goel, David Marn, Kamesh Munagala

Publication date 4 March 2019

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.07984

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Decision theory (91B06) Voting theory (91B12)

Abstract: Many societal decision problems lie in high-dimensional continuous spaces not amenable to the voting techniques common for their discrete or single-dimensional counterparts. These problems are typically discretized before running an election or decided upon through negotiation by representatives. We propose a algorithm called {sc Iterative Local Voting} for collective decision-making in this setting. In this algorithm, voters are sequentially sampled and asked to modify a candidate solution within some local neighborhood of its current value, as defined by a ball in some chosen norm, with the size of the ball shrinking at a specified rate. We first prove the convergence of this algorithm under appropriate choices of neighborhoods to Pareto optimal solutions with desirable fairness properties in certain natural settings: when the voters' utilities can be expressed in terms of some form of distance from their ideal solution, and when these utilities are additively decomposable across dimensions. In many of these cases, we obtain convergence to the societal welfare maximizing solution. We then describe an experiment in which we test our algorithm for the decision of the U.S. Federal Budget on Mechanical Turk with over 2,000 workers, employing neighborhoods defined by $mathcal{L}^1,mathcal{L}^2$ and $mathcal{L}^{i}nfty$ balls. We make several observations that inform future implementations of such a procedure.

Recommendations

• Iterated Majority Voting
• Iterative judgment aggregation
• Voting on multiple issues: what to put on the ballot?
• Continuous social decision procedures
• Sequential Deliberation for Social Choice

Cited in

(10)

• Truthful aggregation of budget proposals
• Markets for public decision-making
• Iterative deliberation via metric aggregation
• An Improved Threshold Approximation for Local Vote Decision Fusion
• Aggregation over metric spaces: proposing and voting in elections, budgeting, and legislation
• Representative committees of peers
• Strategy-proof budgeting via a VCG-like mechanism
• Strategy-proof budgeting via a VCG-like mechanism
• Truthful aggregation of budget proposals with proportionality guarantees
• Voting behavior in one-shot and iterative multiple referenda

This page was built for publication: Iterative local voting for collective decision-making in continuous spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3120424)