An efficient algorithm for the “optimal” stable marriage

ABSTRACT

In an instance of size n of the stable marriage problem, each of n men and 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 O(n4) algorithm for this problem is derived.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: GALE, D., AND SHAPELY, L. S. College admissions and the stability of marriage. Am. Math. Monthly 69 (1962), 9-15.
• 3: Dan Gusfield, Three fast algorithms for four problems in stable marriage, SIAM Journal on Computing, v.16 n.1, p.111-128, Feb. 1987 [doi>10.1137/0216010]
• 4: IRVING, R.W. An efficient algorithm for the "stable room-mates" problem. J. Algorithms 6 (1985), 577-595.
• 5: Robert W Irving , Paul Leather, The complexity of counting stable marriages, SIAM Journal on Computing, v.15 n.3, p.655-667, August 1986 [doi>10.1137/0215048]
• 6: KNUTH, D. E. Mariages Stables. Les Presses de l'Universit6 de Montr6al, Montr6al, Quebec, Canada 1976.
• 7: D. G. McVitie , L. B. Wilson, The stable marriage problem, Communications of the ACM, v.14 n.7, p.486-490, July 1971 [doi>10.1145/362619.362631]
• 8: PICARD, J. Maximum closure of a graph and applications to combinatorial problems. Manage. Sci. 22 (1976), 1268-1272.
• 9: PICARD, J., AND QUEYRANNE, M. Selected applications of minimum cuts in networks, INFOR-- Can. J. Oper. Res. Inf. Process. 20 (1982), 394-422.
• 10: POLYA, G., TARJAN, R. E., AND WOODS, D.R. Notes on Introductory Combinatorics. Birkhauser Vedag, Boston, Mass., 1983.
• 11: RHYS, J. A selection problem of shared fixed costs and network flows. Manage. Sci. 17 (1970), 200-207.
• 12: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 13: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 14: Niklaus Wirth, Algorithms & data structures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Performance, Theory, Verification