Balancing Fairness in Two-Sided Stable Matching Markets

26 concepts18 papers1 proposal

In the classic "Stable Marriage" problem, the Gale-Shapley Deferred Acceptance (DA) algorithm is celebrated for its efficiency and its guarantee of stability—a state where no two participants would both prefer to be with each other over their current partners. However, this stability comes at a steep cost: a fundamental structural asymmetry. As Tziavelis et al. observe, the standard algorithm is strictly proposer-optimal. The side that initiates the offers receives their best possible stable match, while the receiving side is relegated to their worst.

This "proposer-optimal bias" is not merely a mathematical curiosity; it creates significant social unfairness in real-world markets like labor recruitment, school admissions, and organ donation.

The Structural Roots of Inequality

The bias stems from how the algorithm handles choice. In a typical DA setup, proposers move through their preference list from top to bottom. The receivers, meanwhile, can only "hold" the best offer they have received so far, waiting for something better to arrive. Because the proposers control the sequence of offers, they exhaust their favorite options first. By the time the algorithm terminates, the proposers have secured the highest-ranked partner possible that doesn't result in an unstable pair, while receivers are often left with their "pessimal" stable partner.

Shi et al. describe this as "unilateral dominance," where the party initiating the match holds disproportionate power. This imbalance is so pronounced that it motivates strategic manipulation. Gonczarowski et al. demonstrate that the disadvantaged side has a strong incentive to lie about their preferences to achieve better outcomes. In more extreme cases, Hosseini et al. show that a member of the receiving side can even improve their match by conspiring with an "accomplice" on the proposing side.

The Computational Hurdle of Equity

If the two extremes (proposer-optimal and receiver-optimal) are easy to compute but unfair, why not simply find a "middle ground" matching? The challenge is that finding a balanced stable matching—one that minimizes the gap in happiness between the two sides—is NP-hard. Roy et al. highlight that while finding any stable match is fast, finding one that guarantees a specific level of fairness is computationally daunting.

To bridge this gap, researchers have developed new algorithmic frameworks:

  • Deferred Local Search (DLS): Tziavelis et al. introduced DLS to achieve high-equity matchings in quadratic time, providing a practical alternative to the biased Gale-Shapley approach.
  • ISORROPIA: To find the exact optimal balanced matching, Wu et al. developed a method that prunes the search space of stable marriages, reaching solutions up to 1,000 times faster than previous exact methods.
  • The Swing Algorithm: In practical applications like teacher allocations, Morge et al. utilize the Swing algorithm to balance the competing priorities of trainees and supervisors more equitably.

When Markets Balance Themselves

Interestingly, the proposer-optimal bias is not always catastrophic. The nature of the market itself can sometimes act as a stabilizer. Brilliantova et al. found that when preferences are highly correlated—meaning most people agree on who the "best" partners are—the standard Gale-Shapley algorithm naturally produces fairer, more "sex-equal" outcomes.

Furthermore, the advantage is highly sensitive to market size. Vetta et al. proved the "short-side advantage": in a random market, adding just one extra participant to the proposing side causes the strategic power to flip entirely to the receiving side. This happens because the "extra" proposer triggers a domino effect of new offers, allowing the receivers to be much pickier.

Stability as a Shield for Bias

The stakes of algorithmic fairness are highest when they intersect with systemic social bias. Celis et al. argue that when candidate evaluation scores are biased (e.g., in college admissions), standard stable matching algorithms can actually reinforce inequity. In these cases, the mathematical definition of "stability" serves to institutionalize historical disadvantages, funneling underprivileged candidates into their lower-ranked choices even when representational quotas are met.

To combat this, Monachou et al. propose "Directed Matching" policies. By algorithmically identifying biased evaluators and "shielding" vulnerable participants from them, platforms can foster more equitable long-term welfare without sacrificing the overall efficiency of the market.

Ultimately, the shift in this research area is from viewing matching as a purely combinatorial problem to viewing it as a socio-technical one, where the choice of who proposes determines not just the mathematical outcome, but the fairness of the system itself.

Key Foundational Work

Sisterhood in the Gale-Shapley Matching Algorithm (2013) — contributed 1 concept elements to this direction.
An Extended Protocol for Multiple-Issue Concurrent Negotiation (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_proposer_optimal_bias_ea24dd9d,
  title = {proposer-optimal bias},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proposer-optimal-bias/rdr_ea24dd9db3e24e2bbb85ec58cbe88c7b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_proposer_optimal_bias_ea24dd9d_v1,
  title = {proposer-optimal bias},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proposer-optimal-bias/rdr_ea24dd9db3e24e2bbb85ec58cbe88c7b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake