📈 economics

Note on the size of a stable matching

This paper establishes that in a one-to-one matching market where the largest individually rational matching has size $n$ , every stable matching must contain at least $\lceil n/2 \rceil$ pairs, characterizes the preference profiles that achieve this lower bound, and analyzes the trade-offs between maximizing employment and maintaining stability.

Original authors: Gregory Z. Gutin, Philip R. Neary, Anders Yeo

Published 2026-06-26

📖 4 min read☕ Coffee break read

CC0 1.0

Original authors: Gregory Z. Gutin, Philip R. Neary, Anders Yeo

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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 job market as a giant dance floor. On one side, you have workers looking for a partner. On the other side, you have firms (or dance partners) looking for a worker. Everyone has a "wish list" of who they would prefer to dance with, and they would rather sit out than dance with someone they dislike.

The paper by Gutin, Neary, and Yeo asks a simple but tricky question: If we find the absolute best possible way to pair everyone up (the "maximum matching"), how many people are guaranteed to be dancing if we insist on a "stable" arrangement?

Here is the breakdown of their findings using simple metaphors:

1. The "50% Rule" (The Main Discovery)

Imagine you have a room full of people. You find the absolute maximum number of pairs you can form where everyone is happy to be paired. Let's say you can pair up 100 people (50 pairs) in this "perfect world" scenario.

The paper proves that if you look for a stable arrangement (where no two people would secretly prefer to leave their current partners to dance with each other), you are guaranteed to have at least 50 people (25 pairs) dancing.

The Metaphor: Think of stability like a "no cheating" rule. Even if you try to force the most efficient dance floor possible, the "no cheating" rule might force some couples to break up. However, the authors prove you will never lose more than half your dancers. You will always have at least half the number of pairs you could theoretically achieve.

2. When Does the Worst Case Happen?

The paper also asks: What kind of preferences cause us to lose exactly half the dancers?

