The Distortion of Stable Matching
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "The Distortion of Stable Matching".
Jane: Here's the gist of the paper. The paper initiates the study of distortion in stable matching by designing algorithms with limited access to agents' cardinal preferences to compute high-quality stable matchings with respect to an aggregate objective like social welfare<ref:2602.14961#pg6>.
Tom: The first result is a strong impossibility: the classic Deferred Acceptance (DA) algorithm and any deterministic algorithm relying solely on ordinal information about the agents' preferences have unbounded distortion<ref:2602.14961#pg1>.
Jane: Impossibility of Ordinal Algorithms The authors investigate algorithms that either use randomization or perform a small number of value queries to the agents' cardinal preferences<ref:2602.14961#pg4>.
Tom: They prove that a simple randomized version of the DA algorithm achieves a distortion of 2, which is optimal among all randomized stable matching algorithms<ref:2602.14961#pg4>.
Title and authors: Tom: Let's talk about who wrote this stuff. Aris Filos-Ratsikas and Georgios Kalantzis are the authors here, coming from the School of Informatics at the University of Edinburgh >
Jane: They're tackling this distortion problem by looking at algorithms that either use some form of randomization or they perform a small number of queries to get more detail about what agents actually prefer >
Lu: They prove that even with randomization, a simple version of the Deferred Acceptance algorithm still has a distortion bound of two and this is the best possible among all randomized stable matching algorithms > <ref:2602.14961#pg1,among all randomized stable matching algorithms>
Meng: A distortion bound of two is a floor we can aim for; it tells us that if we use randomness to help, we won't do much better than twice the ideal quality on average > <ref:2602.14961#pg1>
Lalam: That means even with some luck from randomization, you still have a significant gap between what you get and what you could get with perfect information >
The paper's summary: Tom: The core idea here is moving beyond those simple ordinal algorithms to see what we can achieve by asking the agents questions about their actual preferences >
Jane: They investigate algorithms that use a small number of value queries, and they show that you can still get a distortion of two with just one query per agent if the algorithm is deterministic > <ref:2602.14961#pg1,a small number of value queries>
Lu: But they also show that to get better than that two distortion bound, which is one plus epsilon, you need either many adaptive queries or a lot more non-adaptive queries per agent > <ref:2602.14961#pg1>
Meng: If we're talking about real-world deployment, needing omega(n) adaptive queries means the system gets bogged down by the complexity of figuring out which query to ask next >
Lalam: That points to a trade-off: you can improve the quality, but it costs a lot in terms of how many times you have to talk to agents >
The paper's improvements: Tom: They present an algorithm that actually manages to achieve a distortion of one plus epsilon using O(n / epsilon two) queries per agent > <ref:2602.14961#pg1>
Jane: That query complexity is asymptotically optimal for any constant approximation, meaning it's the best you can do if you're aiming for a fixed quality level like one plus epsilon >
Lu: Under certain structural restrictions on the preference profiles, they show even better upper bounds on how many queries are needed for that one plus epsilon approximation >
Meng: O(n / epsilon two) is much better than what we might expect from just throwing more queries at it; it shows a specific scaling relationship tied to the desired quality level > <ref:2602.14961#pg1>
Lalam: So, this result is really useful because it gives us a concrete query budget for achieving high-quality stable matchings when we only have partial information >
Conclusion: Tom: To wrap up, we've seen that randomized versions of the Deferred Acceptance algorithm hit a distortion of two and query-enhanced algorithms can achieve one plus epsilon distortion with O(n / epsilon two) queries per agent > <ref:2602.14961#pg1,a distortion of 2, and>
Jane: They also showed that under specific conditions on the rotation poset structure, you can get an even better bound on the number of queries needed for that one plus epsilon approximation >
Lu: The average-case distortion for the Deferred Acceptance algorithm is at most two when agents' values are drawn independently and identically distributed, and experiments suggest this value is often closer to one on typical inputs > <ref:2602.14961#pg1>
Meng: So practically speaking, if you use a standard matching algorithm with random data, you're likely seeing distortion much closer to one than the worst-case two >
Lalam: It shows that while we can't get rid of distortion entirely with limited information, we have ways to control it by carefully choosing how many queries we ask and what kind of information those queries give us >
School of Informatics, University of Edinburgh
cs.GT
Submitted: 2026-02-16
Updated: 2026-11-12
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 91/100
The gist: The paper initiates the study of distortion in stable matching by designing algorithms with limited access to agents' cardinal preferences to compute high-quality stable matchings with respect to an…
Key concepts
- Stable Matching
- A stable matching is an assignment between two groups (like men and women) where no agent would prefer to switch partners, leading to a configuration where everyone is as satisfied as possible given the constraints.
- Distortion
- Distortion measures how far a computed stable matching is from the optimal one, often measured by comparing its social welfare against the best possible outcome. Lower distortion means a better match for society.
- Rotation Poset
- This concept describes all possible stable matchings as points within a mathematical structure called a poset. Stable matchings are related by 'rotations,' which are small changes that move from one stable matching to another, allowing researchers to analyze the space of solutions.
Terminology
Summary
The paper initiates the study of distortion in stable matching by designing algorithms with limited access to agents' cardinal preferences to compute high-quality stable matchings with respect to an aggregate objective like social welfare<ref:2602.14961#pg6>. The first result is a strong impossibility: the classic Deferred Acceptance (DA) algorithm and any deterministic algorithm relying solely on ordinal information about the agents' preferences have unbounded distortion<ref:2602.14961#pg1>.
Impossibility of Ordinal Algorithms
The authors investigate algorithms that either use randomization or perform a small number of value queries to the agents' cardinal preferences<ref:2602.14961#pg4>. They prove that a simple randomized version of the DA algorithm achieves a distortion of 2, which is optimal among all randomized stable matching algorithms<ref:2602. p. 0 To circumvent this impossibility, we consider algorithms that either (a) use randomization or
(b) perform a small number of value queries to the agents’ cardinal preferences. In the former case,
we prove that a simple randomized version of the DA algorithm achieves a distortion of 2, and that
this is optimal among all randomized stable matching algorithms. Similarly to the case of the randomized Deferred Acceptance algorithm, it can be easily observed
that a (deterministic) query-enhanced version of the algorithm achieves a distortion of 2, by using
only a single query per agent. Intuitively, this one query allows the algorithm to identify the best
matching between the man-optimal and the woman-optimal matchings, which, in turn, provides a
2-approximation to the social welfare of the overall optimal matching. A query-enhanced version of the Deferred Acceptance algorithm achieves a distortion of 2 using only one query per agent. Furthermore, any query-enhanced algorithm that achieves a
distortion better than 2 requires Ω(log𝑛) adaptive queries or Ω(𝑛) non-adaptive queries per agent.Where the paper says it
Where the paper says it
Where the paper says it
Query-Enhanced Algorithms and Bounds
The authors present an algorithm that achieves a distortion of 1 + ε using O(logn/ε 2) queries per agent<ref:2602.14961#pg9>. They note that this query bound is asymptotically optimal for any constant approximation<ref:2602. p. 0 For the latter case, we prove
that the same bound of 2 can be achieved with only 1 query per agent, and improving upon this
bound requires Ω(log𝑛) queries per agent. We further show that this query bound is asymptotically optimal for any constant approximation: for any 𝜀 > 0, there exists an algorithm which uses
𝑂(log𝑛/𝜀
2
) queries, and achieves a distortion of 1 + 𝜀. We further show that this query bound is asymptotically optimal for any constant approximation: for any 𝜀 > 0, there exists an algorithm which uses
𝑂(log𝑛/𝜀
2
) queries, and achieves a distortion of 1 + 𝜀. Moreover, under natural structural restrictions on the instances of the problem, we provide improved upper bounds on the number of queries
required for a (1 + 𝜀)-approximation.Where the paper says it
Where the paper says it
Average-Case Performance
The average-case distortion of the Deferred Acceptance algorithm is at most 2 when agents' values are drawn i.i.d. from a common distribution<ref:2602. p. 3 To this end, we consider
its average-case distortion, calculated on valuation profiles that are drawn i. from a common distribution; a notion which was recently studied by Caragiannis and Fehrs [2024]. Average-case Distortion. While our main impossibility result for ordinal deterministic algorithms
renders the Deferred Acceptance algorithm impractical in terms of its worst-case distortion, the algorithm may still exhibit good levels of social welfare on typical instances.Where the paper says it
Where the paper says it
Tight Query Bounds and Structural Improvements
The authors conjecture that the actual bound for achieving a distortion of 1 + ε might be smaller by a factor of ε. They prove this conjecture for rotation poset paths, showing that O(logn/ε) queries are sufficient to achieve distortion 1+ε. p. 3 We show that when the
rotation poset is a path, 𝑂(log𝑛/𝜀) queries are sufficient to achieve a distortion of 1+𝜀. Rotation poset
paths are known to be induced by natural classes of agents’ preferences, e.Where the paper says it
Conclusion and Future Work
The work concludes by summarizing the findings: a randomized version of DA achieves distortion 2, while query-enhanced algorithms can achieve 1+ε distortion with O(logn/ε 2) queries per agent. They also present an algorithm that achieves this bound under structural restrictions, and they confirm the average-case distortion is at most 2. p. 0 We further show that this query bound is asymptotically optimal for any constant approximation: for any 𝜀 > 0, there exists an algorithm which uses
𝑂(log𝑛/𝜀
2
) queries, and achieves a distortion of 1 + 𝜀. Moreover, under natural structural restrictions on the instances of the problem, we provide improved upper bounds on the number of queries
required for a (1 + 𝜀)-approximation. Much like standard notions in algorithm design such as the approximation ratio or the competitive ratio, the distortion quantifies the extent to which an algorithm that
operates under some natural restrictions can approximate the best possible outcome, which could be
achieved without those restrictions. In the case of the distortion, these restrictions are not due to computational considerations or uncertainty about the future, but rather due to the cognitive limitations
of the participants to accurately express their preferences on a cardinal scale.Where the paper says it
Where the paper says it
Appendix A Useful Background
This section reviews the theory of partially ordered sets and explains their relation to the stable matching problem. It defines key concepts such as Poset, Incomparable Elements, Antichain, Chain, Closed Subset, and Hasse Diagram. It introduces the notion of a Rotation and its properties through Lemma A. p. 3 We manage to improve the reliance on 𝜀 over the bound of Informal Theorem 3 for instances of the
problem that display a specific structure in the agents’ preferences. More precisely, we consider restrictions on the type of directed graph associated with the rotation poset of the instance. Consider a matching 𝜇. - We will say that 𝜇 is a man-optimal matching (and we will denote it by 𝜇
∗
𝑀
) if it is stable, and,
for every man 𝑚𝑖
, it holds that 𝜇
∗
𝑀
(𝑚𝑖) ≻𝑚𝑖 𝑤, for all 𝑤 ∈ 𝑆𝑚𝑖
.Where the paper says it
Where the paper says it
B Uniqueness of the Stable Matchings in the Proof of Theorem 3. p. 2 In contrast, the aforementioned
randomized Deferred Acceptance algorithm is ex-post stable, see Definition 2. We summarize the
results of Section 3 in the following informal theorem.Where the paper says it
This section formally argues that the two matchings identified in the proof of Theorem 3.1, namely the man-optimal matching and woman-optimal matching, are indeed the only two stable matchings on a given preference profile. p. 9 For example, the entry (𝑚2,𝑤3) is (1, 3) which indicates that 𝑚2 ranks 𝑤3 first
among the women, and 𝑤3 ranks 𝑚2 third among the men. In this preference profile there are only
two stable matchings, the man-optimal matching, consisting of entries circled in blue with solid lines,
and the woman-optimal matching, consisting of entries circled in red with dashed lines. If 𝜇 = 𝜇
∗
𝑀
, then consider the valuation profile v1, and
observe that SW(𝜇 | v1) = 0, whereas SW(𝜇
∗
𝑊
| v1) = 1; this implies that the distortion is unbounded. Similarly, if 𝜇 = 𝜇
∗
𝑊
, then consider the valuation profile v2, and observe that SW(𝜇 | v2) = 0, whereas
5
In Appendix B we provide a complete argument that employs the concept of rotations, which we define and discuss in
Appendix A. Our first
result of the section is a rather negative one, namely that the Deferred Acceptance algorithm, and,
in fact, any ordinal algorithm for the stable matching problem, has unbounded distortion. To show
that, we construct an instance that only has two stable matchings, the man-optimal matching and the
woman-optimal matching.Where the paper says it
Where the paper says it
Where the paper says it
C The Proof of Lemma 4.1
This section provides a proof for Lemma 4.1, which characterizes the possible stable matchings on the cyclic shift profile. p. 7 The distortion of an ordinal algorithm is defined as the worst-case ratio (over all valuation profiles
v) of the maximum social welfare on v, over the (expected) social welfare of the matching A (≻v)
outputted by the algorithm on input the preference profile ≻v induced by v. As we mentioned in the
Introduction, we are concerned with the best possible distortion within the set of stable matchings, and
therefore the numerator in the definition of the distortion will be the maximum social welfare of any
stable matching. Our main technical result of this section is a matching lower bound,
which shows that no ordinal randomized algorithm for stable matching can achieve a better distortion. This bound is in fact quite robust, as it also applies to ex-ante stable (or stable fractional) matchings,
a weaker stability notion investigated by Caragiannis et al. Our main technical result of this section is a matching lower bound,
which shows that no ordinal randomized algorithm for stable matching can achieve a better distortion. This bound is in fact quite robust, as it also applies to ex-ante stable (or stable fractional) matchings,
a weaker stability notion investigated by Caragiannis et al.Where the paper says it
Where the paper says it
Where the paper says it
D Improved Distortion Bounds for Structured Preference Profiles
This section provides improved upper bounds on the number of queries required to achieve a distortion of 1 + ε when the Hasse diagram of the rotation poset is a path. It presents Algorithm 6, which uses a PosetSearch subroutine to search for stable matchings based on social welfare queries. p. 2 Intuitively, this one query allows the algorithm to identify the best
matching between the man-optimal and the woman-optimal matchings, which, in turn, provides a
2-approximation to the social welfare of the overall optimal matching. Hence, the more interesting
question here is how many queries an algorithm would have to perform in order to beat the distortion
2 barrier. In the former case,
we prove that a simple randomized version of the DA algorithm achieves a distortion of 2, and that
this is optimal among all randomized stable matching algorithms. For the latter case, we prove
that the same bound of 2 can be achieved with only 1 query per agent, and improving upon this
bound requires Ω(log𝑛) queries per agent.Where the paper says it
Where the paper says it
Algorithm 5 PosetSearch
This algorithm searches for a stable matching by querying the social welfare of matchings in M, using binary search. It iteratively finds the next target matching with the largest index such that SW(mu tv) ≤ (1 + ε) · SW(mu lstarv). p. 5 Like before, we will simply write M𝑠 when ≻ is clear from
context. We next present the definition of an optimal stable matching.Where the paper says it
Algorithm 6 HassePath
This algorithm returns a stable matching that achieves distortion 1 + ε using at most 8 log2(n) queries per agent when the rotation poset R is a path. It uses the structure of the rotation poset to search for matchings faster. p. 3 We manage to improve the reliance on 𝜀 over the bound of Informal Theorem 3 for instances of the
problem that display a specific structure in the agents’ preferences. More precisely, we consider restrictions on the type of directed graph associated with the rotation poset of the instance.Where the paper says it
Table 1 Empirical average-case distortion bounds
This table summarizes empirical average-case distortion bounds for the Deferred Acceptance algorithm across different statistical models and distributions. It shows that the distortion of the Deferred Acceptance algorithm is very close to 1 in all cases. p. 2 It is not hard to
see that a randomized version of the Deferred Acceptance algorithm, which selects the proposing side
equiprobably, has a distortion of 2. Our main technical result of this section is a matching lower bound,
which shows that no ordinal randomized algorithm for stable matching can achieve a better distortion.Where the paper says it
Figure 6 The average-case distortion of Deferred Acceptance, as well as its Randomized and 1-query versions
This figure displays the average-case distortion of various stable matching algorithms on the Spiked Uniform Distribution for different values of n. It shows that in this case, the distortion is still no larger than 1. p. 3 Average-case Distortion. While our main impossibility result for ordinal deterministic algorithms
renders the Deferred Acceptance algorithm impractical in terms of its worst-case distortion, the algorithm may still exhibit good levels of social welfare on typical instances. We then turn our attention to algorithms that employ a (limited)
amount of cardinal information on top of the preference rankings in Section 4. Here, we adopt the
model of query enhanced algorithms, introduced by Amanatidis et al. We then turn our attention to algorithms that employ a (limited)
amount of cardinal information on top of the preference rankings in Section 4. Here, we adopt the
model of query enhanced algorithms, introduced by Amanatidis et al.Where the paper says it
Where the paper says it
Where the paper says it
Figure 4 The cyclic shift profile used in the proof of Theorem 3. p. 5 , 1987]; we refer to the corresponding algorithm that achieves that as Ailg. It is not true that every pair (𝑚𝑖
,𝑤𝑗) can be part of a stable matching; see for example the preference
profile of Figure 1. , 1987]; we refer to the corresponding algorithm that achieves that as Ailg. It is not true that every pair (𝑚𝑖
,𝑤𝑗) can be part of a stable matching; see for example the preference
profile of Figure 1. , 1987]; we refer to the corresponding algorithm that achieves that as Ailg. It is not true that every pair (𝑚𝑖
,𝑤𝑗) can be part of a stable matching; see for example the preference
profile of Figure 1.Where the paper says it
Where the paper says it
Where the paper says it
This figure illustrates the cyclic shift preference profile used in the proof of Theorem 3.3. It shows that the set of stable matchings on this instance consists of the “cyclic diagonals”. p. 2 Our main technical result of this section is a matching lower bound,
which shows that no ordinal randomized algorithm for stable matching can achieve a better distortion. This bound is in fact quite robust, as it also applies to ex-ante stable (or stable fractional) matchings,
a weaker stability notion investigated by Caragiannis et al.Where the paper says it
Figure 5 The argument used in the proof of Theorem 4. p. 4 the best) stable matching as the Price of Anarchy (resp. the Price of Stability), two notions that are typically used in the
context of equilibrium performance in strategic games [Koutsoupias and Papadimitriou, 1999; Anshelevich et al.Where the paper says it
This figure depicts the argument used in the proof of Theorem 4.3, illustrating how uninformed regions are updated after a query. p. 0 In the former case,
we prove that a simple randomized version of the DA algorithm achieves a distortion of 2, and that
this is optimal among all randomized stable matching algorithms. For the latter case, we prove
that the same bound of 2 can be achieved with only 1 query per agent, and improving upon this
bound requires Ω(log𝑛) queries per agent. It is not hard to
see that a randomized version of the Deferred Acceptance algorithm, which selects the proposing side
equiprobably, has a distortion of 2. Our main technical result of this section is a matching lower bound,
which shows that no ordinal randomized algorithm for stable matching can achieve a better distortion.Where the paper says it
Where the paper says it
Figure 3 The reverse cyclic shift profile used in the proof of Theorem 3. p. 5 , 1987]; we refer to the corresponding algorithm that achieves that as Ailg. It is not true that every pair (𝑚𝑖
,𝑤𝑗) can be part of a stable matching; see for example the preference
profile of Figure 1. , 1987]; we refer to the corresponding algorithm that achieves that as Ailg. It is not true that every pair (𝑚𝑖
,𝑤𝑗) can be part of a stable matching; see for example the preference
profile of Figure 1. , 1987]; we refer to the corresponding algorithm that achieves that as Ailg. It is not true that every pair (𝑚𝑖
,𝑤𝑗) can be part of a stable matching; see for example the preference
profile of Figure 1.Where the paper says it
Where the paper says it
Where the paper says it
This figure presents the reverse cyclic shift profile used in the proof of Theorem 3.3. It shows that every agent has a different favorite and suitor, and every man ranks his suitor second. p. 5 , 𝑎𝑗 ≻𝑎𝑖
𝑎𝑗
′, for all 𝑎𝑗
′ ∈ 𝐴¯ \ {𝑎𝑗 }. We will call an agent 𝑎𝑗 ∈ 𝐴¯ the suitor of
agent 𝑎𝑖
, and we will denote it by 𝑠(𝑎𝑖), if 𝑎𝑖 appears first in agent 𝑎𝑗
’s ranking, i.Where the paper says it
Figure 1 An example of a preference profile in which no agent is matched with their top choice
This figure provides an example of a preference profile where the only stable matching has social welfare 0, while the best non-stable matching has positive social welfare.
Figure 2 An example on which any ordinal stable algorithm has unbounded distortion
This figure illustrates a preference profile on which any ordinal stable algorithm has unbounded distortion. It shows that there are only two stable matchings, the man-optimal matching and the woman-optimal matching. p. 1 Our first
result of the section is a rather negative one, namely that the Deferred Acceptance algorithm, and,
in fact, any ordinal algorithm for the stable matching problem, has unbounded distortion. To show
that, we construct an instance that only has two stable matchings, the man-optimal matching and the
woman-optimal matching.Where the paper says it
Figure 5 Argument used in the proof of Theorem 4. p. 4 the best) stable matching as the Price of Anarchy (resp. the Price of Stability), two notions that are typically used in the
context of equilibrium performance in strategic games [Koutsoupias and Papadimitriou, 1999; Anshelevich et al. the best) stable matching as the Price of Anarchy (resp. the Price of Stability), two notions that are typically used in the
context of equilibrium performance in strategic games [Koutsoupias and Papadimitriou, 1999; Anshelevich et al. the best) stable matching as the Price of Anarchy (resp. the Price of Stability), two notions that are typically used in the
context of equilibrium performance in strategic games [Koutsoupias and Papadimitriou, 1999; Anshelevich et al.Where the paper says it
Where the paper says it
Where the paper says it
This figure depicts a situation where uninformed regions are updated after a query, showing how U k m1∩U k w1 ≥ 1. It shows that the set of stable matchings is exactly Ms = [mu0, mu1,..., mu n-1].
This figure shows that the set of stable matchings on this instance consists of the “cyclic diagonals”. It illustrates that every agent a j in Abar is a stable partner, and hence S ai = Abar. p. 5 It is not true that every pair (𝑚𝑖
,𝑤𝑗) can be part of a stable matching; see for example the preference
profile of Figure 1. It will be useful to consider, for an agent 𝑎𝑖 ∈ 𝐴, only those agents 𝑎𝑗 ∈ 𝐴¯that 𝑎𝑖 can
be matched with in some stable matching.Where the paper says it
This figure shows that man m i has preference ranking w i≻m i w i+1≻m i w i+2≻m i. It illustrates that woman w j ranks men in the following order m(j−1+k) (mod n)+1 ≻ m(j−1+k) (mod n)+2≻m(j-1+k) (mod n)+3. p. 9 For example, the entry (𝑚2,𝑤3) is (1, 3) which indicates that 𝑚2 ranks 𝑤3 first
among the women, and 𝑤3 ranks 𝑚2 third among the men. In this preference profile there are only
two stable matchings, the man-optimal matching, consisting of entries circled in blue with solid lines,
and the woman-optimal matching, consisting of entries circled in red with dashed lines.Where the paper says it
This figure shows the situation after query t has been asked to man m1 for woman w4, partitioning the previous uninformed region U t-1 m1 into a new uninformed region U t m1.
This figure shows that the distortion of is not as close to 1 as in the cases of the other three distributions, but it is still no larger than 1.5 in all cases, with the exception of the Mallows Model and n=3.
This table shows empirical average-case distortion bounds for the Deferred Acceptance algorithm on randomly generated valuation profiles across different statistical models and distributions. It is clear from the table that the distortion of the Deferred Acceptance algorithm is very close to 1 in all cases. p. 0 , the social welfare. Our first result is a strong
impossibility: the classic Deferred Acceptance (DA) algorithm of Gale and Shapley [1962], as well as
any deterministic algorithm that relies solely on ordinal information about the agents’ preferences,
has unbounded distortion.Where the paper says it
This figure shows that every agent a j in Abar is a stable partner, and hence S ai = Abar.
This figure shows that man m i has preference ranking w i≻m i w i+1≻m i w i+2≻m i. It illustrates that woman w j ranks men in the following order m(j−1+k) (mod n)+1 ≻ m(j-1+k) (mod n)+2≻m(j-1+k) (mod n)+3. p. 9 For example, the entry (𝑚2,𝑤3) is (1, 3) which indicates that 𝑚2 ranks 𝑤3 first
among the women, and 𝑤3 ranks 𝑚2 third among the men. In this preference profile there are only
two stable matchings, the man-optimal matching, consisting of entries circled in blue with solid lines,
and the woman-optimal matching, consisting of entries circled in red with dashed lines.Where the paper says it
**Figure 5 Argument used in the proof of Theorem 4.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Adaptive query-enhanced stable matching algorithms can achieve a distortion of 1 plus epsilon using O(log n/epsilon 2) queries per agent for any constant epsilon greater than 0. This allows AI systems to compute high-quality stable matchings when access to agents' cardinal preferences is limited, trading query complexity for approximation quality.
-
Algorithms employing a single query per agent can achieve a distortion of at most 2, which is the best possible among all randomized stable algorithms. This suggests that systems with minimal information access can still achieve a guaranteed performance floor of 2 on typical inputs.
-
For preference profiles whose rotation poset has a path structure, an algorithm called HassePath achieves distortion 1 plus epsilon with at most 8 log2(n) epsilon queries per agent, improving the query complexity bound from O(log n/epsilon 2) to O(log n/epsilon). This allows for more efficient computation of high-quality stable matchings in structured preference settings.
-
The average-case distortion of the Deferred Acceptance algorithm is at most 2 when agents' values are drawn independently and identically distributed, and experiments suggest this value might be closer to 1 on typical inputs. This provides a practical expectation for the performance of standard matching algorithms in real-world scenarios with noisy or random preference data.
-
The Stable-TSF algorithm can achieve distortion at most 1 plus epsilon using min n, n/4 log2 n / epsilon squared o queries per agent, which is asymptotically best possible when epsilon is a constant. This provides a strong theoretical guarantee for the query complexity trade-off in achieving high approximation quality.
Abstract
We initiate the study of distortion in stable matching. Concretely, we aim to design algorithms that have limited access to the agents' cardinal preferences and compute stable matchings of high quality with respect to some aggregate objective, e.g., the social welfare. Following the recent agenda of Amanatidis et al. (2021), we seek to find the best possible tradeoffs between the distortion of an algorithm and the amount of information elicited via means of cardinal value queries. As a warm-up, we show that purely ordinal algorithms (i.e., algorithms that only use the preference rankings of the agents but no value queries), including the classic Deferred Acceptance (DA) algorithm of Gale and Shapley (1962), have unlimited distortion. Despite this strong impossibility, we observe that a simple randomized version of the DA algorithm achieves a distortion of 2, and show that this is in fact optimal among all randomized stable matching algorithms. We then consider algorithms that also use value queries on top of the ordinal ranking information. Again, it is easy to see that the same bound of 2 can be achieved with only 1 value query per agent, and thus we focus on the question of improving upon this bound. To this end, we provide two strong lower bounds, namely that any stable matching algorithm requires Ω(n) non-adaptive value queries or Ω(n) adaptive value queries per agent to achieve a distortion smaller than 2, where n is the number of agents. Finally, we show an asymptotically tight bound of Θ((1+n epsilon)/epsilon) on the number of queries that are necessary and sufficient to achieve near-optimal distortion, i.e., a distortion of 1+ epsilon, for any epsilon >0.
Sources
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments