Constrained School Choice

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.¹⁴

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.

One easily verifies that at γ(Q) = {{i₁, s₁}, {i₂, s₂}, {i₃, s₃}} (which is indicated by the
square boxes) student i₂ has justified envy for school s₃. So, γ(Q) is not stable. (In fact
the unique stable matching is γ(P) = {{i1, s1}, {i2, s3}, {i3, s2}}, indicated in boldface.)

¹⁴We 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

<<   13   14   15   16   17   18   19   >>

More intriguing information