Proposition 6.1 For any school choice problem P and any quota k, the game Γβ (P, k)
implements S(P) in Nash equilibria, i.e., Oβ(P, k) = S(P).
This result is obtained through a straightforward adaptation of the proof of Theorem 1 in
Ergin and Sonmez (2006). Alcalde (1996, Theorem 4.6) obtained a similar result in the
context of a marriage market (i.e., when both sides of the market are strategic agents) but
without any constraint on the size of the submittable preference lists. A slight adaptation
of his arguments also leads to a proof of Theorem 6.1. Its proof is therefore omitted.
We now turn to the analysis of equilibrium outcomes when the mechanism in use is
SOSM. Since for quota k = 1 BOS and SOSM coincide, the games Γγ (P, 1) and Γβ (P, 1)
also coincide. Hence, Proposition 6.1 implies that the game Γγ (P, 1) implements S(P)
in Nash equilibria, i.e., Oγ(P, 1) = S(P). Together with the nestedness of the equilibria
under SOSM (Theorem 5.3) it follows that any stable matching can be obtained as an
equilibrium outcome under SOSM, for any value of the quota.
Proposition 6.2 (Romero-Medina, 1998, Theorem 7) For any school choice problem P
and any quota k, S(P) ⊆ Oγ(P, k).
However, the next example shows that for higher values of the quota, not all Nash
equilibrium outcomes are necessarily stable.14
Example 6.3 An Unstable Nash Equilibrium Outcome in Γγ(P, k)
Let I = {i1, i2, i3} be the set of students, S = {s1, s2, s3} be the set of schools, and
q = (1, 1, 1) be the capacity vector. The students’ preferences P and the priority structure
f are given in the table below. Let k = 2 be the quota and Q ∈ Q(2)I as given below.
Pil |
P |
P |
fsι |
fs2 |
fs3 | |||
Qil |
Qi2 |
Qi3 | ||||||
— |
— | |||||||
S1 |
s3 |
S3 |
i3 |
i3 |
i1 |
s1 |
s1 |
s3 |
s3 |
s1 |
s2 |
i1 |
i1 |
i2 |
s3 |
s2 |
s1 |
s2 |
^2^ |
s1 |
i2 |
i2 |
i3 | |||
— |
One easily verifies that at γ(Q) = {{i1, s1}, {i2, s2}, {i3, s3}} (which is indicated by the
square boxes) student i2 has justified envy for school s3. So, γ(Q) is not stable. (In fact
the unique stable matching is γ(P) = {{i1, s1}, {i2, s3}, {i3, s2}}, indicated in boldface.)
14We are not the first to provide an example with an unstable equilibrium outcome. Example 3 in
Sotomayor (1998) already made this point for a class of mechanisms that includes SOSM. However, the
generality of her example comes at the cost of using dominated strategies.
16