2025/04/11 by Dimitris Fotakis, Laurent Gourvès, Panagiotis Patsilinakos · 1 voice
Computer Science · Economics, Econometrics and Finance · #Advanced Algebra and Logic #Game Theory and Voting Systems #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.1609/aaai.v39i13.33516
openalex publication_date 2025/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We consider committee election of k >= 3 (out of m >= k + 1) candidates, where the voters and the candidates are associated with locations on the real line. Each voter’s cardinal preferences over candidates correspond to her distance to the candidate locations, and each voter’s cardinal preferences over committees is defined as her distance to the nearest candidate elected in the committee. We consider a setting where the true distances and the locations are unknown. We can nevertheless have access to degraded information which consists of an order of candidates for each voter. We investigate the best possible distortion (a worst-case performance criterion) w.r.t. the social cost achieved by deterministic committee election rules based on ordinal preferences submitted by n voters and few additional distance queries. We show that for any k >= 3, the best possible distortion of any deterministic rule that uses at most k−3 distance queries cannot be bounded by any function of n, m and k. We present deterministic rules for k-committee election with distortion of O(n) with O(k) distance queries and O(1) with O(k log(n)) distance queries.