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

research-article

The metric distortion of multiwinner voting

Authors:

Ioannis Caragiannis,

Alexandros A. VoudourisAuthors Info & Claims

Volume 313, Issue C

https://doi.org/10.1016/j.artint.2022.103802

Published: 01 December 2022 Publication History

Abstract

We extend the recently introduced framework of metric distortion to multiwinner voting. In this framework, n agents and m alternatives are located in an underlying metric space. The exact distances between agents and alternatives are unknown. Instead, each agent provides a ranking of the alternatives, ordered from the closest to the farthest. Typically, the goal is to select a single alternative that approximately minimizes the total distance from the agents, and the worst-case approximation ratio is termed distortion. In the case of multiwinner voting, the goal is to select a committee of k alternatives that (approximately) minimizes the total cost to all agents. We consider the scenario where the cost of an agent for a committee is her distance from the q-th closest alternative in the committee. We reveal a surprising trichotomy on the distortion of multiwinner voting rules in terms of k and q: The distortion is unbounded when q ⩽ k / 3, asymptotically linear in the number of agents when k / 3 < q ⩽ k / 2, and constant when q > k / 2.

References

[1]

Elliot Anshelevich, John Postl, Randomized social choice functions under metric preferences, J. Artif. Intell. Res. 58 (2017) 797–827.

[2]

Elliot Anshelevich, Onkar Bhardwaj, John Postl, Approximating optimal social choice under metric preferences, in: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), 2015, pp. 777–783.

[3]

Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah, Alexandros A. Voudouris, Distortion in social choice problems: the first 15 years and beyond, in: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), 2021, pp. 4294–4301.

[4]

Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, Toby Walsh, Justified representation in approval-based committee voting, Soc. Choice Welf. 48 (2) (2017) 461–485.

[5]

Gerdus Benadè, Swaprava Nath, Ariel D. Procaccia, Nisarg Shah, Preference elicitation for participatory budgeting, Manag. Sci. 67 (5) (2021) 2813–2827.

[6]

Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel D. Procaccia, Or Sheffet, Optimal social choice functions: a utilitarian view, Artif. Intell. 227 (2015) 190–213.

[7]

Robert Bredereck, Piotr Faliszewski, Ayumi Igarashi, Martin Lackner, Piotr Skowron, Multiwinner elections with diversity constraints, in: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), 2018, pp. 933–940.

[8]

Ioannis Caragiannis, Ariel D. Procaccia, Voting almost maximizes social welfare despite limited communication, Artif. Intell. 175 (9–10) (2011) 1655–1671.

[9]

Ioannis Caragiannis, Swaprava Nath, Ariel D. Procaccia, Nisarg Shah, Subset selection via implicit utilitarian voting, J. Artif. Intell. Res. 58 (2017) 123–152.

[10]

John R. Chamberlin, Paul N. Courant, Representative deliberations and representative decisions: proportional representation and the Borda rule, Am. Polit. Sci. Rev. 77 (3) (1983) 718–733.

[11]

Moses Charikar, Prasanna Ramakrishnan, Metric distortion bounds for randomized social choice, in: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022, pp. 2986–3004.

[12]

Xujin Chen, Minming Li, Chenhao Wang, Favorite-candidate voting for eliminating the least popular candidate in a metric space, in: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), 2020, pp. 1894–1901.

[13]

Soroush Ebadian, Anson Kahng, Dominik Peters, Nisarg Shah, Optimized distortion and proportional fairness in voting, in: Proceedings of the 23rd ACM Conference on Economics and Computation (EC), 2022.

[14]

Edith Elkind, Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Properties of multiwinner voting rules, Soc. Choice Welf. 48 (3) (2017) 599–632.

[15]

Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon, Multiwinner voting: a new challenge for social choice theory, Trends Comput. Soc. Choice 74 (2017) (2017) 27–47.

[16]

Uriel Feige, A threshold of ln ⁡ n for approximating set cover, J. ACM 45 (4) (1998) 643–652.

[17]

Allan Gibbard, Manipulation of voting schemes, Econometrica 41 (1973) 587–602.

[18]

Vasilis Gkatzelis, Daniel Halpern, Nisarg Shah, Resolving the optimal metric distortion conjecture, in: Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2020, pp. 1427–1438.

[19]

Ashish Goel, Anilesh K. Krishnaswamy, Kamesh Munagala, Metric distortion of social choice rules: lower bounds and fairness properties, in: Proceedings of the 2017 ACM Conference on Economics and Computation (EC), 2017, pp. 287–304.

[20]

Goel, Ashish; Hulett, Reyna; Krishnaswamy, Anilesh Kollagunta (2018): Relating metric distortion and fairness of social choice rules. arXiv:1810.01092.

[21]

Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc. 58 (301) (1963) 13–30.

[22]

Michal Jaworski, Piotr Skowron, Evaluating committees for representative democracies: the distortion and beyond, in: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), 2020, pp. 196–202.

[23]

David Kempe, Communication, distortion, and randomness in metric voting, in: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), 2020, pp. 2087–2094.

[24]

