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.
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
i i2

P
i i3

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 i
2 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



More intriguing information

1. Bidding for Envy-Freeness: A Procedural Approach to n-Player Fair Division Problems
2. The name is absent
3. The name is absent
4. Modelling the Effects of Public Support to Small Firms in the UK - Paradise Gained?
5. CAN CREDIT DEFAULT SWAPS PREDICT FINANCIAL CRISES? EMPIRICAL STUDY ON EMERGING MARKETS
6. Corporate Taxation and Multinational Activity
7. The Environmental Kuznets Curve Under a New framework: Role of Social Capital in Water Pollution
8. The name is absent
9. The name is absent
10. Telecommuting and environmental policy - lessons from the Ecommute program
11. Foreign Direct Investment and Unequal Regional Economic Growth in China
12. The name is absent
13. The name is absent
14. The name is absent
15. The name is absent
16. Hemmnisse für die Vernetzungen von Wissenschaft und Wirtschaft abbauen
17. Endogenous Heterogeneity in Strategic Models: Symmetry-breaking via Strategic Substitutes and Nonconcavities
18. Optimal Tax Policy when Firms are Internationally Mobile
19. Survey of Literature on Covered and Uncovered Interest Parities
20. Feeling Good about Giving: The Benefits (and Costs) of Self-Interested Charitable Behavior