Deadlines and Matching

Finance and Economics Discussion Series Divisions of Research & Statistics and Monetary Affairs Federal Reserve Board, Washington, D.C. Deadlines and Matching Garth Baughman 2016-014 Please cite this paper as: Baughman, Garth (2016). “Deadlines and Matching,” Finance and Economics Discussion Series 2016-014. Washington: Board of Governors of the Federal Reserve System, http://dx.doi.org/10.17016/FEDS.2016.014. NOTE: Staff working papers in the Finance and Economics Discussion Series (FEDS) are preliminary materials circulated to stimulate discussion and critical comment. The analysis and conclusions set forth are those of the authors and do not indicate concurrence by other members of the research staff or the Board of Governors. References in publications to the Finance and Economics Discussion Series (other than acknowledgement) should be cleared with the author(s) to protect the tentative character of these papers.

DEADLINES AND MATCHING GARTH BAUGHMAN BOARD OF GOVERNORS OF THE FEDERAL RESERVE SYSTEM Abstract Deadlines and fixed end dates are pervasive in matching markets including school choice, the market for new graduates, and even financial markets such as the market for federal funds. Deadlines drive fundamental non-stationarity and complexity in behavior, generating significant departures from the steady-state equilibria usually studied in the search and matching literature. I consider a two-sided matching market with search frictions where vertically differentiated agents attempt to form bilateral matches before a deadline. I give conditions for existence and uniqueness of equilibria, and show that all equilibria exhibit an “anticipation effect” where less attractive agents become increasingly choosy over time, preferring to wait for the opportunity to match with attractive agents who, in turn, become less selective as the deadline approaches. When payoffs accrue after the deadline, or agents do not discount, a sharp characterization is available: at any point in time, the market is segmented into a first class of matching agents and a second class of waiting agents. This points to a different interpretation of unraveling observed in some markets and provides a benchmark for other studies of non-stationary matching. A simple intervention – a small participation cost – can dramatically improve efficiency. Date: January 18, 2016. IwouldliketoacknowledgeKennethBurdett,AndrewClausen,RudyHenkel,PhilipKircher,TymofiyMylovanov,MalleshPai,AndrewPostlewaite,GuillaumeRoger,andLonesSmithalongwithseminarparticipants at Edinburgh University, New York University, and the University of Pennsylvania for their comments. The views expressed here are those of the authors and do not necessarily reflect the views of other members of the research staff, the Board of Governors of the Federal Reserve System, or the Federal Reserve System. 1

2 GARTH BAUGHMAN 1. Introduction In this paper, I analyze the impact of a deadline, a fixed end date when the market closes, on equilibrium dynamics in a canonical model of frictional matching. In the model, search frictions limit the rate at which vertically differentiated agents meet potential partners. When two agents meet, they each learn the type of their prospective partner, and hence their payoff from matching. If both agree, the pair match and leave the market. If not, they continue searching. These exits cause the distribution of available partners to evolve over time. At the deadline, unmatched agents receive some outside option and the game ends. I establish existence of equilibria, provide a condition ensuring uniqueness, and characterize behavior. Many matching markets feature a deadline. In education, students must find a seat before the start of the school year. In the market for entry level professionals, new graduates want to find a job before graduation. In the market for federal funds, banks must meet their reserve requirements before the monitoring deadline every evening. When present, deadlines and the consequent cyclical nature of these markets allows for the implementation ofcentralized,staticmechanisms. Prominentexamplesincludethemedicalresidentmatching programandtheschoolchoicemechanismsinNewYorkandBoston, inadditiontosomewhat less structured systems like the signaling mechanism provided by the American Economic Association’s JOE program.1 The design and analysis of such systems derive from the now prominent literature on centralized matching, which studies what may obtain when agents come together to form matches through a common marketplace or clearinghouse.2 A dual literature, usually termed search and matching, studies incentives and equilibria when agents must seek out matches in a decentralized fashion, lacking ready access to relevant partners. This study applies the decentralized paradigm to markets with deadlines, providing a positive theory of dynamic 1See Roth and Peranson (1999) on medical residents; Abdulkadiro˘glu et al. (2005), Abdulkadiro˘glu et al. (2006), and Pathak and S¨onmez (2008) on school choice; and Coles et al. (2010) on the market for new economists. 2The authoritative introduction being Roth et al. (1992); see Sotomayor and O¨zak (2012) for a more recent and very concise summary.

DEADLINES AND MATCHING 3 behavior in the absence of clearinghouses – a model of the status quo ante that one can compare to the successes of centralization. Consider a decision maker facing a simple search decision problem with a deadline after whichcontinuedsearchisimpossible. Overtime,thedecisionmakerencountersopportunities that she can either accept, ending search, or reject, giving up the opportunity in hopes of finding a better one in the future. As the deadline approaches, she has less time remaining to search, and therefore will encounter fewer opportunities in the future. This leads her to be less selective over time. If the distribution worsens as time goes on, making good opportunities rarer, this should further drive her to adopt a declining reservation level, and also to accept early opportunities. Finally, if she is impatient, with a positive discount rate, pure preference induces her to accept early opportunities. This intuitive strategy – where one both accepts some selection of early opportunities and becomes less choosy over time – holds exactly for the most attractive agents in a matching market with deadline. Everyone will always accept the most attractive type, so the most attractive agents need not concern themselves with the possibility of being rejected by a potential partner; they exactly face the simple decision problem outlined above. Less attractive agents, however, are not so lucky. They may be refused by desirable partners, and so must formulate their strategies in light of the acceptance decisions of others. In a steady state version of the model, Burdett and Coles (1997) show that matching sets partition agents into a finite number of classes, disjoint sets of mutually acceptable types.3 When there is a deadline, one might conjecture that some flavor of a class system persists. Perhaps some finite number of temporary, time-varying classes obtain. Indeed, a first class exists by exactly the same logic as in steady state – once one becomes acceptable to the highest type, one is universally acceptable, so one chooses the same strategy as the highest type. But the dynamics in the model destroy any hope of summarizing less attractive agents so simply. 3This result was developed across a series of papers each with subtly differing assumptions including Bloch and Ryder (2000), Burdett and Coles (1997), Chade (2001), Eeckhout (1999), andMcNamara and Collins (1990). The framework of Burdett and Coles (1997) is the most similar to mine.

4 GARTH BAUGHMAN The complication derives from an “anticipation effect.” When agents join the first class, their opportunity sets jump discretely. As different agents anticipate that they will receive this dramatic improvement in opportunities at different times, they each follow different strategies, destroying the class system. When impatient, agents become increasingly choosy as they get close to joining the first class, further complicating behavior. If there is no discounting, however, the behavior of agents outside the first is easily described; they do not match at all, preferring to wait for the opportunity to match with high types later. At each point in time, the market segments into a first class of matching agents and a second class of waiting agents. This partitioning has a number of implications. The first concerns sorting. In the unravelling literature, agents rush the market. Early matching prevents sorting. Here, because of search frictions, early matching improves efficiency and sorting. The second implication is that a small flow cost of search is Pareto improving, as it drives low types out of the market until it is their time to match. This eliminates the search externality low types exert on high types, and all meetings result in a match. High types obviously appreciate this, but low types do not mind as a higher match probability compensates low types for a lower quality of partner, in expectation. The next section considers some important predecessors in the literature. The following section lays out the basic framework. Section 4 discusses the case of patient agents and is followed by more general results in section 5. Section 6 considers the effect of costs on search behavior for patient agents. The paper then concludes with some discussion. 2. Context in the Literature While a detailed account of the evolution of the literature on frictional matching between heterogenous agents can be found in Smith (2011), the current study is a direct extension of Burdett and Coles (1997) as I impose a deadline on their steady state model. This simple change generates substantially different behavior than previously analyzed in the literature;

DEADLINES AND MATCHING 5 specifically, almost no work considers non-stationary dynamics in a rich search and matching model. Early predecessors of my paper studied search-theoretic decision problems in a changing world. These include Van Den Berg (1990) and Smith (1999).4 These studies hint at the anticipation effect – that one should be willing to wait for promising opportunities in the future – but these are decision theoretic studies, and the strong equilibrium implications of anticipation are obscured. Threeotherstudiesarecloselyrelatedtomine. Thefirst, AfonsoandLagos(2015), considers a model of decentralized trade before a deadline, and is applied to the market for federal funds. In their model, all agents hold some quantity of federal funds and search for a partner withwhomtotrade, afterwhichtheycontinuetosearchforprofitabletradesuntiladeadline. They obtain the remarkable result that, if agents share concave values over final holdings, all meetings result in trade. In that they characterize the case of repeated trade with transferable utility, while the current study considers nontransferable utility with only a single trade – partnership formation – Afonso and Lagos (2012) provides a valuable counterpoint to the results developed below. The second predecessor, Damiano et al. (2005), considers a model of partnership formation with nontransferable utility as in the current study, but differs in that, instead of randomly encountering partners over time, agents encounter one another over a finite number of discrete rounds. This leads to dramatically different results when search costs are incorporated, and so I leave further discussion of this paper to section 6.5 Finally, in a working paper first presented in 1992, Smith (2009) considers the effect of temporary matches in a non-stationary, infinite horizon version of the model.6 There, something similar to a first class obtains driven not by a deadline but instead by population 4To the author’s knowledge, the first paper which describes the Bellman equation faced by a decision maker in a model of non-stationary search was Mortensen (1986), but he immediately specializes to the stationary case. 5This discrete time matching framework has also been considered in the theoretical biology literature, see Alpern and Reyniers (2005) for results which expand upon the Damiano et al. (2005) framework, and summarize previous work in that other literature. 6The author was unaware of this ambitious work when formulating the current study.

