Deferred Acceptance is Unpredictable

Is Deferred Acceptance Simple?

I can think of several desirable ways in which Deferred Acceptance is simple:

• Strategic Simplicity It is in applicants’ best interest to list their true preferences, regardless of what others do.
• Computational Simplicity The algorithm runs quickly, even on large data sets.
• Conceptual Simplicity After the fact, decisions can be rationalized by “admissions cutoffs” for each school. Posting these cutoffs allows students to verify that they have been assigned to their favorite school where their priority exceeded the cutoff.

Despite these advantages, DA is often characterized as a complicated and unintuitive “black box.” This post offers one possible explanation for this: the outcome of DA is unpredictable. By this, I mean that small changes to the input can have a large effect on the output.

An Example

Consider the example shown below. In a market consisting of only Schools A, B, C and students 1, 2, 3, each student gets their first choice – pretty good! Unsurprisingly, adding a fourth student can harm the first three students. Perhaps more surprisingly, in this example, adding student 4 causes students 1, 2 and 3 to each be assigned to their last choice. This occurs despite the fact that student 4 is not assigned to any school!¹

Table 1: An example where adding student 4 dramatically affects the final assignment.

A:	2	3	4	1		1:	A	B	C
B:	3	4	1	2		2:	B	C	A
C:	1	2	3	4		3:	C	A	B
						4:	A	B	C

This example can be generalized: for any \(n\), there is an example with \(n\) students and \(n\) schools where each student gets his or her first choice, but adding a new student results in each original student getting their \(n^{th}\) choice, and the new student going unassigned.²

Defining Predictability

In the preceding example, a “small” change (adding one student) had a “large” effect on the outcome (moving all other students from their first to their last choice). We could formalize this observation by defining the externality of one student to be the sum of the improvement in ranks experienced by other students if this student is removed from the market. So if removing student x moves student y from their third choice to their first, moves student z from their fourth choice to their third, and leaves the assignment of all other students the same, the externality of student x is \((3-1) + (4-3) = 3\).

The preceding example shows that in a market with \(n\) students and \(m\) schools, the externality of a student under DA can be as large as \(n \times (m-1)\). By contrast, the following result states that other commonly-studied mechanisms result in much smaller externalities.

Proposition. In a market with \(n\) students and \(m\) schools, when using Serial Dictatorship or the Boston Mechanism, the externality froma single student is at most \(m\).

\(\color{red}{\text{*Update, November 2022*}}\) Clay Thomas points out to me that this so-called “Proposition” is false for serial dictatorship. Here is a counter-example. There are n students and n schools. Students have “nearly common” rankings: each student prefers low-indexed schools, except that student \(i\) ranks school \(i\) first. In this case, everyone gets their first choice. If we add an additional student \(0\) who starts by taking school \(n/2+1\), this doesn’t affect the next \(n/2\) students, but increases the rank for each of the \(n/2\) remaining students by at least \(n/2\). This is an embarrassing mistake, but I guess it’s bound to happen sometimes, given that much of the point of writing a blog post (rather than a paper) is that I can share ideas more quickly with less careful analysis.

I believe that the claimed result is true for the Boston mechanism. Here is a proof sketch. To fix terminology, say that Boston proceeds over a number of rounds: in round \(k\), it tries to match as many unassigned students to their \(k^{th}\) choice as possible. Let \(S_k\) be the set of participants who participate in round \(k\) (that is, they are not matched in an earlier round). Then the sum of ranks of an assignment is \(\sum_k |S_k|\). Suppose that we add a student to the market. The externality of this student is equal to the sum of ranks in the new assignment, minus the new student’s rank in this assignment, minus the sum of ranks in the original assignment. In particular, if \(S_k'\) is the set of students who participate in round \(k\) after the new student is added, the student’s externality is upper bounded by \(\sum_{k} |S_k'| - \sum_k |S_k|-1\). I claim that for each \(k\), \(S_k \subseteq S_k'\) (the addition of a new student doesn’t help anyone else), and \(|S_k'| \le |S_k| + 1\) (it can cause at most one new displaced student in each round). From this, the upper bound of \(m\) follows. \(\color{red}{\text{*End Update*}}\)

Why Predictability Matters

Participants in matching markets often want to know what to expect. This is especially important during preference formation. Parents have to decide which schools to research, and medical students have to decide where to interview. Without good information about what options will be available, they may waste a lot of time and money exploring irrelevant alternatives. Historical data can offer guidance, but the examples in this post suggest that even relatively small changes from year-to-year (i.e. slightly fewer residency positions, or slightly fewer students applying) can render this information fairly useless.

The unpredictability of DA also matters to policymakers who must decide school priorities. It’s possible to construct examples similar to those above, showing that seemingly small changes to priorities can have large effects on the final outcome. Meanwhile, large changes to priorities can have almost no effect (for one real-world example, see this paper.)

Even academics whose full-time job is to study stable matching algorithms struggle to predict what outcomes will arise when they are deployed. For most practical questions, we resort to simulations, with theory following decades later, if at all. I’ve been working on a new model of stable matching, which makes accurate predictions while maintaining analytical tractability. Stay tuned for more!