Constrained School Choice

8 Equilibria in Truncations

In this section we focus on “truncation” strategies which are shown to be undominated
in the quota-games induced by both the Student-Optimal Stable mechanism and the Top
Trading Cycles mechanism. We first strengthen the negative side of Theorems 6.5 and 6.8
by providing and example that admits a strong Nash equilibrium in truncations that
induces an unstable matching. Next, again for both mechanisms, we will show that in
general there is also no relation between the set of unassigned students at equilibrium
and the set of unassigned students in stable matchings. However, for Nash equilibria in
truncations we do obtain a positive result in this respect for the Student-Optimal Stable
mechanism.

A truncation of a preference list Pi is a list Pi' obtained from Pi by deleting some school
and all less preferred acceptable schools.²⁰ The following lemma says that in the games
Γ^γ(P, k) and Γ^τ (P, k) submitting a truncation “as long as possible” is k-undominated.
Formally, student i’s strategy Qi ∈ Q(k) is k-dominated by another strategy Qi ∈ Q(k)
if φ(Qi,Q-i)Riφ(Qi,Q-i) for all Q-i ∈ Q(k)I\i and φ(Q'i, Q-_i)Piφ(Qi, Q-i) for some
Q-i ∈ Q(k)I∖i. A strategy in Q(k) is k-undominated if it is not k-dominated by any other
strategy in Q(k).

Lemma 8.1 Let P be a school choice problem. Let 1 ≤ k ≤ m. Let i ∈ I be a stu-
dent. Denote the number of (acceptable) schools in Pi by |Pi |. Then, the strategy P_i^k of
submitting the first min{k, |P_i |} schools of the true preference list P_i in the true order is
k-undominated in the games Γ^γ (P, k) and Γ^τ (P, k).

Although the strategy profile P^k := (P_i^k)i∈I is a profile of k-undominated strategies, it
is not necessarily a Nash equilibrium in the games Γ^γ (P, k) and Γ^τ (P, k). In case it is a
Nash equilibrium it may still induce an unstable matching as Example 8.2 shows.

Example 8.2 For both γ and τ: A Strong Nash Equilibrium in (Undominated)
Truncations that yields an Unstable Matching

Let I = {i1, i2, i3, i4} 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.

²⁰Truncations have been studied by Roth and Vande Vate (1991), Roth and Rothblum (1999), and
Ehlers (2004) and have also appeared in practice (see for instance Mongell and Roth, 1991).

24

<<   21   22   23   24   25   26   27   >>

More intriguing information