6 GARTH BAUGHMAN dynamics. Moreover, the option to dissolve a match and search again at the center of that study precludes the anticipation effect driving behavior in the current environment.7 Besides these close predecessors, the search and matching literature related to this study can be broken into two strands. One considers non-trivial matching decisions, but in steady state, and the other explores non-stationary dynamics, but without meaningful matching decisions. The non-stationary literature is concerned primarily with macroeconomic fluctuations, and employs search frictions as a means of explaining labor market dynamics.8 In order to keep the state space small, heterogeneity is either completely idiosyncratic, or absent. In steady state, there is a large literature addressing equilibrium matching behavior. Prominent examples include Burdett and Coles (1997) and Shimer and Smith (2000). The restriction to steady state allows for a careful consideration of the matching decisions of heterogeneous agents, but that restriction precludes analysis of the effect of a changing environment on equilibrium interactions at the heart of the current study. Beyond the close predecessors mentioned above, there are but a handful of other advances towards reconciling non-stationarity and heterogeneity. Rudanko (2011) and Menzio and Shi (2011) assume agents can direct their search, only meeting the partners for whom they actively search. This, coupled with a free entry condition, dramatically simplifies the firms’ side of the market, allowing for a clean characterization of behavior. Coles and Mortensen (2012), Moscarini and Postel-Vinay (2013), and Robin (2011) take a different tack, each showing that a different restriction on the contracting space can simplify the movements of individuals across jobs, affording sharp results. Instead, the current study makes a stark assumption on the nature of non-stationarity – the deadline – and focuses on matching decisions exclusively, eliminating the complications of contracting by instead assuming nontransferable utility. This allows the current study to offer a clean description of matching 7Onatechnicalnote,Smith(2009)considersquadraticmatchinginsteadofthelinearmatchinginthispaper which induces a sort of strategic separability which eliminates the matching externality discussed below. Thisleads touniqueness ofthe firstclass, which isnot generally trueunder thelinear technologyconsidered in the current study. 8Rogerson et al. (2005) and Rogerson and Shimer (2011) survey the literature.

DEADLINES AND MATCHING 7 behavior, highlighting the equilibrium forces underlying non-stationary matching problems more broadly. 3. The Framework The framework is a non-stationary extension of Burdett and Coles (1997). Two groups of agents, say workers and firms, attempt to find a partner from the other side. At time zero, the market is populated with equal masses of workers and firms measuring size N . 0 Instead of explicitly modeling the process by which the two sides evaluate each other, assume that individuals can be characterized by a fixed real number which, following Burdett and Coles (1997), is termed pizazz. This is a vertically differentiated market. Agents’ pizazz are initially distributed according to G0(z) with support X = [x,x] ⊂ (0,∞). Time flows continuously from zero up to T > 0. During this time, agents search for partners from the other group. Each agent encounters a potential partner at a constant rate α > 0.9 Upon meeting, two agents observe each other’s pizazz and simultaneously decide whether or not to propose a match. For a match to occur, both agents in a meet must propose. Utility is non-transferable; the value to an agent with pizazz y of matching with an agent of pizazz x is exactly equal to x, irrespective of y.10 Once matched, agents leave the market (there is no recall or divorce). If, uponreachingtimeT, anagentremainsunmatched, theyreceiveutilityfromanoutside option, the value of which is 0. That all agents share a uniform outside option is not without loss ofgenerality andrepresents asignificant simplification. The strongest implication is that all agents prefer matching with even the least attractive agent to taking the outside option. 9Which one could rationalize with a constant returns to scale meeting function. 10It is not clear whether this is a restriction above and beyond the requirement of identical time-valued VNM preferences. Indeed the analysis goes through equally well if agents receive a general payoff f(x,y) so long as this is multiplicatively separable, increasing, and strictly positive. Additive separability may also be accommodated when agents are patient and do not discount. Eeckhout (1999) and Smith (2006) allow for type-dependent preferences and show that all that is required for a class system to obtain in a stationary framework is identical static VNM preferences across agents, which implicitly allows different discountfactors. Thispaperwillnotallowfordifferencesindiscountrates,andsoassumesidenticalcardinal preferences from the outset.

8 GARTH BAUGHMAN In addition to a declining probability of meeting (because time is running out), agents may be impatient and discount the future at a rate r ≥ 0. Suppose that agents flow into the market at a rate ζ(t) ≥ 0 which is bounded above by ¯ some ζ and that the distribution of the inflowing agents is H(z,t) with support contained in X. Let G(z,t) be the distribution of pizazz at time t (reflecting changes due to both inflows and outflows). Further, write N(t) for the mass of agents at time t so that N(t)G(z,t) is the mass of agents of pizazz less than z at time t. Since an agent x may not receive a proposal from every meeting, write α(x,t) for the (possibly time varying) arrival rate of proposals and G (z,t) for the distribution of agents x who would propose to x upon meeting. Write Ω(x,t) = {y|y is willing to propose to x} and A(x,t) = {y|x is willing to propose to y} and call these the opportunity and acceptance sets, respectively. With the basic elements in hand, write U(x,t) as the (Bellman) value at time t for an agent of pizazz x. Focus on symmetric cutoff strategies where agents accept any partner with pizazz greater than or equal to his or her current value.11 Standard arguments then yield the following Hamilton-Jacobi-Bellman (HJB) equation for the agent’s reservation value.12 (cid:90) x ˙ U(x,t) = rU(x,t)−α(x,t) (z −U(x,t))G (dz,t) x U(x,t) with boundary condition U(x,T) = 0. This states that, as agents wait for a match, the change in their reservation value is given by the asset value of their future opportunities, less the excess value of current matches which did not materialize. Integration by parts gives a more convenient formulation: (cid:90) x ˙ (1) U(x,t) = rU(x,t)−α(x,t) (1−G (z,t))dz. x U(x,t) 11Cutoff strategies are the only weakly undominated ones, and restricting attention to cutoff strategies removespathologicalequilibriasuchas‘everyonealwaysrejects.’ Moreover,itisastrongsymmetryassumption – all x type firms play the same strategy as all x type workers. Symmetry within a group is not binding. While I prove existence of equilibria with symmetry across groups, there may exist asymmetric equilibria even with symmetric initial data, but this is left for future work. 12ThisequationwasfirstderivedinsearchtheoryworkbyMortensen(1986). Hisanalysiswaslaterexpanded to consider more general kinds of time variation by Van Den Berg (1990).

DEADLINES AND MATCHING 9 Given that agents use cutoff strategies, we have the following. Remark 1. Since x will accept any y ≥ U(x,t) we have A(x,t) = {y|y ≥ U(x,t)}, Ω(x,t) = (cid:82) {y|x ≥ U(y,t)}, α(x,t) = α G(dz,t) and Ω(x,t) (cid:82) 1{y ≤ z}G(dy,t) Ω(x,t) G (z,t) = . x (cid:82) G(dy,t) Ω(x,t) (cid:82) (cid:82) This allows one to write α(x,t) f(z)G (dz,t) = α f(z)G(dz,t), for any integrable f, x Ω(x,t) which will be used extensively. In particular, it implies that one’s decision problem depends only on the time path of one’s opportunity set. With the individual’s problem defined, the last step in the setup of the model is to derive the dynamic for G. Write θ(x,t) for the probability that a meeting will result in a match for an agent with pizazz x, (cid:90) θ(x,t) = G(dy,t), A(x,t)∩Ω(x,t) so that the exit rate for an agent of pizazz x is αθ(x,t). Supposing, momentarily, that G(z,t) and H(z,t) possess densities g(z,t) and h(z,t), the number of agents with pizazz z in the market at time t is n(z,t) = N(t)g(z,t). The number of agents with pizazz z leaving the market is αg(z,t)θ(z,t)N(t) and the number entering is ζ(t)h(z,t). This gives n˙(z,t) = −αθ(z,t)g(z,t)N(t) + ζ(t)h(z,t), and, after integrating, N ˙ (t) = −αN(t)E(θ(x,t)) + ζ(t). Writing η(t) = ζ(t)/N(t), and noting that g˙ = [n˙N −nN ˙ ]/N2, one observes g˙(z,t) = αg(z,t)[E(θ(x))−θ(z)]−η(t)[g(z,t)−h(z,t)]. This can be read as saying that, if a given agent’s probability of being matched is greater than average, their relative numbers tend to decline (the first term) unless the entrance of new agents more than compensates (the second term). Integrating again gives the dynamic

10 GARTH BAUGHMAN for G.13 (2) G ˙ (z,t) = αG(z,t)[E(θ(x))−E(θ(x)|x ≤ z)]−η(t)[G(z,t)−H(z,t)]. With the framework in hand, consider now the case where agents are patient. 4. Patient Agents In our motivating applications, agents receive their payoff after the market closes, so it is appropriate to assume no discounting, r = 0. For example, an academic economist does not start working until several months after the end of the search process, and universities do not receive services until that time. Moreover, the case of r = 0 strongly highlights the anticipation effect and produces a tractable equilibrium characterization: highly attractive agents, following the intuitive strategy alluded to in the introduction, become less selective as time ticks on while the rest prefer not to match early in the market, instead waiting until highly attractive agents will accept them. Since this case is relatively uncomplicated, I keep the analysis in this section informal, leaving most formal results for the next section. The first step in the characterization is to notice that when there is no discounting, reservation values can never rise over time. If there is a high value available in the future, patient agents will simply wait for it rather than accepting less attractive options today. Lemma 1. U(x,t) is weakly decreasing in t when r = 0. Proof. Recall equation (1) and substitute r = 0, (cid:90) x ˙ U(x,t) = −α(x,t) (1−G (z,t))dz ≤ 0. x U(x,t) (cid:3) Next, a bound on the value of the highest type obtains. Suppose x were alone in a market exclusively populated with the most attractive agents who are all willing to match. The 13Which holds whether or not G and H possess densities, the above derivation being only for the purposes of exposition.

