Marriage Matching, Knuth

University of Connecticut

DigitalCommons@UConn
Economics Working Papers

Department of Economics

5-1-2007

Marriage Matching: A Conjecture of Donald
Knuth
Vicki Knoblauch
University of Connecticut

Follow this and additional works at: http://digitalcommons.uconn.edu/econ_wpapers
Recommended Citation
Knoblauch, Vicki, "Marriage Matching: A Conjecture of Donald Knuth" (2007).Economics Working Papers. Paper 200715.
http://digitalcommons.uconn.edu/econ_wpapers/200715

This is brought to you for free and open access by the Department of Economics at DigitalCommons@UConn. It has been accepted for inclusion in
Economics Working Papers by an authorized administrator of DigitalCommons@UConn. For more information, please contact
digitalcommons@uconn.edu.

Department ofEconomics Working Paper Series
Marriage Matching: A Conjecture of Donald Knuth
Vicki Knoblauch
University of Connecticut

Working Paper 2007-15
May 2007

341 Mansfield Road, Unit 1063
Storrs, CT 06269–1063
Phone: (860) 486–3022
Fax: (860) 486–4463
http://www.econ.uconn.edu/
This working paper is indexed on RePEc, http://repec.org/

Abstract
Variations of the Gale-Shapley algorithmhave been used and studied extensively in real world markets. Examples include matching medical residents with
residency programs, the kidney exchange program and matching college students
with on-campus housing. The performance of the Gale-Shapley marriage matching algorithm (1962) has been studied extensively in the special case of men’s and
women’s preferences random. We drop the assumptionthat women’s preferences
are random and show that En /n ln n → 1, where En is the expected number of
proposals made when the men-propose Gale-Shapley algorithm is used to match
n men with n women. This establishes in spirit a conjecture of Donald Knuth
(1976, 1997) of thirty years standing. Under the same assumptions, we also establish bounds on the expected ranking by a woman of her assignedmate. Bounds
on men’s rankings of their assigned mates follow directly from the conjecture.
Journal of Economic Literature Classification: C78, D63, D70
Keywords: Two-Sided Matching, Gale-Shapley algorithm

1. Introduction.
One basic line of research in the field of two-sided matching problems is concerned
with the performance of the Gale-Shapley algorithm (1962). In particular, when theGaleShapley algorithm is used to match n men with n women, how many proposals will be
made and what will an individual’s ranking of his or her assigned mate be? This paper addresses these questions in the context of men’s preferences random and women’s
preferences arbitrary. That case is important as a transitional case halfway between the
well-studied case in which all preferences are random andthe more general setting of men’s
and women’s preferences arbitrary.
Before we address these questions about proposals and rankings in the transitional
case, we need to describe the marriage matching problem and the Gale-Shapley algorithm.
Given n men, n women and for each individual a preference ranking of the n members of
the opposite sex, the problem is to find a stable matching into ncouples, each consisting
of a man and a woman. A matching is stable if there do not exist a man and a woman
such that each prefers the other to his assigned mate. We will call the n ranking order
lists of each group (men or women) a preference profile.
As shown by Gale and Shapley (1962), the Gale-Shapley algorithm always produces
a stable matching. We will actually work with the McVitie-Wilsonversion (1971) of the
Gale-Shapley algorithm which produces a stable matching in n rounds. In round 1 the
first man proposes to his most preferred woman. She tentatively accepts and round 1 ends.
In round i > 1, the ith man proposes to his most preferred woman. If she has not been
proposed to before, she tentatively accepts and round i ends. Otherwise she tentatively
accepts man i if she prefers...