The Distortion of Threshold Approval Matching

Mohamad Latifian, Alexandros A. Voudouris

Abstract

We study matching settings in which a set of agents have private utilities over a set of items. Each agent reports a partition of the items into approval sets of different threshold utility levels. Given this limited information on input, the goal is to compute an assignment of the items to the agents that (approximately) maximizes the social welfare. We first consider the well-known, simple one-sided matching problem in which each of $n$ agents is to be assigned exactly one of $n$ items. We show that with $t$ threshold utility levels, the distortion of deterministic matching algorithms is $\Theta(\sqrt[t]{n})$ while that of randomized algorithms is $\Theta(\sqrt[t+1]{n})$. We then show that our distortion bounds extend to a more general setting in which there are multiple copies of the items, each agent can be assigned a number of items up to a capacity, and the utility of an agent for an item depends on the number of its copies that the agent is given.

1. Introduction

In resource allocation problems—such as assigning reviewers to papers or students to dormitories—the primary objective is often to maximize social welfare, defined as the sum of agents' utilities for their assigned items. While achieving the theoretical maximum requires precise cardinal utility information, eliciting such data is practically difficult. Humans generally find it easier to provide qualitative assessments (e.g., "excellent," "good," or "unacceptable") rather than exact numerical values.

Previous literature has extensively studied ordinal information (rankings), but this often leads to high distortion—the worst-case ratio between the optimal social welfare and the welfare achieved under limited information. This paper investigates threshold approvals as a middle ground between simple rankings and full cardinal utilities. We analyze how many threshold levels are necessary to significantly reduce distortion and provide tight mathematical bounds for both deterministic and randomized settings.

2. The Threshold Approval Model

The core of the proposed framework is the elicitation of $t$ threshold utility levels. Instead of reporting a full ranking or exact utilities, each agent partitions the set of items into $t$ "buckets" based on pre-defined utility thresholds.

Figure 1: Representation of a bipartite matching problem where agents $v_i$ categorize items $z_j$ into threshold-based sets $\tau_1$ and $\tau_2$.

As illustrated in Figure 1, the input to the matching algorithm is a bipartite graph where edges represent the membership of an item in an agent's specific threshold set. This limited information serves as the basis for computing an assignment that approximates the optimal social welfare.

3. Algorithmic Framework

The authors propose two primary classes of algorithms to handle threshold-based data:

3.1 Deterministic Matching ($f_t$)

The deterministic approach constructs a weighted bipartite graph where the weight of an edge $(i, j)$ is set to the minimum possible utility agent $i$ could have for item $j$ given the reported threshold. The algorithm then computes a maximum-weight matching on this graph. This conservative approach ensures a baseline level of welfare regardless of the actual underlying utilities.

3.2 Randomized Matching ($R_t$)

To further reduce distortion, a randomized mechanism is introduced. This algorithm chooses between two strategies with equal probability:

  1. Selecting a matching uniformly at random from all possible perfect matchings.
  2. Running the deterministic maximum-weight matching algorithm described above.

3.3 Generalized Matching

The framework is extended to more complex scenarios involving multiple copies of items and varying agent capacities. By utilizing a min-cost flow formulation, the authors demonstrate that the threshold-based approach remains effective even when agents can receive multiple items and marginal utilities vary.

4. Key Results and Theoretical Bounds

The paper establishes asymptotically tight bounds for distortion as a function of the number of thresholds $t$ and the number of agents $n$:

  • Deterministic Distortion: The distortion is $\Theta(\sqrt[t]{n})$. Notably, moving from ordinal rankings to just a single well-chosen threshold improves distortion from $\Theta(n^2)$ to $\Theta(n)$.
  • Randomized Distortion: The distortion is $\Theta(\sqrt[t+1]{n})$.
  • Logarithmic Efficiency: A significant finding is that with $t = O(\log n)$ thresholds, it is possible to achieve constant distortion ($O(1)$). This suggests that a small, manageable number of categories is sufficient to maintain high efficiency.

These bounds are robust across settings. In the generalized model, distortion scales with the total supply $T$ and a capacity parameter $c$, matching the simple matching bounds when capacities are constant.

5. Discussion and Future Work

The results demonstrate that threshold-based elicitation is a powerful tool for balancing elicitation overhead with social welfare. The "bang for your buck" is highest with the first few thresholds, after which diminishing returns set in.

Future research directions include the exploration of relative thresholds (e.g., top $k\%$ of items), randomized elicitation (randomizing the threshold values themselves), and the integration of incentives and fairness constraints into the matching framework.

Summary updated

Abstract

We study matching settings in which a set of agents have private utilities over a set of items. Each agent reports a partition of the items into approval sets of different threshold utility levels. Given this limited information on input, the goal is to compute an assignment of the items to the agents (subject to cardinality constraints depending on the application) that (approximately) maximizes the social welfare (the total utility of the agents for their assigned items). We first consider the well-known, simple one-sided matching problem in which each of $n$ agents is to be assigned exactly one of $n$ items. We show that with $t$ threshold utility levels, the distortion of deterministic matching algorithms is $\Theta(\sqrt[t]{n})$ while that of randomized algorithms is $\Theta(\sqrt[t+1]{n})$. We then show that our distortion bounds extend to a more general setting in which there are multiple copies of the items, each agent can be assigned a number of items (even copies of the same one) up to a capacity, and the utility of an agent for an item depends on the number of its copies that the agent is given.
BibTeX
@inproceedings{latifian2024distortion,
  author = {Mohamad Latifian and Alexandros A. Voudouris},
  title = {{The Distortion of Threshold Approval Matching}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure