Note on the size of a stable matching

Anders Yeo; Gregory Z. Gutin; Philip R. Neary

REVIEW 2 major objections 6 minor 12 references

Note on the size of a stable matching

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that every stable matching has at least $\lceil n/2 \rceil$ pairs whenever the largest individually rational matching has $n$ pairs, and it characterises the markets that achieve this bound.

desk verdict The lower bound is true but folklore, and the advertised characterization is either tautological or rests on an ambiguous definition; not a serious contribution as written. read the letter →

arxiv 2505.24637 v2 pith:SDDWJMSG submitted 2025-05-30 econ.TH

Gregory Z. Gutin , Philip R. Neary , Anders Yeo This is my paper · ORCID

classification econ.TH MSC 91B6805C70

keywords stablematchingtwo-sidedindividuallyrationalmaximumnormalformdigraphtightboundemploymentrate

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This note asks how much employment a stable matching can be forced to sacrifice. It proves that in any one-to-one two-sided matching market, if the largest individually rational matching has $n$ pairs, then every stable matching has at least $\lceil n/2 \rceil$ pairs. The bound is tight, and the paper characterises the preferences that attain it: a small core of participants who appear in every stable matching, surrounded by extra workers and firms who are all ranked below the core and who find no one from the other added side acceptable. A consequence is that the equilibrium employment rate can be driven arbitrarily close to zero by padding the market with additional unattractive participants, even though no stable matching can fall below half of the feasible maximum.

What carries the argument

The matching digraph $D=(V,A)$ is the central object: vertices are acceptable worker–firm pairs, and arcs point from a less-preferred to a more-preferred pair from the worker's side (horizontal arcs) or the firm's side (vertical arcs). A stable matching is exactly an independent set of vertices such that every vertex outside the set has an out-neighbour inside it, which lets the paper reason about preferences as paths and cycles in a graph. The other load-bearing tool is the normal form of a market, obtained by iteratively deleting unattractive alternatives, which reduces any market to a balanced one containing only participants who appear in every stable matching. This normal form underpins the remark after Definition 1 and is what lets the class $\mathcal{G}_n$ be defined by adding new workers and firms around a stable core.

What would settle it

Enumerate all strict preference matrices for three workers and three firms and identify every market whose largest individually rational matching has size 3 and whose stable matchings all have size 2. Theorem 2 asserts that each such market must be constructible by the $\mathcal{F}_n$ recipe; if any one of them is not, the characterisation fails.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1: fix a one-to-one two-sided matching market with an individually rational matching of size $n$; then every stable matching has size at least $\lceil n/2 \rceil$. The proof is a short contradiction—if a stable matching were smaller, some edge of a maximum matching would have both endpoints unmatched, and that edge would be an acceptable pair blocking stability. Theorem 2 shows the bound is tight and identifies the class of markets that attain it, denoted $\mathcal{F}_n$. Up to a normal-form reduction that deletes everyone who appears in no stable matching, such a market consists of a balanced core with a stable matching of size $\lceil n/2 \rceil$, to which one adds at least $\lfloor n/2 \rfloor$ new workers and firms; every added participant is acceptable only to core participants, ranks core participants below the core's own least attractive stable partner, and no new worker finds any new firm acceptable. The paper proves that a market contains a matching of size $n$ and a stable matching of size $\lceil n/2 \rceil$ if and only if it belongs to $\mathcal{F}_n$.

Load-bearing premise

The characterisation depends on reading Definition 1's instruction to 'add an arc' from a new worker to an existing firm as applying only when that worker–firm pair is already acceptable, not as forcing every new worker to be acceptable to every firm in the stable core.

Editorial extensions

If this is right

