Marriage Matching: A Conjecture of Donald Knuth

Vicki Knoblauch ()

No 2007-15, Working papers from University of Connecticut, Department of Economics

Abstract: Variations of the Gale-Shapley algorithm have 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 assumption that 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 assigned mate. Bounds on men's rankings of their assigned mates follow directly from the conjecture.

Keywords: Two-Sided Matching; Gale-Shapley algorithm (search for similar items in EconPapers)
JEL-codes: C78 D63 D70 (search for similar items in EconPapers)
Pages: 16 pages
Date: 2007-05
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://media.economics.uconn.edu/working/2007-15.pdf Full text (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:uct:uconnp:2007-15

Access Statistics for this paper

More papers in Working papers from University of Connecticut, Department of Economics University of Connecticut 365 Fairfield Way, Unit 1063 Storrs, CT 06269-1063. Contact information at EDIRC.
Bibliographic data for series maintained by Mark McConnel ().