The Distortion of Stable Matching

arXiv:2602.14961 · cs.GT · Submitted 2026-02-16 · Read on arXiv

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

Where the paper says it

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.

14961#pg4>. For query-enhanced algorithms, they show that a deterministic version using only one query per agent achieves a distortion of 2<ref:2602. p. 2
Where the paper says it

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.

14961#pg6>. Furthermore, any query-enhanced algorithm achieving a distortion better than 2 requires at least Ω(logn) adaptive queries or Ω(n) non-adaptive queries per agent<ref:2602. p. 2
Where the paper says it

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.

14961#pg8>.

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

Where the paper says it

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 + 𝜀.

14961#pg9>. Under natural structural restrictions on the instances, they show improved upper bounds on the number of queries required for a (1 + ε)-approximation<ref:2602. p. 0
Where the paper says it

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.

14961#pg10>.

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

Where the paper says it

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].

14961#pg9>. Experiments suggest that the empirical average-case distortion might be much closer to 1 on typical inputs. p. 3
Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

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.

Future work includes investigating tighter query bounds and studying other notions of stability like popular matchings. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

1 and Lemma A.2. It establishes that every stable matching can be obtained by eliminating a sequence of rotations from the man-optimal stable matching. p. 6
Where the paper says it

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 𝑤 ∈ 𝑆𝑚𝑖 .

B Uniqueness of the Stable Matchings in the Proof of Theorem 3. p. 2

Where the paper says it

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.

1

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

Where the paper says it

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.

It uses the concept of rotations from Definition A. p. 9
Where the paper says it

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.

7 to show that there is a one-to-one correspondence between stable matchings and closed subsets of the rotation poset. p. 1
Where the paper says it

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.

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

Where the paper says it

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.

It shows that the set of stable matchings is exactly Ms = [mu0, mu1,. p. 2
Where the paper says it

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.

p. 2
Where the paper says it

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.

.., mu n-1], where mu k = [(mi, w(i−1+k) (mod n)+1), for k = 0,.., n − 1].

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

Where the paper says it

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.

The result is that the query complexity per agent is QA = 8 log2(n) log2(1+ε). p. 0
Where the paper says it

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.

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

Where the paper says it

Like before, we will simply write M𝑠 when ≻ is clear from context. We next present the definition of an optimal stable matching.

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

Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

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.

5 in all cases, with the exception of the Mallows Model and n=3. p. 2
Where the paper says it

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.

p. 2
Where the paper says it

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.

Figure 4 The cyclic shift profile used in the proof of Theorem 3. p. 5

Where the paper says it

, 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.

p. 5
Where the paper says it

, 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.

p. 5
Where the paper says it

, 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.

3

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

Where the paper says it

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.

Figure 5 The argument used in the proof of Theorem 4. p. 4

Where the paper says it

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.

3

This figure depicts the argument used in the proof of Theorem 4.3, illustrating how uninformed regions are updated after a query. p. 0

Where the paper says it

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 shows that U k m1∩U k w1 ≥ 1. p. 2
Where the paper says it

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.

Figure 3 The reverse cyclic shift profile used in the proof of Theorem 3. p. 5

Where the paper says it

, 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.

p. 5
Where the paper says it

, 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.

p. 5
Where the paper says it

, 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.

3

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

Where the paper says it

, 𝑎𝑗 ≻𝑎𝑖 𝑎𝑗 ′, 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.

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

Where the paper says it

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.

Figure 5 Argument used in the proof of Theorem 4. p. 4

Where the paper says it

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.

p. 4
Where the paper says it

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.

p. 4
Where the paper says it

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.

3

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

Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

, 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.

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

Where the paper says it

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.

**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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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