📊 statistics

Probably Correct Optimal Stable Matching under Two-Sided Uncertainty

This paper addresses the problem of identifying the optimal stable matching in two-sided markets with initially unknown preferences by introducing the concept of "pervasive stable matching" to leverage partial preference information, thereby proposing efficient elimination-based algorithms for both pure exploration and regret minimization that achieve improved sample complexity and regret bounds independent of the minimum reward gap.

Original authors: Andreas Athanasopoulos, Anne-Marie George, Christos Dimitrakakis

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andreas Athanasopoulos, Anne-Marie George, Christos Dimitrakakis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive, chaotic dance hall where two groups of people—let's call them Dancers and Partners—need to find the perfect dance pair. But here's the catch: nobody knows who they like or who likes them. They have to figure it out by trying to dance together.

Every time a pair dances, they get a "score" (a reward) based on how much they enjoyed it. The goal is to find the Perfect Stable Match: a way of pairing everyone up where no two people would rather switch partners with each other. If such a switch happened, the whole dance floor would become unstable and chaotic.

This paper is about how a central "Dance Manager" can learn the preferences of everyone in the room as quickly as possible to find that perfect, stable lineup, without wasting time on bad dances.

Here is the breakdown of their solution using simple analogies:

1. The Problem: The "Blind Date" Dilemma

Usually, in these matching problems, we assume everyone already knows their preferences (like a speed dating event where everyone has a list). But in the real world (like ride-sharing or hiring), we don't know the preferences yet. We have to learn them by trial and error.

The tricky part is that learning everything about everyone is slow and expensive. If you have 100 dancers, you might think you need to test every single possible pair to know who likes whom. That's a lot of dancing!

2. The Big Idea: "Good Enough" Lists

The authors realized you don't need to know the entire preference list of every dancer to find the perfect match. You just need to know enough to be sure that a specific pairing is the best one.

They use a concept called a "Pervasive Stable Matching."

The Analogy: Imagine you are trying to guess the winner of a race. You don't need to know the exact time of every runner. You just need to know enough to be 100% sure that Runner A is faster than Runner B, and Runner B is faster than Runner C. Once you have that "partial" list, you can declare A the winner without timing everyone down to the millisecond.
In the paper: They show that if you can build a "partial preference map" that guarantees a specific pairing is the best one no matter how the unknown preferences turn out, you can stop learning. This saves a massive amount of time.

3. The Strategy: The "Elimination Game"

The paper proposes a smart algorithm (a set of rules for the Dance Manager) that works like a game of elimination:

The Setup: The manager pairs people up and watches the scores.
The Confidence Zone: As they dance, the manager builds a "confidence interval." Think of this as a fuzzy bubble around the score. If the bubble for Pair A is clearly higher than the bubble for Pair B, the manager knows for sure A is better.
The Cut: Once the manager is sure Pair A is better than Pair B, they eliminate Pair B from future consideration. They stop wasting time testing that pair.
The Stop: The game ends the moment the manager finds a "Pervasive Stable Matching." This means they have eliminated enough bad options that the remaining pairing is mathematically guaranteed to be the best stable one, even if they haven't tested every single possibility.

4. Why This is Better (The "Gap" Problem)

In older methods, the speed of learning depended on the "Minimum Gap."

The Old Way: If two dancers liked each other almost equally (a tiny difference in scores), the manager had to keep dancing with them thousands of times to be sure who was slightly better. This made the process incredibly slow.
The New Way: The authors' method looks at the "Admissible Gap." Because they only need to find a valid partial list (not the full list), they can often stop learning even when the differences between dancers are tiny. They don't need to distinguish between "very similar" options if those options don't matter for the final stable match.

5. The Results: Faster and Smarter

The authors tested this with computer simulations (virtual dance halls):

Speed: Their "Elimination" algorithm found the perfect match much faster than older methods that tried to learn everyone's full list.
Efficiency: They showed that by stopping early (once a "Pervasive" match was found), they saved a huge amount of "sample complexity" (the number of dances needed).
Regret: They also showed that if you have to keep dancing for a long time (minimizing "regret" or bad matches over time), their method still performs better because it learns the essential structure of the preferences faster.

Summary

Think of this paper as a guide for a matchmaker who is too busy to learn everyone's entire life story. Instead, the matchmaker learns just enough to be certain about the best pairings, cuts out the impossible matches early, and stops the process the moment the "perfect" stable group is identified. This saves time, energy, and resources, proving that you don't need to know everything to make the right decision.

Technical Summary: Probably Correct Optimal Stable Matching under Two-Sided Uncertainty

1. Problem Formulation

This work addresses a sequential learning problem within two-sided matching markets where the preferences of agents on both sides are initially unknown. The setting is centralized: an algorithm selects a matching at each time step and receives noisy, stochastic rewards reflecting the underlying utilities of the matched pairs. This follows a semi-bandit feedback structure.

Unlike traditional regret-minimization frameworks common in Multi-Armed Bandit (MAB) literature for matching, this paper adopts a pure exploration perspective. The objective is to design an algorithm that terminates in finite time and outputs the optimal stable matching (specifically the $P$ -optimal stable matching) with high probability ( $1-\delta$ ).

The core challenge is two-sided uncertainty: both sets of agents ( $P$ and $A$ ) have unknown preference rankings. The algorithm must learn these preferences efficiently without necessarily reconstructing the full ranking for every agent, as learning full rankings is often sample-inefficient.

2. Methodology and Key Concepts

2.1 Partial Preferences and Pervasive Stable Matching

The central theoretical innovation is the utilization of partial preference rankings rather than full rankings. The authors leverage the concept of a Pervasive Stable Matching (PSM), introduced by Rastegari et al. [2014].

