Abstract
This paper investigates the efficiency loss, measured by distortion, in matching problems where agents provide limited threshold-based approval information instead of full cardinal utilities. We analyze both one-sided matching and generalized settings with capacities and supplies. We show that a small number of thresholds $t$ significantly reduces distortion, with $t = O(\log n)$ achieving near-optimal social welfare. Specifically, we establish tight distortion bounds of $\Theta(\sqrt[t]{n})$ for deterministic mechanisms and $\Theta(\sqrt[t+1]{n})$ for randomized mechanisms, demonstrating the power of threshold-based elicitation in balancing communication complexity and social efficiency.
Introduction
In many resource allocation scenarios—such as matching students to dorms or reviewers to conference papers—the goal is to maximize social welfare, the total utility of all participants. However, eliciting exact numerical utility values for every item is often difficult and unreliable. Consequently, systems frequently rely on ordinal information (rankings), which unfortunately leads to high distortion: the worst-case ratio between the optimal welfare and that achieved by an algorithm. For deterministic matching, ordinal information can result in a distortion as high as $\Theta(n^2)$, where $n$ is the number of items.
This research explores a "middle ground" elicitation method: threshold approvals. Instead of providing full rankings or exact values, agents partition items into categories based on $t$ predefined thresholds. We investigate how many such thresholds are required to restore efficiency in matching.
Threshold Approval Elicitation
Under the threshold approval model, agents are given $t$ decreasing threshold values. They report which items fall into which threshold interval, effectively providing a coarse-grained version of their cardinal utilities.
As shown in Figure 1, the elicited information forms a structured bipartite graph. This structure allows for the design of algorithms that differentiate between items more effectively than simple rankings, leading to a significant reduction in distortion.
Algorithms and Theoretical Results
The authors propose and analyze two primary mechanisms for matching based on threshold reports:
- Deterministic Mechanism ($f_t$): This mechanism constructs a weighted bipartite graph where the weight of an edge $(i, j)$ is the minimum possible utility agent $i$ could have for item $j$ given the threshold report. It then computes a maximum-weight matching. Despite its "pessimistic" assumption, this approach achieves the best possible theoretical performance for deterministic algorithms.
- Randomized Mechanism ($R_t$): This is a hybrid approach that runs the deterministic algorithm with 50% probability and selects a matching uniformly at random with 50% probability. This randomization acts as a safety net against worst-case utility distributions where high-utility items might fall just below a threshold.
The paper establishes tight bounds on distortion, showing a clear relationship between the number of thresholds $t$ and the efficiency of the matching:
| Mechanism Type | Distortion Bound |
|---|---|
| Deterministic | $\Theta(\sqrt[t]{n})$ |
| Randomized | $\Theta(\sqrt[t+1]{n})$ |
Key Insights
- The Information Jump: Moving from zero information to just one threshold improves deterministic distortion from $\Theta(n^2)$ to $\Theta(n)$, suggesting that even simple approval mechanisms are a massive upgrade over pure rankings.
- The Power of Logarithms: If $t = O(\log n)$ thresholds are used, the distortion drops to a constant $O(1)$. This implies that a few well-chosen categories (e.g., "Eager," "Willing," "Reluctant") are mathematically sufficient for near-optimal efficiency.
Generalized Matching Settings
The study also addresses generalized settings where agents have capacities (can receive multiple items) and items have supplies (multiple copies). In these cases, utilities can vary based on the number of copies an agent receives.
To solve these problems, the authors utilize flow network constructions, as illustrated in Figure 2. This allows the matching problem to be reduced to a flow problem while maintaining the established distortion bounds, scaled by factors representing capacity and supply ratios.
Conclusion
Threshold approval matching provides a practical and theoretically sound framework for efficient resource allocation. By bridging the gap between ordinal and cardinal information, it offers a scalable way to achieve high social welfare with minimal communication overhead. Future research directions include exploring dynamic threshold selection, incentive compatibility, and applying these bounds to cost-minimization problems in metric spaces.
Summary updated