DEADLINES AND MATCHING 11 value in this market is simply equal to the probability of matching (1 − exp{−α(T − t)}) times the value of matching with the highest type (x). This rosy scenario gives a bound on the reservation value of the highest type: ˆ U(x,t) < U(t) ≡ x(1−exp{−α(T −t)}). This implies that, at time zero, at least all agents with x ≥ x(1−exp{−αT}) are acceptable to x. Further, all agents become acceptable to x at some point (because x > 0 = U(x,T)). Define the set acceptable to x as the first class: F(t) = A(x) = {x ≥ U(x,t)}. The time when one joins the first class is important. Define these hitting times as τ(x) = min{t ∈ [0,T]|U(x,t) ≤ x}, so that τ(x) is the time when x becomes acceptable to x (and they remain acceptable because of Lemma 1). Being acceptable to x has an important implication. If t ≥ τ(x), so that x is acceptable to x, then U(x,t) = U(x,t): If one is acceptable to x for all future time, one is acceptable to all other agents into the future.14 Then, since values depend only on opportunity sets, one’s expected value from search is exactly the same as x. This has a strong equilibrium implication: no one outside the first class matches. At τ(x), x gets a partner of his or her own pizazz in expectation: U(x,τ(x)) = x because U(x,τ(x)) = U(x,τ(x)) = x. Moreover, U(x,t) ≥ x for t < τ(x) by Lemma 1. This is the anticipation effect at work. Agents with low pizazz expect to join the first class eventually, Finally, it can also be shown that U(x,t) ≤ x. That is, one is always willing to accept a partner of equal pizazz.15 These, then, give U(x,t) = x for t < τ(x), and all behavior is driven by the value of the highest type. This is summarized in the following proposition and illustrated in figure 1. Proposition 1. When r = 0, U(x,t) wholly determines the equilibrium as 14Which assumes monotone reservation values, proved in by Corollary 1 below 15Which is proved formally in Corollary 2 below.

12 GARTH BAUGHMAN x¯ U(x,t) U(x ,t) 1 x 1 U(x ,t) 2 x 2 x t = 0 t = T Figure 1. Reservation Values when r = 0    x if t < τ(x) U(x,t) =  U(x,t) if t ≥ τ(x).  ¯ Suppress time arguments and write U = U(x,t), the dynamic for G simplifies to    αG(z)[1−G(U ¯ )]2 −η(t)(G(z)−H(z)) if z < U ¯ ˙ (3) G(z) =  αG(U ¯ )[1−G(U ¯ )][1−G(z)]−η(t)(G(z)−H(z)) if z ≥ U ¯ .  Proof. The specification of U derives from the discussion above. The relatively explicit form ˙ for G derives from the fact that θ(x,t), the probability of a meeting resulting in a match, collapses to a step function:16 16There are other possible dynamics if G contains atoms. In this case, the agents with positive mass are indifferent between matching with each other or not before τ(x). This dynamic assumes that they do not. Thisformwoulddissolveotherwise. Indeed,ifthereweresomefinitesetofpizazzlevels,thentheanticipation result dissolves to some extent, as one equilibrium would be for all agents to match with equal pizazz agents before joining the first class. This is resolved by the introduction of avoidable search costs, which induce second class agents to stay home as described below.

DEADLINES AND MATCHING 13    (1−G(U ¯ )) if x ≥ U ¯ θ(x) =  0 if x < U ¯  (cid:3) To reiterate, low types wait, with reservation value equal to their own type, until they become acceptable to the highest type, after which they share a value function with the highest type. The notion that patient agents should only match with their own type is perhaps not surprising. If one were to consider the limit of the Burdett-Coles economy as the discount rate goes to zero, the classes shrink to the point where each type is in their own class. That the introduction of a deadline leads to growing desperation is also unsurprising. The unobvious contribution is that that the interaction of these two considerations leads to equilibrium behavior that admits such a straightforward summary. Straightforward, however, should not be mistaken for simple, as the reservation value for x encodes all of the subtleties of an evolving distribution, weighing off the value of matching today against the possibility of remaining unmatched or facing poor opportunities in the future. Because of the clear characterization available when agents are patient, another important result obtains: Proposition 2 (Uniqueness). If there is no entry (η = 0), agents are patient (r = 0), and G0 is continuous, then the equilibrium is unique. The proof is relegated to the appendix, but derives mostly from a careful consideration of the dynamics of the distribution in light of the equilibrium characterization from Proposition 1. Briefly, if one increases the initial reservation value, high types filter out for some period before the reservation falls back to the original level. This leads to a relatively flat path in the future. Hence, a high initial value leads to a high terminal value – only one path can satisfy the boundary condition. In the context of the job market, that the best candidates match earliest fits common experience, is alluded to in Roth and Xing (1997) in the context of the market for clinical

14 GARTH BAUGHMAN psychologists, and is a model prediction in Damiano et al. (2005) (when there are no costs) and Burdett and Coles (1997) (because higher agents are in larger classes). That low pizazz agents have no strict incentive to match early in the market reflects optimal waiting. At τ(x), the fact that many high type agents may have left is irrelevant. U(x,t) hits x exactly when the value of being in the first class equals x. The (possibly small) probability of matching with very attractive agents offsets the probability of only meeting agents without much pizazz, or having no future meetings at all. 5. General Results This section provides results concerning existence and characterization of equilibria for any discount rate r ≥ 0. In the job market for entry-level professionals, one might think of r > 0 as pure impatience, wanting to know sooner rather than later. Alternatively, r might represent the flow probability of a tragic event – the death of a relative, say – which would cause an agent to quit searching and abandon the market. One has a preference for securing an early match because it resolves this risk. When r > 0, the model exhibits rich behavior. But, before exploring this, note that behavior in the presence of discounting limits to the simpler behavior described above as r → 0. Proposition 3. As r → 0, the discounting equilibrium converges to the no-discounting equilibrium. The complication when r > 0 derives from early matching among low pizazz agents. But as r → 0, this early matching dissolves, and so even if agents are impatient, so long as the duration of the market is short and matching rates are high, early matching has little impact on equilibrium. Turning now to existence, given the focus on cutoff strategies, an equilibrium is any pair U,G which simultaneously solve (1), the Bellman equation, and (2), the differential equation for G, subject to U(x,T) = 0 and G(z,0) = G0(z). No restrictions are required on the initial distributionofpizazzinordertoobtainexistence. Thisderivesfromthefactthatequilibrium is not required to exist in steady state; the only requirement is that agents correctly predict

DEADLINES AND MATCHING 15 the time path of the distribution of pizazz when making matching decisions, and that these matching decisions generate the predicted time path. All omitted proofs can be found in the appendix. Proposition 4 (Existence). There exists an equilibrium for any r ≥ 0. The proof is closely related to that in Smith (2006) with the exception that one instead solves for a whole time path for each object. This leads to significant alteration of his “Fundamental Matching Lemma” which instead relies on arguments from the theory of Banach ODE. When agents discount, expected present values can rise or fall over time – Lemma 1 does not hold. Specifically, the reservation value of the highest type can rise over time if the distribution improves sufficiently. This can occur either because high types enter or because low types match and exit. Hence, an agent who is acceptable to the highest type at a point in time need not be in the future, and so need not share the highest type’s reservation. As in thecaseofr = 0, equilibriumrevolvesaroundtheexistenceofafirstclassofagentswhoshare the same reservation. Now, however, the first class does not consist of those acceptable to x at a point in time. Instead, say an agent is in the first class if they are universally acceptable now and forever. That is: Definition. Let F(t) = {x|∀s ≥ t,Ω(x,s) = X}, and call this set the First Class. Before we can characterize the first class and the behavior of first class agents, some intermediate results are required. The first states that higher types have more opportunities, which follows from cutoff strategies. Lemma 2 (Monotone Opportunity Sets). If x ≤ x then Ω(x ,t) ⊆ Ω(x ,t), and α(x ,t) ≤ 1 2 1 2 1 α(x ,t) for all t. 2 This observation yields another intermediate result towards characterizing the first class. Because opportunity sets are increasing in type, so are reservation values.

