Abstract
Two sides of $n$ people each rank everyone on the other side. A matching is stable if no two people prefer each other to their current partners. A matching is made by one side proposing in order of preference while the other side keeps the best offer so far (the Gale--Shapley method), and it is compared with all matchings. No new theorem or law is claimed.
First, the proposing method always produces a stable matching——making $300$ random sets of preferences with $6$ on each side and finding every stable matching among all $720$, the result of the proposing method was stable in all $300$ (Section 2).
Second, and this is the core. Every proposer gets the best, and every receiver the worst, partner——in all $300$ sets, each proposer got the best partner obtainable in any stable matching, and each receiver the worst (Section 2).
Third, there need not be only one stable matching——with $6$ on each side the number of stable matchings averaged $1.856667$, at most $6$, and was exactly one in $0.426667$ of the sets. With only one it does not matter who proposes; with several, the proposers take the end better for them (Section 2).
Fourth, with more people the gap widens——averaging, over $200$ sets with $100$ on each side, where one’s partner stands in one’s own ranking, proposers were at $\mathbf{5.081700}$ and receivers at $\mathbf{19.731150}$, a gap of $\mathbf{3.882785}$ times (Section 3).
Fifth, the separator is which side proposes——with the same people and preferences, swapping the proposing side swaps which side takes its best end. Both results remain “stable” (Section 3).
Keywords: stable marriage problem, Gale-Shapley algorithm, matching, proposer advantage, mechanism design.
Scope (what is not claimed)
No new theorem or law is claimed——that the proposing method always produces a stable matching, best for proposers and worst for receivers (Gale and Shapley, $1962$), the structure of stable matchings (Knuth, $1976$; Roth and Sotomayor, $1990$), and that the average rank of one’s partner is about $\ln n$ for proposers and $n/\ln n$ for receivers (Pittel, $1989$) are all known. Institutions are not discussed——the assignment of medical residents or school choice are not entered. Preferences are random——real biases in preferences and false reporting are not treated. Relation to earlier papers: Paper 161 showed that “fixed point” theorems are different things according to what each demands and delivers——for stable matchings, the procedure that shows existence also decides which matching is made, and that matching leans to one side. What is added is checking every matching with $6$ on each side against the proposing method, giving the distribution of the number of stable matchings and the average ranks with $100$ on each side, and placing the separator on which side proposes.
1. Notation and the Question
Setting: there are $n$ proposers and $n$ receivers, and each ranks the $n$ people on the other side. A one-to-one matching is stable if there is no pair who both prefer each other to their current partners.
The proposing method: a proposer without a partner proposes to the most preferred person not yet refusing them. A receiver keeps only the most preferred of the offers so far and refuses the rest. A refused proposer proposes to the next preferred person. It ends when nobody is refused.
Question: is the result of the proposing method stable, where does it lie among the stable matchings, and which side does it favour?
2. Comparing with All Matchings
Computation 2.1: $300$ random sets of preferences with $6$ on each side were made, and for each set all $6!=720$ matchings were examined to find every stable one (a route independent of the proposing method).
| what was checked | out of $300$ sets |
|---|---|
| the proposing method’s result is stable | $300$ |
| every proposer has the best partner among stable matchings | $300$ |
| every receiver has the worst partner among stable matchings | $300$ |
Computation 2.2: the number of stable matchings averaged $1.856667$, with a minimum of $1$ and a maximum of $6$; $0.426667$ of the sets had exactly one.
Observation 2.3 this is the core: every proposer gets the best, and every receiver the worst, partner. When there are several stable matchings, they have a good end and a bad end as seen from the proposers. The proposing method takes the proposers’ good end for all of them at once——seen from the receivers, the same matching is the bad end for all of them. One side’s best is the other side’s worst.
Observation 2.4 with only one stable matching, no difference arises. In $0.426667$ of the $300$ sets there was exactly one stable matching, and it does not matter who proposes——in the rest there are two or more, and the proposers decide which is taken.
3. More People
Computation 3.1: $200$ random sets of preferences with $100$ on each side were matched by the proposing method, and the position of one’s partner in one’s own ranking was averaged.
| side | average rank of partner | asymptotic guide |
|---|---|---|
| proposers | $\mathbf{5.081700}$ | $\ln100=4.605170$ |
| receivers | $\mathbf{19.731150}$ | $100/\ln100=21.714724$ |
The ratio of receivers to proposers was $\mathbf{3.882785}$. Using the harmonic number $H_{100}=5.187378$, the guides are $5.187378$ and $100/H_{100}=19.277564$, both close to the measurements.
Observation 3.2 with more people the proposers’ advantage widens. Proposers are matched with about their fifth choice of $100$; receivers with about their twentieth——both matchings are stable, and nobody has a reason to run off with someone else. Still, the gains are split heavily in the proposers’ favour.
Observation 3.3 the separator is which side proposes. With the same people and preferences, swapping proposers and receivers lets the former receivers take their best end——“stable” does not name one matching but a set with two ends. Fixing the procedure is choosing one of those ends.
Observation 3.4 beside Paper 161. Paper 161 showed that “fixed point” theorems are different things according to what each demands and delivers——unlike a theorem that only states existence, the proposing method builds a stable matching, and returns a particular one among them, the best for the proposers.
Observation 3.5 what is not said. The assignment of residents and school choice are not entered. Preferences are random, and false reporting is not treated——what is shown is the comparison with all matchings for $6$ on each side, the average ranks for $100$ on each side, and that swapping the proposing side swaps the advantage.
4. Roll Call and Closing
- the proposing method was stable in all $300$ sets (Computation 2.1): checked against all matchings.
- every proposer gets the best (Computation 2.1): in all $300$.
- every receiver gets the worst (Computation 2.1): in all $300$.
- one side’s best is the other’s worst (Observation 2.3): the core.
- stable matchings average $1.856667$ (Computation 2.2): at most $6$.
- exactly one in $0.426667$ of sets (Observation 2.4): there, no difference.
- proposers at $\mathbf{5.081700}$ with $100$ each (Computation 3.1): close to $\ln n$.
- receivers at $\mathbf{19.731150}$ (Computation 3.1): close to $n/\ln n$.
- ratio $\mathbf{3.882785}$ (Computation 3.1): widening with more people.
- the separator is which side proposes (Observation 3.3): swap it and the advantage swaps.
Closing: When two sides rank each other, one side proposing in order while the other keeps the better offer produces a stable matching. And the proposing side comes out ahead——checking against all $720$ matchings for $300$ random sets with $6$ on each side, the result was always stable, every proposer got the best partner possible among stable matchings, and every receiver the worst. With more people the gap widens——with $100$ on each side, the average rank of one’s partner was $5.081700$ for proposers and $19.731150$ for receivers, $3.882785$ times apart. The separator is which side proposes——stable matchings form a set with two ends, and fixing the procedure chooses one end. Placed among the earlier papers——unlike the theorems of existence separated in Paper 161, here the procedure also decides what it makes, and that leans to one side. To be honest——preferences are random, and neither institutions nor false reporting are entered.
References
- Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly.
- Knuth, D. E. (1976). Mariages stables et leurs relations avec d’autres problèmes combinatoires. Les Presses de l’Université de Montréal.
- Pittel, B. (1989). The average number of stable matchings. SIAM Journal on Discrete Mathematics.
- Roth, A. E., & Sotomayor, M. A. O. (1990). Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press.
- Yamagishi, Y. (2026). A Fixed Point Is Not One Theorem [Paper 161]. Zenodo. 10.5281/zenodo.22092530
Reference
Yamagishi, Y. (2026). In a Stable Matching, the Side That Proposes Comes Out Ahead [Paper 615]. YOI: https://www.yamagishiyuuki.com/yoi/615
DOI: 10.5281/zenodo.23014484
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 615. This paper is a preprint and has not been peer reviewed.