David Kempe, An analysis framework for metric voting based on LP duality, in: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), 2020, pp. 2079–2086.

[25]

Tyler Lu, Craig Boutilier, Budgeted social choice: from consensus to personalized decision making, in: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), 2011, pp. 280–286.

[26]

Reshef Meir, Fedor Sandomirskiy, Moshe Tennenholtz, Representative committees of peers, J. Artif. Intell. Res. 71 (2021) 401–429.

[27]

Burt L. Monroe, Fully proportional representation, Am. Polit. Sci. Rev. 89 (4) (1995) 925–940.

[28]

Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

Digital Library

[29]

Kamesh Munagala, Kangning Wang, Improved metric distortion for deterministic social choice rules, in: Proceedings of the 2019 ACM Conference on Economics and Computation (EC), 2019, pp. 245–262.

[30]

Dominik Peters, Piotr Skowron, Proportionality and the limits of welfarism, in: Proceedings of the 21st ACM Conference on Economics and Computation (EC), 2020, pp. 793–794.

[31]

Dominik Peters, Grzegorz Pierczynski, Nisarg Shah, Piotr Skowron, Market-based explanations of collective decisions, in: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021, pp. 5656–5663.

[32]

Ariel D. Procaccia, Jeffrey S. Rosenschein, The distortion of cardinal preferences in voting, in: International Workshop on Cooperative Information Agents (CIA), 2006, pp. 317–331.

[33]

Ariel D. Procaccia, Jeffrey S. Rosenschein, Aviv Zohar, On the complexity of achieving proportional representation, Soc. Choice Welf. 30 (3) (2008) 353–362.

[34]

Mark A. Satterthwaite, Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions, J. Econ. Theory 10 (1975) 187–217.

[35]

Piotr Skowron, Edith Elkind, Social choice under metric preferences: scoring rules and STV, in: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI), 2017, pp. 706–712.

Cited By

Latifian MVoudouris ALarson K(2024)The distortion of threshold approval matchingProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/316(2851-2859)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/316
Kalayci YKempe DKher VWooldridge MDy JNatarajan S(2024)Proportional representation in metric spaces and low-distortion committee selectionProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i9.28841(9815-9823)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i9.28841
Charikar MRamakrishnan PWang KWu H(2024)Breaking the Metric Voting Distortion BarrierJournal of the ACM10.1145/368962571:6(1-33)Online publication date: 20-Sep-2024
https://dl.acm.org/doi/10.1145/3689625
Show More Cited By

Index Terms

The metric distortion of multiwinner voting

Index terms have been assigned to the content through auto-classification.

Recommendations

Metric Distortion Under Public-Spirited Voting
AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems

We investigate the impact of public-spirited voting on the distortion in the metric framework. We employ the public-spirited model proposed by Flanigan et. al. [3] (EC'23) to model the public-spirited behavior of the agents and evaluate the distortion of ...
On the Complexity of Candidates-Embedded Multiwinner Voting under the Hausdorff Function
AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems

We study candidates-embedded approval-based multiwinner voting. In this model, we are given a metric ƒ on the set of candidates, and voters are free to approve or disapprove any candidates. The task is to select a k-committee that either minimizes the ...
Bounded Approval Ballots: Balancing Expressiveness and Simplicity for Multiwinner Elections
AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

Approval ballots have been celebrated for many voting scenarios [16], in particular because of the low cognitive burden they put on the voters. This however, comes at the cost of expressiveness that can be problematic when voters have sophisticated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Artificial Intelligence

Artificial Intelligence Volume 313, Issue C

Dec 2022

415 pages

ISSN:0004-3702

Issue’s Table of Contents

The Author(s).

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 December 2022

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Latifian MVoudouris ALarson K(2024)The distortion of threshold approval matchingProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/316(2851-2859)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/316
Kalayci YKempe DKher VWooldridge MDy JNatarajan S(2024)Proportional representation in metric spaces and low-distortion committee selectionProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i9.28841(9815-9823)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i9.28841
Charikar MRamakrishnan PWang KWu H(2024)Breaking the Metric Voting Distortion BarrierJournal of the ACM10.1145/368962571:6(1-33)Online publication date: 20-Sep-2024
https://dl.acm.org/doi/10.1145/3689625
Ebadian SKahng APeters DShah N(2024)Optimized Distortion and Proportional Fairness in VotingACM Transactions on Economics and Computation10.1145/364076012:1(1-39)Online publication date: 19-Jan-2024
https://dl.acm.org/doi/10.1145/3640760
Kizilkaya FKempe DLeyton-Brown KSamuelson LHartline J(2023)Generalized Veto Core and a Practical Voting Rule with Optimal Metric DistortionProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597798(913-936)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597798
Gkatzelis VLatifian MShah NLeyton-Brown KSamuelson LHartline J(2023)Best of Both Distortion WorldsProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597739(738-758)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597739
Ebadian SKehne GMicha EProcaccia AShah NKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Is sortition both representative and fair?Proceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3600518(3431-3443)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3600518

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents