Weak stability and Pareto efficiency in school choice

We study the trade-off between stability and students’ welfare in school choice problems. We call a matching weakly stable if none of its blocking pairs can be matched in a more stable matching—one with a weakly smaller set of blocking pairs. A matching is said to be self-constrained efficient if for students it is not Pareto dominated by any more stable matching, and it is self-constrained optimal if it weakly Pareto dominates all such matchings. We show that the following are equivalent for any matching: (1) It is weakly stable and self-constrained efficient; (2) it is self-constrained optimal; (3) it is an efficiency-adjusted deferred acceptance mechanism (EADAM) outcome under some consenting constraints; and (4) it is exactly the EADAM outcome when its own set of blocking pairs is used as consenting constraint.

1. We defer a more rigorous definition of stability to Sect. 2.

2. Ergin (2002) characterizes priority structures at which DA is Pareto efficient. Abdulkadiroğlu et al. (2009) empirically document that students’ welfare loss at DA is significant in New York City high school admission.

3. This partial ordering of stability is first defined by Abdulkadiroğlu et al. (2020), who show that when each school has only one seat, the top trading cycles mechanism proposed by Abdulkadiroğlu and Sönmez (2003) for school choice problems is maximally stable among strategy-proof and Pareto efficient mechanisms. Chen and Kesten (2017) define one mechanism to be more stable than another if the former produces stable outcomes for a larger set of school choice problems.

4. Our notion of weak stability can be used in extensions of two-sided matching problems, like the teacher assignment problem studied by Combe et al. (2017). It can also be useful in situations where stable matchings do not exist, such as roommate problems (Gale and Shapley 1962) and the medical residency matching problems with couples (Roth and Sotomayor 1990). For such problems, the matchings with the smallest number of blocking pairs are always weakly stable.

5. Alcalde and Romero-Medina call a matching \(\alpha\)-equitable if no blocking pair of it can be matched without having any blocking pair that involves other students. It is shown that among efficient matchings, a matching is \(\alpha\)-equitable if and only if it weakly Pareto dominates the DA matching.

6. Pereyra (2013) proposes to use the modified DA algorithm which has previously been studied by Compte and Jehiel (2008) and Guillen and Kesten (2012) for reassignment problems. Also see Sun and Yang (2016) for a more general study on reassignment problems under the framework of matching with commitment.

7. This assumption ensures that all matchings, in particular, all Pareto improvements of the student-optimal stable matching, are individually rational for schools.

8. To describe a school choice problem more formally, we should also include the set of students, the set of schools, and the profile of capacities \(q=(q_{s})_{s\in S}\). Nevertheless, we suppress these for notational simplicity.

9. In the terminology of Balinski and Sönmez (1999), a matching without blocking pairs is called fair.

10. Self-constrained efficiency captures the same intuition as the one-sided maximality (for students) defined in Combe et al. (2017), except that due to the difference in setup, the individual rationality required by them does not apply here.

11. Due to their simplicity, we omit the definitions of these mechanisms and the checking of their weak stability.

12. The concept of underdemanded schools is first proposed by Kesten and Kurino (2019). By restricting the preference domain, Kesten and Kurino try to resolve the trade-off between strategy-proofness and Pareto efficiency of DA.

13. The same generalization of consenting constraint has appeared earlier in Dur et al. (2019), also with application on generalizing Kesten’s EADAM; see Sect. 5.2 for more detailed discussion.

14. Such an improvement is in the form of trading cycles among students, and EADAM selects the most stable cycle among all improvement cycles, in the same spirit of Erdil and Ergin (2008)’s stable improvement cycles algorithm. Dur et al. (2019) and Wang (2016) independently propose trading cycles rules that implement EADAM by explicitly revealing the stable improvement cycles.

15. The constrained efficiency of EADAM is proved under slightly less general consenting constraint in Tang and Yu (2014); it can be extended to the current setup without difficulty. For a complete proof, see Dur et al. (2019).

16. As argued by Kesten (2010), a mechanism that is not strategy-proof does not imply it can be easily manipulated in practice. He shows that in a “limited information” environment, truth telling is an ordinal Bayesian Nash equilibrium of the preference revelation game under EADAM.

17. A similar result has also been independently discovered by Ehlers and Morrill (2020) in their Lemma 14,  where \(\mu\) is assumed to be the DA matching and i is assigned to an underdemanded school.

18. We are grateful to Andrew Kloosterman and Peter Troyan for examples that illustrate this to us. Troyan et al. (2020) provide an example of a matching that is weakly stable but not essentially stable in “Appendix” of their paper.

We are grateful to the helpful suggestions of the Editor and three anonymous referees. We are particularly grateful to Jingsheng Yu for pointing out a mistake in our early characterization result. We also thank Xiang Han, Ju Hu, Onur Kesten, Flip Klijn, Fuhito Kojima, Jinpeng Ma, Jianpei Li, Mengling Li, Zhiwei Liu, Shravan Lucraz, Yangbo Song, Ning Sun, Xiang Sun, Olivier Tercieux, Jie Zheng, seminar participants at CUHK, CUHK Shenzhen, Peking University, Wuhan University, University of Nottingham Ningbo, University of International Business and Economics, Xiamen University, and audiences at the 7th Shanghai Microeconomics Workshop, the 2017 Annual SAET Conference, Workshop on Matching, Search and Market Design at National University of Singapore (IMS), for helpful comments and discussions.

This project is supported by National Natural Science Foundation of China (Nos. 71803114 and 71873081) and Program for Innovative Research Team of Shanghai University of Finance and Economics (No. 2017110093).

Authors and Affiliations

1. School of Economics, Shanghai University of Finance and Economics, Shanghai, 200433, China

   Qianfeng Tang & Yongchao Zhang

Corresponding author

Correspondence to Yongchao Zhang.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

1.1 Proof of Lemma 1

Proof

Let \(I^{\prime }=\{j:\nu (j)P_{j}\mu (j)\}\) be the set of students who prefer the matching \(\nu\) to the matching \(\mu\). It is clear that \(I^{\prime }\) is nonempty since student \(i \in I^{\prime }\). Denote by \(\nu (I^{\prime })\) the set of schools matched by students in \(I^{\prime }\) at the matching \(\nu\). Let \(s = \nu (i),\) then \(s\in \nu (I^{\prime })\). We next proceed by considering the following two possible cases.

Case A. Suppose there exists a student k, who is originally matched with a school in \(\nu (I^{\prime })\) at the matching \(\mu\), but becomes worse off at \(\nu\). Since \(\mu (k) \in \nu (I^{\prime })\), there exists a student \(j \in I^{\prime }\) such that \(\nu (j) = \mu (k)\), and she desires this school \(\mu (k)\) in the matching \(\mu\). Due to the stability of \(\mu\), student j must have lower priority than k at \(\mu (k)\). Therefore, \((k, \mu (k)) \in B(\nu )\), and \(\nu\) is invalidated by the stable matching \(\mu\).

Case B. Suppose instead, all students who are originally matched with schools in \(\nu (I^{\prime })\) at \(\mu\) are weakly better off at \(\nu\). That is, \(\nu (I^{\prime })=\mu (I^{\prime });\) from \(\mu\) to \(\nu\), students matched at \(\nu (I^{\prime })\) are reshuffling seats. Let matching \(\bar{\nu }\) be the matching defined as, \(\bar{\nu }(j) = \nu (j)\), for all \(j \in I^{\prime }\), and \(\bar{\nu }(j) = \mu (j)\) otherwise. It is clear that \(\bar{\nu }\) is well-defined in this case. We see that \(\bar{\nu }\) Pareto dominates \(\mu\) and \(\bar{\nu }(i)=s\). This contradicts the Pareto unimprovability of i to s at \(\mu\). \(\square\)

1.2 Proof of Lemma 2

Proof

For notational simplicity, denote \(EA^{B(\mu )}(P,\succ )\) by \(EA^{B(\mu )}\). By assumption, \(\mu\) is not Pareto dominated by \(EA^{B(\mu )}\) and \(\mu \ne EA^{B(\mu )}\). We only need to show that \(\mu\) is blocked by \(EA^{B(\mu )}\).

Suppose instead for every \((i,s)\in B(\mu ),s\ne EA^{B(\mu )}(i)\). At the original problem \((P,\succ ),\) modify students’ preferences such that for every \((i,s)\in B(\mu ),\) remove s from i’s preference \(P_{i}\). Denote the new problem by \((P^{\prime },\succ )\). Then \(\mu\) and \(DA(P^{\prime },\succ )\) are stable under \((P^{\prime },\succ )\). So is \(EA^{B(\mu )}\), because for all \(i,EA^{B(\mu )}(i)\) is still in \(P_{i}^{\prime }\) and \(B(EA^{B(\mu )})\subseteq B(\mu )\).

On the one hand, the student-optimal stability of \(DA(P^{\prime },\succ )\) implies that \(DA(P^{\prime },\succ )\) weakly Pareto dominates \(EA^{B(\mu )}\), both at \((P^{\prime },\succ )\) and at \((P,\succ )\). On the other hand, at \((P,\succ ),\) the constrained efficiency of \(EA^{B(\mu )}\) under \(C=B(\mu )\) implies that \(DA(P^{\prime },\succ )\) does not strictly Pareto dominate \(EA^{B(\mu )}\). Therefore, \(DA(P^{\prime },\succ )=EA^{B(\mu )}\). But since \(\mu\) is stable under \((P^{\prime },\succ ),DA(P^{\prime },\succ )=EA^{B(\mu )}\) weakly Pareto dominates \(\mu\). This contradicts with our assumption. \(\square\)

1.3 Proof of Theorem 1

Proof

To prove the equivalences among (i)–(iv), we prove that (ii)\(\Rightarrow\)(i)\(\Rightarrow\)(iv) \(\Rightarrow\)(iii)\(\Rightarrow\)(ii). We divide this proof into four parts, among which the part showing (iii)\(\Rightarrow\)(ii) is the major one. For notational simplicity, we use \(EA^{C}\) to denote \(EA^{C}(P,\succ )\) for any consenting constraint C.

