Fleiner (2002, Theorem 5.5), Klaus and Klijn (2006, Theorem 3.2), and Sethuraman et al.
(2006, Theorem 9) generalized Theorem 3 to college admissions problems (Gale and Shapley,
1962) with responsive preferences,7 in which students have to be matched to colleges based
on the students’ and the colleges’ preferences over the other side of the market and colleges’
capacity constraints. It is well-known that for this class of two-sided matching problems the
set of stable matchings is still non-empty and has the “lonely wolf” property, i.e., the set of
single students does not vary from one stable matching to another (see, for instance, Roth
and Sotomayor, 1990, Lemma 5.6 and Theorem 5.12). Martinez et al. (2000) introduced the
domain of q-separable and substitutable preferences for colleges that contains the domain
of responsive preferences. They prove that even for this larger domain the set of stable
matchings is non-empty and that the “lonely wolf” property holds. Surprisingly, we cannot
extend Theorem 3 to the domain of q-separable and substitutable preferences as the following
example shows.
Example 3 No compromise for q-separable and substitutable preferences
Consider Martinez et al.’s (2000, Example 2) college admissions problem with 4 students
s1, s2, s3, s4, 2 colleges C1 and C2 with 2 seats each, and preferences as listed in the table
below. The colleges’ preferences are q-separable and substitutable (for details see Martinez
et al., 2000).
|
ÂC1 |
ÂC2 |
Âs 1 |
Âs2 |
Âs3 |
Âs4 |
|
{s1,s2} |
{s3, s4} |
' |
C2 |
C1 |
C1 |
|
{s1,s3} |
{s2, s4} |
C1 |
C1 |
C2 |
C2 |
|
{s2, s4} |
{s1,s3} | ||||
|
{s3, s4} |
{s1,s2} | ||||
|
{s1,s4} |
{s1,s4} | ||||
|
{s2, s3} |
{s2, s3} | ||||
|
{s1} |
{s1} | ||||
|
{s2} |
{s2} | ||||
|
{s3} |
{s3} | ||||
|
{s4} |
{s4} |
There are 4 stable matchings:
μ 1 = {{C 1, s 1, s2}, {C2, s3, s4}}
μ 2 = {{C 1, s 1, s 3 }, {C2, s 2, s 4 }}
μ 3 = {{C 1, s 2, s 4 }, {C2, s 1, s 3 }}
μ 4 = {{C 1, s 3, s 4 }, {C2, s 1, s 2 }}
Considering the first three matchings, one straightforwardly checks that matching each agent
with its median match is not a matching: C1 would be matched with {s1 , s3} but at the
same time s3 would be matched with C2. ъ
7By responsiveness (Roth, 1985), a college’s preference relation over sets of students is related to its
ranking of single students in the following way: the college always prefers to add an acceptable student to
any set of students (provided this does not violate the capacity constraint) and it prefers to replace any
student by a better student.