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

dc.contributor.author Li, Zhi Cheng
dc.date.accessioned 2009-07-15T17:27:41Z
dc.date.available 2009-07-15T17:27:41Z
dc.date.issued 1992
dc.description Thesis (Ph. D.)--University of Hawaii at Manoa, 1992.
dc.description Includes bibliographical references (leaves 91-92)
dc.description Microfiche.
dc.description vii, 92 leaves, bound ill. 29 cm
dc.description.abstract 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.
dc.identifier.uri http://hdl.handle.net/10125/9533
dc.language.iso en-US
dc.relation Theses for the degree of Doctor of Philosophy (University of Hawaii at Manoa). Communication and Information Sciences; no. 2824
dc.rights 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.
dc.title A generalization of the stable marriage algorithms involving group preferences in resource allocation problems
dc.type Thesis
dc.type.dcmi Text
Files
Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
uhm_phd_9312205_r.pdf
Size:
2.46 MB
Format:
Adobe Portable Document Format
Description:
Version for non-UH users. Copying/Printing is not permitted
No Thumbnail Available
Name:
uhm_phd_9312205_uh.pdf
Size:
2.43 MB
Format:
Adobe Portable Document Format
Description:
Version for UH users