One-sentence Summary

University of Toronto researchers achieve the optimal distortion of $O(n^{1/\lambda})$O(n1/λ) with $\lambda$λ cardinal utility queries per agent in multi-agent matching, and $O((\min\{n,m\})^{1/\lambda})$O((min{n,m})1/λ) in the general social choice problem with $m$m alternatives, settling open questions on the best achievable distortion with a fixed number of queries.

Key Contributions

• In one-sided matching, where n agents are assigned to n alternatives from ordinal rankings, cardinal-value query algorithms achieve O(n^{1/lambda}) distortion with lambda queries per agent for any constant lambda, generalizing the two-query O(sqrt n) bound and matching prior lower bounds up to a constant factor.
• For single-winner elections with n voters and m alternatives, a generalized method achieves O((min{n,m})^{1/lambda}) distortion with lambda cardinal queries per voter for any constant lambda, covering the previously open m=o(n) regime and achieving optimal distortion under prior lower-bound results.
• For 1 <= lambda <= log(min{n,m}), the algorithms provide a finite-query tradeoff of O(lambda * min{n,m}^{1/lambda}) distortion, including deterministic O(log(min{n,m})) distortion with O(log(min{n,m})) queries. This min-based guarantee also lets one-sided matching be modeled as a single-winner election over n! alternatives while retaining an O(n^{1/lambda}) bound up to a constant factor.

Introduction

The paper studies how to make better group decisions when people report only rankings, as in assigning office spaces or choosing a clinic location, because rankings capture preference order but not preference intensity. This matters for maximizing social welfare while keeping questions to participants cognitively low. Prior work on distortion showed that ordinal only mechanisms face strong approximation limits, and cardinal queries can improve outcomes, but the optimal tradeoff when each agent answers only a few queries, especially between two and logarithmic queries, remained unclear. The authors leverage a bounded number of cardinal queries, stable committee ideas, and a modified serial dictatorship to design deterministic polynomial algorithms. For one-sided matching, they achieve asymptotically optimal distortion O(n^{1/lambda}) with constant lambda queries per agent, and for single-winner elections they achieve O(min{n,m}^{1/lambda}), including the open case where agents far outnumber candidates.

Method

The authors formulate the core method as an adaptive mechanism that starts from purely ordinal preferences and obtains a small number of cardinal value queries per agent to improve welfare guarantees. The mechanism family has two settings: one-sided matching, where every agent must be assigned a distinct alternative, and single-winner elections, where one candidate is selected. The same algorithmic skeleton is used in both settings: preferences determine a structured candidate or matching set, cardinal queries reveal how valuable that structure is, and the revealed utilities are reused to design the next query set.

For one-sided matching, the input contains a set of $n$n agents $N$N and $n$n alternatives $A$A. Each agent $i$i has a hidden utility function $u_i: A \to \mathbb{R}_{\ge 0}$ui​:A→R≥0​, but the mechanism initially observes only the induced preference ranking $\sigma_i$σi​. A matching $M$M is a bijection from agents to alternatives, and the welfare of a matching under utility profile $\vec u$u is

A $\lambda$λ-query ordinal matching mechanism is allowed, in addition to the preference profile, to ask at most $\lambda$λ value queries per agent. A query has the form $Q(i,a)$Q(i,a) and returns $u_i(a)$ui​(a). The goal is to output a matching whose welfare is competitive with the optimal welfare-maximizing matching $\mathrm{OPT}(\vec u)$OPT(u), measured through the distortion

where $\vec u \triangleright \vec\sigma$u▹σ denotes that the hidden utilities are consistent with the reported ordinal preferences.

The first major module is a stable set of matchings constructed through a $k$k-capacity serial dictatorship. This subroutine takes an ordinal preference profile $\vec\sigma$σ, agent weights $w$w, and a capacity parameter $k$k. It begins with a multiset containing $k$k copies of every alternative. Agents are processed in nonincreasing order of weight. When agent $i$i appears, she selects her highest-ranked alternative among those that still have remaining capacity. The output is a mapping $g:N\to A$g:N→A in which every alternative is assigned to at most $k$k agents.