16 GARTH BAUGHMAN Corollary 1 (MonotoneValues). Forallt, U(x,t)isincreasinginx, andΩ(x,t)isconnected. Given monotone values, a simple upper bound obtains, yielding the intuitive result that agents are always willing to accept their equals: Corollary 2. U(x,t) ≤ x for all x,t. Proof. If an agent, x, has a value higher than his own pizazz, some other agent with higher pizazz y > x must be willing to match with him (if not today then at some point in the future). Butthatwouldimplyx ≥ U(y,t) ≥ U(x,t). Discountingthisobservationbackwards yields the result. (cid:3) From these points one notices what is a general property of models with non-transferable utility and common preferences. Remark 2. The model delivers Positive Assortative Matching at each point in time in the set-valued sense of Shimer and Smith (2000): the upper and lower bounds on the matching set are weakly increasing everywhere. Because of monotonicity in opportunity sets, the time when one is universally acceptable going forward is exactly the same as the time when one is acceptable to the highest type going forward. This allows for the first class to be formulated in a manner similar to the last section, but allowing for the possibility of non-monotonicity. One does not join the first class immediately upon becoming acceptable to the highest type. Instead, one joins the first class when one becomes acceptable to the highest type forever. Remark 3. F(t) = {x|x ≥ sup U(x,s)} by Lemma 2. s≥t Not only is one always acceptable to one’s equal, the assumption that U(x,T) = 0 implies that every agent is eventually universally acceptable. As in the no discounting case, all agents eventually join the first class. Lemma 3. For every agent, x, there exists τ(x) < T with τ(x) = inf{t|x ∈ F(t)}.

DEADLINES AND MATCHING 17 Proof. At time T, everyone is willing to match with everyone else because x > 0 = U(x,T). That there exists ε > 0 such that the same holds for all t > T −ε follows from boundedness ˙ of U. And, as one’s value depends only on the future path of one’s opportunity set, if Ω(x,t) = X = Ω(x,t) for all t ≥ τ(x), then U(x,t) = U(x,t) for all t ≥ τ(x). But τ(x) is precisely the moment when x joins Ω(x,t). Hence, it is the precise time when x = U(x,t). Thus, U(x,τ(x)) = x. (cid:3) These all together complete the description of the first class. The first class consists exactly of those who are permanently acceptable to the highest type, and all agents join the first class before the deadline. This leads to an analogue of Proposition 1 for the case of discounting. Lemma 4 (First Class Values). All first class agents share the same value: If t ≥ τ(x), U(x,t) = U(x,t) and, specifically, U(x,τ(x)) = x. Proof. That U(x,t) = U(x,t) for t ≥ τ(x) follows from simple inspection of the Bellman equation given that G (·,t) = G(·,t) = G (·,t) and α(x,t) = α = α(x,t). And then, that x x¯ U(x,τ(x)) = x follows from Remark 3. (cid:3) The intuition is the same as in the case of no discounting. Once one has joined the first class, one is universally acceptable going forward, by definition. One’s problem is wholly defined by the time path of one’s opportunity set. If two agents share the same opportunity set going forward, as they have the same preferences, they must make the same decisions and have the same value. Since all agents are eventually universally acceptable, they eventually all share the same value. Moreover, agents smoothly filter into the first class as the deadline approaches and the highest type becomes less and less selective. The fact that all agents eventually share a value function dramatically simplifies the analysis. Note that it is here where the joint assumptions of common preferences and a common outsideoptiontrulybind. Ifoneweretodispensewitheitherofthese, thissharpresultwould dissolve. Indeed, even with these, equilibrium still fails to admit any simple representation with some finite number of classes:

18 GARTH BAUGHMAN Remark 4. There do not exist persistent coincidences of matching sets outside the first class. Second class agents become increasingly selective before they join the first class: ˙ lim U(x,t) = rx. t(cid:37)τ(x) Because different agents expect to be able to get their own pizazz at some point in the future, there can be no persistent coincidence of matching sets for different pizazz levels with τ(x) > 0. Indeed, the only class in the sense of Burdett and Coles (1997) consists of exactly those agents with τ(x) = 0. If x has τ(x) = 0, then x expects to be able to match with all agents at any point in the future. Hence, their problem is identical to that of x. These agents all share the same value, U(x,t), across the whole time path; share the same matching set; and are always willing to match with each other. But, unless all agents fall into this class, one can not capture equilibrium behavior with any finite set of reservation values. One might infer from the proof of Lemma 3 that low pizazz agents join the first class only ε-time before T. This is not the case as one can see from a bound on the reservation value of the highest type. Lemma 5. α ˆ U(x,t) ≤ U(x,t) = x(1−exp{−(r+α)(T −t)}), r+α and so (cid:18) (cid:19) 1 (cid:104) x (cid:16) r(cid:17)(cid:105) τ(x) ≤ τˆ(x) = T + log 1− 1+ . r+α x α Proof. The bound on U derives from considering the value obtained if x were in a market ˙ ˆ ˆ ˆ with only other x pizazz agents: solve U(x,t) = (r+α)U(x,t)−αx, with U(x,T) = 0. The bound on τ(x) comes from solving U ˆ (x,τˆ(x)) = x for τˆ(x). (cid:3) This implies that the first class consists of at least all agents with τˆ(x) = 0, those agents ˆ with x ≥ U(x,0). Moreover, one can say (independent of T) that all agents are in the first class from time zero whenever x r < 1+ . x α

DEADLINES AND MATCHING 19 For matching not to be universal, the ratio between the highest and lowest pizazz levels can not be too tight compared to the matching friction, as measured by r/α. As mentioned in Remark 4, reservations are increasing for agents just before they enter the first class. And, since τ(x) is continuous in x, agents who expect to join the first class near time zero have increasing reservations from the very beginning. Hence, lower agents have decreasing matching opportunities before they enter the first class as more attractive agents become increasingly selective before they join the first class. This, on the one hand, tends to drag down less attractive agents’ reservations as their early matching opportunities dry up. On the other hand, as time goes on, agents move closer to joining the first class, which pushes up reservations. An integral of U makes this clear: Remark 5. If one writes y(x,t) = sup{y ∈ Ω(x,t)}, then Ω(x,t) = [x,y(x,t)] and    (cid:90) τ(x) (cid:90) y(x,s)  (4) U ˙ (x,t) = rxe−r(τ(x)−t)+α e−r(s−t) (G(y(x,s))−G(z,s))dzds   (cid:124) (cid:123)(cid:122) (cid:125)  t U(x,s)  A (cid:124) (cid:123)(cid:122) (cid:125) B (cid:90) y(x,t) −α (G(y(x,t))−G(z,t))dz U(x,t) (cid:124) (cid:123)(cid:122) (cid:125) C The expression derives from substituting U(x,τ(x)) = x into an integral of the Bellman ˙ equation and then substituting the result into the definition of U. The first term, A, is the discounted contribution of the expectation that x will join the first class at time τ(x). The second, B, is the discounted contribution of future excess value of matching opportunities to current utility. The last, C, is the current excess match value. So, the change in reservation is given by the asset value of not matching, r times A plus B, less the expected value of the missed opportunity today, C. This is illustrated in Figure 2. Suppose there is some agent x with τ(x) > 0 and for all agents z > x and times t < τ(z), U ˙ (z,t) > 0. Then y(x,t) is strictly decreasing over time.17 Hence, matching opportunities 17And there exists some such x because for all z, U˙(z,τ(z))=rz >0.

20 GARTH BAUGHMAN x¯ U(x,t) x 1 U(x ,t) 1 x 2 U(x ,t) 2 x t = 0 t = T Figure 2. Value when r > 0 are declining for x. This is reflected in C being large relative to B. So, if τ(x) is far off, A might also be small and so values would be declining. Or, with τ(x) close, A might be large relative to C, yielding increasing values. In general, values might be increasing or decreasing for different agents before they join the first class (and then either increasing or decreasing thereafter). Acondition, however, isavailablewhichguaranteesthateventheleastattractive agents have increasing reservations over the whole period. Lemma 6. Write (cid:104) x (cid:105)(− σ ) λ(σ) = 1− (1+σ) 1+σ e−rT. x If (cid:16) r(cid:17) (cid:16)r(cid:17)2 1+ λ > 1 α α ˙ then for all x with τ(x) > 0, U(x,t) > 0 whenever t ≤ τ(x). While the proof is left for the appendix, it relies on using the bound on τ(x) from Lemma 5 to give an upper bound for y(x,t) and evaluating the matching opportunities if x could

DEADLINES AND MATCHING 21 match with y(x,t) with rate α; hence the bound does not depend on the distribution of agents and is relatively weak. Note that the result holds vacuously if (x/x) < 1+(r/α) where all agents are always in the first class. But, there do exist parameters for which the result holds meaningfully because, for example, lim (1+(r/α))λ(r/α)2 = 1 and r→0 ∂ (cid:16) r(cid:17) (cid:16)r(cid:17)2 1 (cid:16) (cid:16) x(cid:17)(cid:17) lim 1+ λ = 1−2αT −log 1− > 0 r→0 ∂r α α α x forx/xlargerelativetoT. Forsomeparametervalues, unattractiveagentsshouldallbecome more choosy over time before joining the first class. Also, note that the definition of τ(x) can not be simplified: the reservation value of the most attractive agent need not be monotone. As the model allows for arbitrary inflows, this is somewhat obvious. What may be less obvious is that the highest types may become more selective even without inflows because matching behavior of lower types can improve the aggregate distribution. If, for instance, there is a relatively large population of low types, then they match out relatively quickly. This improves the distribution over time. If match ratesarehighandagentsrelativelyimpatient, thisleadstoanincreasingvalueforthehighest types. This is closely related to non-uniqueness in the r > 0 case. The intuition for multiplicity is as follows: If a high pizazz agent, x, expects that other highly attractive agents will match quickly, leading to a poor distribution in the future, then x will lower his reservation value in the present, leading to a higher rate of exit. Alternately, if x expects the distribution to stay relatively stable, he is more patient, yielding a stable distribution.18 Thiskindofmultiplicityseemscloselyrelatedtothethickmarketsexternality described in Burdett and Coles (1997) which dates back to Diamond (1982), but the nonstationarity of the current environment adds a different flavor. 18The author has had no success in applying standard assumptions, such as log-concavity. These kinds of conditions do not seem to bite because, as t→T, the entire shape of the distribution is important, so small initial changes in strategy may have large impacts in the future.

