Proportional Representation in Metric Spaces and Low-Distortion Committee Selection
Open Access
- 24 March 2024
- journal article
- research article
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (9) , 9815-9823
Abstract
We introduce a novel definition for a small set R of k points being "representative" of a larger set in a metric space. Given a set V (e.g., documents or voters) to represent, and a set C of possible representatives, our criterion requires that for any subset S comprising a theta fraction of V, the average distance of S to their best theta*k points in R should not be more than a factor gamma compared to their average distance to the best theta*k points among all of C. This definition is a strengthening of proportional fairness and core fairness, but - different from those notions - requires that large cohesive clusters be represented proportionally to their size. Since there are instances for which - unless gamma is polynomially large - no solutions exist, we study this notion in a resource augmentation framework, implicitly stating the constraints for a set R of size k as though its size were only k/alpha, for alpha > 1. Furthermore, motivated by the application to elections, we mostly focus on the "ordinal" model, where the algorithm does not learn the actual distances; instead, it learns only for each point v in V and each candidate pairs c, c' which of c, c' is closer to v. Our main result is that the Expanding Approvals Rule (EAR) of Aziz and Lee is (alpha, gamma) representative with gammaKeywords
This publication has 11 references indexed in Scilit:
- Proportional Representation in Metric Spaces and Low-Distortion Committee SelectionProceedings of the AAAI Conference on Artificial Intelligence, 2024
- Distortion in metric matching with ordinal preferences2023
- Ordinal Approximation for Social Choice, Matching, and Facility Location Problems Given Candidate PositionsACM Transactions on Economics and Computation, 2021
- Group Fairness in Committee SelectionACM Transactions on Economics and Computation, 2020
- The expanding approvals rule: improving proportional representation and monotonicitySocial Choice and Welfare, 2019
- Approximating optimal social choice under metric preferencesArtificial Intelligence, 2018
- Justified representation in approval-based committee votingSocial Choice and Welfare, 2017
- Optimal social choice functions: A utilitarian viewArtificial Intelligence, 2015
- Generalized Median Voter Schemes and CommitteesJournal of Economic Theory, 1993
- On strategy-proofness and single peakednessPublic Choice, 1980