Every Bit Helps: Achieving the Optimal Distortion with a Few Queries (Extended Abstract)

1 Introduction

Imagine you are tasked with allocating office spaces in a medical building to a group of doctors. Each doctor provides a ranked list of their preferred offices, and your goal as the manager is to find a matching that maximizes the overall satisfaction, or social welfare, of all doctors. While rankings give you a general sense of their preferences, they lack information about intensity of preferences. If you could ask a few targeted questions to obtain their exact numerical utilities, known as cardinal queries, you may be able to improve the allocation significantly. However, these queries are cognitively burdensome for the doctors to answer, so they must be designed carefully in order to maximize their benefit while minimizing burden on the doctors.

The concept of distortion, introduced by Procaccia and Rosenschein [2006], quantifies the loss in social welfare due to the lack of exact numerical preferences. Traditionally, distortion has been studied in settings where only ordinal information is available (see the survey by Anshelevich et al. [2021]). For instance, in one-sided matching problems [Hylland and Zeckhauser, 1979], where n agents are matched to n items based on their preferences, the best achievable distortion is known to be Θ(√n), though this requires randomization and normalized values [Filos-Ratsikas et al., 2014].

* This extended abstract is based on the AAAI 2025 paper of the same title [Ebadian and Shah, 2025].

Recent work has expanded this framework by considering the trade-offs between the amount of cardinal information gathered and the efficiency of the resulting allocation. Amanatidis et al. [2021; 2022] demonstrated that by allowing mechanisms to ask λ · logn cardinal queries per agent, O(n1/(λ+1) ) distortion can be achieved, even without relying on randomization or normalization. Building on this, Amanatidis et al. [2024] showed that a distortion of Θ(√n) can be achieved by asking only two queries per agent (instead of logn), matching the performance of the best randomized mechanism that assumes normalized values.

Despite these advancements, our understanding of the trade-offs between using two cardinal queries per agent and a logarithmic number of queries remains limited. This raises an important question:

As we go from just two to three or more (but a constant number of) queries per agent, how well can we approximate the optimal social welfare of any one-sided matching?

Shifting frommatching to voting, consider another important decision in the medical building: selecting the location for a new specialized clinic. The doctors must vote on several potential locations, each offering distinct advantages, such as proximity to the emergency room, patient accessibility, or the available space. Each doctor has their own underlying utilities for these locations, influenced by their specialty and the needs of their patients. While rankings provide a general understanding of their preferences, they once again fail to capture preference intensities. By eliciting a few cardinal queries, the decision-maker could potentially improve the selection process, aiming to maximize the collective satisfaction of the group, just as before. However, this voting problem is even less understood than the matching problem. When only two queries per agent are allowed, despite the attempt of Amanatidis et al. [2024], the problem of optimal achievable distortion remains unresolved. This again raises the same question posed earlier, but now for the setting more precisely called single-winner elections.

1.1 Our Contributions

We present a novel algorithm for both one-sided matching and single-winner elections, which leverages a limited number of λ cardinal queries per agent to achieve asymptotically optimal distortion bounds when λ is a constant. Table 1 provides a summary of our results alongside relevant prior work in one-sided matching. We impose no restrictions on the utilities, and all our algorithms are deterministic and run in polytime. Our work builds on the ideas of Amanatidis et al. [2024] and introduces novel applications of the notion of stable committees in multi-winner elections [Aziz et al., 2017; Cheng et al., 2020].

One-sidedmatching. For the one-sidedmatching problem, we establish that the optimal distortion with a constant number λ of queries per agent is O(n1/λ ). This significantly generalizes the work of Amanatidis et al. [2024], who only considered two-query algorithms. Our algorithm achieves O(n1/3 ) distortion with just three queries, a result that previously required O(log n) queries [Amanatidis et al., 2022].

More generally, for any 1 ⩽ λ ⩽ logn, we achieve distortion of λ · n1/λ with λ queries. This implies O(log n) distortion with logn queries, improving upon the previous best result that required O(log2 n/ log log n) queries [Amanatidis et al., 2022]. The (asymptotic) optimality of our results for constant λ follows from the Ω(n1/λ ) lower bound established by Amanatidis et al. [2022].

We also establish the existence of an exactly stable committee of matchings by modifying the serial dictatorship algorithm. This result may be of independent interest, as only approximately stable committees exist in committee selection with ranked preferences [Jiang et al., 2020].

