Dynamically stable matching

Doval, Laura Article Dynamically stable matching Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Doval, Laura (2022) : Dynamically stable matching, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 17, Iss. 2, pp. 687-724, https://doi.org/10.3982/TE4187 This Version is available at: https://hdl.handle.net/10419/296368 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/4.0/ Theoretical Economics 17 (2022), 687–724 1555-7561/20220687 Dynamically stable matching Laura Doval Economics Division, Columbia Business School, Columbia University I introduce a stability notion, dynamic stability, for two-sided dynamic matching markets where (i) matching opportunities arrive over time, (ii) matching is oneto-one, and (iii) matching is irreversible. The definition addresses two conceptual issues. First, since not all agents are available to match at the same time, one must establish which agents are allowed to form blocking pairs. Second, dynamic matching markets exhibit a form of externality that is not present in static markets: an agent’s payoff from remaining unmatched cannot be defined independently of other contemporaneous agents’ outcomes. Dynamically stable matchings always exist. Dynamic stability is a necessary condition to ensure timely participation in the economy by ensuring that agents do not strategically delay the time at which they are available to match. Keywords. Dynamic stability, dynamic matching, stable matching, nontransferable utility, externalities, credibility, market design, dynamic arrivals, aftermarkets, sequential assignment. JEL classification. C78, D47. 1. Introduction I formulate a stability notion, denoted dynamic stability, for two-sided dynamic matching markets where (i) matching opportunities arrive over time, (ii) matching is one-toone, and (iii) matching is irreversible. Stability notions provide an analyst with a set of predictions for the self-enforcing outcomes of decentralized matching markets that depend only on the primitive payoff structure. While stability notions are extensively used in the study of static matching markets, they have not been systematically studied for dynamic matching markets, even though the latter are ubiquitous and cover many important applications, such as labor markets and child adoption. Defining stability in a dynamic matching market brings forth two new challenges that arise when taking into account agents’ intertemporal incentives. First, since not all agents are available to match at the same time, it is natural to ask which pairs of agents Laura Doval: [email protected] I wish to thank three anonymous referees for feedback that has greatly improved this paper. I am indebted to Eddie Dekel, Jeff Ely, and Alessandro Pavan for many fruitful conversations and for their continuing guidance and support. I also wish to thank Héctor Chade, Federico Echenique, Jan Eeckhout, Guillaume Haeringer, John Hatfield, George Mailath, Pablo Schenone, James Schummer, Vasiliki Skreta, Alex Teytelboym, Asher Wolinsky, Leeat Yariv, Vijay Vazirani, Charles Zheng, and especially Erik Eyster and Jacob Leshno for useful discussions. Part of this research was conducted at the California Institute of Technology, and I am grateful for its hospitality. All errors are, of course, my own. ©2022 The Author. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at https://econtheory.org.https://doi.org/10.3982/TE4187 688 Laura Doval Theoretical Economics 17 (2022) can object to a proposed matching. Dynamic stability assumes that only agents who are available to match at the same time can form a blocking pair. Second, whether an agent finds their matching partner acceptable depends on what their value of remaining unmatched is. In turn, this value depends on what matching the agent conjectures would ensue upon their decision to remain unmatched. Given a conjectured continuation matching, one could define an agent’s acceptable partners to be those who are preferred to the continuation matching. This, together with a specification of the set of blocking pairs, is enough to determine whether a matching is stable in the dynamic economy: it should have no blocking pairs and agents should always be matched to acceptable partners. The missing step is then to determine what matching the agent conjectures would result following their decision to remain unmatched. The first difficulty is that the set of agents available to match from tomorrow onward depends on both the arrivals into the economy and who remains unmatched from previous periods. In other words, today’s matching together with tomorrow’s arrivals define the set of feasible continuation matchings. When contemplating remaining unmatched, the agent then needs to conjecture both who else remains unmatched today and tomorrow’s continuation matching. Thus, as in the literature on the core with externalities (see, for instance, Shapley and Shubik (1969), Rosenthal (1971), Richter (1974), Sasaki and Toda (1996), Pycia and Yenmez (2017), Rostek and Yoder (2017)), an agent’s payoff from remaining unmatched cannot be defined independently of other contemporaneous agents’ matching outcomes. This externality sets apart dynamic matching markets from their static counterparts. Given a conjecture about who else remains unmatched today, not all continuation matchings are equally reasonable. Indeed, the agent should correctly anticipate that the continuation matching should be itself self-enforcing. Thus, for a given conjecture about today’s matching outcome, the agent rules out those continuation matchings that are not self-enforcing. This is still not enough to pin down a unique continuation matching and, thus, the value of remaining unmatched. For a given conjecture about who else remains unmatched today, there can be many self-enforcing matchings. Moreover, there can be many conjectures about who else remains unmatched today. Thus, the last step in determining whether the agent finds their matching partner acceptable is an assumption on how the agent selects among the reasonable conjectures. Following Sasaki and Toda (1996), I assume that the agent prefers their matching partner to remaining unmatched if the agent prefers their matching partner to one of the conjectured continuation matchings. Unlike Sasaki and Toda (1996), the agent does not entertain all continuation matchings but only those that are self-enforcing in the continuation economy. Dynamic stability (Definition 6) is a recursive definition that builds on the elements previously described. A matching for the dynamic economy is dynamically stable if (i) there is no pair of agents who are available to match at the same time who prefer to match together and (ii) there is no agent who is matched to someone who is unacceptable. Similar to the static notion of stability, dynamic stability is defined by the absence of pairwise blocks and the requirement that each agent is matched to an acceptable Theoretical Economics 17 (2022) Dynamically stable matching 689 partner. In contrast to static notions of stability, the set of acceptable partners today is defined using the set of dynamically stable matchings from tomorrow onward. Dynamically stable matchings always exist in any finite horizon economy (Theorem 1); I discuss their properties in Section 4. As I explain in Section 4, the proof of Theorem 1builds on the insights in Sasaki and Toda (1996) that an agent’s most pessimistic conjecture can be used to define an artificial economy without externalities in which (static) stable matchings are known to exist. Dynamic matching markets pose new challenges for market design, two of which are analyzed in Section 5. First, in a dynamic matching market, agents choose whether and when to participate. Proposition 2shows that dynamic stability is a necessary condition for timely participation in the market: whenever a matching fails to be dynamically stable, market participants have an incentive to delay the time at which they are available to match.1This echoes the observation in static matching markets that stability is a necessary condition for participation (Roth (1984)). Second, in applications such as school choice, college admissions, and teacher assignment, assignments are performed sequentially because not all agents are available to match at the same time (e.g., Westkamp (2013), Andersson et al. (2018), Dur and Kesten (2019)). The centralized markets that perform these assignments operate via spot mechanisms, that output a matching as a function of the current set of available agents and their reported preferences, but do not condition on future matching possibilities. Unsurprisingly, spot mechanisms do not necessarily induce dynamically stable matchings (Example 4). This raises the question of what outcomes may arise when employing spot mechanisms to perform assignments in a dynamic economy. Theorem 2shows that only dynamically stable matchings can arise as outcomes of subgame perfect Nash equilibrium of the noncooperative game induced by a sequence of spot mechanisms. Thus, agents’ forward-looking behavior is enough to overcome the mechanisms’ inability to condition on all parameters of the economy. However, achieving dynamically stable matchings may be at odds with truthful behavior: even if the spot mechanism is strategy-proof for a static economy, in the dynamic economy agents have an incentive to truncate their preferences above and beyond what they would do in a static economy (Roth and Vande Vate (1991)) to ensure that their assignment reflects what they could have instead obtained by waiting to be matched. Related literature Outside of the literature on the core with externalities, this paper relates to five other strands of literature. The first strand is the literature on market design, which studies dynamic matching markets such as those in this paper, but from the point of view of optimality instead of stability (Ünver (2010), Anderson, Ashlagi, Gamarnik, and Kanoria (2015), Leshno (2017), Schummer (2015), Bloch and Cantala (2017), Ashlagi, Burq, Jaillet, and Manshadi (2018), Thakral (2019), Akbarpour, Li, and Gharan (2020), Arnosti and Shi (2020), Baccara,Lee,andYariv(2020)). An exception is Altinok (2019) who studies stability in dynamic many-to-one matching markets. The present study of 1The mechanism design literature on revenue management has studied the problem of strategic participation (see, for instance, Gershkov, Moldovanu, and Strack (2015), Garrett (2016), Bergemann and Strack (2019)). 690 Laura Doval Theoretical Economics 17 (2022) stability is important because stability is considered a key property for the success of algorithms (Roth (1991)) and because it highlights the potential issues in applying the static notions of stability to dynamic environments. The second strand is the literature on matching with frictions, which studies dynamic matching markets, such as those in this paper, in a noncooperative framework (see Burdett and Coles (1997), Eeckhout (1999), Adachi (2003), Lauermann and Nöldeke (2014) for nontransferable utility, and Shimer and Smith (2000) for transferable utility). As in this strand of the literature, an agent’s value of remaining unmatched (their continuation value) is determined endogenously by the remaining agents in the market and the future matching opportunities. The third strand studies stability notions for markets in which matching opportunities are fixed and pairings can be revised over time (e.g., Damiano and Lam (2005), Kurino (2009), Kadam and Kotowski (2018), Liu (2018), Kotowski (2019)). The contribution relative to this strand is to provide stability notions for markets in which matching opportunities arrive over time and matching is irreversible. As discussed in the Introduction, that matching opportunities arrive over time and that matching is irreversible introduces a primitive externality that is absent from these papers and must be addressed when defining what stability means. In particular, while this paper shares with Liu (2018)andKotowski (2019) the perfection requirement (see also Doval (2015)) and with Kotowski (2019) the use of the approach pioneered by Sasaki and Toda (1996), the motivation for using this approach is different. Since in my paper the set of feasible continuation matchings cannot be defined independently of other contemporaneous agents’ matching outcomes, the externality is an intrinsic feature of the environment that must be addressed by the stability notion. Instead, in Kotowski (2019), the set of feasible continuation matchings does not depend on other contemporaneous agents’ matching outcomes, but the set of equilibrium continuation matchings may because of the perfection requirement in the stability notion, together with the assumption of nonseparable payoffs. The fourth strand studies sequential assignment problems (e.g., Westkamp (2013), Dogan and Yenmez (2018), Andersson et al. (2018), Dur and Kesten (2019), Haeringer and Iehlé (2019), Mai and Vazirani (2019), Feigenbaum, Kanoria, Lo, and Sethuraman (2020)). Of these, only Westkamp (2013), Andersson et al. (2018), Dur and Kesten (2019), and Mai and Vazirani (2019) study models in which not all agents are available to be matched at the same time. However, their focus is on the properties of the matching implemented by the mechanism from the point of view of stability in a static market. Theorem 2echoes observations in Westkamp (2013), Andersson et al. (2018), and Dur and Kesten (2019) that sequential assignment may be at odds with stability or truthful behavior. Theorem 2complements these results by identifying dynamic stability as the solution concept for sequential assignment problems. Since stability notions are oftentimes used for preference identification, Theorem 2can inform the empirical study of sequential assignment problems as in Narita (2018)andNeilson, Kapor, and Karnani (2020). The fifth strand is the literature on the farsighted stable set (e.g., Harsanyi (1974), Chwe (1994), Mauleon, Vannetelbosch, and Vergote (2011), Ray and Vohra (2015)), Theoretical Economics 17 (2022) Dynamically stable matching 691 which is used to model externalities in coalition formation games (e.g., Acemoglu, Egorov, and Sonin (2012) apply farsightedness to a dynamic noncooperative coalitional game). As in this literature, agents in my model understand the terminal consequences of their moves. While farsighted stability focuses on the credibility of coalitional blocks, dynamic stability focuses on the credibility of the continuation matchings used to dissuade agents from blocking. Relatedly, Ray and Vohra (1997) provide a recursive definition of binding agreements in a static model in which a blocking coalition anticipates, among other things, that the agents outside the coalition form a binding agreement among themselves. Organization The rest of the paper is organized as follows. Section 2describes the model and Section 3defines dynamic stability. Section 4shows that dynamically stable matchings exist and discusses their properties. Section 5studies participation and incentives in dynamic matching markets. All proofs are in the Appendices. 2. Model The economy lasts for T<∞periods. There are two sides, Aand B. Agents on side A are labeled a∈A, while agents on side Bare labeled b∈B,whereA,Bare finite sets. An economy of length Tis defined by two sequences (A1,,AT)and (B1,,BT) of subsets of Aand B, respectively, that satisfy that As∩Ar=∅and Bs∩Br=∅,whenever s= r. I denote it by ET=(A1,B1,,AT,BT).Foranyt≤T,letAt=t s=1Asdenote the implied arrivals on side Athrough period t; similarly, let Bt=t s=1Bsdenote the implied arrivals on side Bthrough period t. Definitions 1and 2define the set of feasible allocations for ET. Definition 1. A period-tmatching for economy ETis a mapping mt:At∪Bt→ At∪Bt such that: (i) For all a∈At,mt(a)∈{a}∪Bt, (ii) For all b∈Bt,mt(b)∈At∪{b}, (iii) For all k∈At∪Bt,mt(mt(k))=k. Definition 2. A matching mfor economy ETis a tuple (m1,,mT)such that: (i) For all t∈{1, ,T},mtis a period-tmatching, (ii) For all t∈{1, ,T}, for all a∈At,ifmt(a)= a, then ms(a)=mt(a)for all s≥t. Part 2 of Definition 2incorporates the idea that matchings in the economy are irreversible. Let MTdenote the set of matchings for economy ET. Given a matching m and a period t,letMT(mt−1)denote the set of matchings in MTthat coincide with m through period t−1. 692 Laura Doval Theoretical Economics 17 (2022) Fix a matching m, and suppose that agents have matched according to mthrough period t−1. Then the set of agents who can match in period tis determined by the unmatched agents in period t−1 and the new arrivals in period t,(At,Bt). Formally, Amt−1=a∈At−1:mt−1(a)=a∪At, Bmt−1=b∈Bt−1:mt−1(b)=b∪Bt, where mt−1denotes the tuple (m1,,mt−1),withm0={∅}. A matching malso defines a continuation economy of length T−t, denoted by ET t+1(mt), with side-Aarrivals given by (A(mt),,AT)and side-Barrivals given by (B(mt),,BT). I close the model by defining agents’ preferences. Each a∈Adefines a discount factor δa∈[0, 1]and a Bernoulli utility, u(a,·):B∪{a}→ R. Similarly, each b∈Bdefines adiscountfactorδb∈[0, 1]and a Bernoulli utility, v(·,b):A∪{b}→ R. I assume that for all a∈Aand all b∈B,u(a,a)=v(b,b)=0. Fix a matching mand a period t. For every a∈A(mt−1),lettm(a)denote the first date at which ais matched under m.Thatis,tm(a)is the smallest index ssuch that t≤s and ms(a)= a;otherwise,lettm(a)=T.Thenlet Ut(a,m)=δtm(a)−t aua,mT(a), denote a’s payoff from matching mat date t. Similarly, for b∈B(mt−1),let Vt(b,m)=δtm(b)−t bvmT(b),b, denote b’s payoff from matching mat date t. For future reference, I record two properties that matchings mmay satisfy: individual rationality (Definition 3) and stability for static markets (Definition 4). Definition 3. The matching mfor economy ETis individually rational if for all a∈AT, u(a,mT(a))≥0andforallb∈BT,v(mT(b),b)≥0. That is, matching mis individually rational if each agent prefers their matching partner to remaining unmatched through period T. Definition 4(Gale and Shapley (1962)). Suppose T=1. The matching mfor economy E1=(A1,B1)is stable if the following hold: (S1)Foralla∈A1,U1(a,m)≥0, (S2)Forallb∈B1,V1(b,m)≥0, (S3) There is no pair (a,b)∈A1×B1such that u(a,b)>U 1(a,m)and v(a,b)> V1(b,m). Let S(E1)denote the set of stable matchings for E1. Theoretical Economics 17 (2022) Dynamically stable matching 693 In a one-period economy, matching mis stable if each agent is matched to an acceptable matching partner, that is, a partner who is preferred to remaining unmatched, and there is no pair of agents who prefer each other to the partners assigned by m.Importantly, the value of remaining unmatched can be determined using the model primitives. Throughout, I use the following example to illustrate the concepts in the paper. Example 1. The economy lasts for two periods, that is, T=2. In t=1, Jordan, LeBron, and Shaquille arrive on side A, while Bulls and Heat arrive on side B.Int=2, there are no arrivals on side A, and Lakers and Cavaliers arrive on side B.Thatis, A1={Jordan, LeBron, Shaquille},B1={Bulls, Heat}, A2={∅},B2={Lakers, Cavaliers}. Below, I list the agents’ preferences. If (Lakers, 1)(resp., (Cavaliers, 1)) appears before (Heat, 0)in an agent’s ranking, then they prefer to wait 1 period to match with Lakers (resp., Cavaliers) over matching immediately with Heat. That is, the 0s and 1s are the exponents of the discount factors, and the list provides the ranking of the discounted utilities, {δt−1 ·u(·,b):a∈A1}.ForsideB, the list represents the ranking of utilities, {v(a,·):b∈B1∪B2}. Jordan : (Lakers, 1)( Bulls, 0)( Cavaliers, 0) LeBron : (Lakers, 1)( Cavaliers, 0)( Heat, 0)( Cavaliers, 1) Shaquille : (Heat, 0)( Lakers, 1) Bulls : Jordan Heat : LeBron Shaquille Lakers : Shaquille Jordan LeBron Cavaliers : LeBron Jordan Consider the following three matchings illustrated in Figure 1below (in what follows, a horizontal line separates matchings that occur in different periods). Figure 1 illustrates for each matching only the pairings that happen within each period. For instance, note that mL 1specifies that Jordan matches with Bulls and Shaquille matches with Heat, but also that LeBron is single. That is, mL 1(LeBron)=LeBron. Similarly, mL 2specifies that LeBron matches with Lakers and also records the period-1 matching, mL 2(Jordan)=Bulls, mL 2(Shaquille)=Heat. The three matchings in Figure 1satisfy Definition 3: each agent’s matching partner is preferred to remaining single though period 2. However, only the period-2 matchings mL 2and mR 2satisfy Definition 4.Toseethis,considermC. If agents match according to mC 1in t=1, this induces a one-period economy in t=2, with agents on side A,A(mC 1)= {LeBron, Shaquille}, and agents on side B,B(mC 1)={Heat, Lakers, Cavaliers}. Note that mC 2does not satisfy Definition 4for this one-period economy: LeBron and Cavaliers form a block. Instead, it is immediate to verify that mL 2and mR 2do satisfy Definition 4 for the one-period economies E2 2(mL 1)and E2 2(mR 1), respectively. ♦ 694 Laura Doval Theoretical Economics 17 (2022) mL= ⎛ ⎜ ⎜ ⎜ ⎝ Jordan _ Bulls Shaquille _ Heat LeBron _ Lakers ∅_ Cavaliers ⎞ ⎟ ⎟ ⎟ ⎠ mC= ⎛ ⎜ ⎜ ⎜ ⎝ Jordan _ Bulls LeBron _ Heat Shaquille _ Lakers ∅_ Cavaliers ⎞ ⎟ ⎟ ⎟ ⎠ mR= ⎛ ⎜ ⎜ ⎜ ⎝ Shaquille _ Heat Jordan _ Lakers LeBron _ Cavaliers ∅_ Bulls ⎞ ⎟ ⎟ ⎟ ⎠ Figure 1. Three matchings for the economy in Example 1. Remark 1highlights three assumptions that simplify notation, but are otherwise unnecessary for the results. Remark 1. First, while the model presumes that agents can perfectly foresee when each agent arrives in the economy, all of the results extend to the case in which arrivals are stochastic. In this case, an economy of length Tis defined as a distribution GTover sequences ET. Second, I assume that no two agents with the same characteristic arrive within or across periods. Both of these extensions can be found in Doval (2021). Third, while the model is written in terms of time-discounted preferences, all that matters for the results is that time preferences are dynamically consistent. 3. Dynamic stability Section 3defines dynamic stability (Definition 6). Similar to the static notion of stability, dynamic stability is defined by the absence of pairwise blocks and the requirement that each agent is matched to an acceptable partner; that is, someone that is preferred to remaining unmatched. Unlike the static notion of stability, the value of remaining unmatched is determined endogenously (see equation (1) below). In what follows, I first introduce the definition, using Example 1to illustrate its components. I then discuss in detail the different elements in the definition. Given a matching m, the goal is to determine whether the agents will follow the prescription of min every period t∈{1, ,T}. Fix a period tand suppose that the agents have matched according to mthrough period t−1. Thus, the set of agents who can match in period tis A(mt−1)∪B(mt−1). There are two reasons the agents who can match in period t,A(mt−1)∪B(mt−1), may prefer not to follow the prescription of min period t. First,therecouldbeapair of agents who prefer to match together over matching according to m. Second, there could be a single agent who prefers not to match according to m. The latter could be either because mdictates that the agent matches in period t, but the agent could do better by remaining unmatched, or because mdictates that the agent is unmatched in Theoretical Economics 17 (2022) Dynamically stable matching 701 argument in favor of the alternative notion of blocking uses forward induction:when the agents in period t+1 observe that kdeviated from the prescribed matching m,they should infer that this only makes sense if there is a continuation matching that kpreferred to matching m. However, to select k’s most preferred conjecture, the forward induction reasoning should apply to both the period-tmatching and the continuation matching. That is, the remaining period-tagents should be able to react in period tto k’s decision to block. This is inconsistent with the assumption that agents in period t make decisions simultaneously. Second, Definition 6does not require that agents hold “common beliefs” about the matching that would ensue when they decide to be unavailable to match in period t. That is, suppose two agents kand kanticipate that the matchings mkand mkwould ensue when they choose to be unavailable to match in period t.Thenmkand mkneed not coincide for the agents other than kand kin period t. Furthermore, even if mk and mkcoincide in period t, they need not coincide in the continuation economy. This property is shared with the model of Sasaki and Toda (1996) and with the models of Ambrus (2006)andLiu, Mailath, Postlewaite, and Samuelson (2014), where the solution concepts are akin to rationalizability. Note, however, that this lack of commonality only applies to those agents who match in period tand for whom remaining unmatched in period tis an off-path event. Indeed, the property in Remark 2implies that in a dynamically stable matching m, the agents who remain unmatched in period tunder mall share the same conjecture: even if they chose to object to min period t, they all agree that m would still be the outcome from period tonward. 4. Properties Theorem 1presents the main result of the paper: the set of dynamically stable matchings is nonempty. Theorem 1. For all T∈N, the correspondence DTis nonempty valued. See Appendix Afor the proof, which shows how to find a matching (labeled min the proof) that is dynamically stable. Because of the recursive nature of dynamic stability, the proof needs to simultaneously determine the conjectures, MD(k,mt−1),andthe matching, m, that is dynamically stable given these conjectures. To determine the conjectures, the proof proceeds by induction on T≥1: to show that dynamic stability is well-defined for T, one must show that it is well-defined for T<T. This is the step that uses the assumption that T<∞. As argued in Section 3, dynamic stability coincides with the static notion of stability when T=1. It follows from Gale and Shapley (1962)thatD1(·)is nonempty for all one-period economies. Given the set of conjectures, I adapt the proof technique in Sasaki and Toda (1996) to find a matching that is dynamically stable. Sasaki and Toda (1996)showhowtouse a set of conjectures to construct an economy without externalities. Building on their insights, I use the agents’ conjectures to construct a “static” economy in period tas follows. To be concrete, consider the case in which T=2. For each agent k∈A1∪B1,I 702 Laura Doval Theoretical Economics 17 (2022) calculate k’s continuation value to be the payoff from the worst matching in MD(k,·). Given these continuation values, I truncate k’s preferences so that kis only willing to match with period-1 agents that are preferred to k’s continuation value. I choose the period-1 matching, m 1, to be a stable matching for the one-period economy with the truncated preferences. This, in turn, determines the set of unmatched agents at the end of t=1. I then choose the period-2 matching, m 2,tobeastablematchingamongthe newly arriving agents and the remaining ones from period 1. By construction, msatisfies conditions (D1)and(D2) of Definition 6.Inparticular, for agents who do not match in t=1underm,Ishowthatmis a valid conjecture (recall Remark 2). It only remains to check that msatisfies condition (D3) in Definition 6. Suppose there is a pair (a,b)of agents in period 1, who prefer matching together over m.Byconstructionofm, it must be that at least one of the members of the pair is unmatched in t=1. For concreteness, say it is a. It then follows that atruncated their preferences “too much:” mis worse than the worst matching in MD(a,·). However, this contradicts that mis an element of MD(a,·). Both the ability to select conjectures to dissuade agents from blocking a matching together with the property in Remark 2are key to show that dynamically stable matchings exist. To see the role of the former, suppose instead that the existence of a conjecture mthat is preferred to mwas enough for an agent to block matching m.Thenonecould modify the construction in the proof as follows. Instead of truncating each agent’s preferences using the worst element in MD(·), one would truncate each agent’s preferences using the best element in that set. The same construction would again lead to a matching that satisfies the property in Remark 2for those agents who remain unmatched in t=1. However, this is not enough to argue that the unmatched agents would not form a blocking pair with another agent in t=1. After all, the constructed matching need not be the best conjecture for all the unmatched agents. Similarly, without the property in Remark 2, the ability to select conjectures is not enough for the result in Theorem 1. The ability to promise a blocking agent the worst element in MD(·)maximally dissuades agents who match in period tfrom being unavailable to match. However, there may be agents for whom remaining unmatched in period tis the best they can do given this promise. The property in Remark 2implies that one can effectively deliver this promise simultaneously to all of the agents who remain unmatched in period twhen choosing a dynamically stable matching from period t+1onward. 4The reason is that all agents agree that (i) (static) stability is a minimal requirement of the outcome for the agents who match in period tand (ii) continuation matchings are dynamically stable for the continuation economy. Algorithms. Even though it is not constructive, the proof of Theorem 1suggests an algorithm to find dynamically stable matchings for economies of length 2. To see this, fix an economy, E2=(A1,B1,A2,B2). The algorithm consists of three steps: 4The lack of commonality in the conjectures could have hindered existence by making it difficult to find one continuation matching that “works” for all agents who remain unmatched in period t. Theoretical Economics 17 (2022) Dynamically stable matching 703 (a) Conjectures: For each k∈A1∪B1and for each C⊆(A1∪B1)\{k}, define the set M(k,C)as follows. Any matching min M(k,C)is such that (i) m1(k)=kif k/∈C, (ii) the restriction of m1to Ccoincides with side-Adeferred acceptance on C, and (iii) m2is a stable matching for A(m1)∪B(m1).LetM(k)denote the union of M(k,C)over the (possibly empty) subsets C⊆(A1∪B1)\{k}. (b) Period-1 matching: As in the proof of Theorem 1, for each agent k∈A1∪B1,truncate k’s preferences using the set M(k).Letm 1denote the outcome of side-A deferred acceptance on A1∪B1using the truncated preferences. (c) Period-2 matching: The period-2 matching, m 2, is obtained by running side-A deferred acceptance on A(m 1)∪B(m 1). Two comments are in order. First, step (a) does not recover the entire set of conjectures, MD(k,·): In order to do so, one should repeat step (a) for each subset Cand each (static) stable matching among the agents in C. However, k’s payoff from remaining unmatched in period 1 depends on the period-1 matching among the agents in Conly through the set of unmatched agents that it induces. By the Lone Wolf theorem (McVitie and Wilson (1970)), the latter set is independent of the stable matching one selects for C. Second, by changing side-Adeferred acceptance in steps (b) and (c) to other (static) stable matchings, the algorithm retrieves different dynamically stable matchings. Whether an algorithm to find dynamically stable matchings for economies of length T≥3 exists is still an open question. The key difficulty in designing an algorithm for an economy of length Tis to find an algorithm that recovers an agent’s worst dynamically stable matching for an economy of length T−1. After all, step (b) only uses each agent’s worst conjectured matching to truncate their preferences. As an example in Section A.1 illustrates, the algorithm described above for T=2 does not recover every agent’s worst dynamically stable matching. In this example, there are two dynamically stable matchings, labeled mAand mB. The algorithm only recovers mA, whereas there are agents who are worse off under mB. Therefore, the algorithm for T=2 cannot be extended to economies of length T≥3. However, when agents do not discount the future, one can find dynamically stable matchings using the algorithms for the static notion of stability. To see this, let mTbe a (static) stable matching for (AT,BT), that is, an element of S(AT,BT). When the agents do not discount the future, it is immediate to verify that the matching mthat leaves all agents unmatched until period Tand matches them according to mTin period T is dynamically stable. Nevertheless, this construction retrieves some, but not all, dynamically stable matchings. There are two reasons for this. First, the ability to select conjectures can be used to dissuade agents from waiting to be matched and instead, accept matching partners not consistent with the static notion of stability. Second, as Example 2illustrates, even if agents do not discount the future, the dynamic and static notions of stability allow for different pairwise blocks. Example 2. Consider the following variant of Example 1. Jordan and Bulls arrive at t=1. The remaining agents arrive at t=2, except for Cavaliers, who no longer arrives, 704 Laura Doval Theoretical Economics 17 (2022) that is, A1={Jordan},B1={Bulls},A2={LeBron, Shaquille},andB2={Heat, Lakers}. The agents do not discount the future. Their rankings are as follows: Jordan : Lakers Bulls LeBron : Lakers Heat Shaquille : Heat Lakers Bulls : Jordan Heat : LeBron Shaquille Lakers : Shaquille Jordan LeBron The following two matchings are dynamically stable: mS= ⎛ ⎜ ⎜ ⎜ ⎝ ∅ Jordan _ Bulls LeBron _ Heat Shaquille _ Lakers ⎞ ⎟ ⎟ ⎟ ⎠ mD=⎛ ⎜ ⎝ Jordan _ Bulls LeBron _ Lakers Shaquille _ Heat ⎞ ⎟ ⎠. The matching mSis the unique matching obtained by the construction described above: no one matches in t=1 and a (static) stable matching is chosen for t=2. Instead, matching mDis dynamically stable, but cannot be obtained as a (static) stable matching when everyone waits to be matched until t=2. To see this, note that if this matching were to happen in t=2, then Jordan and Lakers would form a (static) block. However, under dynamic stability, when Jordan considers remaining unmatched in t=1, there is a unique valid conjecture and it corresponds to matching mS. Under this conjecture, Jordan matches with Bulls, whereas Lakers matches with Shaquille, whom they prefer to Jordan. Thus, when applied to the dynamic environment, the static notion of stability may rule out matchings by allowing for pairwise blocks that are not credible: Anticipating that Lakers will not form a block with Jordan once Jordan waits for Lakers to arrive, Jordan prefers not to wait for Lakers in the first place. ♦ Further properties In static matching markets, the Lone Wolf theorem (McVitie and Wilson (1970)) and the lattice property are important structural properties. However, the set of dynamically stable matchings inherits neither. Proposition 1. There exist economies for which the set DT(ET)does not satisfy the Lone Wolf theorem. Furthermore, the set DT(ET)does not form a lattice. Proposition 1follows from an example in Section A.1. Despite the differences between the dynamic and static notions of stability, there are also important similarities. Similar to stability in static matching markets, dynamic stability of a matching is a necessary condition for voluntary participation. This is the topic of Section 5. 5. Participation,timing,and incentives in dynamic matching markets In static matching markets, mechanisms that output stable matchings simultaneously address two problems. First, as observed by Roth (1984), stability is a necessary condition for voluntary participation in the mechanism. This identifies mechanisms that output stable matchings for the reported preferences as the only candidates to induce Theoretical Economics 17 (2022) Dynamically stable matching 705 participation. Second, conditional on participating, the mechanism must be such that participants have an incentive to truthfully report their preferences. It is well known that no stable mechanism exists that makes it optimal for both sides of the market to truthfully reveal their preferences. Instead, if the mechanism outputs, say, the matching obtained by side A-proposing deferred acceptance (henceforth, DA), then it is a dominant strategy for agents on side Ato truthfully report their preferences. Thus, in settings in which side Bis nonstrategic, side A-proposing DA is used to simultaneously address the problems of participation and incentives. This section analyzes the issues of participation and incentives in the context of dynamic matching markets. Proposition 2in Section 5.1 shows that dynamic stability is a necessary condition for timely participation in the matching market. Furthermore, an extension of DA to the dynamic economy is shown to give agents on the proposing side the correct incentives to participate as soon as they arrive. Section 5.2 studies the issues of participation and incentives in the context of sequential assignment problems. The main result in Section 5.2,Theorem2, shows that only dynamically stable matchings can arise as subgame perfect equilibrium outcomes of the preference revelation game induced by a sequence of stable mechanisms. 5.1 Voluntary and timely participation Roth and Sotomayor (1992, pp. 22–23) argue that stability is a necessary condition for voluntary participation in a static economy as follows. Suppose a matchmaker can recommend a matching for the economy but cannot compel the agents to accept the matching. Instead, the agents are free to form pairs among themselves or choose to remain unmatched. Then the agents follow the matchmaker’s recommended matching only if it is a stable matching. Proposition 2shows that dynamic stability plays the same role in the dynamic economy: the agents follow the matchmaker’s recommended matching only if it is dynamically stable. Consider a matchmaker who recommends a matching for the agents in ETand whose objective is that the agents follow her recommendation. In each period t,agents arrive in the economy according to ET. Each of the newly arriving agents, together with the remaining unmatched agents from previous periods, announce simultaneously either that they want to follow the matchmaker’s recommendation or the name of an agent they wish to match with (including themselves). The matchmaker’s recommendation is implemented only if all the agents agree to follow it. Instead, any agents kand kwho announce that they wish to match with each other are matched, while the remaining agents remain unmatched. Agents who match exit. The remaining unmatched agents join the newly arriving agents in period t+1. In the dynamic economy, the matchmaker has to recommend not only a matching for economy ET(the one that would ensue if all the agents follow her recommendation), but also a continuation matching in the event that some agent chooses not to follow her recommendation. The matchmaker could potentially condition her recommendation for period ton (i) the matching that has ensued through period t−1, ˆ mt−1, and (ii) on when and which agents in A(ˆ mt−1)∪B(ˆ mt−1)chose not to follow her recommendation. Because it does not affect the conclusion of Proposition 2, I make the simplifying 706 Laura Doval Theoretical Economics 17 (2022) assumption that the matchmaker’s recommendation in period tonly depends on (i). I denote this recommendation by μt(ˆ mt−1),whereμt(ˆ mt−1)is a period-tmatching that respects the matchings that have happened through period t−1. That is, for all a∈At−1, ˆ mt−1(a)= aimplies that μt(ˆ mt−1)(a)=ˆ mt−1(a). I focus on situations where following the matchmaker’s recommendation is a subgame perfect Nash equilibrium (henceforth, SPNE) such that there is no pair of contemporaneous agents who have a joint deviation.5This refinement is standard in the literature that studies the noncooperative implementation of stable matchings (see, for instance, Ma (1995), Shin and Suh (1996), and Sönmez (1997)); I refer to this as a pairwise SPNE. Subgame perfection implies that the agents should find it optimal to follow the matchmaker’s recommendation even after (other) agents in previous periods have chosen not to follow the matchmaker’s recommendation. Allowing for joint deviations by pairs of contemporaneous agents allows us to recover the result in Roth and Sotomayor (1992): when T=1, following the matchmaker’s recommendation is an equilibrium only if the suggested matching is stable. Under such an equilibrium, the matchmaker’s plan describes both the matching that would ensue if everyone follows her recommendation and the matching that would ensue if some agent chooses not to follow her recommendation (but from then on, everyone chooses to follow her recommendation). This addresses two potential difficulties. First, it identifies the recommendations the agents would find optimal to follow, and hence, which matchings the matchmaker can “credibly” recommend. Second, it does away with having to specify the particular protocol by which agents form matchings when they do not follow the matchmaker’s recommendations. To see this, note that the matching plan in period tcan depend on whether the matching through period t−1 coincides with the matchmaker’s recommendation. For instance, it could specify that everyone remains unmatched whenever the agents do not follow the matchmaker’s recommendation. However, if the agents are free to form matchings among themselves, it is not clear that the agents would follow such a recommendation. In this case, the final outcome would be determined by a combination of the matchmaker’s plan together with the agents’ decisions to form matchings. This could require making further assumptions about how the agents form matchings when they do not follow the matchmaker’s recommendations. Requiring that the agents find it optimal to follow the matchmaker’s recommendation on and off the path of play circumvents these difficulties. To state Proposition 2, I introduce one final piece of notation. For any matching through period t,ˆ mt−1,letmμ(ˆ mt−1)denote the matching for ET t(ˆ mt−1)that arises when after ˆ mt−1, the remaining agents and the new entrants follow the matchmaker’s recommendation. Formally, mμ(ˆ mt−1)=(μt(ˆ mt−1),μt+1(ˆ mt−1,μt(ˆ mt−1)),).Inparticular, mμ≡mμ(∅)∈MTdenotes the matching that is implemented if everyone follows the matchmaker’s recommendation. 5At the cost of more notation, I could assume that in each period the agents announce one at a time either that they want to follow the recommendation or an agent on the other side (or themselves) they want to match with and use SPNE as the solution concept (see Lagunoff (1994)). Theoretical Economics 17 (2022) Dynamically stable matching 707 Proposition 2. Suppose that following the matchmaker’s recommendation is a pairwise SPNE. Then, for all t≥1and ˆ mt−1,mμ(ˆ mt−1)is dynamically stable for ET t(ˆ mt−1).In particular, mμis dynamically stable for ET. Proposition 2echoes the observations in Roth (1984)andRoth and Sotomayor (1992) that stability is a necessary condition for voluntary participation. It is immediate to see that the ability of the agents to remain single or form blocking pairs implies that the matching mμ(ˆ mt−1)must be individually rational (Definition 3) and satisfy condition (D3). Proposition 2implies that this is not enough to guarantee that the agents will follow the matchmaker’s recommendation: mμ(ˆ mt−1)must be dynamically stable. Underlying this observation is that from period t+1 onward, the agents follow the matchmaker’s recommendation only if it leads to a dynamically stable matching. In turn, this limits the set of matchings that an agent can expect when they consider not following the matchmaker’s recommendation in period t. Similar to the literature on strategic participation in mechanism design (e.g., Gershkov, Moldovanu, and Strack (2015), Garrett (2016), and Bergemann and Strack (2019)), Proposition 2highlights that in a dynamic economy voluntary participation involves not only the decision of whether to participate, but also when. Indeed, since in the final period the matchmaker’s recommendation is followed only if the matching satisfies the static notion of stability, the result in Roth and Sotomayor (1992) implies that any agent who has not yet participated in the matchmaker’s plan will participate then. Dynamic stability of the matchmaker’s recommended matching guarantees that agents are willing to participate as soon as they arrive. Remark 3. An alternative description of the game would have the matchmaker provide a recommendation as a function of the set of agents who agree to follow her recommendation. That is, μtdepends on both the matching through period t−1, ˆ mt−1, and the set of agents who follow the matchmaker’s recommendation in period t,ˆ At∪ˆ Bt⊆A(ˆ mt−1)∪B(ˆ mt−1). Then, in each period t, the agents who choose to follow the matchmaker’s recommendation are matched according to μt, whereas the remaining agents either remain unmatched or form matching pairs. This alternative specification of the game raises the question of what properties the matching should have whenever the set of agents who follow the matchmaker’s recommendation differs from the set of agents who follow her recommendation on the path of play. For concreteness, suppose that in equilibrium agents in ˆ At∪ˆ Btare supposed to follow the matchmaker’s recommendation. As in Proposition 2, this will identify properties, such as individual rationality, that the matching starting from period tmust satisfy when ˆ At∪ˆ Btfollows the matchmaker’s recommendation. Otherwise, it would not be part of an equilibrium. Consider now an agent k∈ˆ At∪ˆ Btwho contemplates not following the matchmaker’s plan in period t.Thenagentkanticipates that in period t, the matchmaker’s plan for (ˆ At∪ˆ Bt)\{k}would be implemented. Because this is an off the path event, equilibrium play does not even guarantee that this period-tmatching is stable for the agents in (ˆ At∪ˆ Bt)\{k}, let alone individually rational. This, in turn, implies that the matchmaker can threaten kwith period-tmatchings that the agents 708 Laura Doval Theoretical Economics 17 (2022) in ˆ At∪ˆ Bt\{k}would not follow on the path of play. The ability to implement off the path of play period-tmatchings that fail to even satisfy Definition 5runs counter to the matchmaker’s inability to compel the agents to accept such a matching on the path of play.6In turn, the matchmaker’s ability to implement these types of matchings off the path of play may limit what the agents themselves can achieve on the path of play. This again runs counter to the matchmaker’s inability to compel the agents to accept any given matching. The game considered in Proposition 2has the advantage that there is no conflict between what the matchmaker can achieve on and off the path of play. However, the result in Proposition 2would go through in the alternative specification of the game if one requires that for each period t, each matching ˆ mt−1through period t−1, and each subset of agents who follows the recommendation in period t,ˆ At∪ˆ Bt⊆A(ˆ mt−1)∪B(ˆ mt−1),the matchmaker’s plan, μt(ˆ mt−1,ˆ At,ˆ Bt), satisfies Definition 5. Indeed, the following holds.7 Proposition 2∗.Suppose that for all t≥1,ˆ mt−1and ˆ At∪ˆ Bt⊆A(ˆ mt−1)∪B(ˆ mt−1), μt(ˆ mt−1,ˆ At,ˆ Bt)satisfies Definition 5. Then, following the matchmaker’s recommendation is a pairwise SPNE only if for all t≥1,ˆ mt−1,mμ(ˆ mt−1)is dynamically stable for ET t(ˆ mt−1). I omit the proof because it follows the same steps as that of Proposition 2. Proposition 3and Example 3below further illustrate that, even if preferences are known, the option to delay the time at which an agent is available to match creates an incentive problem in dynamic matching markets. While in static matching markets DA provides the agents on the proposing side with the correct incentives to report their preferences, Proposition 3shows that when T=2, a natural extension of DA to the dynamic economy provides the agents on the proposing side with the correct incentives to participate as soon as they arrive. To state Proposition 3,letmA-DA denote the matching obtained by running the following dynamic version of DA: the DA algorithm is run with agents in A1∪A2making proposals (using their intertemporal preferences) to agents in B1∪B2(who choose between proposals using their intertemporal preferences). The following holds. Proposition 3. Let T=2. Then, for all a∈A1,thereexistsm∈MD(a,·)such that U1a,mA-DA≥U1(a,m). Proposition 3states that in a two-period economy, agents in A1cannot improve on the outcome of mA-DA by delaying the time at which they are available to match. To see this, fix an agent a∈A1. Consider the matching mA-DA obtained by running the dynamic version of side-ADA in the economy (A1\{a},B1,A2∪{a},B2). That is, agent amakes 6Indeed, as Proposition 2shows, the matchmaker can only implement individually rational matchings that satisfy condition (D3), which implies that the period-tmatching satisfies Definition 5. 7Note that in this case the matching mμ(ˆ mt−1)denotes (μt(ˆ mt−1,A(ˆ mt−1),B(ˆ mt−1)),μt+1(μt(·),·),). Theoretical Economics 17 (2022) Dynamically stable matching 709 mB-DA =⎛ ⎜ ⎝ LeBron _ Heat Shaquille _ Lakers Jordan _ Cavaliers ⎞ ⎟ ⎠mA-DA =⎛ ⎜ ⎝ Shaquille _ Heat LeBron _ Lakers Jordan _ Cavaliers ⎞ ⎟ ⎠ Figure 4. Matchings obtained by running the dynamic version of DA. proposals as if aarrived in t=2, and agents b∈B1evaluate the payoff from matching with agent aas if aarrived in t=2. I show that mA-DA is an element of MD(a,·).If acould improve on mA-DA by waiting to be matched, then astrictly prefers mA-DA to mA-DA. The same lemma used to prove that DA is strategy-proof for the proposing side in static matching markets implies that aprefers mA-DA to mA-DA.Thus,mA-DA can be chosen as the matching aexpects would arise if ablocked matching mA-DA in t=1. Proposition 3provides a way to construct a matching plan to support mA-DA that satisfies the properties in Proposition 2∗and such that all agents on side Awould follow it in t=1. This follows from three observations. First, mA-DA induces a stable matching in t=2, so that if agents match according to mA-DA in t=1, then it is optimal for the agents in E2 2(mA-DA 1)to follow the matchmaker’s recommendation. Second, by construction, no pair of agents in t=1canimproveonmA-DA by matching together. Third, the matchmaker can credibly promise each a∈A1, that mA-DA is the outcome if they choose not to follow the recommendation in t=1. When aobjects in t=1, the matchmaker implements the period-1 matching mA-DA 1, which by construction satisfies Definition 5. Since mA-DA 2is stable for (A(mA-DA 1),B(mA-DA 1)), agents will participate and follow the matchmaker’s recommendation in t=2. However, the matchmaker may not be able to convince the agents in B1to participate when the matching is mA-DA.AsExample3illustrates, the matching obtained by running the dynamic version of DA with side Bproposing may be improved on by agents on side Awaiting to be matched. Example 3. Consider the following variant of Example 1. LeBron and Shaquille continue to arrive at t=1, whereas Jordan now arrives at t=2. Arrivals on side Bare as before, except that now Bulls no longer arrive. That is, A1={LeBron, Shaquille}, B1={Heat},A2={Jordan}and B2={Lakers, Cavaliers}. Preferences are given by: Jordan : Cavaliers LeBron : (Lakers, 1)( Cavaliers, 0)( Heat, 0)( Cavaliers, 1) Shaquille : (Heat, 0)( Lakers, 1) Heat : LeBron Shaquille Lakers : Shaquille LeBron Cavaliers : LeBron Jordan Figure 4illustrates the matchings obtained by running the dynamic version of DA with sides Band Aproposing, respectively. 710 Laura Doval Theoretical Economics 17 (2022) The matching mB-DA is not dynamically stable: LeBron can guarantee to be matched with Lakers by remaining unmatched in t=1. To see this, note that Shaquille also needs to match in t=2 for LeBron not to match with Lakers in t=2. Hence, LeBron needs to conjecture that everyone matches in t=2 when he waits to be matched. However, when this is the case, all stable matchings match LeBron with the Lakers. Thus, if the matchmaker suggests mB-DA, LeBron does not follow the matchmaker’s recommendation in t=1. ♦ Proposition 3and Example 3echo the static matching markets’ results that side Aproposing DA is strategy-proof for agents on side A, whereas side B-proposing DA is not. Indeed, as previously explained, the proof of Proposition 3is intimately related to the strategy-proofness of DA for the proposing side. However, the analogy between the result in Proposition 3and the strategy-proofness of DA for the proposing side is incomplete. Whereas the latter refers to agents’ incentives to truthfully report their preferences conditional on participating in the mechanism, the former refers to agents’ incentives to timely participate in the mechanism when their preferences are commonly known. In other words, in a dynamic matching market, agents can strategically decide when to participate and what preferences to report. This is the focus of Section 5.2. 5.2 Sequential assignment problems Section 5.2 studies the issues of timely participation and preference manipulation in dynamic matching markets within the context of sequential assignment problems. In sequential assignment, matchings are performed in multiple stages via a sequence of spot mechanisms that output a matching as a function of the current set of available agents and their reported preferences, but do not condition on future matching opportunities. Sequential assignment covers important applications such as school choice and college admissions, in which both students and school seats become available over time. In school choice, admissions to public, charter, and private schools often occur at different times, and through different mechanisms, schools update the number of seats available as the beginning of the school year approaches, and new students join the public school system during the summer as families move across district and/or state boundaries (Andersson et al. (2018) provide an excellent description of different school districts and their sequential algorithms). In many districts in the United States, this leads to aftermarkets (see Pathak (2016)): Public school districts run their matching algorithms several times to accommodate newly incoming students, newly available seats, and also the timing of private and charter schools’ decisions. While in the United States private schools do not participate in the centralized matching procedure, they do in Turkey and some localities in Sweden. For instance, seats in public and private schools are assigned via a two-stage procedure in Turkey. Since 2015, this two-stage procedure operates as follows. In the first stage, students are assigned based on test scores via serial dictatorship to private schools. In the second stage, unmatched students from the first stage Theoretical Economics 17 (2022) Dynamically stable matching 717 Appendix B: Proofs of Section 5 Proof of Proposition 2. Suppose it is a pairwise SPNE for the agents in ETto follow the matchmaker’s recommendation for all t,ˆ mt−1. Since an agent can always guarantee the payoff from being single through period Tby always rejecting the matchmaker’s recommendation, mμ(ˆ mt−1)must be individually rational. Furthermore, mμ(ˆ mt−1)satisfies condition (D3)forET t(ˆ mt−1); otherwise, there is a pair of agents who can match in the same period and can jointly deviate and match together, improving on the matchmaker’s recommendation. It follows that for all ˆ mT−1,μT(ˆ mT−1)satisfies the static notion of stability (Definition 4)forET T(ˆ mT−1). Toward a contradiction assume that there exists t,ˆ mt−1,suchthatmμ(ˆ mt−1)is not dynamically stable. Let t≤T−1 denote the largest s≤T−1 such that there exists ˆ ms−1 such that mμ(ˆ ms−1)fails either (D1)or(D2) in Definition 6.Thus,thereexists ˆ mt−1and k∈A(ˆ mt−1)∪B(ˆ mt−1)such that kprefers all elements of MD(k,ˆ mt−1)to their outcome under mμ(ˆ mt−1). By assumption, all agents in A(ˆ mt−1)∪B(ˆ mt−1)\{k}are following the matchmaker’s recommendation. Thus, if kwere to deviate and choose to remain single when the matchmaker recommends μt(ˆ mt−1), and then follow the equilibrium strategy, everyone remains unmatched this period (denote this matching by m∅ t)and from tomorrow onward the matching mμ(ˆ mt−1,m∅ t)would ensue. By definition of t, ˆ mt−1,mμ(mt−1,m∅ t)∈DT−t(ET t+1(ˆ mt−1,m∅ t)).Thus, (ˆ mt−1,m∅ t,mμ(ˆ mt−1,m∅ t))∈MD(k,ˆ mt−1).Thenkhas a one-shot deviation to reject the matchmaker’s recommendation, contradicting the definition of SPNE. Proof of Proposition 3.LetE2and mA-DA be as in the statement of Proposition 3. Let a∈A1be such that mA-DA 1(a)= a. Construct a matching mas follows. Run deferred acceptance as if the economy was given by (A1\{a},B1,A2∪{a},B2),thatis: (a) amakes proposals as if aarrived in t=2Thatis,aproposes to b∈B2before b∈B2 if and only if u(a,b)>u (a,,b). (b) b∈B1accepts a’s offer over a∈A1only if δbv(a,b)>v (a,b). Note that m∈MD(a,mA-DA). Toward a contradiction, suppose that U1(a,m)> U1(a,mA-DA).LetA+denote the set of agents on side Awho prefer mto mA-DA. According to a lemma by J. S. Hwang (see Gale and Sotomayor (1985) for a proof), there exists a/∈A+and b∈m2(A+)such that δ1[b∈B2,a∈A1] au(a,b)>U ·(a,m)and δ1[b∈B1,a∈A2] bv(a,b)>V ·(b,m). This contradicts the definition of m. Thus, it cannot be that astrictly prefers mto mA-DA. B.1 Proof of Theorem 2 I introduce notation to define the agents’ strategies and the solution concept. A public history at the beginning of period t,ht, is a matching through period t−1, ˆ mt−1. Let s≥1andletk∈As∪Bs. For any period t≥s,agentkwould have observed a public history ˆ mt−1, together with their decision to participate and their reported preferences. While agent kcan condition their period tstrategy both on htand their past 718 Laura Doval Theoretical Economics 17 (2022) actions, it will be clear from the proof that it is without loss of generality to focus on strategies that condition on the public history alone. Thus, to keep notation simple, I define agent k’s behavioral strategy in period tas a mapping σk,t, that takes a public history htsuch that kis unmatched in period tand outputs k’s decision to participate and a ROL, k,t.Letσk=(σk,t)t≥sdenote k’s strategy profile. A pure strategy profile σ=(σk)k∈AT∪BTdetermines a terminal history hT+1 σ= (ˆ mσ 1,,ˆ mσ T), where letting ˆ Aσ t∪ˆ Bσ tdenote the set of agents who participate in the spot mechanism in period tunder σwe have that ˆ mσ t|ˆ Aσ t∪ˆ Bσ t=νtˆ Aσ t,ˆ Bσ t,σkht σk∈ˆ Aσ t∪ˆ Bσ t. Also, ˆ mσ t(k)=kfor all k∈A(ˆ mσ,t−1)∪B(ˆ mσ,t−1)\(ˆ Aσ t∪ˆ Bσ t). Finally, ˆ mσ t(k)=ˆ mσ t−1(k) for k∈(At∪Bt)\(A(ˆ mσ,t−1)∪B(ˆ mσ,t−1)). Similarly, a pure strategy profile σtogether with a public history ht=ˆ mt−1determine a continuation matching mσ(ˆ mt−1). An agent’s payoff from strategy profile σat public history ˆ mt−1is determined by the payoff from the matching it induces. That is, letting a∈A(ˆ mt−1), Ua,σ|ˆ mt−1=Uta,ˆ mt−1,ˆ mσˆ mt−1, and similarly for b∈B(ˆ mt−1). Definition 8. A pure strategy profile σ=(σk)k∈AT∪BTis a pairwise SPNE of 2if it is a SPNE of 2and the following holds: There is no period t≥1, public history ht=ˆ mt−1, and pair (a,b)∈A(ˆ mt−1)∪B(ˆ mt−1)such that there exists σ a,σ bsuch that U(a,(σ−(a,b),σ a,σ b)|ht)>U(a,σ|ht)and V(b,(σ−(a,b),σ a,σ b)|ht)>V(b,σ|ht). In what follows, I assume that preferences over matchings are strict.12 Lemma 1. In both games, it is without loss of generality to focus on strategy profiles where the agents participate in the mechanism whenever they are unmatched. This follows from noting that (i) participating is not observable, and (ii) agents who participate can submit a ROL that only includes themselves, that is, an empty ROL. Lemma 2. In both games, without loss of generality, agents either submit an empty ROL or a truncation of the ranking induced by their Bernoulli utility function. Proof. Fix a history ht=ˆ mt−1and an agent k∈A(ˆ mt−1)∪B(ˆ mt−1).Therearetwo cases to consider. First, assume that given the equilibrium strategies at ht,kis matched at the end of period t. Then the result in Roth and Vande Vate (1991) implies that k can do weakly better by submitting a truncation. Second, suppose instead that given the equilibrium strategy at ht,kremains unmatched at the end of period t.Thenit is a property of stable mechanisms that the set of agents other than kwho are unmatched is independent of the ROL submitted by k,aslongaskis unmatched. To 12This is relevant in the proof of Lemma 3for 1. Theoretical Economics 17 (2022) Dynamically stable matching 719 see this, let denote the submitted ROLs under σat ht. Furthermore, let coincide with for k∈A(ˆ mt−1)∪B(ˆ mt−1)\{k}.Letmt=νt(A(ˆ mt−1),B(ˆ mt−1),)and mt=νt(A(ˆ mt−1),B(ˆ mt−1),). Assume that mt(k)=mt(k)=k. Toward a contradiction, suppose there exists a∈A(ˆ mt−1)such that mt(a)= a=mt(a).LetA−={a∈ A(ˆ mt−1):mt(a) amt(a)}and B+={b∈B(ˆ mt−1):mt(b) bmt(b)}.Thedecomposition lemma (Roth and Sotomayor (1992)) implies that mt(A−)=mt(A−)=B+,acontradiction. Thus, without loss of generality, kcan submit an empty list in that case. Since the ROL that ksubmits at htis unobserved, in both cases one can then change k’s strategy at htwithout affecting the equilibrium. Lemma 3. In both games, for all tand public history ˆ mt−1, the continuation matching mσ(ˆ mt−1)is individually rational and satisfies condition (D3)inET t(ˆ mt−1). Proof. Individual rationality follows from the ability of the agents to remain single through period Tby always submitting empty ROLs. In 2, condition (D3) follows from the possibility of joint deviations: otherwise, there would be a period s≥tand a pair (a,b)∈A(ˆ mt−1,(mσ r(·))r∈{t,,s−1})∪B(·)that can deviate by submitting lists that only list each other. Any stable mechanism matches (a,b)together. In 1, condition (D3)follows from the properties of deferred acceptance. Suppose there is a period s≥tand apair(a,b)∈A(ˆ mt−1,(mσ r(·))r∈{t,,s−1})∪B(·)that prefer to match with each other over their outcome under (ˆ mt−1,mσ(ˆ mt−1)).Ifmσ s(ˆ mt−1)(a)= a, then this contradicts either that asubmitted a truncation of their true ranking or the stability of the deferred acceptance algorithm with respect to the reported preferences. Suppose then that mσ s(ˆ mt−1)(a)=a. The stability of the outcome of DA with respect to the reported preferences implies that adid not include bin their ROL. Consider the following strategy for a: asubmits ˜ alisting all b∈Bthat are preferred to a’s outcome under mσ(ˆ mt−1).Under this ROL, which includes b, it cannot be that ais unmatched in period s.Otherwise,b would still be matched to mσ s(ˆ mt−1)(b), a contradiction (recall the proof of Lemma 2). Then ais matched at the end of period s,sothatahas a profitable deviation, contradicting the definition of SPNE. A corollary of this is that mσ(ˆ mT−1)satisfies Definition 4for A(ˆ mT−1)∪B(ˆ mT−1). Lemma 4. In 1, for any period tand public history ˆ mt−1, the matching mσ(ˆ mt−1)cannot be improved upon by agents on side Awaiting to be matched. Similarly, in 2, for any period tand public history ˆ mt−1, the matching mσ(ˆ mt−1)∈DT−(t−1)(ET t(ˆ mt−1)). Proof. The proof is similar for both games so I focus on 2.Lett≤T−1denote the largest s≤T−1 such that there exists ˆ ms−1such that mσ(ˆ ms−1)fails either (D1) or (D2) in Definition 6.Letk∈A(ˆ mt−1)∪B(ˆ mt−1)be such that kprefers all matchings in MD(k,ˆ mt−1)over (ˆ mt−1,mσ(ˆ mt−1)). Consider the matching (ˆ mt−1,mt,,mT) that arises when kdeviates and submits an empty ROL and then continues to play the equilibrium strategy. By definition of t,(ms)s≥t+1∈DT−t(ET t+1(ˆ mt−1,mt)). (Note that mσ(ˆ mt−1,mt)=(ms)s≥t+1.) It remains to show that mtsatisfies Definition 5.Towarda 720 Laura Doval Theoretical Economics 17 (2022) contradiction, suppose there exists a pair (a,b)such that mt(a)= aand mt(b)= b,but u(a,b)>u (a,mt(a)) and v(a,b)>v (mt(b),b). Then it must be that the ROLs (a,b) satisfy that either mt(a)abor mt(b)ba. This contradicts Lemma 2:undertruncations, the agents do not switch the order of agents on the other side relative to their true preferences. It follows that mtsatisfies Definition 5, and hence, (ˆ mt−1,mt,,mT)∈ MD(k,ˆ mt−1).Thus,khas a deviation at public history ˆ mt−1, contradicting the definition of SPNE. References Acemoglu, Daron, Georgy Egorov, and Konstantin Sonin (2012), “Dynamics and stability of constitutions, coalitions, and clubs.” American Economic Review, 102, 1446–1476. [691] Adachi, Hiroyuki (2003), “A search model of two-sided matching under nontransferable utility.” Journal of Economic Theory, 113, 182–198. [690] Akbarpour, Mohammad, Shengwu Li, and Shayan Oveis Gharan (2020), “Thickness and information in dynamic matching markets.” Journal of Political Economy, 128, 783–815. [689] Altinok, Ahmet (2019), “Dynamic many-to-one matching.” Available at SSRN 3526522. [689,715] Ambrus, Attila (2006), “Coalitional rationalizability.” The Quarterly Journal of Economics, 121, 903–929. [701] Anderson, Ross, Itai Ashlagi, David Gamarnik, and Yash Kanoria (2015), “A dynamic model of barter exchange.” In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1925–1933, SIAM. [689] Andersson, Tommy, Umut Dur, Sinan Ertemel, Onur Kesten et al. (2018), “Sequential school choice with public and private schools.” [689,690,710] Arnosti, Nick and Peng Shi (2020), “Design of lotteries and wait-lists for affordable housing allocation.” Management Science.[689] Ashlagi, Itai, Maximilien Burq, Patrick Jaillet, and Vahideh Manshadi (2018), “On matching and thickness in heterogeneous dynamic markets.” Available at SSRN 3067596. [689] Baccara, Mariagiovanna, SangMok Lee, and Leeat Yariv (2020), “Optimal dynamic matching.” Theoretical Economics, 15, 1221–1278. [689] Bergemann, Dirk and Philipp Strack (2019), “Progressive participation.” [689,707] Bloch, Francis and David Cantala (2017), “Dynamic assignment of objects to queuing agents.” American Economic Journal: Microeconomics, 9, 88–122. [689] Braun, Sebastian, Nadja Dwenger, and Dorothea Kübler (2010), “Telling the truth may not pay off: An empirical study of centralized university admissions in Germany.” The BE Journal of Economic Analysis & Policy, 10. [712] Theoretical Economics 17 (2022) Dynamically stable matching 721 Burdett, Ken and Melvyn G. Coles (1997), “Marriage and class.” The Quarterly Journal of Economics, 141–168. [690] Chowdhury and Prabal Roy (2004), “Marriage markets with externalities.” Technical report, Indian Statistical Institute, New Delhi, India. [699] Chwe, Michael (1994), “Farsighted coalitional stability.” Journal of Economic theory, 63, 299–325. [690] Damiano, Ettore and Ricky Lam (2005), “Stability in dynamic matching markets.” Games and Economic Behavior, 52, 34–53. [690] Dogan, Battal and M. Bumin Yenmez (2018), “When does an additional stage improve welfare in centralized assignment?” [690] Doval, Laura (2015), “A theory of stability in dynamic matching markets.” Available at http://economics.yale.edu/sites/default/files/doval_jmp.pdf.[690,699] Doval, Laura (2021), “Dynamically stable matching.” arXiv preprint arXiv:1906.11391. [694] Dur, Umut and Onur Kesten (2019), “Sequential versus simultaneous assignment systems and two applications.” Economic Theory, 68, 251–283. [689,690,714] Eeckhout (1999), “Bilateral search and vertical heterogeneity.” International Economic Review, 40, 869–887. [690] Feigenbaum, Itai, Yash Kanoria, Irene Lo, and Jay Sethuraman (2020), “Dynamic matching in school choice: Efficient seat reassignment after late cancellations.” Management Science.[690] Gale, David and Lloyd S. Shapley (1962), “College admissions and the stability of marriage.” American Mathematical Monthly, 9–15. [692,701,715] Gale, David and Marilda Sotomayor (1985), “Some remarks on the stable matching problem.” Discrete Applied Mathematics, 11, 223–232. [717] Garrett, Daniel F. (2016), “Intertemporal price discrimination: Dynamic arrivals and changing values.” American Economic Review, 106, 3275–3299. [689,707] Gershkov, Alex, Benny Moldovanu, and Philipp Strack (2015), “Efficient dynamic allocation with strategic arrivals.” Available at SSRN 2548740. [689,707] Haeringer, Guillaume and Vincent Iehlé (2019), “Gradual college admission.” [690] Harsanyi, John C. (1974), “An equilibrium-point interpretation of stable sets and a proposed alternative definition.” Management Science, 20, 1472–1495. [690] Hassidim, Avinatan, Assaf Romm, and Ran I. Shorrer (2020), “The limits of incentives in economic matching procedures.” Management Science.[714] Kadam, Sangram V. and Maciej H. Kotowski (2018), “Multiperiod matching.” International Economic Review, 59, 1927–1947. [690] 722 Laura Doval Theoretical Economics 17 (2022) Kotowski, Maciej H. (2019), “A perfectly robust approach to multiperiod matching problems.” [690] Kurino, Morimitsu (2009), “Credibility, efficiency and stability: A theory of dynamic matching markets.” Jena economic research papers, JENA. [690] Lagunoff, Roger D. (1994), “A simple noncooperative core story.” Games and Economic Behavior, 7, 54–61. [706,714] Lauermann, Stephan and Georg Nöldeke (2014), “Stable marriages and search frictions.” Journal of Economic Theory, 151, 163–195. [690] Leshno, Jacob (2017), “Dynamic matching in overloaded waiting lists.” [689] Liu, Ce (2018), “Stability in repeated matching markets.” [690] Liu, Qingmin, George J. Mailath, Andrew Postlewaite, and Larry Samuelson (2014), “Stable matching with incomplete information.” Econometrica, 82, 541–587. [701] Ma, Jinpeng (1995), “Stable matchings and rematching-proof equilibria in a two-sided matching market.” Journal of Economic Theory, 66, 352–369. [706] Mai, Tung and Vijay V. Vazirani (2019), “Stability-preserving, incentive-compatible, time-efficient mechanisms for increasing school capacity.” arXiv preprint arXiv:1904.04431.[690] Mauleon, Ana, Vincent J. Vannetelbosch, and Wouter Vergote (2011), “Von Neumann– Morgenstern farsightedly stable sets in two-sided matching.” Theoretical Economics,6, 499–521. [690] McVitie, David G. and Leslie B. Wilson (1970), “Stable marriage assignment for unequal sets.” BIT Numerical Mathematics, 10, 295–309. [703,704] Narita, Yusuke (2018), “Match or mismatch? Learning and inertia in school choice.” [690, 714] Neilson, Christopher, Adam Kapor, and Mohit Karnani (2020), “Aftermarket frictions and the cost of off-platform options in centralized assignment mechanisms.” [690,714] Parkes, David C. (2007), “Online mechanisms.” In Algorithmic Game Theory (Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani, eds.). Cambridge University Press. [711] Pathak, Parag (2016), “What really matters in designing school choice mechanisms.” [710] Pycia, Marek and M. Bumin Yenmez (2017), “Matching with externalities.” [688] Ray, Debraj and Rajiv Vohra (1997), “Equilibrium binding agreements.” Journal of Economic theory, 73, 30–78. [691,700] Ray, Debraj and Rajiv Vohra (2015), “The farsighted stable set.” Econometrica, 83, 977– 1011. [690] Theoretical Economics 17 (2022) Dynamically stable matching 723 Richter, Donald K. (1974), “The core of a public goods economy.” International Economic Review, 131–142. [688] Rosenthal, Robert W. (1971), “External economies and cores.” Journal of Economic Theory, 3, 182–188. [688] Rostek, Marzena J. and Nathan Yoder (2017), “Matching with multilateral contracts.” [688] Roth, Alvin E. (1984), “The evolution of the labor market for medical interns and residents: A case study in game theory.” The Journal of Political Economy, 92. [689,704,707] Roth, Alvin E. (1991), “A natural experiment in the organization of entry-level labor markets: Regional markets for new physicians and surgeons in the United Kingdom.” American Economic Review, 415–440. [690] Roth, Alvin E. and Marilda A. Oliveira Sotomayor (1992), Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press. [705,706,707,719] Roth, Alvin E. and John H. Vande Vate (1991), “Incentives in two-sided matching with random stable mechanisms.” Economic theory, 1, 31–44. [689,713,718] Sasaki, Hiroo and Manabu Toda (1996), “Two-sided matching problems with externalities.” Journal of Economic Theory, 70, 93–108. [688,689,690,701] Schummer, James (2015), “Influencing waiting lists.” Technical report, Kellogg School of Management. [689] Shapley, Lloyd S. and Martin Shubik (1969), “On the core of an economic system with externalities.” The American Economic Review, 59, 678–684. [688] Shimer, Robert and Lones Smith (2000), “Assortative matching and search.” Econometrica, 68, 343–369. [690] Shin, Sungwhee and Sang-Chul Suh (1996), “A mechanism implementing the stable rule in marriage problems.” Economics Letters, 51, 185–189. [706] Shorrer, Ran I. and Sándor Sóvágó (2018), “Obvious mistakes in a strategically simple college admissions environment: Causes and consequences.” Available at SSRN 2993538. [714] Sönmez, Tayfun (1997), “Games of manipulation in marriage problems.” Games and Economic Behavior, 20, 169–176. [706] Thakral, Neil (2019), “Matching with stochastic arrival.” AEA Papers and Proceedings, 109, 209–212. [689] Ünver, M. Utku (2010), “Dynamic kidney exchange.” The Review of Economic Studies, 77, 372–414. [689] Westkamp, Alexander (2013), “An analysis of the German university admissions system.” Economic Theory, 53, 561–589. [689,690,711,712,714] 724 Laura Doval Theoretical Economics 17 (2022) Co-editor Ran Spiegler handled this manuscript. Manuscript received 6 March, 2020; final version accepted 12 June, 2021; available online 15 June, 2021.