Fair and efficient student placement with couples

We study situations of allocating positions or jobs to students or workers based on priorities. An example is the assignment of medical students to hospital residencies on the basis of one or several entrance exams. 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 (Ergin, 2002). We show that in the presence of couples, which introduces complementarities into the students' preferences, acyclicity is still necessary, but not sufficient (Theorem 4.1). A second necessary condition (Theorem 4.2) is ``priority-togetherness'' of couples. A priority structure that satisfies both necessary conditions is called pt-acyclic. For student placement problems where all quotas are equal to one we characterize pt-acyclicity (Lemma 5.1) and show that it is a sufficient condition for the existence of a fair and efficient placement mechanism (Theorem 5.1). If in addition to pt-acyclicity we require ``reallocation-'' and ``vacancy-fairness'' for couples, the so-called dictator-bidictator placement mechanism is the unique fair and efficient placement mechanism (Theorem 5.2). Finally, for general student placement problems, we show that pt-acyclicity may not be sufficient for the existence of a fair and efficient placement mechanism (Examples 5.4, 5.5, and 5.6). We identify a sufficient condition such that the so-called sequential placement mechanism produces a fair and efficient allocation (Theorem 5.3).

Local and global consistency properties for student placement

In the context of resource allocation on the basis of priorities, Ergin (2002) identifies a necessary and sufficient condition on the priority structure such that the student-optimal stable mechanism satisfies a consistency principle. Ergin (2002) formulates consistency as a local property based on a fixed population of agents and fixed resources -- we refer to this condition as local consistency and to his condition on the priority structure as local acyclicity. We identify a related but stronger necessary and sufficient condition (unit acyclicity) on the priority structure such that the student-optimal stable mechanism satisfies a more standard global consistency property. Next, we provide necessary and sufficient conditions for the student-optimal stable mechanism to satisfy converse consistency principles. We identify a necessary and sufficient condition (local shift-freeness) on the priority structure such that the student-optimal stable mechanism satisfies local converse consistency. Interestingly, local acyclicity implies local shift-freeness and hence the student-optimal stable mechanism more frequently satisfies local converse consistency than local consistency. Finally, in order for the student-optimal stable mechanism to be globally conversely consistent, one again has to impose unit acyclicity on the priority structure. Hence, unit acyclicity is a necessary and sufficient condition on the priority structure for the student-optimal stable mechanism to satisfy global consistency or global converse consistency.