Research map / Multi-agent systems and games / Games and equilibria
A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use λ-TSF, querying each agent's top item and value thresholds | One-sided matching with unrestricted valuations · One-sided matching, unrestricted valuations | distortion: unbounded -> 2 n^{1/(λ+1)} | Helped |
| Use ordinal preferences only, with no value queries | One-sided matching with unit-sum valuations · One-sided matching, unit-sum valuations | distortion: Θ(n^2) | Hurt |
| Use ordinal preferences only, with no value queries | One-sided matching with unrestricted valuations · One-sided matching, unrestricted valuations | distortion: unbounded | Hurt |
| Use k-FMM, querying one boundary value in each of the first k item sets | One-sided matching on k-well-structured instances · k-well-structured one-sided matching | distortion: O(k \cdot n^{1/k}) | Helped |
| Use FPA with at most two adaptive value queries per agent | One-sided matching with unit-sum valuations · One-sided matching, unit-sum valuations | distortion: O(n^{2/3}\sqrt{\log{n}}) | Helped |
| Allow k value queries per agent | Any matching algorithm for unrestricted valuations · One-sided matching, unrestricted valuations | distortion: Ω(\frac{1}{k} \cdot n^{1/k}) | Hurt |
| Allow k value queries per agent under unit-sum normalization | Any matching algorithm for unit-sum valuations · One-sided matching, unit-sum valuations | distortion: Ω(\frac{1}{k} \cdot n^{1/(k+1)}) | Hurt |
| Use (λ,A)-TSF with a ρ-approximation algorithm on simulated values | Ordinal-Max-on-Graphs · Ordinal-Max-on-Graphs | distortion: 3 ρ \, r^{\frac{1}{\lambda+1}} | Helped |
Closest papers by meaning
- Every Bit Helps: Achieving the Optimal Distortion with a Few Queries (AAAI 2025 · similarity 0.91)
- Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity (AAAI 2025 · similarity 0.88)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.87)
- Can a Few Decide for Many? The Metric Distortion of Sortition (ICML 2024 · similarity 0.87)
- Improved Metric Distortion via Threshold Approvals (AAAI 2024 · similarity 0.87)
- Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning (NeurIPS 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.