Robust stability in matching markets

Kojima, Fuhito Article Robust stability in matching markets Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Kojima, Fuhito (2011) : Robust stability in matching markets, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 6, Iss. 2, pp. 257-267, https://doi.org/10.3982/TE780 This Version is available at: https://hdl.handle.net/10419/150154 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/3.0/ Theoretical Economics 6 (2011), 257–267 1555-7561/20110257 Robust stability in matching markets Fuhito Kojima Department of Economics, Stanford University In a matching problem between students and schools, a mechanism is said to be robustly stable if it is stable, strategy-proof, and immune to a combined manipulation, where a student first misreports her preferences and then blocks the matching that is produced by the mechanism. We find that even when school priorities are publicly known and only students can behave strategically, there is a priority structure for which no robustly stable mechanism exists. Our main result shows that there exists a robustly stable mechanism if and only if the priority structure of schools is acyclic (Ergin 2002), and in that case, the student-optimal stable mechanism is the unique robustly stable mechanism. Keywords. Matching, stability, strategy-proofness, robust stability, acyclicity. JEL classification. C71, C78, D71, D78, J44. 1. Introduction Matching theory has influenced the design of labor markets and student assignment systems. Stability plays a central role in the theory: A matching is stable if there is no individual agent who prefers being unmatched to being assigned to her allocation in the matching, and there is no pair of agents who prefer being assigned to each other to being assigned to their respective allocations in the matching. In real-world applications, empirical studies have shown that mechanisms often succeed whereas unstable ones often fail. In recent years, the incentive properties of stable mechanisms have attracted much attention. Roth (1982) shows that any stable mechanism is manipulable. However, if preferences of one side of the market are common knowledge, as in school choice (Abdulkadiro˘ glu and Sönmez 2003) where school priorities are exogenously given by law, the student-optimal stable mechanism is both strategy-proof and stable (Dubins and Freedman 1981,Roth 1982). Indeed, the student-optimal stable mechanism has been adopted in practical assignment problems, such as student assignment in New York City and Boston, and the National Resident Matching Program. However, most existing analysis has overlooked other types of manipulation, as stability and strategy-proofness have been studied separately. If agents are capable of Fuhito Kojima: [email protected] I am grateful to Eric Budish, Yeon-Koo Che, Haluk Ergin, Guillaume Haeringer, Jinwoo Kim, Taro Kumano, Yusuke Narita, Yuki Takagi, Kentaro Tomoeda, Alex Westkamp, Yosuke Yasuda, and especially Michael Ostrovsky, Al Roth, the co-editor, and two anonymous referees for insightful comments. Peter Troyan provided excellent research assistance. Copyright ©2011 Fuhito Kojima. Licensed under the Creative Commons Attribution-NonCommercial License 3.0. Available at http://econtheory.org. DOI: 10.3982/TE780 258 Fuhito Kojima Theoretical Economics 6 (2011) misreporting their preferences during the centralized matching process and also rematching (blocking) after the matching is announced, then they may be able to use the combination of these manipulations to their advantage. Chakraborty et al. (2010) consider the combination of these manipulations and propose a strong stability concept that requires robustness against these manipulations in a matching problem with interdependent values.1Adapting their concept to the standard matching model without interdependent values, we say that a mechanism is robustly stable if no student is made strictly better off by a combined manipulation of misreporting preferences and rematching. Although this departure from the standard concepts may seem small, it has very different implications on the design of matching mechanisms. First, we demonstrate that even when school priorities are exogenously given and only students can behave strategically, there is no robustly stable mechanism in general. Given the above impossibility result, a natural question is what conditions allow for a robustly stable mechanism. Our main result characterizes the existence of a robustly stable mechanism in terms of the priority structure of schools. More specifically, we show that there is a robustly stable mechanism in a market if and only if the priority structure of schools in that market is acyclic (Ergin 2002). Moreover, if there is a robustly stable mechanism, then it coincides with the student-optimal stable mechanism. The analysis of this paper suggests that one cannot expect complete elimination of manipulations even when only students can act strategically. If the social planner can influence the priority structure, as in the case of student placement in public schools, the theory suggests that acyclicity is likely to make the system immune to manipulations. However, acyclicity is a very demanding condition, and so this paper suggests that robust stability is hard to guarantee, even when the social planner can influence the priority structure to some extent. Are combined manipulations important in the real world? While a comprehensive analysis is beyond the scope of this paper, a suggestive example can be found in the school choice problem (Abdulkadiro˘ glu and Sönmez 2003). For instance, in New York City, many students participate in an appeals process to be assigned to a school they like better than their prescribed assignment (Abdulkadiro˘ glu et al. 2005,2009). About 300 appeals out of about 5,000 were from students who received their stated first choices. This may suggest that students can engage in rematching in the school choice setting. A more detailed discussion is given in the Conclusion. Section 2 presents the model and the results. The relation to the literature is discussed after the main result of the paper. Section 3 concludes. Some proofs are provided in the Appendix. 2. Model and results A matching problem is the tuple (SCPq).SetsSand Care finite and disjoint sets of students and schools. For each student s∈S,Psis a strict preference relation over C 1The relation to their paper is discussed subsequently. Theoretical Economics 6 (2011) Robust stability in matching markets 259 and being unmatched (denoted by ∅). We write cR sc(where cc∈C∪{∅})ifeither cP scor c=c. For each school c∈C,cis a priority, which is a strict, complete, and transitive binary relation over S.2We write =(c)c∈C.Foreachc∈C,qcis the quota of c.Amatching is a vector μ=(μs)s∈Sthat assigns a seat at school μs∈Cor ∅to each student s, with seats in each school cassigned to at most qcstudents. We write μc={s∈S|μs=c}for the set of students who are assigned seats at school c.Thesetof a student’s possible preferences is denoted by P. We say that matching μis blocked by (s c) ∈S×Cif cP sμsand either (1) |μc|<q cor (2) |μc|=qcand scsfor some s∈μc. A matching μis individually rational if μsRs∅ for every s∈Sand |μc|≤qcfor every c∈C. A matching μis stable if it is individually rational and is not blocked. We refer to a tuple (S Cq)as a market and consider a situation where only student preferences are private information while the market (SCq)is given. A mechanism is a function ϕfrom P|S|to the set of all matchings. Mechanism ϕis stable if ϕ(P) is a stable matching for every P∈P|S|. Mechanism ϕis strategy-proof if ϕs(P) Rsϕs(P sP−s)for every P∈P|S|,s∈S,andP s∈P. Note that we allow only students to report preferences; school priorities are publicly known. This assumption simplifies the analysis and helps illuminate the consequences of the stability concept of this paper. Publicly known school priorities arise naturally in the school choice setting: As Abdulkadiro˘ glu and Sönmez (2003) point out, school priorities are exogenously given by law in many school districts. Similarly, Chakraborty et al. (2010)considertwo-sided matching between students and colleges in which preferences of students are publicly known. They motivate their assumption by noting that (i) information about colleges is mostly public in practice and (ii) because of extant impossibility results, such an assumption is necessary to obtain positive results. These points hold in our setting as well. Definition 1. A mechanism ϕis robustly stable if the following conditions are satisfied. (1) Mechanism ϕis stable. (2) Mechanism ϕis strategy-proof. (3) There exist no s∈S,c∈C,P∈P|S|,andP s∈Psuch that (i) cP sϕs(P) and (ii) scs for some s∈ϕc(P sP−s)or |ϕc(P sP−s)|<q c. In words, a mechanism is robustly stable if it is stable, strategy-proof, and also immune to a combined manipulation, where a student first misrepresents his or her preferences and then blocks the matching that is produced by the centralized mechanism. Condition (3) is the additional requirement over the combination of stability and strategy-proofness, and it plays a central role in our analysis. To the best of our knowledge, Chakraborty et al. (2010) are the first to consider this combined manipulation in 2As we are primarily interested in the school choice problem, we assume that every student is acceptable to every school. 260 Fuhito Kojima Theoretical Economics 6 (2011) two-sided matching.3They consider a Bayesian game of matching with interdependent values in which a player can both misreport in the matching process and rematch afterward. They say that a mechanism is stable if there is a perfect Bayesian equilibrium in which all players report their signals truthfully and all players accept their assigned partners on the equilibrium path. Although the direct comparison is somewhat subtle because of modeling differences, the robust stability concept defined here is conceptually close to and is motivated by the stability concept employed by Chakraborty et al. (2010). Given P, the student-proposing deferred acceptance algorithm produces a stable matching ϕS(P) (Gale and Shapley 1962). The student-optimal stable mechanism is a mechanism ϕSthat produces ϕS(P) for every P∈P|S|. It is well known that ϕSis stable (Gale and Shapley 1962) and strategy-proof (Dubins and Freedman 1981,Roth 1982). Moreover, Alcalde and Barberà (1994) show that ϕSis the unique stable and strategyproof mechanism. The following example demonstrates, however, that ϕSis not immune to the combination of these two kinds of manipulations even though it is immune to each of them separately. Example 1. Consider a problem with S={123},C={ab},and P1:ba ∅ P2:a∅ P3:ab ∅ a:123q a=1 b:312q b=1 Under the true preferences P=(P1P2P3), the student-optimal stable mechanism ϕS produces ϕS(P) =(ϕS 1(P) ϕS 2(P) ϕS 3(P)) =(a ∅b). Now consider a false preference P 2of student 2, P 2:∅Then, under P=(P 2P−2), ϕSproduces ϕS(P)=(b∅a). Since aP 2∅=ϕS 2(P) and 2a3∈ϕS a(P),ϕSis not robustly stable. More specifically, student 2has incentives to first report P 2and then block ϕS(P), violating condition (3) of the definition of robust stability. ♦ Mechanism ϕSis the only mechanism that is stable and strategy-proof (Alcalde and Barberà 1994). Thus Example 1 implies that given a priority structure, there does not necessarily exist a robustly stable mechanism. Theorem 1. There exists a priority structure for which there is no robustly stable mechanism. The next question to ask is whether we can say a mechanism is robustly stable in aspecific market. In other words, we investigate conditions on a pair (q), called a 3In a different context of the principal–agent problem, Myerson (1982) considers a similar notion of combined manipulations. Theoretical Economics 6 (2011) Robust stability in matching markets 261 priority structure, under which the mechanism is robustly stable. The following concept will prove useful. Definition 2(Ergin 2002). Let (q)be a priority structure. A cycle is a b ∈C,i j k ∈S such that •iajakand kbi •there exist disjoint sets of students SaSb⊂S\{i j k}such that |Sa|=qa−1, |Sb|=qb−1,sajfor every s∈Sa,andsbifor every s∈Sb. A priority structure (q)is acyclic if there exists no cycle. With the above notion, we can now present our main result, which is a characterization of markets for which a robustly stable mechanism exists. Theorem 2. For market (SCq),ϕSis robustly stable if and only if the priority structure (q)is acyclic. Given that ϕSis the unique stable and strategy-proof mechanism (Alcalde and Barberà 1994), this theorem implies that, given the market, there exists a robustly stable mechanism if and only if the priority structure is acyclic. To obtain intuition for Theorem 2, it is useful to review Example 1.Ifstudent2 declares all schools unacceptable in the student-proposing deferred acceptance algorithm, then students 1and 2apply to schools band a, respectively, and both are admitted. On the contrary, if 2reports that ais her first choice, then that will displace 3from a. Then 3applies to his second choice b, displacing 1from her first choice b, resulting in her applying to her second choice b.Thenbrejects 2and the algorithm terminates. By refraining from applying to a,student2can change matching of other students without changing her own matching (∅in both cases). This enables her to engage in a combined manipulation if she finds ato be acceptable: First misreport preferences so that other students are matched differently than under truthtelling and then rematch with a more preferred school aafter the matching is prescribed. The property that students cannot influence matchings of others without changing their own matches, called nonbossiness, turns out to play a key role more generally. Ergin (2002)showsthatϕSis nonbossy if and only if the priority structure is acyclic; the proof of Theorem 2 is based on his result. Theorems 1and 2suggest that manipulations may be unavoidable even when only students can act strategically. If the social planner can influence the priority structure, as in the case of student placement in public schools, the theory suggests that acyclicity would make the system immune to manipulations.4This point of view is shared by a number of studies, from related but different aspects. Ergin (2002)showsthat 4Alternatively, the social planner could regulate the rematching process so that a student cannot be matched to a more preferred school even if she has high priority. 262 Fuhito Kojima Theoretical Economics 6 (2011) the student-optimal stable mechanism is group strategy-proof if and only if the priority structure is acyclic. Haeringer and Klijn (2009) show that, in the school choice setting, the set of Nash equilibrium outcomes under the student-optimal stable mechanism (possibly with constraints on the length of rank order lists) coincides with the set of stable matchings if and only if the priority structure is acyclic. Kesten (forthcoming) shows that the student-optimal stable mechanism is immune to capacity manipulation (Sönmez 1997) if and only if the priority structure of schools is acyclic. Following the current paper, Afacan (2010) introduces the concept of group robust stability and investigates priority structures that guarantee the condition. Kesten (2006) introduces a slightly stronger acyclicity concept and shows that the top trading cycles mechanism coincides with the student-optimal stable mechanism if and only if the priority structure satisfies his version of acyclicity. The concept of acyclicity has been generalized to coarse priorities, and acceptant and substitutable priorities (as defined by Kojima and Manea (2010)) by Ehlers and Erdil (2010)andKumano (2009), respectively. An important related paper is Chakraborty et al. (2010). They consider a matching market with interdependent values and introduce a stability concept with the possibility of combined manipulations. In that environment, they establish impossibility theorems that assert that there is no stable mechanism in their sense. Meanwhile they also note that their impossibility theorems can be obtained even with a weaker notion of stability, namely the combination of traditional stability and strategy-proofness as required separately. The current study complements their study by showing that there does not necessarily exist a robustly stable mechanism, even if there is no interdependent value component, and then characterizing the condition necessary and sufficient for the existence of a robustly stable mechanism. Note that our characterization result critically depends on the assumption of private values. With interdependent values, Chakraborty et al. (2010) show the impossibility of stable mechanisms even when the priority structure is acyclic, so our private values assumption is important in Theorem 2. The definition of robust stability requires that the mechanism be immune to combined manipulations even if a student knows everything about the environment and reported preferences of other students. Clearly, perfect information is a strong assumption in many applications. However, it turns out that combined manipulations are easy to carry out without any knowledge other than the student’s own preferences. Specifically, consider the following strategy of a student: (1) Declare all schools to be unacceptable to the mechanism and (2) then rematch with her most preferred school available once the matching is prescribed by the mechanism.5 Proposition 1. In ϕS, any student who uses the above strategy is matched to a school that she weakly prefers to the school matched under truthtelling. A related question is whether combined manipulations are expected in large markets.6Proposition 1 implies that incentives for combined manipulations remain in large 5I am grateful to anonymous referees for encouraging me to consider this issue and for suggesting Proposition 1. 6In the two-sided matching setting, Roth and Peranson (1999), Immorlica and Mahdian (2005), and Kojima and Pathak (2008) show that manipulation incentives become small under ϕSas the market size grows. Theoretical Economics 6 (2011) Robust stability in matching markets 263 markets (although the magnitude may as well become small). This is because a student can safely misreport preferences and rematch with the same school as under truthtelling even in the worse case. 3. Conclusion This paper introduces a new stability concept—robust stability. Theorem 1 demonstrates that, given a priority structure, there does not necessarily exist a robustly stable mechanism. This result suggests that one cannot eliminate manipulations completely, even when agents on only one side of the market have private information. Then, Theorem 2 characterizes the market structures that enable robustly stable mechanisms to exist. If the social planner can design the priority structure, as in the case of student placement to public schools, the theory suggests that acyclicity is likely to make the system robust to manipulations. However, acyclicity is a very demanding condition, so one possible way to read this paper is to say robust stability is not only impossible for arbitrary markets (Theorem 1), but also is hard to guarantee by judiciously specifying a priority structure (Theorem 2). The extant literature has also found acyclic priority structures to be key in producing desirable properties in matching markets. Papers cited herein are only a few examples. This paper identifies one more sense in which such a structure proves critical for the design of matching markets. We envision that investigating further implications of priority structures may be a fruitful direction of future research. Before concluding the paper, we comment on a conceptual issue. The model assumes that school priorities are publicly known. Publicly known school priorities arise naturally in the school choice setting: As Abdulkadiro˘ glu and Sönmez (2003) point out, school priorities are exogenously given by law in many school districts. In such a case, however, one might argue that schools are not strategic players and hence do not participate in rematching, so combined manipulations are unimportant, and, instead, stability and strategy-proofness are sufficient. Even in school choice, however, robust stability may be important. For instance, consider the appeals process. In student placement to high schools in New York City, many students participate in an appeals process to be assigned to a school they like better than their prescribed assignment (Abdulkadiro˘ glu et al. 2005, 2009). For the academic year 2003–2004, the first year when the studentoptimal stable mechanism was implemented there, more than 5,000 students appealed their assignments, and about 300 appeals were from students who received their stated first choices.7The Department of Education granted about half of the appeals. This suggests that students may be able to engage in rematching even in the school choice setting.8 Needless to say, the above interpretation is only suggestive. First, students are often required to offer a reason for appeal, for instance, a new address. Second, it is not clear 7Interestingly, successful manipulations that appear in our analysis involve students rematching after they receive their stated first choices. 8I am grateful to Al Roth for suggesting this example. 264 Fuhito Kojima Theoretical Economics 6 (2011) whether the same school priorities as those used in the initial allocation process are respected during the appeals process. Also, it is difficult to see whether students engage in combined manipulations in actual school choice problems (the appeals may be due to different reasons such as changes in student preferences). Even so, the analysis of this paper raises the possibility that combined manipulations may happen in matching markets, and suggests that the market organizer take into account such possibilities when designing a mechanism. Another possible application is to labor markets where preferences of one side of the market are publicly known. In this context, the assumption that preferences of one side of the market are publicly known may be too strong. However, it may be a reasonable first approximation in some cases. For instance, firms may have sufficiently established reputations so that workers’ preferences over firms can be estimated from them with reasonable precision. A similar application is college admission. The assumption that student preferences are known may be a reasonable approximation of actual college admission because information about colleges is mostly public in practice. A more thorough analysis of these issues is beyond the scope of this paper and is left for future research. Appendix Proof of Theorem 2 We say that mechanism ϕis nonbossy if ϕs(P sP−s)=ϕs(P) implies ϕ(P sP−s)=ϕ(P). The following result proves useful. Result 1(Ergin 2002). Mechanism ϕSis nonbossy for market (S C q)if and only if (q)is acyclic.9 Proof of the “only if”direction. We show the claim by contraposition. Suppose that the priority structure is not acyclic. Then, by definition, there exist a b ∈C,i j k ∈S such that •iajakand kbi •there exist disjoint sets of students SaSb⊂S\{i j k}such that |Sa|=qa−1, |Sb|=qb−1,sajfor every s∈Sa,andsbifor every s∈Sb. Consider the following preferences of students: Pi:ba ∅ Pj:a∅ Pk:ab ∅ 9Part of Theorem 1 of Ergin (2002) states that ϕSis group strategy-proof if and only if the priority structure is acyclic. Result 1 follows from the two well known facts: (i) ϕSis strategy-proof for any priority structure, and (ii) a mechanism is group strategy-proof if and only if it is both strategy-proof and nonbossy.