Constrained School Choice

Routine computations show that i2 has no profitable deviations. So, Q ∈ E^γ (P, 2). Notice
also that γ(Q) does not Pareto dominate γ(P), nor is it Pareto dominated by γ(P).
Finally, and in view of Proposition 4.2, notice that (1) none of the students’ strategies in
the equilibrium exhibits “dominated reversals” of schools and (2) all students submit a
preference list with the maximum number k of schools.                              ^

Example 6.3 and Theorem 5.3 suggest that unstable equilibrium outcomes are difficult
to avoid in the quota-game under SOSM. Hence, the only degree of freedom that is left
to obtain stable equilibrium outcomes is the schools’ priority structure. The next result
provides a condition on the priority structure under which SOSM implements the corre-
spondence of stable matchings in Nash equilibria. The relevant condition is an acyclicity
condition introduced by Ergin (2002). Loosely speaking, Ergin-acyclicity guarantees that
no student can block a potential improvement for any other two students without affecting
his own assignment.

Definition 6.4 Ergin-Acyclicity (Ergin, 2002)

Given a priority structure f, an Ergin-cycle is constituted of distinct s, s^′ ∈ S and i, j, l ∈ I
such that the following two conditions are satisfied:

Ergin-cycle condition:  f_s(i) < f_s(j) < f_s (l) and f_s′ (l) < f_s′ (i) and

ec-scarcity condition: there exist (possibly empty and) disjoint sets I_s,I_s' ⊆ I∖{i,j,l}
such that Is ⊆ Uf(j), Is’ ⊆ Uf(i), |Is| = qs - 1, and |Is’| = qs’ - 1.

A priority structure is Ergin-acyclic if no Ergin-cycles exist.                             △

Theorem 6.5 Let k = 1. Then, f is an Ergin-acyclic priority structure if and only if
for any school choice problem P , the game Γ^γ(P, k) implements S(P) in Nash equilibria,
i.e., O^γ(P,k) =S(P).

Ergin (2002) showed that Ergin-acyclicity of the priority structure is necessary and suf-
ficient for the Pareto-efficiency of SOSM.¹⁵ Therefore, Theorem 6.5 shows that Ergin-
acyclicity has a different impact depending on whether one considers SOSM per se or in
the context of the induced preference revelation game.

¹⁵Ergin (2002) also showed that Ergin-acyclicity is sufficient for group strategy-proofness and consis-
tency of SOSM as well as necessary for each of these conditions separately. In the setting of a two-sided
matching model where also schools are strategic agents, Kesten (2007) showed that schools cannot ma-
nipulate by under-reporting capacities or by pre-arranged matches under SOSM if and only if the priority
structure is Ergin-acyclic.

17

<<   14   15   16   17   18   19   20   >>

More intriguing information