The Distortion of Stable Matching

summary

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…

In short

The paper studies how much a stable matching can be distorted when an algorithm has limited access to agents' full preferences. It shows that standard algorithms have unbounded distortion, but query-enhanced methods can achieve 1+epsilon distortion using queries. Specific structural properties of preference profiles allow for even better query bounds.

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 used across episodes

This episode discusses

The paper

The Distortion of Stable Matching · Read on arXiv

School of Informatics, University of Edinburgh

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.

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 >

More episodes

← Home