22 GARTH BAUGHMAN 6. Unravelling and Costly Search with Patient Agents In the market for entry-level professionals, many studies describe unravelling – an incentive to rush the market (e.g. Roth et al. (1992), Roth and Xing (1997), Li and Suen (2004)). The equilibria presented above do not feature this rushing of the market. Instead, agents wait patiently, smoothly filtering into the first class. To some extent, this is purely technological. The matching technology prevents a complete rushing of the market, as agents only occasionally meet a potential partner. But it is the strategic implications of search frictions that prevent unravelling more than the technology itself. When meetings are only occasional, everyone forecasts that at least a few attractive agents will have failed to match today, and so will be available to match in the future. This, then, allows for selectivity and so for smoothly decreasing reservation values. High types, of course, would prefer to match with other high types, and the matching friction combined with a limited duration prevents them from doing so. Indeed, high types have a strict incentive to start searching earlier. What is less obvious, however, is that low types are either indifferent or prefer a longer duration. Lemma 7. Whenagents are patient, if thedeadlineis extended(or, equivalently, themarket starts earlier), the extended market time-zero Pareto dominates the shorter market. That high types benefit from having more time to search for each other is clear. That low types do not mind the fact that they wait longer derives from patience. But if high types spend more time matching with each other, then when a low type does join the first class he or she samples from a worse distribution. They are exactly compensated for this by the higher probability of matching given the longer duration of the market. To reduce the effect of search frictions, everyone would prefer that the market started earlier. Indeed, if agents could coordinate, the market would start at time minus infinity and would deliver perfect sorting. In the presence of search frictions, early matching serves to improve sorting rather than diminish it.

DEADLINES AND MATCHING 23 Moreover, it is exactly the anticipation effect which allows for this result. If meetings are too uniform and high types match out too quickly, then unravelling obtains. To this point, Damiano et al. (2005) consider a discrete-time version of the model here. In each period, each agent meets a partner randomly drawn from the set of unmatched agents. They show that, when there are participation costs and fewer rounds than types, the unique equilibrium involves complete unravelling – everyone accepts their first partner. This result derives from the uniformity of meetings. When all of the agents are paired in each period, one equilibrium is that everyone accepts their first partner, forecasting that the market will be empty next period. That no other equilibria exist derives from avoidable, costly search. When search is costly and avoidable, low type agents opt out until they join the first class. That is, if one does not expect to match in a given period, one should wait outside of the market. This implies that, at any point in time, only first class agents participate. If meetings are uniform, if in each round every agent meets a partner, and all participating agents are mutually acceptable, then all will match and exit. Perforce, in the model with discrete and uniform meeting rounds, all of the first class agents at any time match out of the market. But the first class consists of exactly those types better than the expected type searching tomorrow less the search cost, and all of these exit today. So the best type left tomorrow must be worse than the average type tomorrow. No distribution has this property, everyone must have left today. The only equilibrium is complete unravelling. If meeting rounds are not uniform and enough first class agents fail to meet a partner, this result breaks. Sorting can take place. Consider the continuous time model with random meeting times and patient agents, but suppose that in order to receive meetings at any time t, agents must incur a flow cost of c. This yields the following HJB equation: (cid:26) (cid:90) x (cid:27) ˙ U(x,t) = −max 0,−c+α(x,t) (z −U(x,t))G (dz,t) . x U(x,t) Proposition 5. The equilibrium with c > 0 is totally determined by the reservation value of the highest type as in Proposition 1. Moreover, agents outside the first class do not participate, preferring to wait until they become acceptable to the highest type.

24 GARTH BAUGHMAN Proof. Inspection of the HJB reveals non-increasing reservation values. A similar argument as above implies that U(x,t) = x for t < τ(x). Hence, agents outside the first class find it unprofitable to search. (cid:3) As a point of clarification, the equilibrium does depend on costs. The characterization here is the same as in Proposition 1: all behavior can be summarized in terms of the reservation value of the highest type. This reservation value, however, is significantly affected both directly as it now includes costs but also indirectly because of the different population operating in the market. The important difference relative to the market without costs is that low types stay out of the market until they match. Since, when there are costs, all agents in at a given time are first class, all meetings result in matches. This tends to increase reservation values. On the other hand, costs have a direct negative effect on reservation values as they mimic impatience (as previously described in a steady state framework by Adachi (2003)). In contrast to Damiano et al. (2005), notice that agents smoothly filter into the market no matter the magnitude of α (unless α is so small that it is not profitable to search at all). Hence, it is not a small expected number of meetings which leads to unravelling. Instead, the harsh strategic interaction induced by simultaneous and costly rounds of search leads to the stark results obtained in Damiano et al. (2005). A final distinction is interesting. Far from destroying sorting, small search costs improve it. Even for vanishing search costs, less attractive types wait outside the market. This removes the search externality that low types exert on high types – without costs, the two meet although they are not do not match. With search costs, every meeting results in a match, thus increasing efficiency of the matching process. Costly search induces agents to “wait their turn,” greatly improving the probability of a match for every single type, and also the sorting of types. When search costs are small, that the highest types prefer this arrangement is obvious – they trade a small flow cost for a discrete jump in match efficiency. That low types are indifferent or better off follows from the same logic as Lemma 7. The very lowest types are indifferent, receiving their own pizazz in expectation either way. That

DEADLINES AND MATCHING 25 they match with a lower type in expectation (because high types match out faster) is exactly compensated for by an increased probability of matching. Medium types – those who are in the first class at time zero without search costs but not with them – are better off because, although they have to wait to join the first class, they receive a higher value when they do. Hence, small flow costs lead to a Pareto improvement over the no-cost model. 7. Conclusion In this paper I explored the impact of a particularly harsh form of non-stationarity – a deadline – on a canonical matching model. I showed existence and characterized equilibria. Attractive individuals form a first class segment of the market whose members are all mutually acceptable. As the deadline approaches and the expected number of future meetings declines, thisclassexpands. Themodelexhibitsan“anticipationeffect”forlowtypesasthey anticipate that their opportunity set will jump discretely when they join the first class. This drives less attractive agents either not to match at all before they join the first class or to become more selective, with increasing reservations before they join the first class. The two cases obtain when agents are patient or impatient, respectively. When agents are patient, the equilibrium is unique and a small cost of search both improves efficiency and sorting. The randomness of meeting opportunities prevents complete unravelling of the market as in Damiano et al. (2005) but still generates an incentive for early matching. Omitted Proofs Proof of Proposition 2 (Uniqueness). Suppose there are two equilibria (UL(t),GL(z,t)) and (UH(t),GH(z,t)) with UH(0) ≥ UL(0). The proof proceeds in three major steps. First, a likelihood ratio across the two equilibria is evaluated. From this one derives a mean life remaining ordering. This ordering, combined with the first step, implies a monotone likelihood ratio property which is used to show that the lower equilibrium is always flatter thanthehigher. Concluding, wefindthatthetwoequilibriacannotbothsatisfytheterminal condition, so not both in fact satisfy equilibrium.

26 GARTH BAUGHMAN A word on notation: throughout, superscripts index the equilibrium from which the relevantobjectderivessothatτL(x)solvesUL(τL(x)) = x. Additionallysubscriptsindicatethat t = τ(x)asGi(z) = Gi(z,τi(x)). Further,denotehazardrateswithri(z) = gi(z)/(1−Gi(z)) x x x x (cid:16) (cid:17) and mean life remaining as mi(z) = (cid:82)x (1−Gi(y))dy /(1−Gi(z)). x z x x Also note that indeed we must have UH(0) > UL(0), otherwise UH(t) = UL(t) for all t as the dynamic for U is Lipshitz. Since G0 posesses a density, so does Gi(z,t) and we may write    αgi(z,t)(1−Gi(Ui(t),t))2 if z < Ui(t) g˙i(z,t) =  −αgi(z,t)Gi(Ui(t),t)(1−Gi(Ui(t),t)) if Ui(t) ≤ z.  Integrating this yields    min{τi(z),t}   (cid:90) (cid:90) t   gi(z,t) = g0(z)exp α [1−Gi(Ui(s),s)]ds− Gi(Ui(s),s)[1−Gi(Ui(s),s)]ds .     0   0 Hence, (cid:40) (cid:34) (cid:35)(cid:41) min{τL(z),τL(x)} τL(x) (cid:82) (cid:82) exp α [1−GL(UL(s),s)]ds− GL(UL(s),s)[1−GL(UL(s),s)]ds gL(z) 0 0 x = . (cid:40) (cid:34) (cid:35)(cid:41) gH(z) min{τH(z),τH(x)} τH(x) x (cid:82) (cid:82) exp α [1−GH(UH(s),s)]ds− GH(UH(s),s)[1−GH(UH(s),s)]ds 0 0 This expression is continuous everywhere and differentiable except at UL(0), UH(0), and x. Noting that dτi(z)/dz = 1/U ˙i(τi(z)) by the inverse function theorem, some algebra gives   0 if z < x,      (cid:16) (cid:17)(cid:16) (cid:17) d (cid:20) gL(z) (cid:21)   α 1−GL z (z) − 1−GH z (z) g x L(z) if x < z < UL(0), x = U˙ z L U˙ z H g x H(z) dz gH(z) (cid:16) (cid:17)(cid:16) (cid:17) x       −α 1−G U˙ z H z H (z) g g x H x L( ( z z ) ) if UL(0) < z < UH(0),    0 if z < UH(0).

