Note on the size of a stable matching

Gregory Z. Gutin Philip R. Neary Anders Yeo · 2025

Read Note on the size of a stable matching by Gregory Z. Gutin Philip R. Neary Anders Yeo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-24637.txt.

Introduction

Gregory Gutin, Philip Neary, and Anders Yeo prove, in a 2025 mathematics note, a floor on the size of stable matchings in a two-sided market. Workers and single-position firms rank each other. A matching is stable when no unmatched pair would both rather break away together.

Suppose the largest self-consistent matching holds n pairs. The authors show every stable matching then employs at least half of n, rounded up. They also pin down exactly which preference patterns hit that floor. A second result counts the equilibrium pairings that must be given up when maximizing employment. Worst-case guarantees like this tell market designers how much stability can cost.

Catalog record

CREATORGregory Z. Gutin Philip R. Neary Anders Yeo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-24637

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Note on the size of a stable matching Thanks: We thank Vince Crawford, Gabriel Facchini, Evan Piermont, Michael Richter, Frances Ruane, Joel Sobel, Ija Trapeznikova, and Gregory F. Veramendi for useful discussions. Any remaining errors are ours. Gregory Z. Gutin Philip R. Neary Anders Yeo 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 n pairs. We show that the number of workers employed and positions filled in every stable matching is bounded from below by ⌈ n 2 ⌉ \lceil\frac{n}{2}\rceil and we characterise the class of preferences that attain the bound. 1 Introduction Our starting point in this paper is a one-to-one two-sided matching market, à la Gale and Shapley 1962 , with ‘‘workers’’ on one side and single-position ‘‘firms’’ on the other. 1 1 1 While we employ labour market terminology (see the classic papers of Crawford and Knoer 1981 and Kelso and Crawford 1982 ), the set up is applied widely and we could have labelled the two sides “students” and “colleges”, or “men” and “women”, etc. Roth 2015 is a popular book that details many environments to which the framework applies. The only assumption we make on preferences is that the largest individually rational matching is of size n . That is, there exists an assignment in which each of the n matched workers prefers their position to being unemployed and each of the n firms that has its post filled prefers its employee over leaving the position empty. Given this, we ask: what fraction of workers are assured of employment in equilibrium? Our first result is that the number of those employed in equilibrium can never go below 50\% of what is attainable. In other words, every stable matching is at least half the size of a maximum matching: Theorem 1 . Fix a one-to-one two-sided matching market with an individually rational matching of size n . Then, every stable matching has at least \lceil\frac{n}{2}\rceil pairs. Formulating the stable matching problem using undirected graphs facilitates a short proof. 2 2 2 This formulation appears in, for example, Chapter 1 of the Echenique et al. 2023 edited volume “Online and Matching-Based Market Design” ( Echenique et al. 2023 ). Fix a bipartite graph, G=(W,F;E) , where W and F are the set of workers and the set of firms respectively, and the edge set, E , represents the acceptable pairs (i.e., for each edge, both parties prefer to be matched to each other over being unmatched). Finally, assume that each vertex has a strict preference ranking over each of its neighbours. Proof. Let \mu_{\max} denote a maximum (possibly non-stable) matching of size n . Let \mu^{*} denote a stable matching, and suppose, towards a contradiction, that |\mu^{*}|<\lceil\frac{n}{2}\rceil . Since the inequality is strict, there exists an edge in \mu_{\max} with neither end-point in \mu^{*} . But because any such edge corresponds to an acceptable pair, there is some acceptable pair, call it (w,f) , where both parties are unmatched in \mu^{*} . This implies that \mu^{*} is not individually rational, since we could add the edge (w,f) , and therefore contradicts that \mu^{*} is stable. ∎ While succinct, the proof of Theorem 1 is not particularly informative. Indeed, two natural questions remain unanswered. Is the bound tight? And in the event that it is, what is the structure of preferences that attain it? Theorem 2 confirms that the answer to the first question is “yes” and it also resolves the second. All preferences that attain the bound share a property: amongst those participants that do not appear in an individually rational matching, and therefore also not in any stable one, at least one must find the other unacceptable. If not, then there would be an acceptable pair amongst them which would increase the size of a feasible assignment. One natural (sub)class of preferences that attain the bound possess this property and also have a feature that could be termed “agreement on those at the top”. That is, every workers that appears in a stable matching ranks the firms that do not appear in a stable matching below the firms that do (with a similar statement for firms). It is worth emphasising that Theorem 1 does not guarantee that the equilibrium employment rate – the number of workers with jobs as a percentage of the total labour force – must be at least 50%. Far from it. Indeed, our characterisation illustrates how any two-sided market could, in theory, be extended indefinitely so that the equilibrium employment rate can be taken arbitrarily close to zero even when there are unemployed workers and unfilled jobs out there. As mentioned above, this kind of market failure will maintain as long as either unemployed workers prefer unemployment over any of the empty vacancies or the opposite (or both). Section 2 defines the environment and fixes notation. Despite having stated Theorem 1 in the language of undirected graphs, going forward we change tack and adopt the directed graph (digraph) formulation of the stable matching problem due to Maffray 1992 . Our reason for settling on this approach is that it provides a nice visual aid to illustrate preferences that attain the bound. In Section 3 , we characterise this class using digraphs. 2 Preliminaries The set up is the original one-to-one two-sided matching model of Gale and Shapley 1962 enriched in two ways: (i) there need not be the same number of participants on each side of the market, and (ii) there may be those who prefer to be unmatched over being paired with some participants. Let W denote the finite set of workers and let F denote the finite set of single-position firms . The sets W and F are disjoint. Each market participant has a complete, transitive, and strict preference ordering over some nonempty subset of those on the other side of the market. A matching is a one-to-one mapping \mu from W\cup F to itself, such that: \mu(w)=f if and only if \mu(f)=w , in which case we will say that w is matched to f ; if \mu(w) is not in F , then \mu(w)=w , in which case w is unmatched ; if \mu(f) is not in W , then \mu(f)=f , in which case f is said to be unmatched . A matching is individually rational if no participant prefers to be unmatched over who they are matched to. We say that the pair (w,f) in W\times F is acceptable if w and f prefer each other over being unmatched, and we assume that every market participant belongs to at least one acceptable pair. A matching \mu is stable if it is individually rational and there is no blocking pair: an acceptable pair (w,f) such that worker w is either unmatched or prefers firm f to \mu(w) and firm f is either unmatched or prefers w to \mu(f) . Given a matching market, we define the associated matching digraph , D=\big(V,A) , where the vertex set V is the collection of acceptable pairs and the arc set A is defined as follows. 3 3 3 The digraph

Read the complete text