Single-winner elections. Applying similar techniques, we achieve comparable results for single-winner elections with a distortion bound of O((min{n,m})1/λ ) for constant λ. While Amanatidis et al. [2024] showed O(√m) distortion for m = Ω(n) with two queries, the case of m = o(n), with the number of agents far exceeding the number of candidates, remained open. Notably, our bounds depend on min{n,m} rather than just m as in typical voting distortion results. For example, this allows modeling one-sided matching as a single-winner election with n! possible matchings as alternatives, yet still achieve an appealing bound of O(n1/λ ) with only a constant factor increase.

1.2 RelatedWork

The study of querying beyond ordinal preferences builds on earlier work on distortion using only ordinal information, initiated by Procaccia and Rosenschein [2006] in the context of single-winner elections. Caragiannis and Procaccia [2011] and Caragiannis et al. [2017] demonstrate that the optimal distortion achievable by deterministic voting rules under normalized valuations is Θ(m2 ). For randomized voting rules, Boutilier et al. [2015] and Ebadian et al. [2022] identify the best achievable distortion as Θ(√m). Additionally, Caragiannis et al. [2017] explore distortion in multi-winner elections. Borodin et al. [2022] consider scenarios where even less information than ranked votes is used. Distortion is also examined in the metric voting framework [Anshelevich and Postl, 2017; Anshelevich et al., 2018], with a comprehensive overview provided by Anshelevich et al. [2021].

Some studies relax query-type restrictions, allowing any query that elicits a fixed number of bits from voters, including ordinal elicitation, and focus on optimizing the query format itself [Mandal et al., 2019; Mandal et al., 2020] (and Kempe [2020] for metric voting). For single-winner elections, deterministic elicitation requires ˜Θ(m/d) bits, while randomized elicitation requires ˜Θ(m/d3 ).

Latifian and Voudouris [2024] and Ma et al. [2021] investigate threshold approval queries for one-sided matching, while Ebadian et al. [2023] apply the same elicitation to voting. In the metric voting framework, Ebadian et al. [2024] propose nearly-optimal algorithms using limited pairwise comparisons per agent, with various constraints on query adaptivity, while Anagnostides et al. [2022] study adaptive algorithms that ask the same set of queries to all agents.

2 Model

Let [t] := {1, . . . , t} for t ∈ N.

One-sided matching. In one-sided matching, there is a set N of n agents and a set A of n alternatives. A matching M is a one-to-one mapping from N to A, pairing each agent with a unique alternative. Each agent i ∈ N has a valuation function ui : A → R⩾0, where ui(a) denotes the utility agent i receives when matched to alternative a. The utilitarian social welfare of a matching M is denoted by sw(M) = ∑i∈N ui(M(i)).

Implicitly utilitarian ordinal matching. For each agent i ∈ N, let σi : [n] → A be the preference ranking of agent i induced by the valuation function ui (ties broken arbitrarily); that is, ui(σi(1)) ⩾ . . . ⩾ ui(σi(n)). The preference profile ⃗σ = {σi}i∈N is the collection of all agents' preferences. We denote by ⃗u ▷ ⃗σ that ui aligns with σi for each i. By a ≻i a′ we mean i strictly prefers a to a′ . An ordinal matching mechanism returns a matching based only on ⃗σ.

Value queries. A λ-query ordinal matching mechanism, in addition to the preference profile ⃗σ, is allowed to ask up to λ value queries per agent. Through a value query Q(i, a), the algorithm learns ui(a).

Distortion. The distortion of a λ-query mechanism M w.r.t. a preference profile ⃗σ is its worst-case approximation ratio to the optimal welfare-maximizing matching OPT(⃗u) over all consistent utility profiles. That is,

3 Ordinal Matching with Value Queries

In this section, we present a λ-query mechanism with λ · n1/λ distortion. We first describe a simple algorithm to find a stable "committee" of k matchings, which is a key subprocedure of the final matching algorithm.

3.1 Stable Matching Sets

Amanatidis et al. [2024] define a particular type of assignment called a "sufficiently representative set" that is specific to their two-query mechanism. The crux of this notion and its role in the algorithm, we believe, is closely related to finding a stable committee of √n matchings. We extend their algorithm and show a weighted form of k-stable committee of matchings exists and can be computed by a simple algorithm for all k ∈ [n].

Definition 1 (Stable set of matchings). For an ordinal matching instance with agent weights w, a set of k matchings X = {M1, . . . ,Mk} is stable if there does not exist another matching M ′ and agents N ′ ⊆ N such that w(N ′ ) ⩾ w(N)/k and M ′ (i) ≻i Mℓ(i) for all i ∈ N ′ and Mℓ ∈ X.

