Match making: Assignments based on bilateral preferences

The stable marriage problem, i.e., the problem of assigning the members of two disjoint sets to one another is extended to the case in which individual preferences are represented by weak orderings instead of linear orderings. This leads to a more natural solution for such problems as the processing of college admissions and the optimal distribution of personnel. The paper begins with a formal definition of an assignments function and introduces conditions on it, among them stability. It is shown how the Gale and Shapley algorithm for finding stable assignments can be extended to the more general case considered here. It is shown that if there is an assignment which is preferred by a majority to all other assignments, then this assignment is necessarily stable. Moreover, in a situation where all preference orders are linear orders, all stable assignments are majority assignments.