Every Bit Helps: Achieving the Optimal Distortion with a Few Queries

Soroush Ebadian, Nisarg Shah

TL;DR

This paper tackles the challenge of making optimal resource allocation decisions (like matching people to jobs or selecting a winner in an election) when we only have partial information about preferences. They introduce new algorithms that achieve near-optimal outcomes using a small, fixed number of "value queries" (asking about specific preferences) in addition to basic preference rankings, significantly improving upon previous methods.

What Problem Does This Paper Address?

In many real-world scenarios, like assigning office spaces to doctors or deciding on a new clinic location, we need to make decisions that maximize overall satisfaction or "social welfare." The ideal way to do this would be to know everyone's exact numerical preferences (their "utilities") for each option. However, collecting this detailed information can be burdensome. Typically, we only get ordinal rankings (e.g., "I prefer A over B"). This incomplete information leads to "distortion," a measure of how much worse the outcome is compared to the ideal scenario with full utility information.

Previous research showed that asking just a few targeted "value queries" could drastically reduce this distortion. For instance, asking two value queries per agent could achieve a certain level of improvement. However, the trade-off between the number of queries and the achievable distortion was not fully understood, especially for a small, constant number of queries beyond two. This paper aims to bridge that gap by developing algorithms that achieve optimal or near-optimal distortion with a fixed, small number of value queries for both matching and voting problems.

Methods

The core of this paper lies in developing novel algorithms for two key problems: one-sided matching (assigning agents to alternatives) and single-winner elections.

For one-sided matching, the authors propose a $\lambda$-query algorithm that achieves $O(n^{1/\lambda})$ distortion. This is a generalization of prior work, showing that with $\lambda$ queries, we can get significantly better results than with just two. The algorithm works by iteratively querying agents about their preferences for specific alternatives identified by a "serial dictatorship" process. The utilities learned from these queries are then used as weights in subsequent rounds, refining the selection of alternatives to query about. This iterative approach, combined with a concept of "stable matching sets," allows them to bound the distortion effectively.

For single-winner elections, they adapt their matching algorithm to achieve a distortion of $O((\min\{n, m\})^{1/\lambda})$, where $n$ is the number of agents and $m$ is the number of candidates. A key innovation here is the dependence on $\min\{n, m\}$, which is crucial for scenarios where the number of agents significantly exceeds the number of candidates. The algorithm leverages the concept of "approximately stable committees" to guide its queries.

Both algorithms are deterministic and run in polynomial time.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and algorithmic design rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The power of a few queries: The paper strongly demonstrates that even a small, fixed number of value queries can dramatically improve allocation outcomes, closing the gap between ordinal-only and full-utility scenarios.
  • Generalizing beyond two queries: The work extends previous findings from two queries to any constant number $\lambda$, providing a more flexible framework for balancing elicitation burden and outcome quality.
  • Bridging matching and voting: The paper shows how techniques developed for matching can be adapted to the voting setting, revealing a common underlying structure and enabling new results in voting theory.
  • The importance of $\min\{n, m\}$: For voting, the dependence on the minimum of agents and candidates is a significant insight, particularly for scenarios with many more agents than options, which was previously an open problem.
  • Deterministic algorithms are sufficient: The authors achieve optimal or near-optimal distortion bounds using deterministic algorithms, which are often preferred for their predictability and simplicity compared to randomized approaches.

Key Results

  • One-sided Matching: Achieves $O(n^{1/\lambda})$ distortion with $\lambda$ queries per agent, which is optimal up to a constant factor for constant $\lambda$. This generalizes prior results and settles open questions about the query-distortion trade-off.
  • Single-Winner Elections: Achieves $O((\min\{n, m\})^{1/\lambda})$ distortion with $\lambda$ queries per agent, also optimal for constant $\lambda$. This result is particularly impactful for scenarios where $n \gg m$.
  • Constant Distortion: For a constant number of queries ($\lambda = O(1)$), the distortion is $O(n^{1/\lambda})$ for matching and $O((\min\{n, m\})^{1/\lambda})$ for voting.

Limitations and Future Work

  • Adaptive vs. Non-adaptive Mechanisms: The current algorithms are adaptive, meaning queries in one round depend on the results of previous rounds. Future research could explore non-adaptive mechanisms, which might offer different trade-offs.
  • Cost of Ordinal Queries: The paper assumes ordinal queries are "free" and focuses on the cost of cardinal queries. A more nuanced approach could consider a budget for both types of queries.
  • Constant Factor Optimization: While the asymptotic bounds are optimal, there's still room for improvement in the constant factors, especially in the voting setting where a "black-box" reduction introduces a constant factor $\beta$ from approximate stability.
  • Achieving Constant Distortion with Minimal Queries: Settling the exact number of queries needed to achieve constant distortion (e.g., $O(1)$) in both matching and voting remains an open problem.

Summary updated

BibTeX
@inproceedings{ebadian2025every,
  author = {Soroush Ebadian and Nisarg Shah},
  title = {{Every Bit Helps: Achieving the Optimal Distortion with a Few Queries}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i13.33507},
}
Figure