Abstract: In algorithmic economics, the one-sided matching problem seeks to assign items to agents to maximize social welfare. While agents' full numerical (cardinal) valuations are often difficult to elicit, relying solely on ranked (ordinal) preferences leads to significant efficiency losses, known as distortion. This paper explores the middle ground: how many cardinal queries are necessary to achieve low distortion? We show that while ordinal information results in $\Theta(n^2)$ distortion for unit-sum valuations and is unbounded for unrestricted valuations, a small number of queries can dramatically improve outcomes. Specifically, $O(\log^2 n)$ queries per agent are sufficient to achieve constant distortion, bridging the gap between ordinal and full-information settings.
Introduction
Matching is a fundamental problem in resource allocation, where $n$ items are assigned to $n$ agents. Ideally, an algorithm would utilize exact numerical valuations to maximize the sum of values (social welfare). However, eliciting precise values for every item is cognitively demanding for agents. Consequently, most systems rely on ordinal preferences—simple rankings. This paper, presented at AAAI-21, investigates whether asking a limited number of specific numerical questions can significantly reduce the distortion inherent in ordinal-only mechanisms.
Problem Definition and Distortion
The authors focus on the one-sided matching problem, also known as house allocation. The primary metric of interest is distortion, which quantifies the worst-case ratio between the maximum possible social welfare (attainable with full information) and the welfare achieved by an algorithm with limited information.
Previous results established that deterministic algorithms using only ordinal information suffer from a distortion of $\Theta(n^2)$ in the unit-sum case. The goal of this research is to determine if a small number of cardinal queries can break these lower bounds and provide meaningful guarantees for unrestricted valuations.
Algorithmic Framework
The researchers propose two main approaches:
- $\lambda$-ThresholdStepFunction ($\lambda$-TSF): This algorithm uses ordinal rankings to guide binary searches for specific value thresholds. By querying an agent's value for their top item and then finding items that fall into predefined value "buckets" (e.g., $1/n$, $1/n^2$), it constructs a simulated valuation that approximates the true preferences.
- FirstPositionAdaptive (FPA): Designed for "unit-sum" valuations (where total value sums to 1), this adaptive algorithm uses the first query's result to strategically choose a second query, maximizing the information gain.
Results and Tradeoffs
The core contribution of the paper is a comprehensive mapping of the tradeoff between query complexity and distortion.
As shown in the figure above, the distortion decreases significantly as more queries are allowed:
- Unrestricted Valuations: With $O(\lambda \log n)$ queries, the distortion is $O(n^{1/(\lambda+1)})$. Notably, $O(\log^2 n)$ queries (setting $\lambda = \log n$) achieve constant $O(1)$ distortion.
- Unit-Sum Valuations: Just 2 queries can reduce distortion from $\Theta(n^2)$ to $\tilde{O}(n^{2/3})$.
- Lower Bounds: The authors also establish fundamental limits, proving that any algorithm with $k$ queries must face a distortion of at least $\Omega(n^{1/k}/k)$.
Key Insights
- The Power of Thresholds: Knowing the "order of magnitude" of preferences via threshold queries is often sufficient to prevent major welfare losses. Knowing if an item is worth $1/n$ or $1/n^2$ of the top item is more critical than knowing its exact value.
- Ordinal-Guided Elicitation: Using rankings to perform binary search for values allows for efficient information gathering, requiring only $O(\log n)$ queries to find a specific threshold boundary among $n$ items.
- Fundamental Limits: The "almost logarithmic" barrier suggests that constant distortion is unattainable without roughly $\log n$ queries, highlighting a critical threshold in information requirements.
Conclusion
This work demonstrates that a small amount of cardinal information can go a long way in improving the efficiency of matching mechanisms. By moving beyond the binary choice of "ordinal vs. cardinal," the authors provide a flexible framework for balancing elicitation costs with social welfare. Future research may explore randomized algorithms in this cardinal-query setting or investigate the communication complexity in terms of total bits transmitted.
Summary updated