Research map / Multi-agent systems and games / Games and equilibria
Constant-Factor Distortion Mechanisms for k-Committee Election
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first constant-distortion mechanisms for k-committee election under the l-centrum (top-l) cost, using few value queries via a black-box metric reduction, sparsification, and adaptive sampling.
Problem
Ordinal k-committee election minimizing the sum of the l largest agent costs in a metric space; without cardinal information distortion is unbounded for k>=2 (k-median) and k>=3 in general, so the question is whether a few value queries can give O(1) distortion.
Approach
Elicit limited cardinal information via value queries and combine it with a black-box reduction to a cardinal l-centrum approximation, sparsification via a bicriteria facility-location (Meyerson-style) solution, and an adaptive sampling variant using the separable proxy (d(i,S)-t)^+ that yields per-agent query complexity independent of n and total query bounds polylogarithmic in n.
Key results
- O(1)-distortion mechanism with O(log k log n) value queries per agent
- Per-agent query bound independent of n: O~(k log(min{l, n/l})), via adaptive sampling
- Total query complexity O(k^2 log^2 n log l), so average queries per agent vanish as n grows
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use value-query mechanisms rather than ordinal information alone | k-committee ℓ-centrum · ℓ-centrum (k≥2) | distortion: unbounded -> O(1) | Helped |
| Use Meyerson-BB with a cardinal ℓ-centrum approximation algorithm | ℓ-centrum (A=C) · ℓ-centrum | distortion: O(1) | Helped |
| Use adaptive sampling with a threshold parameter tℓ | ℓ-centrum (A=C) · ℓ-centrum | approximation cost: 35(1+\varepsilon)·OPT | Helped |
| Implement adaptive sampling by sampling distance rings | ℓ-centrum (A=C) · ℓ-centrum | approximation cost: 50(1+2\varepsilon)·OPT | Helped |
| Use standard adaptive sampling for k-median on the ℓ-centrum objective | ℓ-centrum · ℓ-centrum (Top₁ / k-center) | probability of cost below L·OPT: < 2\epsilon | Hurt |
Surprising findings
- For k>=3 (and k=2 with Omega(n) distortion), no bounded-distortion mechanism exists using only ordinal information, even for k-median
Limitations
- Mechanisms are randomized and achieve O(1) distortion only with constant success probability; failure cannot be detected
- Approximation constants are large and not optimized
- Results established for A=C setting primarily; extension to A≠C is discussed separately
Experimental setup
Metrics: distortion per-agent query complexity total query complexity
Baselines: Anshelevich et al. ordinal lower bound Gonzalez k-center 2-approximation k-means++ adaptive sampling Aggarwal et al. adaptive sampling
Builds on: Meyerson facility location k-means++ adaptive sampling Boruvka's algorithm Gonzalez 2-approximation for k-center Anshelevich et al. distortion
Closest papers by meaning
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.92)
- Every Bit Helps: Achieving the Optimal Distortion with a Few Queries (AAAI 2025 · similarity 0.89)
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.88)
- Improved Metric Distortion via Threshold Approvals (AAAI 2024 · similarity 0.88)
- Metric Distortion of Line-up Elections: The Right Person for the Right Job (AAAI 2025 · similarity 0.87)
- Low-Distortion Clustering with Ordinal and Limited Cardinal Information (AAAI 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.