The mapping $g$g is then decomposed into $k$k matchings. For each alternative $a$a, collect all agents mapped to $a$a and assign the first such agent to the first matching, the second to the second matching, and so on. Because no alternative receives more than $k$k agents, this creates $k$k partial matchings, each of which can be completed arbitrarily into a full matching. The resulting set of $k$k matchings is stable in the following sense: there is no other matching $M'$M′ and no group of agents $N'$N′ with weight at least $w(N)/k$w(N)/k such that every agent in $N'$N′ strictly prefers $M'$M′ to every matching in the constructed set.

The stability argument is based on the serial dictatorship blocking structure. If a group $N'$N′ could deviate toward some matching $M'$M′ that all its members prefer to the constructed set, then when the algorithm considered an agent $i\in N'$i∈N′, the alternative $M'(i)$M′(i) must already have exhausted its $k$k copies. Therefore, $k$k earlier agents must have chosen $M'(i)$M′(i), and because those earlier agents were processed before $i$i, each has weight at least $w(i)$w(i). The sets of blockers for different agents in $N'$N′ are disjoint, and the last agent in $N'$N′ cannot block another agent in $N'$N′. Summing the weights of all such blockers gives a total weight strictly larger than $k w(N')$kw(N′), which contradicts $w(N')\ge w(N)/k$w(N′)≥w(N)/k. Hence the constructed set of matchings is stable.

The main $\lambda$λ-query matching mechanism uses this stable set subroutine as a query design module. It runs in multiple rounds, where each round produces a mapping $g_r$gr​ and then asks each agent for the utility of that mapped alternative. The first round is initialized with uniform weights and runs an $n$n-capacity serial dictatorship. Since capacity $n$n cannot be exhausted before all agents are assigned, every agent receives her top-ranked alternative:

The mechanism then asks each agent for $u_i(g_1(i))$ui​(g1​(i)). These revealed utilities become the weights for the next round:

In round $r$r, the algorithm sets

It runs an $\alpha_r$αr​-capacity serial dictatorship with weights $w_r$wr​ and preference profile $\vec\sigma$σ, obtains a mapping $g_r$gr​, and asks each agent for $u_i(g_r(i))$ui​(gr​(i)). The weights for the following round are updated as

Thus the process is adaptive: the first query set is determined entirely by preferences, while later query sets are determined by both preferences and the cardinal values learned in earlier rounds.

After all $\lambda$λ rounds, the algorithm constructs a proxy utility profile $\widetilde u$u. For each agent $i$i and alternative $a$a, the proxy utility is the largest cardinal value that is guaranteed by preference dominance among the queried alternatives. Formally,

with $\widetilde u_i(a)=0$ui​(a)=0 if no relevant utility was learned. This uses the fact that if agent $i$i prefers $a$a to some queried alternative $b$b, then her true utility for $a$a is at least $u_i(b)$ui​(b). The mechanism finally returns a matching that maximizes proxy welfare:

The welfare analysis relies on the stable set of matchings produced in each round. Because the output $g_r$gr​ of an $\alpha_r$αr​-capacity serial dictatorship can be decomposed into $\alpha_r$αr​ matchings, an averaging argument shows that at least one matching in this decomposition has proxy welfare large enough relative to the revealed utilities $u_i(g_r(i))$ui​(gr​(i)). Since $\widetilde M$M is optimal for the proxy utilities, its welfare is also at least this averaged value.

To convert this into a distortion guarantee, the agents are partitioned according to how much better the optimal matching is than the algorithm’s queried mappings. Agents who prefer $\mathrm{OPT}$OPT to $g_2$g2​ form the first group, agents who prefer $\mathrm{OPT}$OPT to $g_3$g3​ but not to $g_2$g2​ form the second group, and so on. Stability of the stable set of matchings bounds the total weight of each deviating group with respect to the weight vector used in that round. Since each weight vector is built from utilities of alternatives that are at least as good as the optimal alternative for that group, the welfare contribution of each group to the optimum is bounded by a factor $n^{1/\lambda}$n1/λ times the mechanism’s welfare. Summing over the $\lambda$λ groups yields the distortion

The same architecture extends to single-winner elections. The input now contains $m$m candidates $C$C, and the mechanism selects one candidate. The ordinal part is unchanged: each agent reports a ranking over candidates. The cardinal part again asks for values of specific candidates. The main algorithmic difference is that the stable set of matchings is replaced by an approximately stable committee.

