Constrained School Choice

(Qi₁ , . . . , Qi_n) of “length” at most k (i.e., preference lists with at most k acceptable
schools). Here, k is a positive integer, 1 ≤ k ≤ m, and is called the quota. Subsequently,
a mechanism φ is used to obtain the matching φ(Q) and for all i ∈ I, student i is assigned
a seat at school φ(Q')(i).

Clearly, the above procedure induces a strategic form game, the quota-game Γ^ψ(P, k) :=
(I, Q(k)I, P). The set of players is the set of students I. The strategy set of each stu-
dent is the set of preference lists with at most k acceptable schools and is denoted by
Q(k). Let Q := Q(m). Outcomes of the game are evaluated through the true preferences
P = (P_i1 , . . . , P_in), where with some abuse of notation P denotes the straightforward ex-
tension of the preference relation over schools (and the option of remaining unassigned) to
matchings. That is, for all i ∈ I and matchings μ and μ', μPiμ' if and only if μ(i)Piμ'(i).

For any profile of preferences Q ∈ Q^I and any i ∈ I, we write Q_-i for the profile of
preferences that is obtained from Q after leaving out preferences Q_i of student i. A profile
of submitted preference lists Q ∈ Q(k)I is a Nash equilibrium of the game Γ^ψ(P, k) (or
k-Nash equilibrium for short) if for all i ∈ I and all Qi ∈ Q(k), φ(Q_i,Q_-i)R_iφ(Q^,_i,Q_-i).
Let E^φ(P, k) denote the set of k-Nash equilibria. Let O^φ(P, k) denote the set of k-Nash
equilibrium outcomes, i.e., O^ψ(P, k) := {φ(Q) : Q ∈ E^ψ(P, k)}.

Remark 4.1 Setting the same quota for all students is without loss of generality since
in the proofs we never compare the values of the quota for different students.

If the quota is smaller than the total number of schools, i.e., k < m, then students
typically cannot submit their true preference lists and hence there is no weakly dominant
strategy for SOSM and TTC. The next result shows that nevertheless there is a class of
undominated strategies.

One piece of advice about which preference list a student should submit follows from
the strategy-proofness of the Student-Optimal Stable mechanism and the Top Trading
Cycles mechanism in the unconstrained setting: it does not pay off to submit a list of
schools that does not respect the true order. More precisely, a list that does not respect
the order of a student’s true preferences is weakly dominated by listing the same schools
in the “true order.” Let φ be a mechanism. Student i’s strategy Qi ∈ Q(k) in the game
Γ^φ(P, k) is weakly k-dominated by another strategy Qi ∈ Q(k) if φ(Q'i, Q_-i)R_iφ(Q_i, Q_-i)
for all Q-i ∈ Q(k)^I\i.

Lemma 4.2 Let P be a school choice problem. Let 1 ≤ k ≤ m. Let i ∈ I be a student.
Consider two strategies Qi,Qi ∈ Q(k) such that (a) Qi and Qi contain the same set of

13

<<   10   11   12   13   14   15   16   >>

More intriguing information