DEADLINES AND MATCHING 27 Further recalling that U ˙i = −α (cid:82)x (1−Gi(z,t))dz, we see that this can be written as x x   0 if z < x,     (cid:16) (cid:17)(cid:16) (cid:17) d (cid:20) gL(z) (cid:21)    1 − 1 g x L(z) if x < z < UL(0), x = mH z (z) mL z (z) g x H(z) dz gH(z) (cid:16) (cid:17)(cid:16) (cid:17) x    1 g x L(z) if UL(0) < z < UH(0),  mH(z) gH(z)  z x     0 if UH(0) < z. Hence, we have a monotone likelihood ratio at τ(x) if mL(z) ≥ mH(z) for z ∈ (x,UL(0)). z z Monotone likelihood ratios implies monotone hazard rates. And, in particular, if we set x = UL(0), then   0 if z < UL(0),   d (cid:20) gL(z) (cid:21)   (cid:16) (cid:17)(cid:16) (cid:17) x = 1 g x L(z) if UL(0) < z < UH(0), dz g x H(z)   mH z (z) g x H(z)    0 if UH(0) < z. This implies that rH (z) = rL (z) for z > UH(0) and rH (z) > rL (z) for z < UL(0) UL(0) UL(0) UL(0) UH(0). Also, noting that dmi/dz = rimi −1, it straightforward to derive that (cid:90) x (cid:26) (cid:90) y (cid:27) mi(z) = exp − ri(s)ds dy. x x z z This, combined with our inequality on ri above, yields mL (UL(0)) > mH (UL(0)). UL(0) UL(0) On the way to a contradiction, suppose there exists some x < UL(0) such that mL(x) = x mH(x)andletx˜denotethelargestsuchcrossingpoint. Becausex˜isthelargestsuchx,mL(x) x x is continuous in x, and mL (UL(0)) > mH (UL(0)), we must have mL(x) > mH(x) for UL(0) UL(0) x x all x > x˜. Hence, gL(z)/gH(z) is increasing in z, and strictly so for z ∈ (x,UH(0)) and x x x ≥ x˜. This implies, for x ∈ (x˜,UL(0)], that rH(z) = rL(z) for z ∈ (UH(0),x), and x x rH(z) > rL(z) for z ∈ [x,UH(0)). So, from our equation for mi above, we must also x x have mL(x˜) > mH(x˜), our desired contradiction. We conclude that mL(x) > mH(x) for all x˜ x˜ x x x ∈ [0,UL(0)], sothatthelikelihoodratiogL(z)/gH(z)isincreasinginz forallx ∈ [0,UL(0)]. x x This, then, implies that 1 − GL(z) ≥ 1 − GH(z) for all x ∈ [0,UL(0)] and z ∈ X, so that x x

28 GARTH BAUGHMAN (cid:82)x (1−GL(z))dz > (cid:82)x (1−GH(z))dz and U ˙L < U ˙H. Thus, since T = τi(0), we have x x x x x x (cid:90) 0 d (cid:90) 0 1 (cid:90) 0 1 (cid:90) 0 d T = τL(z)dz = dz < dz = τL(z)dz = T−τH(UL(0)) < T, dz U ˙L U ˙H dz UL(0) UL(0) z UL(0) z UL(0) a contradiction. We conclude that the equilibrium is unique. (cid:3) Proof of Lemma 2. Suppose x < x and fix t. Suppose y ∈ Ω(x ,t) so that x ≥ U(y,t). 1 2 1 1 Then x ≥ U(y,t), so y ∈ Ω(x ,t). Hence Ω(x ,t) ⊂ Ω(x ,t). The rest follows by Remark 2 2 1 2 1. (cid:3) Proof of Corollary 1. For monotone U, note that if x ≤ x , then x could simply choose 1 2 2 A(x ,t) = A(x ,t)∩Ω(x ,t) and receive the same value as x . Hence, U(x ,t) ≥ U(x ,t). 2 1 1 1 2 1 That Ω is connected follows from x ≥ U(z,t) ⇒ x ≥ U(z(cid:48),t) for all z(cid:48) < z. (cid:3) Proof of Proposition 4 (Existence). Without loss of generality, suppose T = 1. Further, write mˆ(x,y,t) for the acceptability function: mˆ(x,y,t) = 1 if y ∈ Ω(x,t) and 0 otherwise. Next, writem(x,y,t)forthematchingfunction: m(x,y,t) = mˆ(x,y,t)mˆ(y,x,t)whichequals one if (x,y) are mutually acceptable at time t and zero otherwise. In what follows some function arguments, subscripts, etc. are dropped to save space when it does not cause confusion. The proof is in several steps and closely follows Smith (2006). Given value functions U(x,t), a continuous map U → m is defined (Lemma 8). Next, we show that m → G U m exists and is continuous (Lemma 9). Finally, closing the circle, define an operator, T, from the HJB equation, substituting in m and G , prove the existence of a fixed point for U mU U = TU – which is an equilibrium – using Schauder’s fixed point theorem. First, let B ≥ max{x,αx} be some fixed number and let B = Bexp{(r+α)(1−t)}. t Let V = {f : X → R|0 ≤ f ≤ x,(cid:107)f(cid:107) ≤ B } where the norm is the total variation norm. t t I.e., V is a subset of the functions of bounded variation on X. Equip V with the weakt t * topology.19 Then, by Alaoglu’s theorem, V is weak-* compact. And, by Tychonoff’s t 19 To clarify, Let C be the set of continuous functions on X and BV be the set of functions of bounded variation on X. Of course, BV is isometrically isomorphic to the set of measures of bounded variation on X which is the dual of C by the Riesz Representation Theorem. The weak-* topology on BV is, then, the (cid:82) weakest topology where if f ∈ C and µ ∈ BV then µ → fdµ is a continuous function for every f (this

DEADLINES AND MATCHING 29 (cid:81) theorem, V = V is compact in the product topology. Since V is convex, V is convex t∈[0,1] t t under pointwise operations. V will be the space of candidate U used in the application of Schauder’s Fixed point theorem. Define T : V → V by (cid:90) 1(cid:18) (cid:90) (cid:19) T(U)(x,t) = −rU(x,s)+α max{0,z −U(x,s)}G (dz,s) ds U t ΩU(x,s) By Lemma 11, T is continuous. By Lemma 10, TV ⊂ V. Hence there exists a fixed point U∗ = TU∗ by Schauder’s Fixed Point theorem. (cid:3) Lemma 8. There exists a continuous map U → mˆ and a continuous map U → m both U U essentially unique. Proof. Let U → U in V. Smith (2006), in his Lemma 8(a), proves that, for fixed t, there n exists a continuous map U(·,t) → mˆ(·,·,t) and that this yields a continuous map U(·,t) → m(·,·,t). Since V is equipped with the product topology in t, continuity for each t implies joint continuity of U → mˆ and U → m . That these maps are only essentially unique U U follows from the fact that agents are indifferent over measure zero differences. But, as shown in Smith (2006), there exists but one m such that U → U implies m → m pointwise U n Un U and it is this map which is selected. (cid:3) Lemma 9 (Fundamental Matching Lemma). There exists a continuous map m → G and m it is unique. Proof. The Cauchy problem20 is to find a G solving G ˙ (z,t) = αG(z,t)(E [θ(x,t)]−E [θ(x,t)|x ≤ z])−η(t)[G(z,t)−H(z,t)] ≡ F(t,G(·,t))(z) x x is also sometimes called the vague topology). Then, the weak-* topology on V is just the relative topology t inherited from BV equipped with the weak-* topology. 20This proof relies heavily the theory of ODE in Banach spaces. Statements and proofs of the relevant theorems can be found, for example, in Driver (2003).

30 GARTH BAUGHMAN (cid:82) and G(z,0) = G0(z) where θ(x,t) = m(x,z,t)G(dz,t) is the probability that a meet will result in a match for x at time t. Existence and uniqueness follow from the Cauchy-Lipshitz theorem for which we need to check that F is bounded, measurable in t, and Lipshitz in G. Notice that since m(x,y,t) is bounded and measurable, then both θ(x,t) and E(θ,x,t)) are bounded and measurable as well. If we equip G(·,t) with the weak-* topology (i.e. L´evy metric), then θ is continuous as a function of G and so F is continuous in G. Given that we are using the weak-* topology for G, it suffices to show that F(t,G) has uniformly bounded variation. So, fix G and let z ,z ∈ X. Then |F(t,G)(z )−F(t,G)(z )| = 1 2 1 2 |αG(z ,t)(E [θ(x,t)]−E [θ(x,t)|x ≤ z ])−η(t)[G(z ,t)−H(z ,t)] 1 x x 1 1 1 −(αG(z ,t)(E [θ(x,t)]−E [θ(x,t)|x ≤ z ])−η(t)[G(z ,t)−H(z ,t)])| 2 x x 2 2 2 = |α(G(z ,t)−G(z ,t))E [θ(x,t)]−α(G(z ,t)E [θ(x,t)|x ≤ z ]−G(z ,t)E [θ(x,t)|x ≤ z ]) 1 2 x 1 x 1 2 x 2 −η(t)(G(z ,t)−G(z ,t)−(H(z ,t)−H(z ,t)))| 1 2 1 2 ≤ |2α+η(t)||G(z ,t)−G(z ,t)|+|η(t)||H(z ,t)−H(z ,t)|. 1 2 1 2 where the last inequality follows because |G|,|θ| ≤ 1, and (cid:12)(cid:90) (cid:18)(cid:90) (cid:19) (cid:12) |G(z ,t)E(θ|x ≤ z )−G(z ,t)E(θ|x ≤ z )| = (cid:12) (cid:12) m(x,y,t)G(dy,t) G(dx,t) (cid:12) (cid:12) 1 1 2 2 (cid:12) (cid:12) z1≥x≥z2 (cid:12) (cid:12) (cid:90) z1 (cid:12) (cid:12) ≤ (cid:12) G(dx,t)(cid:12) ≤ |G(z ,t)−G(z ,t)|. 1 2 (cid:12) (cid:12) z2 Since G and H are probability distributions, their total variation is one. So, if η¯(t) = ¯ sup η(t) ≤ ζN exp(α), then (cid:107)F(cid:107) ≤ 2(α+η¯). Thus, there exists a solution. For uniqueness, t 0 consider the following: Fix two distributions, G and G . Given the calculation on θ above, 1 2 we have (cid:107)G (·,t)E(θ (x)|x ≤ ·)−G (·,t)E(θ (x)|x ≤ ·)(cid:107) ≤ (cid:107)G −G (cid:107) 1 G1 2 G2 1 2 (cid:82) and note that θ is Lipshitz in G: (cid:107)θ (x)−θ (x)(cid:107) = (cid:107) m(x,y,t)(G (dy,t)−G (dy,t))(cid:107) ≤ g1 g2 1 2 (cid:107)G − G (cid:107), hence any definite integral of θ is Lipshitz in G, and so is any other Lipshitz 1 2