A committee $X\subset C$X⊂C of size $k$k is approximately stable if no outside candidate $c'\notin X$c′∈/X is unanimously preferred to all members of $X$X by a group of agents whose total weight is too large. More formally, let

Then $X$X is $\beta$β-stable if

The voting mechanism constructs a sequence of such committees whose sizes shrink geometrically from roughly $\min\{n,m\}$min{n,m} toward small committees. In each round, the mechanism asks each agent for the utility of her favorite candidate inside the current committee. The answer again becomes the agent’s weight for the next round. After the query phase, the mechanism constructs proxy utilities over all candidates using preference dominance, exactly as in the matching setting, and selects the candidate with maximum proxy welfare.

The dependence on $\min\{n,m\}$min{n,m} rather than only $m$m comes from an averaging argument at the top of the preference profile. If there are more candidates than agents, the number of distinct top candidates is at most $n$n, so one can average over only those candidates that actually appear at the top. If there are fewer candidates than agents, averaging over all $m$m candidates is appropriate. This yields the voting distortion bound

up to the stability factor $\beta$β when only approximately stable committees are available.

The method can also be expressed as a black-box reduction from matching or allocation to voting. Given a one-sided matching instance, one can create a single-winner election whose candidates are all possible matchings. Each agent ranks these election candidates according to the position of the alternative she receives in that matching. A value query to a candidate in the election corresponds exactly to asking the agent for the utility of her assigned alternative in the matching. Since the number of matchings is $n!$n!, the relevant maximum in the voting bound becomes

Applying the voting mechanism to this induced election gives a matching mechanism with distortion of the form $\lambda n^{1/\lambda}$λn1/λ, with an additional constant factor if one uses only approximately stable committees. When the exact stable set of matchings subroutine is used instead, the matching-specific construction recovers the same form without relying on the larger election candidate space. The same viewpoint applies to resource allocation, where candidates can be all possible allocations, although doing so requires access to ordinal rankings over an exponentially large outcome space.

Experiment

The analysis studies randomized voting rules in the standard ordinal setting without value queries, focusing on restricted utility classes, especially unit-range and unit-sum utilities, when the number of voters and candidates are unbalanced. It shows that utility restrictions lead to different distortion behavior: the stable lottery rule obtains a better dependence on the number of voters for unit-range utilities, while unit-sum utilities continue to force larger distortion as the number of voters grows. Overall, the findings reveal a clear contrast between the two utility models and establish that the observed distortion lower bound under unit-sum utilities is unavoidable for randomized rules.

The comparison summarizes the tradeoff between the number of cardinal queries per agent and the worst-case distortion in one-sided matching under unrestricted utilities. A constant number of queries per agent yields asymptotically optimal distortion, and increasing the query budget lowers the distortion as a smaller power of the instance size. The results also improve prior tradeoffs at logarithmic query budgets, achieving strong distortion with fewer queries than earlier work required. With no cardinal queries, ordinal matching can have unbounded distortion when utilities are unrestricted. For constant query budgets, the new upper bound matches the known lower bound up to constant factors. Increasing the number of queries per agent substantially reduces the achievable distortion bound. The new analysis achieves strong distortion with three queries, where earlier results required logarithmic queries.

The comparison shows how distortion guarantees for single-winner elections change with the number of cardinal value queries per agent. Without queries, unrestricted ordinal rules can have unbounded distortion, while additional queries yield progressively tighter upper bounds. Some new bounds depend on the smaller of the number of agents and candidates, making them stronger than candidate-only guarantees when agents are few relative to candidates. No-query ordinal rules have unbounded distortion when utilities are unrestricted. A constant query budget yields sublinear distortion, and a logarithmic budget yields logarithmic distortion. Bounds involving the smaller of the agent and candidate counts improve on prior candidate-only bounds. For restricted utility classes, no-query distortion can be finite and tied to both agent and candidate counts.

The comparison evaluates one-sided matching and single-winner elections under unrestricted utilities by examining how worst-case distortion varies with the number of cardinal value queries per agent. It shows that cardinal queries are essential, since ordinal mechanisms without such queries can have unbounded distortion, while even a small constant number of queries yields strong, asymptotically near-optimal guarantees for matching. Across both settings, increasing the query budget progressively improves distortion bounds, and the new results offer better query-distortion tradeoffs than earlier analyses, including cases where guarantees depend on the smaller of agent and candidate counts.