A generalization of the stable marriage algorithms involving group preferences in resource allocation problems

Li, Zhi Cheng
Journal Title
Journal ISSN
Volume Title
Starting Page
Ending Page
Alternative Title
The resource allocation problem usually involves optimization on uniform resources. This thesis solves the problem of finding matchings between several resources and activities which are optimal for a given linear objective function and are stable with regard to preferences of the resources and activities. The concept of a stable matching comes from the stable marriage problem. Given an equal number of men and women, and, for each person, a strictly ordered preference list containing all the members of the opposite sex, a stable marriage is a one-to-one matching of men and women in which there is no man and woman who prefer each other to their partners. Although this stable marriage problem with its strictly ordered preference lists (no ties or indifference) has been studied for three decades in computer science, there are few applications. When arbitrary indifference is allowed, the stable marriage problem has more applications but fails to have some valuable properties such as Pareto Efficiency and majority assignment. We suggest using group preference lists to allow limited indifference in applications. That is, each person belongs to a group that has a preference list for all groups of the opposite sex. We show that with this approach, stability guarantees Pareto Efficiency. We have constructed a correct definition of majority assignment for our case, and show that stability also guarantees majority assignment. For our approach, there is also a polynomial-size representation of all the stable matchings for a given problem. Thus polynomial-time complexity algorithms are possible for optimization over all such matchings. We give algorithms to find the maximal elements in the solution lattice, to find the polynomial-size representation of the solution lattice using rotations, and to find the partial order on the set of rotations. The first two algorithms generalize those of Gale-Shapley and Gusfield. The third one is new. All three algorithms run in O(Np) time, where N is the total number of men or women, p is the number of groups in the other sex. We also develop the lattice structure theory supporting the algorithms.
Thesis (Ph. D.)--University of Hawaii at Manoa, 1992.
Includes bibliographical references (leaves 91-92)
vii, 92 leaves, bound ill. 29 cm
Geographic Location
Time Period
Related To
Theses for the degree of Doctor of Philosophy (University of Hawaii at Manoa). Communication and Information Sciences; no. 2824
All UHM dissertations and theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission from the copyright owner.
Rights Holder
Email libraryada-l@lists.hawaii.edu if you need this content in ADA-compliant format.