In contrast to committee selection from a set of candidates, where even 2-stable committees may fail to exist [Jiang et al., 2020], we show a stable set of matchings always exist.

Theorem 2. For an ordinal matching instance and agent weights w, there always exists a set of k matchings that is stable and can be computed in poly(n) time.

Algorithm 1 k-Capacity Serial Dictatorship

Input: Preference profile ⃗σ, weights {w(i)}i∈N, and k Output: A k-capacity mapping

• 1: B ←multiset of k copies of each alternative a ∈ A
• 2: for i ∈ N in decreasing order of weights wi do
• 3: Match i to their most preferred alternative ai ∈ B
• 4: Remove one copy of ai fromB
• 5: end for
• 6: return g = {i → ai}i∈N

Algorithm 2 λ-Query Matching Algorithm

Input: Preference profile ⃗σ and λ

Output: Matching ˜ M

• 1: Let w1(i) = 1 for all i ∈ N
• 2: for ℓ ∈ {1, . . . , λ} do
• 3: Set kℓ ←n1-(ℓ-1)/λ
• 4: gℓ ← kℓ-Capacity Serial Dictatorship(⃗σ, {wℓ(i)}i∈N)
• 5: Query each agent i ∈ N of gℓ(i)
• 6: wℓ+1(i) ← ui(gℓ(i)) for all i ∈ N
• 7: end for
• 8: ˜ ui(a) ← max{ui(gℓ(i)) | a ≽i gℓ(i), ℓ ∈ [λ]}, or 0 if no such queries exist
• 9: return social welfare maximizing matching ˜ M based on {˜ ui}i∈N .

We achieve Theorem 2 via Algorithm 1 that closely follows the √n-Serial Dictatorship algorithm of Amanatidis et al. [2024]. The main difference is that we go over the agents in the order of the weights, which enables proving Theorem 2 for arbitrary agent weights and any k ∈ [n].

k-Capacity serial dictatorship. Algorithm 1 is a serial dictatorship process that starts with a multiset containing k copies of each alternative. Agents then make their selections, by picking their favourite among the remaining alternatives, in an order determined by weights in non-increasing order. Since each alternative is mapped to at most k agents, we can decompose such a mapping g into a set of k matchings where each agent i is mapped to g(i) in at least one of the k matchings.

Lemma 3. Let g : N → A be a k-capacity mapping. There exists a set of k matchings M1, . . . ,Mk such that for all i ∈ N, g(i) = Mℓ(i) for some ℓ ∈ [k], and it can be computed in poly(n) time.

3.2 The λ-Query Algorithm

Next, we present our λ-query mechanism that achieves a distortion of λ · n1/λ , which uses Algorithm 1 and its guarantee (Theorem 2) to inform the queries.

The first round of queries. In the first round, since k = n, the capacity is always unexhausted, so the returned map satisfies g1(i) = σi(1), and the first query to each agent is about their favourite alternative.

Subsequent rounds. For round ℓ ⩾ 2, the algorithm uses the answers to the previous queries as the weights, i.e., wℓ(i) = ui(gℓ-1(i)). It computes gℓ via a (n1-(ℓ-1)/λ )- capacity serial dictatorship, and makes the ℓ-th set of queries based on gℓ by asking each agent i of their utility for gℓ(i).

The final matching. Finally, after making all the λ queries, the algorithm creates a proxy utility profile ˜ u based on the queried utilities. The algorithm sets ˜ ui(a) to the maximum guaranteed utility learnt by either directly asking ui(a) or an alternative a′ ≻i a ranked below a. The algorithm returns a matching with maximum social welfare w.r.t. ˜ u.

Minimum welfare guarantee. Let ˜ sw denote the social welfare with respect to the proxy utilities ˜ u. By construction, ˜ u is an underestimation of u, so sw(M) ⩾ ˜ sw(M) for every matching M. The matching ˜ M returned by Algorithm 2 comes with the following lower bound.

Lemma 4 (Minimum Welfare Guarantee). For an ordinal matching instance, the matching ˜ M returned by Algorithm 2 achieves

The lemma follows from Theorem 3: for each ℓ, the mapping gℓ decomposes into αℓ = n1-(ℓ-1)/λ matchings whose proxy welfares sum to at least ∑i∈N ui(gℓ(i)), and the best of them is dominated by the proxy-optimal matching ˜ M.

Main result. We now have all the ingredients to prove the main distortion bound.