DEADLINES AND MATCHING 31 function of θ. Hence, (cid:90) t (cid:18) (cid:90) t (cid:19) N (t) = exp α E θ (x,τ)dτ ζ(s)ds G G G 0 s isLipshitzinGand,finally,η (t) = ζ(t)/N (t)isLipshitzinGbecauseN (t) ≥ N exp(−αT) G G G 0 (I.e. there are always more people in the economy than if all matches were accepted over all time). Thus, since F is a composition of Lipshitz functions, it is Lipshitz. Hence, the solution is unique and continuous in m. (cid:3) Lemma 10 (Uniform Boundedness). If U ∈ V, then TU ∈ V. Proof. We need 0 ≤ TU(x,t) ≤ x and TU(·,t) to have total variation less than B . Simple t boundedness is obvious, so focus on bounding the total variation. Let U ∈ V, t ∈ [0,1], and x < x ∈ X be arbitrary but fixed. We will bound |TU(x )−TU(x )| and then sum over 1 2 1 2 all partitions to obtain a bound for the total variation of TU. Write ∆ = Ω(x )\Ω(x ) x1,x2 1 1 (recall x < x =⇒ Ω(x ) ⊆ Ω(x )). 1 2 1 2 Break up the second integral in TU into two pieces Q (x ,x ) and Q (x ,x ) as follows. 1 1 2 2 1 2 (cid:90) (cid:90) max{0,z −U(x )}G(dz)− max{0,z −U(x )}G(dz) 2 1 Ω(x2) Ω(x1) (cid:90) (cid:90) = max{0,z −U(x )}−max{0,z −U(x )}G(dz)+ max{0,z −U(x )}G(dz) 2 1 2 Ω(x1) ∆ (cid:124) (cid:123)(cid:122) (cid:125) (cid:124) (cid:123)(cid:122) (cid:125) ≡Q1(x1,x2) ≡Q2(x1,x2) Now, because |max(a ,b )−max(a ,b )| ≤ |a −a |+|b −b |, we have 1 1 2 2 1 2 1 2 (cid:90) |Q (x ,x )| ≤ |0−0|+|U(x )−U(x )|G(dz) ≤ |U(x )−U(x )| ≤ B |x −x |. 1 1 2 1 2 1 2 t 1 2 Ω(x1) And, (cid:90) (cid:90) |Q (x ,x )| ≤ |max{0,z −U(x )}|G(dz) ≤ x G(dz). 2 1 2 2 ∆ ∆

32 GARTH BAUGHMAN Continuing, |TU(x )−TU(x )| 2 1 (cid:12)(cid:90) 1(cid:18) (cid:18)(cid:90) (cid:90) (cid:19)(cid:19) (cid:12) (cid:12) (cid:12) = (cid:12) r(U(x )−U(x ))−α max{0,z −U(x )}dG− max{0,z −U(x )}dG ds(cid:12) 2 1 2 1 (cid:12) (cid:12) t Ω(x2) Ω(x1) (cid:90) 1 ≤ r|U(x )−U(x )|+α(|Q (x ,x )|+|Q (x ,x )|)ds 2 1 1 1 2 2 1 2 t (cid:90) 1(cid:18) (cid:90) (cid:19) ≤ rB |x −x |+αB |x −x |+αx G(dz) ds s 1 2 s 1 2 t ∆ Substituting in for B , one obtains t (cid:90) 1(cid:18) (cid:90) (cid:19) (cid:90) (cid:0) (cid:1) (r+α)Be(r+α)(1−s)|x −x |+αx G(dz) ds = −B|x −x | 1−e(r+α)(1−t) +αx(1−t) G(dz). 1 2 1 2 t ∆ ∆ Hence, summing over all possible partitions of X, (cid:88) (cid:0) (cid:1) (cid:107)TU(cid:107) = sup |TU(x )−TU(x )| ≤ B|x−x| e(r+α)(1−t) −1 +αx(1−t) ≤ B . i i−1 t {xi∈X} xi (cid:3) Lemma 11 (Continuity). T is continuous. Proof. Fix U,U ∈ V with U → U. Recall that V has the product topology in the t n n dimension and the weak-* topology in the x dimension. Hence, U (x,t) → U(x,t) pointwise n in t and a.e. pointwise in x. And, because 0 ≤ U ,U ≤ x, the dominated convergence n theorem gives convergence in L1 in both x and t. To show continuity, we need TU → TU n (cid:82) weak-* for each t. A sufficient condition for convergence is that, for each t, |TU (x,t)− I n TU(x,t)|dx for every measurable I ⊂ X. But, since 0 ≤ TU ≤ x, we need only show a.e. pointwise convergence (again by the dominated convergence theorem). We will divide |TU − TU| into several pieces and apply the triangle inequality. While there are many n expressions, the division looks at the two terms of T and decomposes the change in each into (1) a part from the change in Ω, (2) a part from the direct change in U, and (3) a part from

DEADLINES AND MATCHING 33 the change in G. Define the following: (cid:32) (cid:33) (cid:18) (cid:90) (cid:19) (cid:90) Q (x,s,n) = α G (dz,s)+r U(x,s)− α G (dz,s)+r U(x,s), 1 U U ΩU(x,s) ΩUn (x,s) (cid:32) (cid:33) (cid:32) (cid:33) (cid:90) (cid:90) Q (x,s,n) = α G (dz,s)+r U(x,s)− α G (dz,s)+r U (x,s), 2 U U n ΩUn (x,s) ΩUn (x,s) (cid:32) (cid:33) (cid:32) (cid:33) (cid:90) (cid:90) Q (x,s,n) = α G (dz,s)+r U (x,s)− α G (dz,s)+r U (x,s), 3 U n Un n ΩUn (x,s) ΩUn (x,s) (cid:90) (cid:90) W (x,s,n) = max{z,U(x,s)}G (dz,s)− max{z,U(x,s)}G (dz,s), 1 U U ΩU(x,s) ΩUn (x,s) (cid:90) (cid:90) W (x,s,n) = max{z,U(x,s)}G (dz,s)− max{z,U (x,s)}G (dz,s), 2 U n U ΩUn (x,s) ΩUn (x,s) (cid:90) (cid:90) W (x,s,n) = max{z,U (x,s)}G (dz,s)− max{z,U (x,s)}G (dz,s). 3 n U n Un ΩUn (x,s) ΩUn (x,s) (cid:82)1 (cid:80) (cid:80) Note, then, that TU(x,t) − TU (x,t) = ( Q (x,s,n)−α W (x,s,n))ds. Consider n t i i i i each term in turn. Because mˆ → mˆ pointwise almost everywhere, Un U (cid:12)(cid:90) (cid:12) (cid:12) (cid:12) |Q (x,s,n)| = αU(x,s)(cid:12) mˆ (x,z,s)−mˆ (x,z,s)G(dz,s)(cid:12) → 0 for a.e. (x,s). 1 (cid:12) U Un (cid:12) Because U (x,s) → U(x,s) pointwise a.e., n (cid:12) (cid:90) (cid:12) (cid:12) (cid:12) |Q (x,s,n)| = |U(x,s)−U (x,s)|(cid:12)α G (dz,s)+r(cid:12) → 0 for a.e. (x,s). 2 n U (cid:12) (cid:12) ΩU(x,s) Next, because G (z,s) → G (z,s) weak-* for a.e. s, we have Un U (cid:90) |Q (x,s,n)| = αU (x,s) |G (dz,s)−G (dz,s)| → 0 for a.e. (x,s). 3 n Un U ΩUn (x,s) (cid:82)1(cid:80) (cid:80) Thesameargumentsapplyfor|W |,i = 1,2,3. Hence, |Q (x,s,n)|+α |W (x,s,n)|ds → i t i i i i 0 for a.e. x again by dominated convergence, so that |TU(x,t)−TU (x,t)| → 0 for a.e. x. n This, then, gives (cid:82) |TU(x,t)−TU (x,t)|dx → 0 for every t. (cid:3) I n Lemma 12. For fixed G and r = 0 the dynamic for U is Lipshitz continuous.