If Theorem 1 is correct, no stable outcome in a one-to-one market can ever drop below half the size of the largest individually rational matching, so the worst-case efficiency loss from stability is bounded by a factor of two.
Because the bound is tight, market designers know that half-size stable outcomes are possible and that the responsible preference structures are exactly the ones described by $\mathcal{F}_n$.
Any market can be padded with arbitrarily many new workers and firms who are ranked below the core and find each other unacceptable, so the equilibrium employment rate can be driven arbitrarily close to zero while a stable matching of size $\lceil n/2 \rceil$ persists.
The normal form of a market pins down which participants can ever appear in a stable matching; the characterisation says the tight bound occurs precisely when all other participants are 'below' the core and disconnected from each other.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Extension: the same factor-of-two floor may hold for many-to-one matching with fixed quotas, since the proof of Theorem 1 only needs a blocking pair to exist when both endpoints of a maximum-matching edge are unmatched.
Extension: the characterisation makes it trivial to generate all small tight-bound markets, which could support computational studies of how often real preference profiles land on the worst case.
Connection: the normal-form viewpoint suggests that the guaranteed stable-matching size rises with the size of the always-matched core, so any design that enlarges that core may automatically raise the floor.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: the half-size lower bound is real but it's just the standard observation that stable matchings are maximal and maximal matchings are at least half the size of a maximum matching. The paper's claimed characterization is the soft spot: Definition 1 is ambiguous in a way that matters, and Theorem 2 ends up restating the definition of F_n.

What's good: Theorem 1 is correctly proved, and the direct proof is fine for a note. The digraph setup is a legitimate way to draw extremal examples, and the 'agreement at the top' discussion gives a clean sufficient condition for the bound to bind. If Definition 1 were fixed, Lemma 1's forward direction would likely go through.

The problems: Definition 1 says to add an arc from (w',f) to (w,f) for every new worker w' and every firm f in µ, without saying that (w',f) must be a vertex. The literal reading forces every new worker to be acceptable to every firm in µ, contradicting the paper's own Figure 1, where w3 is acceptable only to f2. The proof of Lemma 1 uses the permissive reading — arc only when the vertex exists. So the definition as printed is inconsistent with the example and the proof. Under the permissive reading, G_n is simply the set of markets with a stable matching of size n, so Lemma 1 is true but tautological, and Theorem 2 is a restatement of the definition of F_n. That is not a characterization in any informative sense.

There are also typos: 'F' = FR \ Wµ' should be F_R \ F_µ, and the stable matchings in Figure 1 are misprinted. Minor, but symptomatic of a rushed draft.

Who this is for: someone who wants to cite the half-size bound might use it, but they'd be citing folklore. The characterization doesn't do the advertised work. I'd desk-reject as is. If the authors fix the definition and honestly present Theorem 1 as folklore, a note might be worth a second look, but the current text overclaims.

Referee Report

2 major / 6 minor

Summary. The paper studies one-to-one two-sided matching markets with the possibility of unacceptable partners. Its first result, Theorem 1, states that if the largest individually rational matching has n pairs, then every stable matching has at least ceil(n/2) pairs. The proof uses the observation that, if a stable matching had fewer than ceil(n/2) pairs, some edge of a maximum individually rational matching would have both endpoints unmatched, creating a blocking pair. The paper then develops a digraph construction in Section 3, defining classes G_n and F_n, proving Lemma 1 (a market has a stable matching of size n iff it belongs to G_n) and Theorem 2 (a market contains a matching of size n and a stable matching of size ceil(n/2) iff it belongs to F_n). The final part of Section 3 describes a sufficient condition, called 'agreement at the top', under which the bound is attained.

Significance. Theorem 1 is correct and its proof is concise, but the bound is a standard consequence of the fact that a stable matching is maximal, and any maximal matching in a bipartite graph has size at least half the maximum matching; the ceiling arises simply from integrality. The constructive examples in Figures 1 and 2 do demonstrate that the bound is tight. The advertised characterization, however, is not delivered: F_n is defined as the class of markets in G_ceil(n/2) with a matching of size n, and Lemma 1 identifies G_ceil(n/2) with markets having a stable matching of size ceil(n/2), so Theorem 2 is a definitional restatement. The paper would need either a genuine preference-based characterization or a honest reframing as a note on the tightness example to meet the claims in the abstract.

major comments (2)

[Section 3, Definition 1 and Lemma 1] Definition 1 says that for any (w,f) in mu and w' in W', 'we add an arc from (w',f) to (w,f)'. Since arcs in the digraph D=(V,A) are defined only between vertices (acceptable pairs), this instruction is ambiguous: either it presupposes that every (w',f) is a vertex, or it must be read as 'if (w',f) is a vertex, add the arc'. The strict reading forces every new worker to accept every original firm and vice versa, which contradicts the paper's own example in Figure 1, where w3 is acceptable only to f2; it would also make the forward direction of Lemma 1 false. The permissive reading is the one actually used in the proof of Lemma 1 (the disjunction 'either (w',f) not in V(D_R) or (w',f)(w,f) in A(D_R)'), but it is never stated in Definition 1. Because Lemma 1 is the only bridge between the graph construction and the economic properties, this ambiguity is load-bearing for the characterization claim.
[Section 3, definition of F_n and Theorem 2] The class F_n is defined on page 7 as 'all markets in G_ceil(n/2) with a matching of size n', with an 'In other words' paragraph giving an equivalent constructive description. Lemma 1 establishes that G_ceil(n/2) is exactly the class of markets containing a stable matching of size ceil(n/2). Therefore Theorem 2, which states that a market contains a matching of size n and a stable matching of size ceil(n/2) if and only if R belongs to F_n, is true by definition; its proof merely unpacks the definition. The promised 'characterisation of the class of preferences that attain the bound' is thus vacuous, and the sufficient 'agreement at the top' condition at the end of Section 3 does not supply a necessary characterization. This is a central issue because the abstract and introduction advertise the characterization as the paper's main contribution beyond Theorem 1.