First, (ii)\(\Rightarrow\)(i). Suppose \(\mu\) is self-constrained optimal. This directly implies that \(\mu\) must be self-constrained efficient. To see that \(\mu\) is also weakly stable, suppose instead it is not. Then by definition, there exists a matching \(\nu\) which blocks \(\mu\) and \(B(\nu )\subseteq B(\mu )\). That is, \(\nu\) is more stable than \(\mu\) and is not Pareto dominated by \(\mu\). This contradicts with \(\mu\) being self-constrained optimal.

Second, (i)\(\Rightarrow\)(iv). Suppose \(\mu\) is weakly stable and self-constrained efficient. If instead \(\mu \ne EA^{B(\mu )},\) then due to Lemma 2, \(\mu\) is invalidated by \(EA^{B(\mu )}\). This contradicts with the weak stability of \(\mu\).

Third, (iv)\(\Rightarrow\)(iii) holds trivially.

Fourth, (iii)\(\Rightarrow\)(ii). Given any consenting constraint C, we need to show that \(EA^{C}\) weakly Pareto dominates every matching \(\mu\) more stable than it. We will proceed by showing that \(EA^{C}\) and \(\mu\) are both stable matchings in a modified problem, while \(EA^{C}\) is the student-optimal stable matching.

We first prove the weak stability of \(EA^{C},\) which will be useful later. Suppose instead \(EA^{C}\) is not weakly stable for some consenting constraint C. Then, there exists \((i,s)\in B(EA^{C})\) and a matching \(\nu\) such that \(s=\nu (i)\) and \(B(\nu )\subseteq B(EA^{C})\). Consider the round of the EADAM procedure when i is matched and removed. Suppose this round is the m-th round of EADAM. Denote this round’s DA outcome by \(DA^{m}\) and the updated preference profile of students’ in this round be \(P^{m}\). Therefore, \(DA^{m}=DA(P^{m},\succ ).\) At \((P^{m},\succ )\), i must be matched with an underdemanded school at \(DA^{m}\). As a result, \(\nu (i)P_{i}DA^{m} (i)=EA^{C}(i).\) Moreover, since \(\nu\) improves the Pareto unimprovable student i at \(DA^{m},\) due to Lemma 1, at \((P^{m},\succ ),\nu\) is blocked by \(DA^{m}.\) That is, at \((P^{m},\succ ),\) for some student \(k,(k,DA^{m}(k))\in B(\nu )\). Since \(P_{k}^{m}\) is obtained by removing certain schools from \(P_{k}\), at the original problem \((P,\succ ),\) we also have \((k,DA^{m}(k))\in B(\nu ).\) But since \(EA^{C}\) weakly Pareto dominates \(DA^{m}\) at \((P,\succ ),k\) does not desire school \(DA^{m}(k)\) at \(EA^{C}.\) Therefore, \((k,DA^{m}(k))\notin B(EA^{C})\). A contradiction with \(B(\nu )\subseteq B(EA^{C})\) at \((P,\succ )\).

Next, we modify students’ preferences as follows. For each student i, if there exists a school s such that \((i,s)\in B(EA^{C}),s\) is marked as unacceptable and removed from i’s preference. Denote i’s preference after modification by \(P_{i}^{\prime }\) for all students, and the modified preference profile by \(P^{\prime }\). The modified problem is \((P^{\prime },\succ )\). We will henceforth refer to the modified problem as “the new problem” and the original one as “the old problem.”

We then show that both \(\mu\) and \(EA^{C}\) are stable in the new problem \((P^{\prime },\succ )\). Suppose that \(EA^{C}\) is not a stable matching in the new problem, and let (i, s) be a blocking pair of it in the new problem. According to the modification of \(P_{i}\), this blocking pair remains a blocking pair of \(EA^{C}\) in the old problem \((P,\succ )\). However, this school s should have been removed from \(P_{i}\) in the modification; thus, this school is not desired by student i under \(P_{i}^{\prime }\) anymore. A contradiction. We next verify the stability of \(\mu\) in the new problem. In the old problem, for any student \(i,(i,\mu (i))\notin B(EA^{C})\) because due to its weak stability, \(EA^{C}\) cannot be blocked by any more stable matching \(\mu\). As a result, \(\mu (i)\) is still an acceptable school in \(P_{i}^{\prime }\) for any student i. The stability of \(\mu\) in the new problem can then be similarly proved as in the proof of the stability of \(EA^{C}\) above.

Finally, due to the optimality of the student-optimal stable matching in the new problem, both \(\mu\) and \(EA^{C}\) are weakly Pareto dominated by the DA outcome in the new problem, denoted by \(DA(P^{\prime },\succ )\). Also note that any blocking pair of \(DA(P^{\prime },\succ )\) evaluated in the old problem \((P,\succ )\) must be in \(B(EA^{C})\); hence, its set of blocking pairs is a subset of C. Due to the constrained efficiency of EADAM, \(EA^{C} =DA(P^{\prime },\succ )\). We thus complete the proof that \(EA^{C}\) weakly Pareto dominates \(\mu\). \(\square\)

Reprints and permissions