Theorem 5. There is a λ-query ordinal matching mechanism that achieves a distortion of λ·n1/λ and runs in poly(n) time.

Proof sketch. Let OPT be the welfare-maximizing matching. At a high level, we partition the agents into λ groups N1, . . . , Nλ and show that sw(OPT | Nℓ) ⩽ n1/λ · sw(˜ M) for each ℓ ∈ [λ]. Summing over the λ groups yields sw(OPT) ⩽ λ · n1/λ · sw(˜ M), which proves the sought distortion bound.

Partitioning by deviation. Recall that g1(i) = σi(1), so no agent strictly prefers OPT to g1. For each ℓ ∈ [λ - 1], let

be the set of agents who "deviate" from gℓ+1 to OPT but not from any of g1, . . . , gℓ. Finally, let Nλ = N \ (⋃ℓ∈[λ-1] Nℓ) be the remaining agents.

Bounding the welfare of Nℓ. Fix ℓ ∈ [λ - 1]. For each i ∈ Nℓ, gℓ(i) ≽i OPT(i) ≻i gℓ+1(i), so the agents in Nℓ collectively prefer OPT to every matching in the stable set associated with gℓ+1. By Theorem 2, this group has small wℓ+1-weight:

where we used wℓ+1(i) = ui(gℓ(i)) and gℓ(i) ≽i OPT(i) for the first inequality. Combined with sw(˜ M) ⩾ ˜ sw(˜ M) and Theorem 4, we obtain sw(OPT | Nℓ) ⩽ n1/λ · sw(˜ M). The same bound for Nλ follows directly: since gλ(i) ≽i OPT(i) for all i ∈ Nλ, we have sw(OPT | Nλ) ⩽ ∑i∈N ui(gλ(i)), and applying Theorem 4 for ℓ = λ gives the bound.

Implications. For a constant number of queries, i.e., λ = O(1), given the Ω(n1/λ ) lower bound of Amanatidis et al. [2021], Theorem 5 settles the optimal distortion using λ queries to be Θ(n1/λ ). For λ = log n, since n1/ log n = O(1), the bound translates to O(logn) distortion. It is notable that the distortion bound is minimized at O(logn). Previously, Amanatidis et al. [2021] required O(log2 n/ log log n) queries to achieve O(log n) distortion, and O(log2 n) queries to achieve O(1) distortion. Determining the optimal number of queries needed for constant distortion remains an exciting open problem.

4 Single-Winner Elections

We turn briefly to the general social choice setting where the goal is to select one out of m candidates. Existing results were weaker than their counterparts for one-sided matching: the optimal distortion bound was open even for two queries when m = o(n). We settle the question for a constant number of queries.

Theorem 6. There is a λ-query single-winner voting rule that achieves a distortion of O(λ · (min{n,m})1/λ ) and runs in poly(n,m) time.

The algorithm closely follows Algorithm 2. The main difference is that, instead of invoking Algorithm 1, the voting rule finds a β-approximately stable committee Cℓ of size (min{n,m})1-(ℓ-1)/λ in round ℓ using Jiang et al. [2020] (with β = 32 + ϵ), and queries each agent of their utility for their favourite candidate in Cℓ. When λ is a constant, Amanatidis et al. [2024] show a matching Ω(m1/λ ) lower bound, settling the question of optimal distortion in singlewinner voting up to a constant factor.

The dependence on min{n,m} rather than m has further consequences. As an instructive example, modeling onesided matching as a single-winner election with the n! possible matchings as "candidates" yields the bound O(λ · n1/λ ) via this generic black-box reduction (recovering Theorem 5 up to a constant). The same reduction also provides nontrivial distortion bounds for query-efficient resource allocation by viewing each allocation as a candidate, even with nonmonotone utilities and externalities; see [Ebadian and Shah, 2025] for details.

5 Discussion

We settle the optimal distortion achievable in one-sided matching (and single-winner elections, up to constants) using a fixed number of cardinal value queries per agent. The approaches taken by Mandal et al. [2019; 2020] and Kempe [2020], which do not differentiate between ordinal and cardinal queries, and the research assuming that ordinal elicitation is free while cardinal elicitation is very costly, represent more extreme viewpoints. A more balanced approach would involve assigning a cost to ordinal elicitation, with a higher cost for cardinal elicitation, and then optimizing mechanisms within this framework subject to an elicitation budget. Another limitation of our algorithm is its strong dependence between rounds; future research could investigate the tradeoffs associated with non-adaptive mechanisms.

Acknowledgements

This research was partially supported by an NSERC Discovery grant.