They found that this happens when the "unwanted" people (those who can't find a partner in the stable version) are completely unacceptable to each other.

The Metaphor: Imagine the workers who didn't get a job in the stable version. If they looked at the empty dance spots and said, "I'd rather sit on the couch than dance with any of those empty spots," then the system locks into a smaller, stable group.
The "Agreement at the Top": The paper also describes a specific pattern where everyone who does get a job agrees that the people who didn't get a job are at the very bottom of their wish lists. This "agreement" creates a wall that prevents the system from expanding to fill all the empty spots, keeping the number of dancers at exactly the minimum 50%.

3. The Cost of "Full Employment"

The final part of the paper explores a trade-off. What happens if we try to fill every single job opening, even if it means breaking up stable couples?

The authors show a surprising relationship:

If the stable group is as small as it possibly can be (the 50% scenario), then none of the pairs in that stable group will be part of the "maximum employment" group.
The Metaphor: Imagine you have a stable dance circle of 25 couples. If you try to expand the floor to fit 50 couples, you might have to break up every single one of those original 25 couples to make room for new, different pairings.
The Takeaway: Trying to maximize the number of people employed doesn't just mean adding new people; it might require sacrificing the specific, stable relationships that already exist. There is a hidden cost to "filling all vacancies" that goes beyond just the number of people; it involves losing the specific pairings that were working well.

Summary

In short, the paper tells us:

Stability is safe: Even in the worst-case scenario, a stable market will always employ at least half as many people as the theoretical maximum possible.
The "Unacceptable" Trap: The market shrinks to this minimum size only when the unemployed workers and empty jobs simply refuse to accept each other.
The Trade-off: If you try to force the market to hire everyone, you might have to completely dismantle the existing stable pairs. You can't always have both "maximum employment" and "keeping the original stable couples."

The authors limit their study to this specific "one-to-one" dance floor scenario and do not claim these rules apply to more complex markets (like couples applying together or schools with multiple spots), though they suggest those might be interesting future topics.

Technical Summary: Note on the Size of a Stable Matching

Problem Statement
The paper investigates the relationship between the size of a stable matching and the size of the largest individually rational (maximum) matching in a one-to-one two-sided matching market (workers and single-position firms). While the Gale-Shapley framework guarantees the existence of stable matchings, it does not guarantee that these matchings maximize the number of employed workers or filled positions. The authors address the following question: Given a market where the largest individually rational matching contains $n$ pairs, what is the lower bound on the number of pairs in any stable matching? Furthermore, they seek to characterize the specific preference structures that force stable matchings to be as small as possible relative to the maximum, and analyze the overlap between stable pairs and maximum pairs.

Methodology
The authors employ a graph-theoretic approach to model the matching market, utilizing both undirected and directed graph formulations.

Undirected Graph Formulation: The market is modeled as a bipartite graph $G = (W, F; E)$ , where edges represent acceptable pairs. The authors utilize the properties of maximal and maximum matchings to establish bounds.
Directed Graph (Digraph) Formulation: To characterize preference structures, the authors adopt the matching digraph formulation proposed by Maffray (1992). In this digraph $D = (V, A)$ , vertices represent acceptable pairs $(w, f)$ , and arcs represent preference rankings (e.g., an arc from $(w, f)$ to $(w, f')$ indicates worker $w$ prefers $f'$ to $f$ ).
Iterated Deletion of Unattractive Alternatives (IDUA): The authors utilize the IDUA procedure (Balinski and Ratier, 1997; Gutin et al., 2023) to reduce the market to its "normal form." This process iteratively removes pairs that cannot belong to any stable matching (e.g., pairs where a participant is matched to a less preferred partner while their most preferred partner is unmatched).
Constructive Characterization: The authors define specific classes of markets ( $G_n$ and $F_n$ ) by constructing preference profiles that extend a base market with a maximum stable matching, adding new participants whose preferences are structured to be "unattractive" to the existing stable participants.

Key Contributions and Results

Theorem 1 (Size Bound): The primary result establishes that in any market where the largest individually rational matching has size $n$ , every stable matching must have a size of at least $\lceil n/2 \rceil$ .
- Proof Logic: The proof relies on two facts: (i) a stable matching is a maximal matching (no acceptable pair exists with both parties unmatched), and (ii) any maximal matching in a graph is at least half the size of a maximum matching.
- Implication: The equilibrium employment rate can never fall below 50% of the maximum attainable employment, provided the maximum matching is individually rational.
Theorem 2 (Characterization of Extremal Preferences): The paper characterizes the class of preference profiles ( $F_n$ ) that attain this lower bound.
- A market attains the bound (stable size = $\lceil n/2 \rceil$ , max size = $n$ ) if and only if it belongs to the class $F_n$ .
- Structural Property: In these markets, participants who do not appear in any stable matching (the "unmatched" in equilibrium) must find each other unacceptable. If they found each other acceptable, they would form a blocking pair, increasing the stable matching size.
- Agreement at the Top: A natural subclass of these markets exhibits "agreement at the top," where participants in the stable core rank all new, non-stable participants below their least preferred stable partner.
Theorem 3 (Overlap and Sacrifice): The authors analyze the intersection between the set of pairs in a stable matching ( $\mu^*$ ) and a maximum matching ( $\mu$ ).
- Let $r$ be the number of common pairs. The theorem states: $|\mu^*| \geq (|\mu| + r) / 2$ .
- Implication: When the stable matching is minimized (i.e., $|\mu^*| = \lceil |\mu|/2 \rceil$ ), the overlap $r$ must be zero. This means that if the market is structured such that stable matchings are as small as possible, none of the pairs in the stable matching appear in the maximum matching.
- Cost of Stability: Maximizing employment (filling all vacancies) may require "sacrificing" all equilibrium pairings that would otherwise exist in a smaller, stable configuration.

Significance and Scope
The paper frames its analysis as an exploration of the "cost of stability." It quantifies the trade-off between stability and efficiency (measured by matching size). The authors note that while stability ensures no blocking pairs, it can result in a significant reduction in the number of employed workers compared to the theoretical maximum, specifically in markets with the preference structures identified in Theorem 2.

The authors explicitly limit the scope of their results to one-to-one two-sided matching markets. They acknowledge that while the framework is widely applicable (e.g., student-college, doctor-hospital), the specific bounds and characterizations derived here do not automatically extend to more complex environments such as many-to-one markets, markets with couples, or one-sided "roommate" problems. The paper does not propose new algorithms or experimental applications but rather provides a theoretical bound and a structural characterization of the worst-case scenarios for employment rates in stable equilibria.

1. The "50% Rule" (The Main Discovery)

2. When Does the Worst Case Happen?

3. The Cost of "Full Employment"

Summary

More like this