Tâtonnement in matching markets
Abstract
I study tâtonnement processes in a matching market without transfers. In each period, schools set cutoffs, i.e., the preference ranks of the least preferred students they are willing to admit, and students accept their most preferred offers. Cutoffs are adjusted on the basis of demand–supply imbalances. A school's adjustment from one period to the next is moderate if it is bounded by the most recently observed imbalance at that school. I show that for any period in which all schools adjust moderately, the sum of demand–supply imbalances across all schools weakly decreases. Moreover, if all schools always adjust moderately and there is a unique stable matching, then adjustments converge to a market-clearing cutoff vector. If there is more than one stable matching, moderate adjustments may cycle indefinitely, but the supremum and the infimum of all cutoff vectors observed along a cycle are both market-clearing.
1 Introduction
Starting with Gale and Shapley (1962)'s seminal analysis of the marriage problem, matching theory has been successful in developing centralized mechanisms with appealing allocative and incentive properties. These mechanisms are not only theoretically appealing but also work well in practice. In fact, extensions of the Gale–Shapley deferred acceptance algorithm are now used, for example, to match children to public schools (see Abdulkadiroglu, Pathak, Roth, and Sönmez (2006), Abdulkadiroglu, Pathak, and Roth (2009), Pathak (2011)) and medical graduates to their first professional position (see Roth and Peranson (1999)). However, many markets with very similar characteristics operate in a decentralized manner. An important example is university admissions, where centralized clearinghouses are the exception rather than the norm and full centralization often seems unlikely. Since the decentralized processing of admission offers (rejections and acceptances) in these markets takes a nonnegligible amount of time, there is often only room for relatively few rounds of offers. To avoid missing their enrollment targets, universities typically overbook, i.e., make more offers than they would ideally like to be accepted. It is easy to find examples in which universities overbook too little or too much.1 Motivated by these observations, I focus on the question of what happens in the long and short run when schools adjust their admission offers on the basis of observed discrepancies between target and realized enrollments. In particular, I am interested in finding simple conditions under which successive updating by schools from an arbitrary starting point eventually leads to market-clearing or at least comes close to it.
At a theoretical level, my research speaks to the justification of stability as an equilibrium concept for many-to-one matching markets. One important justification for an equilibrium concept is that it can be learned by “myopic” agents via a distributed, iterative adjustment procedure.2 A classic example of such a procedure for competitive equilibrium is tâtonnement where producers of goods in excess demand increase prices and producers of goods in excess supply decrease prices. In the context of many-to-one matching between universities and students, the natural analogy is a tâtonnement process in which universities make admission offers to students and each university adjusts its selectivity in the direction of its excess enrollment. If such a process were guaranteed to converge to a stable matching, it would provide us with a “learning foundation” for stability as an equilibrium concept. I show that convergence obtains whenever the underlying matching market has a unique stable matching, but may fail otherwise.
I consider a standard many-to-one matching problem with responsive preferences and no monetary transfers. There are finite sets of students and schools. Each student has a strict preference ranking of available schools. Each school has a fixed enrollment target and responsive preferences with respect to some strict ranking of individual students. My analysis focuses on tâtonnement processes in which schools make binding admission offers, each student demands the most preferred school among those from which she received an offer, and schools then update offers on the basis of observed demand–supply imbalances. For the most part, I restrict attention to the case where schools' offers can be described by cutoffs, i.e., each school decides on the least preferred individual student it wants to admit and then makes an offer to all weakly preferred candidates. Cutoff adjustments from one period to the next are moderate if they are bounded by the most recently observed demand–supply imbalances: Schools increase their cutoffs by no more than their most recent excess demand and decrease their cutoffs by no more than their most recent excess supply.3
My main results are as follows: First, moderate adjustments always bring the market weakly closer to clearing in the sense of weakly decreasing the aggregate imbalance, which I define as the sum of demand–supply imbalances across all schools (Theorem 1). Second, if schools adjust moderately and either (a) schools only decrease cutoffs when there is no school in excess demand or (b) schools only increase cutoffs when there is no school in excess supply, then adjusted cutoffs are guaranteed to converge to a market-clearing cutoff vector (Theorem 2).4 Third, moderate adjustments may cycle indefinitely when the underlying matching market has more than one stable matching (Theorem 3). Finally, if moderate adjustments cycle indefinitely, then the supremum and the infimum of all cutoff vectors observed along the cycle are both market-clearing (Theorem 4). As a corollary, I obtain that moderate adjustments are guaranteed to converge to market-clearing if the underlying matching market has a unique stable matching (Corollary 3).
1.1 Related literature
Since I study a tâtonnement process in which schools use observed enrollments to update their admissions offers, one line of research that is closely connected to my paper is that on tâtonnement processes for markets with indivisible goods and continuous monetary transfers.5 Demange, Gale, and Sotomayor (1986) introduce a dynamic clock auction for markets with multiple heterogeneous goods and unit-demand bidders. This auction mechanism is guaranteed to converge to the smallest competitive equilibrium price vector, provided it starts from the vector of reservation prices. Gul and Stachetti (2000) extend the dynamic clock auction to the case where bidders' preferences satisfy the gross substitutes condition of Kelso and Crawford (1982). Contrary to the finding of Demange, Gale, and Sotomayor (1986), Gul and Stachetti (2000) show that, in general, there is no dynamic clock auction mechanism with a single ascending price trajectory that implements the Vickrey–Clarke–Groves (VCG) outcome. Ausubel (2006) presents a different tâtonnement-based auction process to compute competitive equilibrium prices. His process ensures that agents ultimately receive their VCG payments and converges from any initial price vector.6 There are two crucial differences between this line of research and mine. First, cutoffs are different from prices since they determine who gets an offer from which school, but otherwise do not affect students' utilities. Second, all of the above papers assume that there is one central auctioneer who controls price movements of all objects in the economy. In contrast, I explicitly want to allow for situations in which schools react independently to imbalances between realized and target enrollments.
Also related is a literature that has developed a linear programming approach to stable matchings. VandeVate (1989) and Rothblum (1992) have shown that the set of stable matchings in a one-to-one matching problem can be described by a linear programming problem whose extreme points are all integral.7 That finding extends to many-to-one matching problems (see, e.g., Baiou and Balinski (2000), Fleiner (2003), and Sethuraman, Teo, and Qian (2006)). Given the connection to linear programming, it is natural to try to leverage linear programming techniques to solve stable matching problems. For one-to-one matching problems, (both versions of) the Gale–Shapley algorithm can be interpreted as a dual ascent algorithm; see Abeledo and Rothblum (1995b) and Vohra (2012).8 Dual ascent algorithms solve a linear programming problem through a series of relaxed programming problems that are connected via the updating of dual variables associated with constraints that are violated in the solutions of these relaxed problems. An important similarity between dual gradient methods and the tâtonnement processes that I study is that, for both, the individual adjustment at a specific school only depends on the extent to which feasibility and stability constraints involving that school are violated. A key difference is that dual gradient methods often rely on a carefully chosen starting point, whereas I study cutoff adjustments from arbitrary starting points. The focus on such fully distributed procedures, where there is no coordination on specific initial conditions or the adjustments of cutoffs across different schools, is motivated by the desire to understand the conditions under which completely decentralized matching markets arrive at a stable matching.
Several papers have studied different decentralized implementations of Gale and Shapley (1962)'s famous deferred acceptance algorithm (DAA). In these studies, the main question typically is whether a stable matching is reached in (subgame perfect) equilibrium. For example, Niederle and Yariv (2009) consider a decentralized market game where, in each period, firms simultaneously make an offer to some worker and workers then simultaneously decide on received offers. Preferences of the agents are assumed to satisfy a strong alignment condition that, among other things, guarantees that there is a unique stable matching. Niederle and Yariv show that under complete information, a stable matching is implemented with probability 1 in any equilibrium that survives iterative elimination of weakly dominated strategies. This finding does not extend to the case of incomplete information and it is possible that no (Bayes–Nash) equilibrium implements a stable matching with certainty. Other papers that have studied different decentralized implementations of the DAA under the assumption of complete information are Pais (2008) and Haeringer and Wooders (2011).
Also related to my work is the question of whether processes that, starting from an unstable matching, allow randomly selected blocking pairs to rematch converge to a stable matching. Roth and Vande Vate (1990) show that for two-sided matching markets in which no agent can be matched to more than one partner, such a random process converges to a stable matching with probability 1.9 This finding was extended to a certain class of many-to-many matching markets by Kojima and Ünver (2008), to (solvable) roommate markets by Diamantoudi, Miyagawa, and Xue (2004), to (solvable) matching markets with couples by Klaus and Klijn (2007), and to matching markets with salaries by Chen, Fujishige, and Yang (2010).10 While these papers are interesting studies of market equilibration in matching markets, they do rely on implicit assumptions about the coordination between and the information available to the agents. First, they assume that agents have sufficiently detailed information to identify a blocking opportunity. Second, it is taken for granted that agents coordinate in a way that guarantees that intended deviations are actually realized. I relate my findings to the random paths literature in more detail below.
Finally, Lauermann and Nöldeke (2014) embed a standard marriage market in a search model with random meetings and study the limit of steady-state equilibria when frictions vanish. Lauermann and Nöldeke show that equilibrium matchings are guaranteed to converge to stable matchings if and only if the underlying matching market has a unique stable matching. Although there does not seem to be a direct connection between sequences of steady-state equilibria and the adjustment processes that I study, the just described result mirrors my finding that moderate cutoff adjustments are guaranteed to converge to market-clearing if and only if the core is a singleton.
2 Model
There is a finite set of students I with and a finite set of schools S with . Each student i has a strict preference relation over the set of available schools and strictly prefers all schools to being left unmatched. Each school has a fixed enrollment target and a fixed strict ranking of individual students in I.11 In addition, each school s has a weak preference ranking12 on the set of all potential entering classes, , that is responsive (Roth (1985)) to and in the sense that for any , , if and only if , if , and if . For school and student , i's score at s is given by , where is the rank that i has in . Hence, the tth most preferred student according to has a score of at school s. The underlying matching market is assumed fixed from here on out. To simplify notation, relevant market features, such as preferences or capacities, are typically suppressed in the following text.
A matching is a mapping such that (i) for all ,13 (ii) for all , (iii) , and (iv) if and only if . A matching μ is stable, if there is no student–school pair such that and either or for some . One of the central results in matching theory is that there always exist student- and school-optimal stable matchings (Gale and Shapley (1962), Roth (1984)). Denote the student-optimal stable matching by and the school-optimal stable matching by .
Cutoffs and market-clearing
Azevedo and Leshno (2016) have shown that market-clearing and stability are essentially equivalent concepts.14 To describe this insight more formally, first fix a matching μ and define an induced cutoff vector by setting if and otherwise. Next, given a cutoff vector c, define a mapping by setting and . We have the following lemma.
Lemma 1. ([Azevedo and Leshno] ([2016]))If μ is stable, then is market-clearing. If c is market-clearing, then is stable. Moreover, there exists a uniformly lowest market-clearing cutoff vector and a uniformly highest market-clearing cutoff vector .
Given some stable matching μ, say that c induces μ if . As discussed in Azevedo and Leshno (2016), induces and induces .
Tâtonnement processes
I consider simple tâtonnement processes in which schools set cutoffs, each student demands her most preferred school among those for which her score exceeds the cutoff, and schools then update cutoffs on the basis of observed discrepancies to their quotas. Tâtonnement can be interpreted as taking place either over multiple admission periods (where cutoffs represent binding admission offers), within a given admission period (where cutoffs represent tentative admission offers that only convert to binding ones when enrollment targets are met), or a mix between the two (for example, a few rounds of adjustments within a given period and then an initial round of offers in the next period that reflects students' reactions to the last round of offers in the previous period). In case of adjustments across multiple periods, my analysis assumes that the underlying matching problem is always the same, i.e., that a new and identical student population arrives in each period. That assumption is approximately satisfied if the admission environment is stable over time so that enrollments only change significantly when schools change their cutoffs.
Since the underlying matching market is fixed throughout, a cutoff vector induces the demand vector and the vector of demand–supply imbalances . Hence, while tâtonnement processes will typically be defined on the basis of some intermediary statistic, such as demand–supply imbalances, I can define them directly on the basis of cutoff vectors. For now, I restrict attention to time-invariant adjustment processes where adjustments only depend on the current cutoff vector. Formally, a time-invariant adjustment process is a mapping A from C to itself. Until Section 4.2, adjustments will always be assumed to be time-invariant and I will simply refer to adjustment processes. I assume throughout that only if c is market-clearing or, equivalently, at least one school adjusts its cutoff when the current cutoff vector is not market-clearing. Finally, for any , let denote the t-fold application of A to c.
To fix ideas, here are two examples.15
Example 1.Let and be arbitrary. The simple adjustment of s at c is given by
In words, the simple adjustment of s at c is to increase its cutoff by 1 if it is oversubscribed at c and to decrease its cutoff by 1 if it is undersubscribed at c. ◊
Next, I focus on a generalization of Gale and Shapley (1962)'s famous deferred acceptance (DA) algorithm by Adachi (2000) that encompasses the student- and school-proposing variants as special cases. The main idea is to characterize stable matchings as the set of fixed points of an operator from a finite lattice into itself. This idea figures heavily in the literature on generalized matching models following Hatfield and Milgrom (2005) and Ostrovsky (2008).16
Example 2.Let and be arbitrary. The generalized DA adjustment for school s is defined by
While the two DA variants have been central to matching theory and its applications, nothing is known about the behavior of DA dynamics from arbitrary starting points. In practice, even if the admissions process is centralized and relies on a DA algorithm, a school may be able to place bounds on its selectivity that have to be respected if it manages to hit its target enrollment. Hence, we might be faced with situations in which DA algorithms cannot be guaranteed to start from the extreme points for which their behavior is well understood. My results below show under which conditions DA algorithms are guaranteed to converge.
3 Main results
Definition 1.An adjustment process A
- (i) increases moderately if, for all and ,
- (ii) decreases moderately if, for all and ,
- (iii) is moderate if it increases and decreases moderately.
Going back to the examples presented in the previous subsection, the simple adjustment process and the generalized Gale–Shapley process are both moderate.
Note that if a school s is oversubscribed at c and increases its cutoff moderately, then at , it will remain affordable to at least of the students who demanded it at c and can, therefore, only become undersubscribed if at least one other school has decreased its cutoff. Similarly, if a school s is undersubscribed at c and decreases its cutoff moderately, then at it will become affordable to at most additional students and can, therefore, only become oversubscribed if at least one other school has increased its cutoff. Note that both of these statements do not rely on information about students' preferences beyond what students demand at the cutoff vector c.17
In the first part of my analysis, I focus on the short-run properties of adjustment processes. The anecdotal evidence gathered in the Introduction supports the view that demand–supply imbalances occur in practice and that these imbalances are costly: students have to cramp into crowded lecture halls for oversubscribed schools, while undersubscribed schools suffer significant revenue losses. Here is a simple aggregate measure for these costs.
Definition 2.The aggregate imbalance at is given by
Note that if minimizes the aggregate imbalance, then either c is market-clearing or there is a market-clearing cutoff vector such that for all s such that . Taking aggregate imbalance as a measure of distance to market-clearing assumes that there is a constant cost associated to every student above or below a school's target enrollment. While it would certainly be interesting to study other cost measures, this is out of the scope of the current paper. Now remember that moderate adjustments ensure that the imbalance of a given school, defined as , will weakly decrease if no other school changes its cutoff, that is, for any moderate adjustment process A, for any cutoff vector c. However, this property may easily fail if multiple schools adjust their cutoffs simultaneously. Furthermore, even if only one school were to change its cutoff, it may well be that imbalances at other schools increase. The first main result of this paper is that moderate adjustments always bring the market weakly closer to clearing in the sense of weakly decreasing the aggregate imbalance.
Theorem 1.If A is moderate, then for all .
Theorem 1 relies on the fact that lowering a cutoff by x units makes the corresponding school affordable to exactly x additional students and increasing it by x units makes the school unaffordable to exactly x students. Hence, adjusting a cutoff is different from adjusting the (nonpersonalized) price of an object, since the latter affects the affordability and attractiveness of the object to all agents. Before discussing the intuition behind Theorem 1, I show via a small example that the aggregate imbalance may strictly increase if only one school does not adjust moderately.
Example 3.There are three students, i, , and , and two schools s and with target enrollments . Students' scores are given by and . Students' preferences are given by , , and .
Consider the cutoff vector . At c, students i and both demand s, while cannot afford any school. Hence, the aggregate imbalance at c is 2. Now consider the cutoff vector . Note that the adjustment from c to is moderate for s but not for . At , all students demand and the aggregate imbalance is 3. ◊
To get some intuition for Theorem 1, assume there are only two schools, and . Fix a moderate adjustment process A and some cutoff vector c such that is oversubscribed and is undersubscribed at c. Since A is moderate, cannot decrease and cannot increase its cutoff from c to . Hence, no student can demand at c, but at . Therefore, we can restrict attention to students whose demand switches from to when going from c to . First, let be the set of those students who switch their demands to at and who strictly prefer over . The total effect of demand changes by agents in is to decrease the aggregate imbalance by . To see this, I distinguish two cases.
- Case 1: . The demand change of each student in decreases the excess supply at due to moderate decreases and the excess demand at .
- Case 2: . The demand changes of the first students in decrease the excess supply at and the excess demand at . The demand changes of the remaining students in do not affect the aggregate imbalance since they decrease the excess supply at and increase the excess supply at .
Second, let be the set of those students who switch their demands to at and who strictly prefer to . I will argue that the demand changes of students in can at most increase the aggregate imbalance by . I again distinguish two cases.
- Case 1: . By moderate increases, we have that . Since the demand change of each individual student can increase the aggregate imbalance by at most 2, we obtain that the demand changes of students in increase the aggregate imbalance by at most .
- Case 2: for some . The demand changes of at least students in cannot increase the aggregate imbalance since these demand changes decrease the excess demand at . The demand changes of the remaining at most k students in increase the aggregate imbalance by at most 2k.
Hence, if each school limits its adjustments by the magnitude of its most recent demand–supply imbalance, then adjustments always at least weakly reduce the aggregate disparity between supply and demand. Since the aggregate imbalance is bounded from below, we immediately obtain the following important implication of Theorem 1.
Corollary 1.If A is moderate, then exists for all .
From now on, I will focus on results about the long-run behavior of adjustment processes. The first result shows that it is relatively easy to ensure convergence to market-clearing from any initial cutoff vector if schools are willing to coordinate their cutoff adjustments and temporarily maintain cutoffs despite demand–supply imbalances.
Theorem 2.Suppose A is moderate and either of the following conditions holds:
- (i) Cutoffs are only increased when there is no undersubscribed selective school, i.e., for all , if there is at least one school s such that and .
- (ii) Cutoffs are only decreased when there is no oversubscribed school, i.e., for all , if there is at least one school s such that .18
Then exists for all .
The intuition for this result is straightforward: If A only increases cutoffs when there is no undersubscribed school with nontrivial cutoff, there must eventually come a point at which no school is undersubscribed if A satisfies moderate decreases. However, from this point onward, no school can become undersubscribed again if A satisfies moderate increases. As I show in Theorem 7 in Appendix B.2, both types of adjustment processes have a variety of other appealing features, such as independence of adjustment magnitudes (subject to being moderate) and convergence to market-clearing cutoff vectors that are “close” to the initial cutoff vector.
Next, I focus on adjustment processes that randomly select a set of schools that are allowed to moderately adjust their cutoffs. Theorem 2 can be used to show that such processes are guaranteed to converge to market-clearing if there is always a positive probability that only oversubscribed and a positive probability that only undersubscribed schools are selected. To formulate this corollary, some further notation and terminology is useful. Given a cutoff vector , let be the set of all oversubscribed schools at c. Similarly, define to be the set of undersubscribed schools with nontrivial cutoffs at c. With these preparations, we have the following corollary.
Corollary 2.Fix an arbitrary cutoff vector and let be a random sequence of cutoff vectors such that for each , whenever is not market-clearing, then is obtained from 19 by the following method.
- (i) Randomly select a set of schools .
- (ii) Allow schools in to adjust their cutoffs moderately from subject to the requirement that for at least one school in .
If for any , there is a strictly positive probability that and a strictly positive probability that , then converges to a market-clearing cutoff vector with probability 1.
The corollary follows from Theorem 2 on noting that this result implies that from any c, there are at least two finite paths of cutoff adjustments that lead to a market-clearing cutoff vector. If the random sequence of cutoff vectors defined in the corollary were to cycle indefinitely, at least one cutoff vector must occur infinitely often and the random process would have to choose a non-convergent path each time it reaches that cutoff vector. Under the assumptions of the corollary, however, finite convergent paths always have a strictly positive probability of being chosen (since there is always a positive probability of only choosing oversubscribed schools until there are no more oversubscribed schools and always a positive probability of only choosing undersubscribed selective schools until there are no more undersubscribed selective schools) and we obtain a contradiction. The random blocking dynamics studied by Roth and Vande Vate (1990) are similar to a special case of the dynamic defined in Corollary 2 in which we require that only one school is selected at each point.20
Corollary 2 shows that if at each instance there is a positive probability that all schools that do adjust their cutoffs adjust in the same direction, then convergence to market-clearing is guaranteed. The just mentioned result implicitly relies on the existence of some coordinating entity that can identify which schools are oversubscribed and which are undersubscribed, and that can at least temporarily prevent some schools from adjusting their cutoffs. For the remainder of this section, I focus on adjustment processes that represent situations in which there is no such coordinating entity and schools that do not achieve their enrollment target always adjust their cutoffs. The latter condition is the subject of the next definition.
Definition 3.An adjustment process A is strict, if for all and all s, only when either or and .
I also need the following more stringent notion of moderate adjustments.
Definition 4.An adjustment process A is strongly moderate if, for all ,
Note that the simple adjustments in the sense of Example 1 are strongly moderate. On the other hand, the generalized DA adjustment process of Example 2 is moderate, but not strongly so: A school that is oversubscribed at c increases its cutoff to the th highest score at s among all students in and that score may exceed .
The next result shows that strict adjustment processes can only be guaranteed to converge if the underlying matching market has a unique stable matching.
Theorem 3.Suppose A is strict and strongly moderate. If , then there exists a cutoff vector c such that does not exist.
The intuition for this result is that if there are two stable matchings, we can always find a cutoff vector for which some students can afford their more preferred stable match, while others cannot. Furthermore, the cutoff vector can be constructed so that schools, which are affordable to all students who match to them in the more preferred stable outcome for the students, are oversubscribed and all other schools are undersubscribed. Given the restrictions on adjustment magnitudes, a strict adjustment process cycles forever. However, as the next result shows, the lowest and the highest cutoffs observed along any cycle of an eventually moderate adjustment process are both market-clearing.
Theorem 4.Let A be a strict adjustment process, let be an arbitrary cutoff vector, and let T be such that for all .21 Define cutoff vectors and by setting, for each school s, and . If A is moderate, then and are market-clearing.
Theorem 4 implies immediately that any strict and moderate adjustment process will eventually enter the “market-clearing corridor” between and , that is, for all , there exists a such that for all . Hence, if the difference between the two extreme market-clearing cutoff vectors is very small, strict and moderate adjustment procedures will become almost constant in the long run.
Theorem 4 is also readily seen to imply that moderate adjustment processes always converge if the underlying market has a unique stable matching.22
Corollary 3.If A is moderate and strict, and , then exists for all .
Corollary 3 is particularly useful when the market under consideration is large. For such markets, there is often a unique stable matching (see, e.g., Kojima and Pathak (2009) and Azevedo and Leshno (2016)) and, thus, moderate, strict adjustment procedures are guaranteed to converge to market-clearing.
4 Extensions
The analysis up to this point has assumed that schools use cutoff strategies and that adjustments are time-invariant. However, in decentralized and congested matching markets, schools may sometimes prefer to make offers that are not representable by cutoffs, for example, because they also care about the likelihood with which an offer is accepted.23 On the other hand, a school may condition adjustments on the whole history of cutoffs, for example, because it is initially uncertain about the fraction of its offers that will be accepted and then tries to revise its estimated “yield” on the basis of all enrollments observed so far. I now briefly sketch two extensions that allow for more general offers by schools and time-dependent adjustments, respectively.
4.1 Beyond cutoffs
One can now define generalized adjustment processes starting at some exogenously given vector of offer sets O. As for adjustment processes, I assume that only if O is market-clearing. For generalized adjustment processes, Definition 6 in Appendix A introduces a natural generalization of Definition 1: A generalized adjustment process  increases moderately if undersubscribed schools expand their set of admission offers and if each oversubscribed school s continues to offer admission to at least of the students who demanded it at O; a generalized adjustment process  decreases moderately at O if oversubscribed schools shrink their set of admission offers and if each undersubscribed school s makes at most as many new admission offers as it had vacant seats at O. In Appendix A, I show that Theorems 1 and 2 both extend to moderate generalized adjustment processes. By contrast, Theorem 4 does not directly extend unless offer sets are very close to having a cutoff structure (details are available upon request).
4.2 Dynamic adjustments
If adjustments are allowed to depend on the whole history of cutoffs, we can define an adjustment procedure for school s as a mapping , where, for any , is the set of all sequences of cutoff vectors of length t. Here, for any , is the cutoff that s sets for period t if cutoffs in periods 0 to are given by the vectors to . The adjustment of school s at may depend on any information directly or indirectly (for example, via demand–supply imbalances) conveyed by . As in the analysis of the preceding sections, I focus on the evolution of cutoffs induced by a profile of adjustment procedures from an arbitrary initial condition as in the following definition.
Definition 5.Let be a profile of adjustment procedures and let c be an arbitrary cutoff vector. The adjustment process induced by and c is defined inductively by setting and for each .
For the remainder of this discussion, I take a profile of adjustment procedures to be fixed and focus directly on properties of the induced adjustment processes. For each and t, let . Instead of assuming directly that adjustment processes can only come to rest at market-clearing cutoff vectors, I make the weaker assumption that adjustment processes are responsive to demand in the sense that no school ignores upward or downward pressure on its cutoff forever.
Assumption 1.There do not exist a cutoff vector , a school , and a time T, such that either
- (i) and for all or
- (ii) , , and for all .
Thus, from any point onward, a school that is continuously oversubscribed eventually increases its cutoff and, thus, makes fewer offers. Similarly, a selective school that is continuously undersubscribed eventually decreases its cutoff and, thus, makes more offers. It is straightforward to show that Assumption 1 ensures that adjustment processes can only come to rest at market-clearing cutoff vectors.
Observation 1.If an adjustment process A satisfies Assumption 1, then for all such that exists, is market-clearing.
To illustrate, here is an example in which adjustments are not time-invariant.
Example 4.Suppose each school s has some prior belief on its yield , that is, a belief about the fraction of offers that will be accepted by students. Given its prior belief, each school sets its cutoff so that expected enrollment equals its target. Hence, a school s with prior initially sets a cutoff of .25 If all schools follow this routine, we get an initial cutoff vector that induces observed enrollments and yields . Given observations about past enrollments, school s updates its yield to , where is the weight s places on the observed yield in period 1, and then updates its cutoff to , again ensuring that expected enrollment equals target enrollment.
More generally, in each non-initial period , schools similarly use past enrollments in previous periods to update their yield estimates. I assume that at the beginning of period t, school s estimates its yield to be , where is the yield estimate of school s at the beginning of period and is the weight school s attaches to the realized yield in period , . For period , school s then sets a cutoff of , so that it meets its enrollment target in expectation given its revised estimate of the yield.
Note that the adjustment process Y satisfies Assumption 1. In contrast to the generalized DA adjustment process in Example 2, this process uses information about all previous enrollments, not just the most recent one. ◊
Depending on schools' priors, the average yields adjustment process may initially require large downward or upward adjustments and, therefore, fail to be moderate. However, if for all t and , adjustments become moderate for large enough t. More formally, I say that an adjustment process is eventually moderate, if, for any c there exists some , such that is a moderate adjustment from for all .
In terms of results, Theorem 1 extends straightforwardly: whenever we arrive at a period where adjustments to the next period are moderate, the aggregate imbalance will weakly decrease. Hence, if adjustments are moderate for large enough t, the aggregate imbalance will converge. Similarly, if adjustments satisfy the conditions in Theorem 2 or Corollary 2 for large enough t, we obtain convergence. The negative result of Theorem 3 obviously extends to the more general adjustment processes I consider in this subsection. Finally, for Theorem 4, note that for a non-time-invariant adjustment process A, for some cutoff vector c does not imply that adjustments cycle from period t onward. However, it is not difficult to see that the proof of Theorem 4 implies that for any eventually moderate A and any c, the supremum and infimum of all accumulation points of the sequence both define market-clearing cutoff vectors; see Theorem 8 in Appendix B.6 for a formal statement and proof.
5 Conclusion
I have studied tâtonnement processes for matching markets without transfers. Schools have fixed enrollment targets and use their observations about realized enrollments to adjust their cutoffs. It was shown that whenever schools' cutoff adjustments are bounded by the most recently observed imbalance between actual and target enrollment, the market moves weakly closer to clearing. If, at each point in time, only oversubscribed or only undersubscribed schools adjust their cutoffs, convergence to market-clearing was seen to be guaranteed from any initial situation. However, whenever the underlying matching market has more than one stable matching and all schools instantaneously react to enrollment imbalances, the existence of initial conditions from which adjustment processes cycle indefinitely was established. For the case where schools adjust moderately, it was shown that market-clearing cutoff vectors can be constructed from cycles in the adjustment process as the supremum and the infimum of all cutoff vectors observed along a cycle are both always market-clearing. In particular, convergence is guaranteed when the underlying matching market has a unique stable matching.
There are many avenues for future research on the topics presented in this paper. Most importantly, if one takes tâtonnement processes as a model of decentralized matching markets, there are a number of assumptions that one might want to relax. First, the analysis implicitly assumed that application costs are negligible so that students apply to all schools. If this assumption is not satisfied, students face a difficult portfolio allocation problem. In this case, one should expect students also to rely on their observations about past market conditions to decide where to apply. Second, the environment was assumed to be completely stationary and it is important to study the effects of substantial preference shocks on adjustment processes. Third, it would be useful to derive optimal learning rules as a theoretical benchmark. This and most of the other open questions will most likely require additional assumptions about (the evolution of) schools' and students' preferences.
Appendix A: Beyond cutoffs
In this section, I consider the more general version of my model introduced in Section 4.1. In the process, I present and prove more general versions of several of the results in the main body of the paper. I start by generalizing the notion of moderate adjustments from the main body of the paper.
Definition 6.A generalized adjustment process Â
- (i) increases moderately at if for all ,
and
- (ii) decreases moderately at if for all ,
and
- (iii) is moderate at , if it increases and decreases moderately at O.
I now relate cutoffs to offer sets. First, note that a cutoff vector c induces the offer vector , where . Furthermore, say that has a cutoff structure if there exists a cutoff vector c such that . Second, given an adjustment process A, we can define an associated generalized adjustment process à as follows: Let be such that for some cutoff vector c and then set . Note that an adjustment process A converges if and only if the associated generalized adjustment process à converges. Note also that, for any c, it holds that for all . The next lemma describes the basic relationships between cutoff adjustment processes and their generalized counterparts that apply for any vector of offer sets.
Lemma 2.
- (i) If adjustment process A increases moderately in the sense of Definition 1, then à increases moderately at all that have a cutoff structure.
- (ii) If adjustment process A decreases moderately in the sense of Definition 1, then à decreases moderately at all that have a cutoff structure.
- (iii) If adjustment process A is moderate in the sense of Definition 1, then à is moderate at all that have a cutoff structure.
Proof.(i) Fix some with cutoff structure and let c be such that . If , then and, thus, . The last inequality immediately implies . If , then is equal to the th highest score of students in . Hence, we obtain that .
(ii) Fix some with cutoff structure and let c be such that . By the second part of Definition 1, we have that . The last inequality immediately implies . Moreover, I also obtain that if .
(iii) The last part follows immediately from the first two parts. □
The next definition generalizes the notion of aggregate imbalance.
Definition 7.The aggregate imbalance at is given by
With these preparations, I now state and prove a generalized version of Theorem 1.
Theorem 5.Let be arbitrary. If the generalized adjustment process  is moderate at O, then .
Proof.Suppose the generalized adjustment process  is moderate at and let . Define to be the set of oversubscribed and to be the set of undersubscribed schools at O. I now consider the aggregate effects of changes in individual demands caused by the move from O to .
First, let denote the set of all students who demand a school in at O. By the weak axiom of revealed preference, we must have for all since and, given that  is moderate at t, all schools in make less (in a subset sense) offers at than at O. Furthermore, if for some , then and . Now let be arbitrary. Since  decreases moderately at t and O, there are at most students who get an offer from s at but not at O. Hence, if we momentarily disregard potential demand changes of agents in , then no school in can be oversubscribed at . This implies that the aggregate imbalance is exactly the same after we have accounted for the demand changes of agents : The demand change of an agent from to increases the excess supply of seats at s by 1 and decreases the excess supply of seats at by 1. Let for all schools , for all , and be the associated aggregate imbalance.
Next I account for the demand changes of agents in . Call an agent a voluntary leaver of if and . Let denote the set of all voluntary leavers of s and . Note that for all , . I will first consider the aggregate effects caused by demand changes of agents in V. For this analysis, I neglect demand changes of agents in , as these will be considered in the last step of the proof. Set for all , set for all ,26 and let be the associated aggregate imbalance.
Consider first a school such that . In this case, the aggregate imbalance at is units lower than the aggregate imbalance at O after we have accounted for the demand changes of agents in . To see this, note first that , so that after accounting for demand changes of agents in the excess demand for places at s is units lower at than at O. Furthermore, for all , since from O to , has become affordable to at most additional agents given that  decreases moderately at t and Õ. This implies, in particular, that , so that after accounting for demand changes of agents in , aggregate excess supply of schools in is units lower at than at O.
Next consider a school such that . In this case, the aggregate imbalance at is units lower than at O after we have accounted for demand changes of agents in . To see this, note first that , so that from O to the absolute value of excess enrollment at school s changes by . On the other hand, as in the previous case, after accounting for demand changes of agents in , aggregate excess supply of schools in is units lower at than at O. Summing up these changes, we see that after we have accounted for demand changes of agents in , the aggregate imbalance is units lower at than at O.
Summing up, after we have accounted for demand changes of agents in for all , the aggregate imbalance is .
To complete the proof, I now consider the effect of demand changes of students . For the remainder of the proof, fix a school and let be the set of students who are forced to leave s going from O to . Note that since  increases moderately at t and Õ, . I now consider the change in aggregate imbalance caused by the demand changes of agents in starting at . I distinguish three cases.
Suppose first that . In this case, the change in the imbalance at s due to demand changes of agents in starting at is . Furthermore, in the worst case, each student in increases the excess enrollment at some school by one unit. Hence, the total increase in the aggregate imbalance caused by demand changes in starting at is at most given moderate decreases. Since in the case I consider here, and the aggregate imbalance demand after accounting for demand changes of agents in is at most .
Next suppose that . In this case, the increase in the excess supply of seats at s due to demand changes of agents in starting at is . Furthermore, in the worst case, each agent in increases the excess enrollment at some school by 1. Since in the case I consider here, . After accounting for demand changes of agents in , the aggregate imbalance is at most
Finally, when demand changes of agents in cannot increase the aggregate imbalance relative to .
An iterative application of this argument for all schools in shows that and, thus, completes the proof. □
In the following discussion, I refer to a moderate generalized adjustment process  that satisfies for all as long as there is at least one oversubscribed school as an upward–downward generalized adjustment process. Similarly, I refer to a generalized adjustment process  that satisfies for all whenever there is at least one undersubscribed school as a downward—upward generalized adjustment process. The next result summarizes a key property of the two processes just described.
Theorem 6.If  is either a moderate generalized upward–downward adjustment process or a moderate generalized downward–upward adjustment process, then exists for all .
Proof.The proof relies on the following lemma.
Lemma 3.(i) If is such that for all , either or , then exists for any moderate generalized adjustment process Â.
(ii) If is such that for all , , then exists for any moderate generalized adjustment process Â.
Proof.(i) Let  be an arbitrary moderate generalized adjustment process.
I show first that if no selective school is undersubscribed at O, then all students are weakly worse off under than under O and no selective school is undersubscribed at . The first property follows immediately, since all selective schools are undersubscribed at O and  is moderate. For the second property, note first that the weak axiom of revealed preference implies that, for all , if , then . Since  is moderate, therefore implies that . By the contrapositive of the last observation, we have that implies and, thus, by our assumptions about O, . Since  is moderate, as well.
Iterating the above reasoning, for all t such that is not market-clearing, we must have for at least one s. Hence, there must exist a such that for some i. Since student welfare is bounded from below, exists.
(ii) Let  be an arbitrary moderate generalized adjustment process. I show first that if no school is oversubscribed at O, then all students are weakly better off under and no school is oversubscribed at . The first property follows immediately, since no school is oversubscribed at O and  is moderate. For the second property, note first that the weak axiom of revealed preference implies that, for all , if and , then . Hence, for all . Since  is moderate, and, combined with the previous finding, I obtain . Hence, no school is oversubscribed at if no school is oversubscribed at O.
Iterating the above reasoning, for all t such that is not market-clearing, we must have for at least one s. Hence, there must exist a such that for some i. Since student welfare is bounded from above, exists. □
Let  be any moderate upward–downward generalized adjustment process and let be arbitrary. Note that there must be a such that for all : For any t such that there is a school s for which , then the assumption that  is upward–downward jointly implies ; since the set of offers for each school is bounded from below by ∅, I obtain a contradiction. Let and note that Lemma 3(i) implies that exists. This completes the proof of convergence for the case of moderate upward–downward generalized adjustment processes. To establish the convergence of moderate downward–upward generalized adjustment processes, first establish that such a generalized adjustment process must eventually reach an offer vector at which no selective school is undersubscribed and then apply Lemma 3(ii). I omit the details. □
Appendix B: Proofs
The following additional lemma describes some important structural properties of cutoffs that induce a given stable matching.
Lemma 4.Let μ be some stable matching.
- (i) There exist cutoff vectors and such that and both induce μ, and, for any cutoff vector c that induces μ, .
- (ii) For any c such that , for all .
Proof.(i) For each school s, let if and let otherwise. Since μ is stable, it is straightforward that induces μ. Now consider some cutoff vector c such that for some . I claim that c does not induce μ. Given the construction of and the assumption that , we must have . However, then, and c cannot induce μ, since there is at least one student in who cannot afford at c.
Next I construct . For any school s, let be the set of students who desire s at μ. For any school s such that , let . For any school s such that , let . Stability of μ again immediately implies that induces μ. Now consider some cutoff vector c such that for some . I claim that c does not induce μ. Given the construction of , it is immediate that . Let be such that . By the definitions of and , we must have . Since can afford at c, we have and, thus, c does not induce μ.
(ii) Let c be an arbitrary cutoff vector such that . Note first that since for all s such that , all students can afford the schools that they are matched to under μ. Next, let i be an arbitrary student for whom there exists a school s such that . Since , we have and, thus, . Hence, i cannot afford s at c and . □
B.1 Proof of Theorem 1
B.2 Proof of Theorem 2
Similar to Appendix A, I refer to an adjustment process A that satisfies if there is at least one oversubscribed school at c as an upward–downward adjustment process. Furthermore, I refer to an adjustment process A that satisfies if there is at least one undersubscribed selective school at c as a downward–upward adjustment process. I start by introducing a stronger version of Theorem 2.
Theorem 7.
- (i) If A is a moderate upward–downward adjustment process, then for all c, exists. Moreover, for any c and any moderate upward–downward adjustment process B, for all .
- (ii) If A is a moderate downward–upward adjustment process, then for all c, exists. Moreover, for any c and any moderate downward–upward adjustment process B, for all .
- (iii) If A is a moderate upward–downward adjustment process and , then and there is no market-clearing cutoff vector such that and for some .
- (iv) If A is a strongly moderate downward–upward adjustment process27 and , then and there is no market-clearing cutoff vector such that and for some .
Proof.The existence of the limits in parts (i) and (ii) follows immediately from Theorem 6 and Lemma 2. For the remaining parts of Theorem 7, I now introduce and prove two additional lemmata.
Lemma 5.
- (i) If c and are two cutoff vectors such that , then .
- (ii) Given a cutoff vector c and a school s, define
and let . If c and are two cutoff vectors such that , then .
(i) I only need to establish that for any s that is oversubscribed at c, since the statement is trivially true otherwise. If , the definition of Δ implies that . Otherwise, note that since , we must have . In particular, the th highest score of agents in must be weakly lower than the th highest score of agents in . This establishes the statement.
(ii) Consider some school s that is undersubscribed at c and let . If , the statement follows since . So suppose that and let be such that . Note that for any i such that and , we must have since . Hence, it has to be the case that . This, in turn, implies . Since and , we obtain . The definition of implies that and this completes the proof.
Lemma 6.Let c and be such that and one of the following two conditions is satisfied:
- (i) For all , either or .
- (ii) For all , .
For any pair of moderate adjustment processes A and B, we have that for all , where is the smallest integer such that is market-clearing and is the smallest integer such that is market-clearing.
Proof.(i) Assume that c and are such that and, for all , either or . I show first that for all , there exists a such that for all and all .
Note first that the statement is trivially true for , since (a) , (b) for all , and (c) for all given that A is moderate and given that, for all , either or .
So suppose the statement is true up to some and let be such that for all and all . I need to show that there is some such that for all and all . Suppose not. Then there has to exist some such that for all . Let . Note that we must have
Since , we have that and, hence,
Combining the last insights, I find that
Next we must have given that . Since B is moderate and, by the conditions on demands at , either or , we must have and . Since and , we obtain , which is a contradiction to the definition of .
By the statement that I have just established, I obtain that for all . A symmetric argument yields the converse. Since preferences are strict, I obtain for all .
(ii) Assume that c and are such that and, for all , . I show first that for all , there exists a such that for all and all .
Note first that the statement is trivially true for , since (a) , (b) for all , and (c) for all , given that A is moderate and given that, for all , .
So suppose the statement is true up to some and let be such that for all and all . I need to show that there is some such that for all and all . Suppose not. Then there has to exist some such that for all . In particular, .
Let and note that we must have . Next observe that
Now consider first the case where . Combining the above insights, we have
Next assume that . By the inductive assumption, there cannot be an agent i such that , , and (because such an agent would strictly prefer over ). Hence,
With the help of Lemmas 5 and 6, I now complete the proof of Theorem 7.
(i) Let A and B be two moderate upward–downward adjustment processes and let c be an arbitrary cutoff vector. For any integer t, set and .
Let be the smallest integer such that no school is oversubscribed at and let be the smallest integer such that no school is oversubscribed at . Define a second sequence of cutoffs by setting and for all . Let T be the smallest integer such that no school is oversubscribed at .
Claim 1. for all .
Proof.I show the statement for the sequence . The proof for the sequence is completely analogous. Note first that for all t: The statement is trivially true for ; suppose we had already shown that . Then, by Lemma 5(i) and since A is moderate, .
Next I argue that . By definition of T and what was just established, I immediately obtain . If , I immediately obtain the desired inequality. So assume that .28 By the first part of Lemma 5, I obtain . Since no school is oversubscribed at , we have that . Since A is moderate, . Hence, and iterating these arguments, I obtain the desired result.
To complete the proof of Claim 1, I now show by induction that for all , there exists a such that for all and all , . In particular, for all and, given the already established fact that , we must have for all .
Now the desired statement is trivially true for since and, therefore, for all . Now suppose the statement is true for all . I show that it is also true for . Fix and i so that . We must have . By definition of , there must be at least students such that and . By the inductive assumption, for all , none of these students can afford a more preferred school at and, consequently, all enroll at at . Hence, for any such that for at least one , at least one school must be oversubscribed. Since only if c is market-clearing, there must exist a such that for all , each student weakly prefers her demand at over her demand at . □
To complete the proof, I can now apply the second part of Lemma 6 to and .
(ii) Let A and B be two moderate downward–upward adjustment processes and let c be an arbitrary cutoff vector. For any integer t, set and .
Let be the smallest integer such that no selective school is undersubscribed at and let be the smallest integer such that no selective school is undersubscribed at . Define a second sequence of cutoffs by setting and for all . Let T be the smallest integer such that no selective school is undersubscribed at .
Claim 2.We have for all .
Proof.I show the statement for the sequence . The proof for the sequence is completely analogous. Note first that for all t. This is trivially true for . So suppose we had already established that for some . By the second part of Lemma 5, I obtain .
Next I argue that . By definition of T and what was just established, I immediately obtain . If , I immediately obtain the desired inequality. So assume that . By the second part of Lemma 5, I obtain . Since no selective school is undersubscribed at , we have that . Since A is moderate, . Hence, and iterating these arguments, I obtain the desired result.
To complete the proof of Claim 2, I now show by induction that for all , there exists a such that for all and all , . In particular, for all and, given the already established fact that , we must have for all .
The desired statement is trivially true for since and, therefore, for all . Now suppose the statement is true for all . I show that it is also true for . Fix and i so that . Since , the inductive assumption yields for all . Furthermore, so that must have been undersubscribed at and . The inductive assumption also implies that for all j such that and , . Hence,
To complete the proof, I can now apply the first part of Lemma 6 to and .
(iii) Since A is upward–downward, there exists a such that and for all . Furthermore, and Lemma 5 is easily seen to imply . Let and . Note that we must have . Since and for all , we have that for all . By the weak axiom of revealed preference, I then obtain for all and, therefore, . Since for all and , I obtain that for all . Since for all , is market-clearing and given that A is moderate, we have that .
Now take any market-clearing cutoff vector such that . By Lemma 5, we have that . Furthermore, the definitions of Δ and immediately imply . Since A is moderate, I obtain . Iterating this argument, I find that , which completes the proof.
(iv) Since A is downward–upward, there exists a such that and for all , either or . Furthermore, and Lemma 5 is easily seen to imply . Let and . Note that we must have . Now for any , and the weak axiom of revealed preference imply . Hence, . Furthermore, for any such that , the weak axiom of revealed preference implies . So for all . Since and , I thus obtain for all . Given that A is strongly moderate, it is then straightforward to show for all and all . By (ii), converges to a market-clearing cutoff vector . By the rural hospitals theorem (Roth (1986)), we have that for all and, therefore, for all such s. Combining the previous two insights, I obtain that .
Now take any market-clearing cutoff vector such that . By Lemma 5, I obtain . Hence, and the desired result follows.
B.3 Proof of Theorem 3
Consider first an arbitrary school . If there is an agent such that but , we obtain a contradiction to the stability of μ since (i) , so that implies , and (ii) , since scores are strict. The same arguments show that if there is an agent such that , we must have for some . This is impossible unless and , which would contradict the definition of a stable improvement cycle. Hence, we must have so that , since either or .
Next I consider the schools involved in the stable improvement cycle. First, take some and agent . Since and , . If for some , we obtain a contradiction to the definition of a stable improvement cycle since and . Hence, we must have . A completely analogous argument shows that for all . Now consider agent . By the definition of a stable improvement cycle and , we must have . Since , . Together with the above arguments, this implies , , and for all . Since A is strongly moderate and strict, I obtain , , and for all .
An iterative application of these arguments is easily seen to imply that, for all , (where ), for all , and for all . In particular, and this completes the proof. □
B.4 Proof of Theorem 4
To simplify the notation in the proof, set for all t.
-
I first establish that no school is oversubscribed at . Suppose to the contrary that s is such that and let . Note that by the definition of and the weak axiom of revealed preference, we must have, for all , whenever t is such that . Since the adjustment process is strict, there must thus exist a smallest such that .
Let . By the above arguments, we must have . Hence, if , then the above arguments imply that s is not undersubscribed at and since A decreases moderately. If , then since A decreases moderately, we obtain . Furthermore, . Combining the last two observations, I find that . Hence, given that . I have shown that if , then as well. Iterating this argument, I find that for all . However, the last relationship contradicts the definition of and this contradiction completes the proof.
-
Next I show that no selective school is undersubscribed at . Suppose to the contrary that s is such that as well as . Note that for all t and i, . The last observation implies that for any student i such that but , we have for all t. Hence, s must be undersubscribed whenever . Since the adjustment process is strict, there must thus exist a smallest such that .
If , we must have , since A increases moderately. Next consider the case of . Since A increases moderately, we must have . Since , we must, therefore, have that . The preceding arguments show that whenever , if A increases moderately. Iterating this argument, we find that for all . This contradicts the definition of .
Using the just established findings, I now show that and are both market-clearing. Note first that given that no school is oversubscribed at and that given that no selective school is undersubscribed at . Now let be a school such that for some stable matching μ. By the rural hospitals theorem (Roth (1986)), we have for all stable matchings . Hence, and . Furthermore, it is straightforward to verify that . Next let be the set of all schools that fill their capacities in any stable matching. By the previous observations, we have that , that is, between and , demand can only flow between schools that fill their capacities in all stable matchings. Furthermore, by definition of , . However, if there was an undersubscribed selective school at , then there would also have to be an oversubscribed school at . Hence, is market-clearing. Finally, if there was an oversubscribed school at , the previous findings indicate that there would also have to be a school that is undersubscribed at . Since there are no undersubscribed selective schools at , we must have and, thus, also . However, by revealed preference and , we then obtain and, thus, . Since we have already shown that is market-clearing, we obtain a contradiction to . □
B.5 Proof of Corollary 3
By Theorem 4(iii), there is a T such that for all . It is straightforward to show that in the case I consider here, any cutoff vector that lies between the lowest and highest market-clearing cutoff vector must be market-clearing.
B.6 Time-varying adjustments
In this subsection, I first formulate a more general version of Theorem 4 and then discuss the necessary adjustments to the proof.
Theorem 8.Let A be an arbitrary adjustment process, let be an arbitrary cutoff vector, and let be the set of accumulation points of the sequence . Let be the supremum of and let be the infimum of . If A is moderate, then and are market-clearing.
Proof.Note that there exists T such that for all by the definition of . Conditional on this observation, the remainder of the proof proceeds almost exactly as the proof of Theorem 4. The only remaining difference is that we now use Assumption 1 to infer that an oversubscribed school at and an undersubscribed selective school at must both eventually adjust their cutoffs. □