A matching is a PSM for a partial preference profile if it remains the optimal stable matching for every possible full refinement of that partial profile.
The algorithm's goal is to identify a valid partial preference profile that admits a PSM. Once such a profile is found, the algorithm can terminate, having identified the optimal stable matching without needing to resolve all preference ambiguities.

2.2 Admissible Gap

To analyze sample complexity, the paper defines an admissible gap ( $\Delta_F$ ). Unlike the standard minimum reward gap ( $\Delta_{min}$ ) which considers the hardest-to-distinguish pair in the true full ranking, $\Delta_F$ is defined as the maximum of the minimum gaps over all valid partial preference profiles.

$\Delta_F \ge \Delta_{min}$ .
By focusing on valid partial profiles, the algorithm can avoid dependence on the potentially tiny $\Delta_{min}$ , leading to improved sample complexity bounds.

2.3 Algorithms

The paper proposes several algorithms:

Uniform Exploration Strategies:
- The algorithm samples matchings from a minimal matching cover (derived from edge-coloring arguments on bipartite graphs) to ensure all pairs are sampled uniformly.
- Two variants are analyzed: one using $\Delta_{min}$ and one using $\Delta_F$ to determine the number of exploration rounds. The $\Delta_F$ variant demonstrates that reasoning about partial preferences can significantly reduce sample complexity.
E-PSM (Elimination PSM):
- An adaptive elimination algorithm that does not require prior knowledge of reward gaps.
- Mechanism: It maintains confidence intervals for mean rewards. Pairs are eliminated when their confidence intervals are disjoint, establishing a partial order with high probability.
- Stopping Rule: The algorithm terminates as soon as the current partial preference profile admits a PSM (computed via the POSM algorithm).
- Complexity: The sample complexity bound depends on $\Delta_F$ and utilizes edge-coloring arguments to bound the number of matchings sampled per round.
Extended Elimination (EE-PSM):
- An extension that further eliminates pairs upon identifying a super stable matching (a matching stable under all refinements, even those with indifferences).
- While this can lead to early termination, the paper notes that theoretical guarantees for the sample complexity of this specific extension remain an open problem, though empirical results suggest benefits.
Regret Minimization Meta-Algorithm:
- The authors extend the pure exploration approach to regret minimization by running E-PSM as an exploration phase followed by a "commit" phase.
- This yields a regret bound that avoids dependence on $\Delta_{min}$ , a significant improvement over previous Explore-Then-Commit (ETC) results in two-sided settings.

3. Key Contributions

Two-Sided Uncertainty in Pure Exploration: The work extends prior literature (which largely focused on one-sided uncertainty or regret minimization) to a two-sided learning environment with a pure exploration objective.
Partial Preference Utilization: The paper demonstrates that identifying the optimal stable matching does not require learning full preference orderings. By targeting PSMs, the algorithm bypasses the need to resolve all preference gaps.
Refined Sample Complexity:
- Theoretical bounds are provided for uniform strategies and elimination algorithms that depend on the admissible gap $\Delta_F$ rather than the minimum gap $\Delta_{min}$ .
- The analysis utilizes edge-coloring arguments on bipartite graphs to handle the sampling of matchings efficiently.
Regret Bounds: The paper establishes the first regret bound for two-sided uncertainty with respect to the optimal stable matching that is independent of $\Delta_{min}$ .
Lower Bounds: A theoretical lower bound on sample complexity is established using techniques from combinatorial MAB literature, characterizing the intrinsic difficulty of the problem.

4. Results and Evaluation

4.1 Theoretical Results

Uniform Strategies: Theorem 4.2 shows that using $\Delta_F$ reduces the sample complexity bound from $O(\frac{\ln(KN/\delta)}{\Delta_{min}^2})$ to $O(\frac{\ln(KN/\delta)}{\Delta_{F}^2})$ . Since $\Delta_F$ can be arbitrarily larger than $\Delta_{min}$ , this represents a significant theoretical improvement.
Elimination Algorithm: Theorem 5.1 provides a sample complexity bound for E-PSM that scales with the sum of inverse squared gaps over valid partial profiles.
Regret: Theorem 5.2 provides a regret bound for the meta-algorithm that avoids the $\Delta_{min}$ dependence, a limitation noted in previous ETC approaches.

4.2 Empirical Results

Simulations were conducted on random instances with varying market sizes ( $n$ ):

Sample Complexity: The elimination-based algorithms (E-PSM and EE-PSM) significantly outperformed uniform sampling baselines (U, U-PSM).
Stability: The elimination strategy (E-NS) showed more stable performance across random instances compared to uniform sampling, which exhibited high variability.
Stopping Rule Impact: Comparing E-NS (no stopping rule) to E-PSM (stopping on PSM) highlighted the drastic reduction in sample complexity achieved by the PSM-based stopping criterion.
Regret: In a one-sided uncertainty setting (used for benchmarking against AETGS-E), the E-PSM approach achieved lower cumulative regret than the adaptive elimination baseline, particularly in instances requiring exploration restarts.

5. Significance and Claims

The authors claim that this work provides a more natural framework for analyzing matching algorithms under uncertainty by focusing on pure exploration. The primary significance lies in the decoupling of the learning objective from full preference reconstruction. By identifying that a PSM is sufficient for optimality, the paper demonstrates that algorithms can terminate earlier and with fewer samples than methods requiring full ranking recovery.

The work also claims to resolve a gap in the literature regarding regret bounds in two-sided markets, offering the first bound independent of the minimum reward gap. The authors remain modest regarding the extended elimination rule (EE-PSM), noting that while empirical results are promising, a formal sample complexity guarantee for this specific extension remains an open theoretical challenge.

Finally, the paper identifies the design of algorithms that match the derived lower bounds and the development of efficient approximations for the Track-and-Stop optimization problem as key directions for future research.