Research map / Multi-agent systems and games / Games and equilibria
Every Bit Helps: Achieving the Optimal Distortion with a Few Queries
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.
Shows that λ cardinal value queries per agent suffice for O(n^{1/λ}) distortion in one-sided matching (and O(λ·min{n,m}^{1/λ}) in single-winner voting), matching lower bounds up to constants.
Problem
Optimal distortion achievable in one-sided matching and single-winner elections when agents' ordinal rankings are supplemented by a small constant number of cardinal value queries per agent.
Approach
A deterministic λ-round algorithm using capacity-based serial dictatorship to build stable sets of matchings (or approximately stable committees) whose sizes shrink geometrically (n^{1-(ℓ-1)/λ}), with each round's queries informing the next round's weights; the final matching maximizes welfare under the guaranteed lower-bound utilities.
Key results
- Deterministic λ-query matching mechanism achieves distortion λ·n^{1/λ}, giving O(n^{1/3}) with three queries per agent versus previously requiring O(log n) queries.
- Single-winner voting mechanism achieves O(λ·min{n,m}^{1/λ}) distortion, settling optimal constant-query distortion up to constants.
- With log n queries, distortion O(log n) is achieved, improving the previous O(log^2 n / log log n) query requirement for that bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use λ cardinal queries per agent, for constant λ | One-sided matching · One-sided matching | distortion: O(n1/λ); prior lower bound Ω(n1/λ) | Helped |
| Increase the query budget to three queries per agent | One-sided matching · One-sided matching | distortion: O(n1/3) | Helped |
| Use log n queries per agent | One-sided matching · One-sided matching | distortion: O(log n) | Helped |
| Use λ cardinal queries per agent | Single-winner voting · Single-winner elections | distortion: O(λ·(min{n, m})1/λ) | Helped |
| Use a stable lottery under unit-range utilities | Single-winner voting · Single-winner elections | distortion: O(min{√n, √m}) | Helped |
Surprising findings
- Exactly stable sets of matchings always exist, unlike approximately stable committees in general committee selection, where exact stability may fail.
Limitations
- Strong dependence between adaptive rounds of queries; non-adaptive mechanisms not studied.
- Asymptotic bounds only; constant factors (λ) matter and the gap between log n and constant distortion remains open.
Experimental setup
Metrics: distortion
Baselines: Amanatidis et al. 2024 Amanatidis et al. 2022 Amanatidis et al. 2021 Caragiannis and Fehrs 2023
Builds on: Amanatidis et al. 2024 two-query sqrt(n) mechanism Amanatidis et al. 2022 lambda-query mechanism Jiang, Munagala, and Wang 2020 approximately stable committees
Closest papers by meaning
- Improved Metric Distortion via Threshold Approvals (AAAI 2024 · similarity 0.90)
- Can a Few Decide for Many? The Metric Distortion of Sortition (ICML 2024 · similarity 0.90)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.89)
- Low-Distortion Clustering with Ordinal and Limited Cardinal Information (AAAI 2024 · similarity 0.87)
- Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity (AAAI 2025 · similarity 0.86)
- Eliciting Kemeny Rankings (AAAI 2024 · similarity 0.85)
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.