Access Restriction

Author Irving, Robert W. ♦ Leather, Paul ♦ Gusfield, Dan
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1987
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract In an instance of size $\textit{n}$ of the stable marriage problem, each of $\textit{n}$ men and $\textit{n}$ women ranks the members of the opposite sex in order of preference. A stable matching is a complete matching of men and women such that no man and woman who are not partners both prefer each other to their actual partners under the matching. It is well known [2] that at least one stable matching exists for every stable marriage instance. However, the classical Gale-Shapley algorithm produces a marriage that greatly favors the men at the expense of the women, or vice versa. The problem arises of finding a stable matching that is optimal under some more equitable or egalitarian criterion of optimality. This problem was posed by Knuth [6] and has remained unsolved for some time. Here, the objective of maximizing the average (or, equivalently, the total) “satisfaction” of all people is used. This objective is achieved when a person's satisfaction is measured by the position of his/her partner in his/her preference list. By exploiting the structure of the set of all stable matchings, and using graph-theoretic methods, an $\textit{O}(\textit{n}4)$ algorithm for this problem is derived.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1987-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 34
Issue Number 3
Page Count 12
Starting Page 532
Ending Page 543

Open content in new tab

   Open content in new tab
Source: ACM Digital Library