טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentPerach Nitsan
SubjectThe Stable Matching Model with an Entrance Criterion
DepartmentDepartment of Industrial Engineering and Management
Supervisor Mr. Uriel Rothblum (Deceased)
Full Thesis textFull thesis text - English Version


Abstract

This research concentrates on matching models, which were originally developed by David Gale and Lloyd Shapley (GS) in 1962. One model that GS introduced is the (pure) stable marriage problem. This model has two groups of players each having a preference over being matched with individuals of the other side. GS defined a notion of stability for this model and provided an algorithm that finds a stable match.

In this thesis we extend stable matching models to include an “entrance criterion” for one side of the population. This situation is motivated by a case study of assigning students to dormitory-groups. Under this model students are considered for an assignment only if they meet a competitive eligibility condition. Still, the assignment of the students found eligible is based on preferences of the two sides over the other.

In Chapter 2, we define this model and describe and analyze an algorithm that produces a corresponding stable outcome with desirable properties for the case of a common and complete dormitory-groups preferences list. This algorithm was implemented successfully for the assignment of students to dormitories at the Technion toward the 2004/2005 academic year.  

Chapter 3 generalizes the framework of the first part of this research by relaxing the assumptions that preferences lists of the dormitory-groups are uniform and complete. In particular, dormitory-groups are allowed to use different evaluation criteria for the desirability of having a student be assigned to them. We then adapt the algorithm we used in the first part to the generalized model and show that the extension has most of the properties of the original algorithm. Chapter 3 also includes a study of incentive compatibility (the incentives of the agents to misrepresent their preferences so as to get a better assignment) in the generalized model with the new algorithm. We show that a single student cannon benefit from misrepresenting preferences to the algorithm.

Chapter 4 considers the model introduced in Chapter 3 and provides more solutions (formally quasi-stable outcomes) and mechanisms that produce them. In particular, we explore desirable properties of those mechanisms extending the discussion of incentive compatibility to more than one agent.

The chapters here are presented independently (except for explicit cross-referencing) so as to fit separate publications. In particular, results and equations are enumerated independently in each chapter.