minor comments (6)

[Section 3, proof of Lemma 1] In the proof of Lemma 1, 'F′ = FR \ Wµ' should read 'F′ = FR \ Fµ'.
[Section 1, proof of Theorem 1] The sentence 'This implies that µ∗ is not individually rational' is not the right conclusion after adding an edge to µ∗; adding an acceptable edge between two unmatched agents produces a larger individually rational matching and creates a blocking pair. The conclusion that µ∗ is not stable is correct, but the wording should be adjusted.
[Section 1, proof of Theorem 1] The existence of an edge in µmax with neither endpoint in µ∗ follows from the counting observation that at most 2|µ∗| edges of µmax can have an endpoint in µ∗, and 2|µ∗| < n follows from |µ∗| < ceil(n/2). The proof should state this counting argument explicitly.
[Section 3, Definition 1] There are several typographical issues: 'for all markets with n workers, n firms, and contains a stable matching' is ungrammatical; in the 'In other words Fn' paragraph, '(w,f) ∈ S' should be '(w,f) ∈ μ', and 'specified by I' should be 'specified by P'.
[Section 3, Figure 1] The text says 'There are two stable matchings both of size two, {(1,1),(2,2)} and {(1,1),(2,2)}'; the second matching should presumably be {(1,2),(2,1)}.
[Section 2, matching digraph] The displayed definition 'D = V, A)' is missing the opening parenthesis and should be 'D = (V, A)'.

Circularity Check

2 steps flagged · score 7.0 of 10

The characterization theorems reduce to the definitions: Gn is generated from a market that already has a stable matching of size n, and Fn is explicitly defined as the class of markets with the very properties Theorem 2 states.

self definitional [Section 3, Definition 1 and Lemma 1]
"Let P be any matching market with a set of n workers, W, and a set of n firms, F, that contains a stable matching, µ, of size n. Add any number of new workers W′ and any number of new firms F′. ... This defines the class Gn. ... Lemma 1. A stable matching problem, R, contains a stable matching of size n if and only if R ∈ Gn."

Definition 1 constructs every member of Gn by starting from a base market P that already contains a stable matching µ of size n, and then forces arcs so that every old matched pair is preferred to any new participant. Thus the original µ remains stable in the generated market by construction. Lemma 1's forward direction merely verifies these same defining conditions, and its reverse direction simply observes that µ is still stable. The claimed characterization therefore restates the construction mechanism rather than establishing an independent structural criterion for the class of markets with a stable matching of size n.
self definitional [Section 3, definition of Fn and Theorem 2]
"let n be an integer, odd or even, and define a class of markets, Fn, as all markets in G⌈n/2⌉ with a matching of size n. ... Add at least ⌊n/2⌋ new workers W′ and at least ⌊n/2⌋ new firms F′ such that there is a matching of size n in the resulting instance. ... Theorem 2. A matching market, R, contains a matching of size n and a stable matching of size ⌈n/2⌉ if and only if R ∈ Fn."

