Balancing Stability and Fairness in Two-Sided Matching Markets

This direction is split into other directions: stability-fairness tradeoff. Its last version stays readable and citable here.

Version 1 of 128 papers37 conceptsfrozen 2026-10-04

In a classic matching market—like pairing medical residents with hospitals or students with schools—we usually seek stability. A matching is stable if no two participants would both prefer to leave their current assignments to be with each other. Since the seminal work of Gale and Shapley, we have known that at least one stable matching always exists.

However, stability is a "local" property: it merely ensures that no individual pair has the incentive to deviate. It says nothing about the "global" distribution of happiness. Recent research has revealed a troubling reality: the algorithms we use to ensure stability often produce outcomes that are profoundly unfair, systematically favoring one side of the market while leaving the other with their worst possible options.

The Proposer’s Advantage and the Fairness Gap

The standard tool for finding a stable matching is the Deferred Acceptance (DA) algorithm. While efficient, DA is inherently biased. If the "proposing" side consists of doctors, the resulting matching is "doctor-optimal"—every doctor gets the best possible partner they could have in any stable matching. Conversely, it is "hospital-pessimal"—every hospital gets its worst possible stable partner.

As Shraddha Pathak notes in a recent survey, this inherent welfare gap creates a "sex-equality" problem. In many real-world scenarios, such as the "waiting child" problem in Japanese daycare allocation studied by Zhaohong Sun and colleagues, a lack of stability can undermine public trust. Yet, prioritizing stability through standard algorithms often ignores broader social objectives.

The challenge is that finding a "balanced" stable matching—one that minimizes the difference in satisfaction between the two sides—is computationally daunting. Sanjukta Roy and co-authors demonstrated in Balanced Stable Marriage: How Close Is Close Enough? that finding such a middle ground is NP-hard. This creates a fundamental tension: we can easily find a stable matching that is unfair, but finding a stable matching that is fair is a significant algorithmic hurdle.

The Impossibility of Universal Symmetry

Is it even theoretically possible to satisfy everyone? Ulle Endriss used automated SAT solving to prove new "impossibility theorems" in Analysis of One-to-One Matching Mechanisms via SAT Solving. The results show that stability cannot be guaranteed simultaneously with "gender-indifference"—a property requiring the mechanism to treat both sides of the market symmetrically.

This suggests that fairness isn't just computationally hard; it often conflicts with the very structure of stability. In markets with "externalities"—where organizations care about where their affiliates end up—Marina Knittel and John P Dickerson show that stability and social equity diverge even further.

If perfect fairness is impossible or hard to compute, how do we design better markets? Researchers are attacking this from several angles:

  1. Exact Optimization: New algorithms like ISORROPIA, developed by Siyuan Wu and colleagues, can find the exact optimal balanced matching up to 1,000x faster than previous methods. This allows market designers to move away from biased heuristics toward outcomes that minimize maximum dissatisfaction.
  2. Randomization and "Fair Shares": When participants have tied preferences (indifference), a single stable matching can be devastatingly unfair. Shiyun Lin and Vianney Perchet propose using a distribution over matchings. In Stable Matching with Ties: Approximation Ratios and Learning, they show that while no single matching is perfect, a randomized approach can guarantee every participant a "logarithmic fraction" of their best possible outcome.
  3. Bridging Matching and Fair Division: Traditionally, matching (who gets whom) and fair division (who gets how much) were separate fields. Evi Micha and Nisarg Shah have begun to bridge this gap, applying notions like "Envy-Freeness" to two-sided markets to ensure that even if a matching is stable, the participants don't feel "envy" toward the bundles assigned to others.

Why It Works: Stability as a Constraint, Not a Goal

The shift in this research area is treating stability as a constraint rather than the final objective. In decentralized exchange networks, Mohsen Bayati and Christian Borgs showed that fair, balanced outcomes are mathematically equivalent to stable ones. This suggests that in the right network structures, fairness and stability can align.

In practical applications like Fourth-Party Logistics (4PL), Na Yuan incorporates "trading psychology" to set fairness thresholds. If the gap in perceived benefits between two matched parties is too large, the partnership is likely to fail, regardless of its mathematical stability.

Ultimately, the goal of this research direction is to move beyond the "proposer-optimal" binary. By using tools from Nash Social Welfare—as explored by Pallavi Jain and Rohit Vaish—and interactive explanation platforms like MatchXplain by Hadi Hosseini, researchers are making the trade-offs between stability, efficiency, and equity transparent and manageable for real-world decision-makers.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_balancing_stability_and_fairness_in_two__69dacbce,
  title = {Balancing Stability and Fairness in Two-Sided Matching Markets},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/balancing-stability-and-fairness-in-two-sided-matching-markets/rdr_69dacbceff31445ea1cd16892d64bede},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_balancing_stability_and_fairness_in_two__69dacbce_v1,
  title = {Balancing Stability and Fairness in Two-Sided Matching Markets},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/balancing-stability-and-fairness-in-two-sided-matching-markets/rdr_69dacbceff31445ea1cd16892d64bede/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}