34 GARTH BAUGHMAN ˙ Proof. When r = 0, we need only consider the dynamic for x which we will write as U = (cid:82)x L(U) = −α (1−G(z))dz. Then, fixing U and U , we have U 1 2 (cid:13) (cid:13) (cid:90) U2 (cid:13) (cid:13) (cid:107)LU −LU (cid:107) = α(cid:13) (1−G(z))dz(cid:13) ≤ α(cid:107)U −U (cid:107). 1 2 1 2 (cid:13) (cid:13) U1 So the dynamic has a Lipshitz constant of α. (cid:3) Proof of Proposition 3. BecauseU(x,τ(x)) = x,agent’sutilityisboundedbelowbyxe−r(τ(x)−t) (i.e. agents can do no worse at any time than deciding not to match, instead waiting to join the first class). Hence, for all t where an agent is not in the first class, his utility is bounded below by xexp{−r(T −t)}. Letting r → 0, U(x,t) ≥ x for all t when x is not in the first class. I.e. as r → 0, we obtain an equilibrium where low agents wait to join the first class. (cid:3) Proof of Lemma 6. Since, for t < τ(x), we can write (cid:90) τ(x) (cid:90) y(x,t) U(x,t) = xe−r(τ(x)−t) +α e−r(s−t) (G(y(x,t))−G(z))dzds t U(x,t) we have U(x,t) ≥ xe−r(τ(x)−t) ≥ xe−r(τˆ(x)−t) (cid:20) x (cid:16) r(cid:17) (cid:21)− r+ r α = x 1− 1+ e−r(T−t) ≡ U ˆ (x,t) x α where the last line comes from substituting in for τˆ(x) as defined in Lemma 5. Since U(y(x,t),t) = x, we have (cid:20) (cid:21) r (cid:20) (cid:21) r y(x,t) (cid:16) r(cid:17) r+α x (cid:16) r(cid:17) r+α y(x,t) ≤ x 1− 1+ er(T−t) ≤ x 1− 1+ er(T−t) ≡ yˆ(x,t). x α x α Write P(x,t) = G(y(x,t))−G(U(x,t)) and V(x,t) = E(z|y ≥ z > U) so that ˙ U(x,t) = (r+αP(x,t))U(x,t)−αP(x,t)V(x,t).

DEADLINES AND MATCHING 35 Now, V(x,t) < y(x,t) so that ˙ ˆ U(x,t) ≥ (r+αP(x,t))U(x,t)−αP(x,t)yˆ(x,t) (cid:20) x (cid:16) r(cid:17) (cid:21)− r+ r α (cid:20) x (cid:16) r(cid:17) (cid:21) r+ r α ≥ (r+αP(x,t))x 1− 1+ e−r(T−t) −αP(x,t)x 1− 1+ er(T−t) x α x α = x(rλ ˆ +αP(x,t)(λ ˆ −λ ˆ−1)) if one writes (cid:20) (cid:21) r x (cid:16) r(cid:17) r+α λ ˆ ≡ 1− 1+ e−r(T−t). x α ˆ ˙ Then, since t < τ(x), λ ≤ 1, and so U(x,t) ≥ 0 if (r/α)λ ˆ2 ≥ P(x,t). ˆ 1−λ2 And, since P(x,t) < 1, the result obtains. (cid:3) Proof of Lemma 7. SupposeT(cid:48) > T aretwodeadlines, andthatU ¯(cid:48) andU ¯ aretheequilibrium reservation values of the highest type under each deadline. The same logic as in the proof of Proposition 2 shows that U ¯(cid:48)(0) > U ¯ (0) (whichever reservation value starts lower must hit ¯ 0 earlier, and so it must be U). Those in the first class under the extended duration get U ¯(cid:48)(0) instead of U ¯ (0), an im- ¯ provement. Moreover, all x < U(0) are indifferent between the two equilibria, because they get their own pizazz in expectation under both. Those who were first class in the short duration market but are not in the long duration instead get their own pizazz. This is an ¯ improvement, as they were getting only U(0) with the short duration – the definition of being in the first class at time zero. (cid:3) References Abdulkadirog˘lu, A., P. A. Pathak, and A. E. Roth (2005): “The New York City High School Match,” The American Economic Review, 95, 364–367.

36 GARTH BAUGHMAN Abdulkadirog˘lu, A., P. A. Pathak, A. E. Roth, and T. So¨nmez(2006): “Changing the Boston School Choice Mechanism,” Boston College Working Papers in Economics 639, Boston College Department of Economics. Adachi, H. (2003): “A search model of two-sided matching under nontransferable utility,” Journal of Economic Theory, 113, 182 – 198. Afonso, G. and R. Lagos (2012): “Trade dynamics in the market for federal funds,” Tech. rep., Staff Report, Federal Reserve Bank of New York. ———(2015): “TheOver-the-CounterTheoryoftheFedFundsMarket: APrimer,” Journal of Money, Credit and Banking, 47, 127–154. Alpern, S. and D. Reyniers (2005): “Strategic mating with common preferences,” Journal of Theoretical Biology, 237, 337–354. Bloch, F. and H. Ryder (2000): “Two-Sided Search, Marriages, and Matchmakers,” International Economic Review, 41, pp. 93–115. Burdett, K. and M. G. Coles (1997): “Marriage and Class,” The Quarterly Journal of Economics, 112, 141–168. Chade, H. (2001): “Two-sided search and perfect segregation with fixed search costs,” Mathematical Social Sciences, 42, 31 – 51. Coles, M. G. and D. T. Mortensen(2012): “EquilibriumLaborTurnover,FirmGrowth and Unemployment,” Working Paper 18022, National Bureau of Economic Research. Coles, P., J. Cawley, P. B. Levine, M. Niederle, A. E. Roth, and J. J. Siegfried (2010): “The Job Market for New Economists: A Market Design Perspective,” Journal of Economic Perspectives, 24, 187–206. Damiano, E., H. Li, and W. Suen(2005): “UnravellingofDynamicSorting,”The Review of Economic Studies, 72, 1057–1076. Diamond, P. A.(1982): “AggregateDemandManagementinSearchEquilibrium,” Journal of Political Economy, 90, 881–894. Driver, B. K. (2003): Analysis Tools with Applications, Springer.

DEADLINES AND MATCHING 37 Eeckhout, J. (1999): “Bilateral Search and Vertical Heterogeneity,” International Economic Review, 40, 869–887. Li, H. and W. Suen (2004): “Self-Fulfilling Early-Contracting Rush,” International Economic Review, 45, 301–324. McNamara, J. M. and E. J. Collins (1990): “The Job Search Problem as an Employer- Candidate Game,” Journal of Applied Probability, 27, 815–827. Menzio, G. and S. Shi (2011): “Efficient Search on the Job and the Business Cycle,” Journal of Political Economy, 119, 468–510. Mortensen, D. (1986): “Job search and labor market analysis,” Handbook of Labor Economics, 2, 849–919. Moscarini, G. and F. Postel-Vinay (2013): “Stochastic Search Equilibrium,” The Review of Economic Studies. Pathak, P. A. and T. So¨nmez (2008): “Leveling the Playing Field: Sincere and Sophisticated Players in the Boston Mechanism,” American Economic Review, 98, 1636–1652. Robin, J.-M. (2011): “On the Dynamics of Unemployment and Wage Distributions,” Econometrica, 79, 1327–1355. Rogerson, R. and R. Shimer (2011): “Chapter 7 - Search in Macroeconomic Models of the Labor Market,” in Handbook of Labor Economics, ed. by O. A. a. D. Card, Elsevier, vol. Volume 4, Part A, 619–700. Rogerson, R., R. Shimer, and R. Wright (2005): “Search-Theoretic Models of the Labor Market: A Survey,” Journal of Economic Literature, 43, 959–988. Roth, A. and X. Xing (1997): “Turnaround Time and Bottlenecks in Market Clearing: Decentralized Matching in the Market for Clinical Psychologists,” Journal of Political Economy, 105, 284–329. Roth, A. E. and E. Peranson (1999): “The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design,” American Economic Review, 89, 748–780.

38 GARTH BAUGHMAN Roth, A. E., M. Sotomayor, R. Aumann, and S. Hart (1992): “Chapter 16 Twosided matching,” in Handbook of Game Theory with Economic Applications, Elsevier, vol. Volume 1, 485–541. Rudanko, L. (2011): “Aggregate and Idiosyncratic Risk in a Frictional Labor Market,” American Economic Review, 101, 2823–2843. Shimer, R. and L. Smith (2000): “Assortative Matching and Search,” Econometrica, 68, 343–369. Smith, L. (1999): “Optimal job search in a changing world,” Mathematical Social Sciences, 38, 1 – 9. ——— (2006): “The Marriage Model with Search Frictions,” Journal of Political Economy, 114, 1124–1144. ——— (2009): “Cross-Sectional Dynamics in a Two-Sided Matching Model,” Tech. rep., Working Paper, available from www.lonessmith.com. ——— (2011): “Frictional Matching Models,” Annual Review of Economics, 3, 319–338. ¨ Sotomayor, M. and O. Ozak (2012): “Two-Sided Matching Models,” in Computational Complexity, ed. by R. A. Meyers, Springer New York, 3234–3257. Van Den Berg, G. J. (1990): “Non-stationarity in Job Search Theory,” The Review of Economic Studies, 57, 255–277.