טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentDeutsch Yael
SubjectOn the Stable Roommates Problem
DepartmentDepartment of Industrial Engineering and Management
Supervisor Mr. Uriel Rothblum (Deceased)
Full Thesis textFull thesis text - English Version


Abstract

We address the Stable Roommates Problem introduced by Gale and Shapley [1962]. Irving [1985] resolved a question raised by Knuth [1976] and obtained a polynomial-time algorithm, that determines if a stable matching exists for a given problem and constructs one when the answer is positive. Irving's algorithm considers instances when the number of agents is even and any agent prefers all the other agents than to be single. We simplify Irving's algorithm and extend it to fit the general case, when the number of agents is arbitrary and preferences are partial. We use the extended algorithm as a basis for developing other polynomial-time algorithms, which address several problems: (i) List all the possible stable partners of a given agent, (ii) Splitting the set of agents in a given Stable Roommates Problem into those that can be matched in a stable way and those that their presence disrupts stability and (iii) Exploring truth revelations and the existence of a mechanism that enforces truth revelations in the Stable Roommates Problem.

We also show that Pareto-optimal matching, a notion introduced by Morrill [2008], always exists for the general case of the Roommates Problem and introduce an extended polynomial-time algorithm, which determines if a given Roommates matching is Pareto-optimal and if it is not, modifies it to be one. Here, again, we extend results (of Morrill), who considered the special case when the number of agents is even and any agent prefers all the other agents than to be single.