Premium
Match making: Assignments based on bilateral preferences
Author(s) -
Gärdenfors Peter
Publication year - 1975
Publication title -
behavioral science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.371
H-Index - 45
eISSN - 1099-1743
pISSN - 0005-7940
DOI - 10.1002/bs.3830200304
Subject(s) - disjoint sets , preference , stability (learning theory) , stable marriage problem , function (biology) , mathematical optimization , computer science , mathematics , distribution (mathematics) , linear programming , combinatorics , mathematical economics , statistics , matching (statistics) , machine learning , mathematical analysis , evolutionary biology , biology
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.