Fair and efficient student placement with couples (Q2458423)

The paper considers the student placement problem or house allocation. A student placement problem is determined by a set of position types, the number of available positions of each type, and the students' strict preferences over position types. The aim in this problem is to find a mechanism for the assignment of positions to students, so that each student will receive at most one position based on his/her priorities. For markets without couples, e.g., for undergraduate student placement, acyclicity is a necessary and sufficient condition for the existence of a fair and efficient placement mechanism. The paper shows that in the presence of couples, acyclicity is still necessary, but not sufficient. A second necessary condition is the priority-togetherness of couples. The paper is structured in five sections, besides the introductory one. In section 2 the student placement problem with couples is introduced, while section 3 introduces the notions of efficiency, fairness, and acyclicity. Section 4 studies the necessary conditions for the compatibility of fairness and efficiency, while section 5 focuses on special placement problems where only one position is available for each position type, and extends the some the results of the previous study to general student placement problems.