Fn is defined, by the paper's own words, as the set of markets in G⌈n/2⌉ that also contain a matching of size n; by Definition 1 and Lemma 1, G⌈n/2⌉ is equivalently the set of markets containing a stable matching of size ⌈n/2⌉. Therefore membership in Fn is, by construction, exactly the conjunction 'contains a stable matching of size ⌈n/2⌉ and a matching of size n', which is precisely the predicate Theorem 2 claims to characterize. The proof's statement that all markets in Fn contain a matching of size n 'by construction' confirms that the equivalence is definitional rather than derived from independent conditions.

full rationale

The paper's first result, Theorem 1, is self-contained and non-circular: its proof uses only that a stable matching is maximal and that every maximal matching in a bipartite graph has size at least half the maximum matching. The circularity is confined to the advertised characterization. Lemma 1's class Gn is generated from a base market P that already contains a stable matching of size n, and the construction rules force the original µ to remain stable; hence 'R has a stable matching of size n' and 'R ∈ Gn' are equivalent by construction rather than through an independent criterion. Theorem 2 is then a direct restatement of the definition of Fn, which is explicitly 'all markets in G⌈n/2⌉ with a matching of size n'; the proof says the matching of size n is present 'by construction'. Thus the central characterization claim reduces to its own input. Separately, and not scored as circularity, Definition 1 as written presupposes vertices (w′, f) for every new w′ and every f matched in µ, which is inconsistent with Figure 1's R where (w3, f1) is absent; the proof of Lemma 1 uses a weaker conditional. That ambiguity is a real correctness risk in the same passage but is not itself a circularity. Overall the central characterization is definitionally forced, while Theorem 1 retains independent content.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no free parameters and no new entities. It relies on standard matching theory facts and on a result from the authors' own prior paper for the normal form reduction.

assumptions (3)

standard math A stable matching is maximal: no acceptable pair of mutually unmatched participants can exist in a stable matching.
Used in the proof of Theorem 1 and in the introductory remark; it follows directly from the definition of stability.
domain assumption The normal form of any matching market is balanced and consists of the agents matched in every stable matching (rural hospitals theorem with iterated deletion).
Invoked in the remark after Definition 1 to justify assuming n workers and n firms; cited to Balinski and Ratier (1997) and Gutin et al. (2023).
standard math Every maximal matching has size at least half the size of a maximum matching.
Implicit in Theorem 1's proof; the paper's counting argument is a special case of this standard graph theory bound.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Note on the size of a stable matching." pith.science (2026). https://pith.science/paper/SDDWJMSG

@misc{pith2026250524637,
  author       = {Pith},
  title        = {Pith review of: Note on the size of a stable matching},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SDDWJMSG}},
  note         = {Machine review of arXiv:2505.24637}
}

abstract

Consider a one-to-one two-sided matching market with workers on one side and single-position firms on the other, and suppose that the largest individually rational matching contains $n$ pairs. We show that the number of workers employed and positions filled in every stable matching is bounded from below by $\lceil\frac{n}{2}\rceil$ and we characterise the class of preferences that attain the bound. We then identify the minimum number of equilibrium pairings that must be ``sacrificed'' when maximising the employment rate is the objective; if each stable matching is of size $\ceiling{\frac{n}{2}}$, then no such pairs appear when all vacancies are filled.

Figures

Figures reproduced from arXiv: 2505.24637 by the authors.

**Figure 1.** A two-sided matching market, P, with a stable matching of size two (depicted by the yellow vertices) and a matching market, R, with a stable matching of size two and a matching of size 4 (depicted by the red vertices). Note that {(1, 1),(2, 2)} is a stable matching in P but is not in R. Note further that all horizontal and vertical arcs that are implied by transitivity of preferences have been omitted from for reada… view at source ↗

**Figure 2.** On the left is the two-sided matching market, [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 11 canonical work pages

[1]

Of stable marriages and graphs, and strategy and polytopes

Michel Balinski and Guillaume Ratier. Of stable marriages and graphs, and strategy and polytopes. SIAM Review, 39 0 (4): 0 575--604, 1997

work page 1997
[2]

On the existence of stable roommate matchings

Kim-Sau Chung. On the existence of stable roommate matchings. Games and Economic Behavior, 33 0 (2): 0 206--230, 2000

work page 2000
[3]

Crawford and Elsie Marie Knoer

Vincent P. Crawford and Elsie Marie Knoer. Job matching with heterogeneous firms and workers. Econometrica, 49 0 (2): 0 437--450, 1981

work page 1981
[4]

Vazirani

Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani. Online and Matching-Based Market Design. Cambridge University Press, Cambridge, 2023

work page 2023
[5]

Gale and L

D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69 0 (1): 0 9--15, 1962

1962
[6]

Gutin, Philip R

Gregory Z. Gutin, Philip R. Neary, and Anders Yeo. Unique stable matchings. Games and Economic Behavior, 141: 0 529--547, 2023

work page 2023
[7]

Job matching, coalition formation, and gross substitutes

Jr Kelso, Alexander S and Vincent P Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50 0 (6): 0 1483--1504, November 1982

work page 1982
[8]

Kernels in perfect line-graphs

Fr \'e d \'e ric Maffray. Kernels in perfect line-graphs. Journal of Combinatorial Theory, Series B, 55 0 (1): 0 1--8, 1992

work page 1992

Show all 12 references

[9]

D. G. McVitie and L. B. Wilson. Stable marriage assignment for unequal sets. BIT Numerical Mathematics, 10 0 (3): 0 295--309, 1970

1970
[10]

Alvin E. Roth. The evolution of the labor market for medical interns and residents: A case study in game theory. Journal of Political Economy, 92 0 (6): 0 991--1016, 1984

1984
[11]

Alvin E. Roth. On the allocation of residents to rural hospitals: A general property of two-sided matching markets. Econometrica, 54 0 (2): 0 425--427, 1986

1986
[12]

Who gets what--and why: the new economics of matchmaking and market design

Alvin E Roth. Who gets what--and why: the new economics of matchmaking and market design. Houghton Mifflin Harcourt, 2015

2015

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Of stable marriages and graphs, and strategy and polytopes

Michel Balinski and Guillaume Ratier. Of stable marriages and graphs, and strategy and polytopes. SIAM Review, 39 0 (4): 0 575--604, 1997

work page 1997

[2] [2]

On the existence of stable roommate matchings

Kim-Sau Chung. On the existence of stable roommate matchings. Games and Economic Behavior, 33 0 (2): 0 206--230, 2000

work page 2000

[3] [3]

Crawford and Elsie Marie Knoer

Vincent P. Crawford and Elsie Marie Knoer. Job matching with heterogeneous firms and workers. Econometrica, 49 0 (2): 0 437--450, 1981

work page 1981

[4] [4]

Vazirani

Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani. Online and Matching-Based Market Design. Cambridge University Press, Cambridge, 2023

work page 2023

[5] [5]

Gale and L

D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69 0 (1): 0 9--15, 1962

1962

[6] [6]

Gutin, Philip R

Gregory Z. Gutin, Philip R. Neary, and Anders Yeo. Unique stable matchings. Games and Economic Behavior, 141: 0 529--547, 2023

work page 2023

[7] [7]

Job matching, coalition formation, and gross substitutes

Jr Kelso, Alexander S and Vincent P Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50 0 (6): 0 1483--1504, November 1982

work page 1982

[8] [8]

Kernels in perfect line-graphs

Fr \'e d \'e ric Maffray. Kernels in perfect line-graphs. Journal of Combinatorial Theory, Series B, 55 0 (1): 0 1--8, 1992

work page 1992