Stable Matching with Mistaken Agents

Stable Matching with Mistaken Agents

\setstretch{1}

\allowdisplaybreaks

\setstretch{1.2}

Introduction

Strategy-proofness and stability are two important desiderata in market design for two-sided matching abdulkadiroglu/sonmez:03. One describes agents' optimal behavior, and the other is a property of a matching outcome. Strategy-proofness---making it a weakly dominant strategy to truthfully reveal one's own preferences---minimizes the scope for mistakes and thus levels the playing field. It also aids empirical research by making agents' choices easy to interpret. Stability---ensuring that each agent is matched with her favorite partner among those who are willing to match with her---is crucial for the long-term sustainability of a mechanism roth:91 and the fairness of matching, particularly in the context of centralized college admissions and school choice abdulkadiroglu/sonmez:03.

These two desiderata are satisfied under one of the most popular mechanisms in practice, the Deferred Acceptance (DA): it is strategy-proof for agents on one side of the market, and the matching outcome is always stable when agents report truthfully. Alarmingly, there is growing evidence that non-truthful behaviors, which are called strategic mistakes in the literature, are common in DA.\footnote{The literature uses the term “mistake” to refer to the play of a {\it weakly dominated strategy}, regardless of whether it entails an actual payoff loss (which depends on other individuals' actions). We call a mistake payoff-relevant when it leads to a payoff loss for an agent, i.e., her truthful reporting of preferences would have matched her with a more preferred partner given other agents' actions.} Laboratory experiments chen/sonmez:02 and studies of high-stake real-life matching markets rees-jones:16,shorrer/sovag:2017,chen_li:2015,ACH:Proj0WP,HRR:16 show that a significant fraction of participants misreport their preferences. When agents make mistakes, DA no longer guarantees stability.

Mistaken agents may pose a broad challenge to market-design research, both theoretical and empirical. Most theoretical studies on strategy-proof mechanisms assume that agents play their unique dominant strategy, truth-telling (TT), which guarantees a stable matching under DA. A natural question is: Do the documented mistakes, i.e., non-truthful behaviors, imply that the theoretical predictions about DA outcomes in the literature are incorrect? Moreover, much of the empirical literature relies on assumptions that ignore mistakes. Does it mean that the estimates from that literature are biased? These are the questions that our paper aims to answer.

We examine agent behavior and outcome in many-to-one matching economies operated by DA. Participants on one side, which are labeled “colleges,” use priority scores to strictly rank those on the other side, whom we call “applicants.” Each applicant knows her own score when applying to colleges. This setting captures many practices in the field. For example, the markets with mistaken agents mentioned above fit this description and cover admissions to secondary schools, universities, or post-graduate programs in four different countries. In these settings, priority scores may be a measure of an applicant's academic performance such as scores from entrance exams. We define a college as {\it feasible} to an applicant if her score is above the college's {\it cutoff}, which is the lowest score among the college's accepted applicants. When each applicant is matched with her favorite feasible college, the matching is stable. Therefore, a stable matching can be characterized by a set of “market-clearing” cutoffs azevedo/leshno:16.

An important empirical finding from the literature is that, although mistakes are frequent, only a small fraction of them have payoff consequences; that is, unilaterally correcting a mistake changes the assignment for only few applicants. In general, mistakes are difficult to identify in the field because applicant preferences are unknown to researchers. Some recent studies shorrer/sovag:2017,ACH:Proj0WP,HRR:16 focus on pairs of education programs that differ only in a financial component (e.g., scholarship vs.\ no scholarship) and hence an applicant's preference order between the two in a pair can be unambiguously determined. As summarized in Table (ref), 17--35% of applicants in these studies make an identifiable mistake: when reporting their ordinal preferences to the mechanism, they rank a program without a scholarship above the identical program with a scholarship (column 3). However, among the applicants with an identified mistake, only 1--20% would have a different assignment if each applicant's mistake is corrected unilaterally (columns 5 and 7).

Motivated by such an empirical pattern---a significant presence of mistakes but largely of little payoff consequences---, we employ a new solution concept, which we call robust equilibrium, that relaxes Bayesian Nash equilibrium to allow for mistakes with “small” payoff consequences. We operationalize the payoff “smallness” by studying a sequence of DA-run matching economies that grow large both in the number of applicants and the number of seats per college, with a fixed number of colleges. Along the sequence, applicant types---i.e., their preferences and their priority scores at colleges---are randomly drawn from a well-behaved distribution (to be made precise later). This random sampling maintains certain tractability while, at the same time, approximating applicants' uncertainty about the types of other applicants in real life. We define a strategy profile as a (possibly asymmetric) function that maps randomly drawn types to the rank-order lists (ROLs) submitted by each applicant. While TT is a weakly dominant strategy under DA, our concept allows for possible mistakes or deviations from TT. Specifically, robust equilibrium is a strategy profile in which, for any $\epsilon>0$, each applicant obtains within $\epsilon$ of their highest possible payoff in a sufficiently large economy.

Recall that one of our research questions is about the empirical literature that assumes no mistakes by agents. In DA, such an assumption implies TT. Our first main result (Theorem (ref)) says that this assumption is not justified in a robust equilibrium, as all but a vanishing fraction of applicants may submit untruthful ROLs. To the extent that robust equilibrium captures applicants' behavior, this result suggests that we should not be surprised by the documented mistakes. Furthermore, our theorem does not impose any structure on mistakes: applicants may omit their more preferred colleges or flip the order of colleges in their ROLs as long as the probability of admission to these colleges is low. Both of these behaviors are consistent with the evidence reported in Table (ref).

In contrast, regarding our other research question, we obtain a positive answer: the theoretical predictions about stable matching under DA are generally valid, at least in large economies. Despite the behavioral multiplicity and ambiguity, under mild conditions, {\it all} robust equilibria yield a virtually unique outcome in a sufficiently large economy (Theorem (ref)). The outcome is asymptotically stable---the fraction of applicants who obtain their favorite feasible college converges to one---and converges to the outcome that would arise from TT. In other words, even if applicants make mistakes, the outcome is well approximated by the outcome that would arise with fully rational applicants (Corollary (ref)).

At first glance, asymptotic stability may appear to be an unsurprising consequence of robust equilibrium. One may conjecture that, as payoff losses vanish, fewer applicants suffer a loss, which would imply that most applicants must obtain their favorite feasible college. However, a robust equilibrium allows everyone to have a vanishing loss, so a possibility remains that an arbitrarily large number of applicants do not obtain their favorite feasible college. In other words, robustness does not conceptually imply asymptotic stability.

Alternatively, one may expect asymptotic stability to result from applicants becoming “price-takers” in a large economy; namely, every applicant may simply perceive the colleges' admission cutoffs as fixed and unaffected by her unilateral deviation. While acting optimally against fixed cutoffs might lead to a stable matching, such a price-taking hypothesis cannot be taken for granted even in an arbitrarily large economy.

The lack of price-taking can be illustrated using a version of an example due to roth:82. There are three applicants, ($\theta_1$, $\theta_2$, $\theta_3$), and three colleges, ($a, b$, $c_3$), with one seat each. Applicant preferences and college priority rankings are:

An unstable matching ($\theta_1$--$b$, $\theta_2$--$a$, $\theta_3$--$c_3$) is a Nash equilibrium outcome under DA, with $\theta_1$ and $\theta_2$ adopting TT and $\theta_3$ listing only $c_3$ in her ROL. Applicant $\theta_3$'s deviation to TT, her best possible deviation, is unprofitable, as it activates a chain of rejections that leaves $\theta_3$'s assignment unchanged. Specifically, $\theta_3$ knocks off $\theta_2$ from $a$, who knocks off $\theta_1$ from $b$, who knocks off $\theta_3$ from $a$ to $c_3$. There is a failure of price-taking here. To see this, recall that colleges rank applicants by scores. Suppose that $\theta_1$'s scores at colleges $a$ and $b$ are 1 and 0, respectively; $\theta_2$'s are 0 and 1; and $\theta_3$'s are 0.5 at both colleges. In the unstable equilibrium matching, the cutoffs of colleges $a$ and $b$ are zero, determined by their matched applicant. When $\theta_3$ deviates to TT, the outcome will be the unique stable matching, ($\theta_1$--$a$, $\theta_2$--$b$, $\theta_3$--$c_3$), and the cutoffs of colleges $a$ and $b$ both jump to one. Thus, price-taking is not satisfied.\footnote{Although in a different setting, this example may also help to illuminate Theorems (ref) and (ref). The stable matching ($\theta_1$--$b$, $\theta_2$--$a$, $\theta_3$--$c_3$) is an equilibrium outcome even when applicants do not adopt TT, as in Theorem (ref), e.g., by ranking their matched colleges first. In contradiction to Theorem (ref), the matching ($\theta_1$--$b$, $\theta_2$--$a$, $\theta_3$--$c_3$) is an equilibrium outcome but unstable. Both $a$ and $b$ have a zero cutoff, below $\theta_3$'s score (which is 0.5), and are therefore feasible to $\theta_3$. Applicant $\theta_3$ is assigned her least preferred college, $c_3$, among her feasible colleges, violating stability. In Theorem (ref), we find conditions that eliminate unstable equilibrium outcomes.} Example (ref) in Section (ref) will show that merely increasing the size of the economy does not restore price-taking.

The key step to our results is to re-establish the price-taking behavior (Proposition (ref)), which presents a major challenge compared to the literature acy:15,azevedo/leshno:16,Agarwal-Somaini(2014),Fack-Grenet-He(2015),grigoryan2022convergence. Those papers often study a fixed strategy, which allows them to impose conditions directly on the demand induced by that strategy. In our setting, such an approach would amount to imposing conditions on possible deviations, which is not justified. Instead, we impose conditions on the model primitives by assuming the full support of applicant types. To maintain full support when applicants adopt a strategy, we restrict ourselves to study regular strategies that require TT being played with some arbitrarily low probability.\footnote{The full support assumption can be readily relaxed to allow for uni-dimensional applicant scores, as in Serial Dictatorship. Regularity can also be weakened to mean that there is a positive mass of applicants who report truthfully with some probability.} Intuitively, these two restrictions make it unlikely that a unilateral deviation triggers a massive rejection chain. Without assumptions on demand, we develop novel proof techniques that use the lattice structure of stable matching and the properties of DA (for both sides). We establish that “demand curves” are well-behaved in that an infinitesimal change in demand can only happen if there is an infinitesimal change in cutoffs. Lastly, we show that unilateral deviations do not significantly change demand or cutoffs faced by applicants in large economies.

The above arguments lead us to Proposition (ref), stating that any (possibly non-robust-equilibrium) strategy profile must admit a subsequence of random cutoffs that converge almost surely to a vector of fixed cutoffs {\it uniformly} with respect to any possible unilateral deviation by applicants. This uniform convergence is of independent interest, as it generalizes the existing large economy convergence results. When applicants employ symmetric strategies---a special case of which is TT---, our result implies uniform almost-sure convergence of cutoffs to the cutoffs of the unique stable matching in the limit economy.

This proposition is the key to proving Theorems (ref) and (ref). As the economy grows, the uncertainty about cutoffs vanishes and the set of feasible colleges become apparent to applicants. For their ROL, applicants then know which colleges they can safely omit (hence Theorem (ref)) and which colleges they must include (hence Theorem (ref)). With the price-taking behavior restored, robust equilibrium behavior along {\it each} converging subsequence ensures that stability must hold asympotically, and all such outcomes must converge to the unique stable matching in the limit.

Our Theorems (ref) and (ref) are reassuring news for the theoretical literature on DA. To the extent that outcomes are more important than applicant behavior, the existing results that rely on applicants' truthful behavior are largely robust to applicants' mistakes, at least in large economies.

Our results also yield important implications for empirical research. Strategy-proofness is sometimes taken literally in interpreting applicants' ROLs and leads to the assumption of weak truth-telling (WTT); see, for example, Hallsten:2010 and Kirkeboen_2012. WTT hypothesizes that an applicant ranks her most-preferred colleges truthfully, but may not rank all acceptable colleges. Theorem (ref) calls such an approach into question. When an applicant omits a more-preferred out-of-reach college, WTT infers that that college is less preferred than any college listed in the applicant's ROL, leading to biased estimates. At the same time, an alternative approach that assumes stability of the matching is justified in large enough economies by Theorem (ref). This approach only makes inference about feasible colleges, but “refuses” to infer any preferences over infeasible ones. We illustrate the empirical implications of our theorems in Monte Carlo simulations. WTT estimates have low variance, but are substantially biased when applicants omit out-of-reach colleges.

Even though our results advise caution in relying on TT for preference estimation, they support using TT for the counterfactual analysis of policies. That is, our Theorem (ref) justifies the approach that uses estimated applicant preferences, say based on the stability hypothesis, but simply assumes TT in simulating the outcome, as long as preference estimates are consistent. Despite the fact that applicants may make mistakes, the counterfactual outcome is well approximated by the outcome with TT applicants.

One may be tempted to use an alternative approach to counterfactual analysis in which one skips the estimation step and assumes that an applicant submits the same ROL in both regimes, given that DA is strategy-proof. If applicants play robust equilibrium, this assumption is not theoretically justified: if previously out-of-reach colleges become within-reach for an applicant under the counterfactual, we should not expect her to submit the same ROL. This possibility is not just of academic interest but of significant policy importance, as it arises under many reforms aiming at expanding access by disadvantaged students to high-quality schools. Counterfactual analyses using observed ROLs or using WTT-based estimates are likely to underestimate the impact of such policy by mis-inferring their preferences for high-quality schools that are out of reach under the pre-reform regime. Our Monte Carlo simulations illustrate this point: assuming the same ROLs across two regimes can mis-predict the assignment of 40% of the applicants, and the WTT-based estimates mis-predict 25%. In contrast, the mis-prediction rate is merely 4.5% when we use the stability-based estimates to simulate counterfactual outcomes.

\paragraph{Other Related Literature.}

Our paper is the first to provide a theoretical foundation for stable matching in the presence of mistaken agents and hence lends strong support for using stability in theoretical and empirical studies. There is a long line of theoretical research recognizing that agents may not report truthfully even in a strategically straightforward environment (e.g., li:17,Rabin_Reference-Dependent-DA:2019,Fack-Grenet-He(2015),Meisner2022lossAversion).\footnote{Our results do not apply to strategically complex environments such as those using the Immediate Acceptance (IA) mechanism. IA is not strategyproof, which implies that TT is not necessarily the optimal strategy. How an applicant's sophistication in IA affects her outcome has been studied theoretically Miralles2008:WP,pathak/sonmez:08,acy:11 and empirically he:2017,Agarwal-Somaini(2014),Calsamiglia-Fu-Guell(2014).} Each of these papers offers a specific explanation for such behaviors, often maintaining the assumption that agents are rational in a certain sense. In contrast, we only postulate that the higher the payoff consequences of a mistake are, the rarer the mistake is in equilibrium.\footnote{This is consistent with the evidence reported in Table (ref) that shows that payoff-relevant mistakes are a small fraction of all identified mistakes. Furthermore, shorrer/sovag:2017 find that mistakes are more common when their expected utility cost is lower.} Our approach to accommodating mistakes is consonant with the previous literature on deviations from optimal behavior, e.g., rational inattention sims:03,matejka/mckay:15 and quantal response equilibria mckelvey/palfrey:95. While based on similar ideas, our solution concept is designed for a different goal. We are interested in the implications of mistakes and therefore are agnostic about why agents make mistakes. Compared to these existing concepts, robust equilibrium imposes less structure, and is thus more permissive, on the types of mistakes allowed. At the same time, it is more tractable for our large economy analysis and admits a sharp prediction.\footnote{The rational inattention model and quantal response equilibria, as formalized in the papers cited above, are generally intractable for a rich choice environment like matching where a choice takes the form of a rank-order list.}

Among the papers cited in the above paragraph, only Fack-Grenet-He(2015) (FGH, hereafter) study how non-truthful behaviors affect the stability of DA outcome. They assume fully rational agents and introduce application costs in DA. Deviations from TT occur when the probability of admission to a college is so low that it is not worth paying the application cost. FGH therefore cannot accommodate mistakes that have real payoff consequences. Even though our model is more general than theirs and thus requires new proof techniques, our prediction with respect to equilibrium outcome is sharper: Theorem (ref) shows that every regular robust equilibrium leads to asymptotic stability; in contrast, FGH show that there exists one such sequence of equilibria.

As we are interested in studying the implications of strategic mistakes for stable matching, our motivation and results are similar to kalai:04 and deb/kalai:15. They also study approximate Bayesian equilibrium and show that it implies “hindsight-stability.” Critically, they assume that the effect any participant can unilaterally have on an opponent's payoff is uniformly bounded and decreases with the number of participants in the game. This assumption is tantamount to assuming “price-taking” behavior and does not hold in our setting even in an arbitrarily large economy (Example (ref)). Instead, we derive the result endogenously through elaborate asymptotics of large random economies.

Our setting of random economies is similar to Section IV.B of azevedo/leshno:16 (AL, hereafter). They assume that colleges are overdemanded (i.e., the total college capacity is less than the total number of applicants) and that the gradient of demand is invertible. These assumptions may not hold in our setting and our results do not rely on them.\footnote{{When studying convergence for purposes different from ours, some other papers also relax these conditions. For example, Agarwal-Somaini(2014) do not require overdemandness while maintaining some restrictions on demand; grigoryan2022convergence relaxes both conditions and studies the asymptotics of DA when there may be multiple stable matchings in the limit.}} Further, AL perform price-theory analysis of stable matchings without a game-theoretic framework. Yet, when applicants are allowed to make mistakes, in accord with the evidence, they may not be price-takers even in a large economy. A richer game-theoretical setup makes some of the key results in AL inapplicable. For instance, because applicants can adopt asymmetric strategies and make unilateral deviations, the induced submitted ROLs will not be i.i.d., while AL require i.i.d.\ draws of ordinal preferences. We also allow mixed strategies, so the measure of submitted ROLs, which needs to be well-defined in AL and here depends on both strategies and the measure of types, requires a law of large numbers on the limit economy to be well-defined. That has usual conceptual difficulties Judd_continuum_iid:1985. We thus use a novel technique, exploiting the lattice structure of stability and the properties of DA. {As such, we are able to study the effects of any unilateral deviation by applicants, which is an innovative and necessary ingredient in our analysis.}

\vskip0.5cm

The rest of the paper is organized as follows. We first describe the model primitives in Section (ref). Section (ref) presents the analysis of applicant behavior and outcome under our solution concept. In Section (ref), we provide a sketch of the proofs and highlight the asymptotics of cutoffs with unilateral deviations. The implications of our results for market design are discussed in Section (ref). We conclude in Section (ref).

Model Primitives

Consider an economy, $F^k$, in which $k$ applicants compete for admissions to a finite set of colleges, $\bm{C}=\{c_1, \dots, c_C\}$, $C \geq 2$, under the applicant-proposing Deferred Acceptance algorithm gale/shapley:62. Throughout, we refer to this algorithm simply as DA. A formal definition of DA can be found in Appendix (ref).

Each applicant has a type $\theta=(\bm{u}, \bm{s}) \in \Theta=[\ensuremath{\underline{u}}, \ensuremath{\overline{u}}]^C \times [0,1]^C$, with $\ensuremath{\underline{u}} < \ensuremath{\overline{u}}$ and $\ensuremath{\overline{u}} > 0$. $\bm{u} = (u_1, \dots, u_C)$ is a vector of von-Neumann Morgenstern utilities of attending colleges, and $\bm{s}=(s_1, \dots, s_C)$ is a vector of scores representing the colleges' priorities, such that an applicant with a higher score has a higher priority at a college. We assume that being unassigned, or taking an outside option, gives an applicant a zero utility. Note that $\ensuremath{\underline{u}}$ can be positive or negative. If $\ensuremath{\underline{u}} <0$, an applicant can be assigned to a college with a negative utility and thus incur {some loss relative to her outside option.} {A vector $\bm{u}$ induces ordinal preferences over colleges, denoted by a rank-order list (ROL) $\rho(\theta)$, of colleges with positive utilities of length up to $C$.}

Colleges rank applicants by their scores; college capacities are a $C$-vector $k\cdot \bm{S}^k=[k\cdot \bm{S}]$, where $\bm{S} = (S_1,\ldots,S_C)$, $0<S_c<1$ for all $c$, is a fixed vector and $[\bm{x}]$ is the vector of integers nearest to $\bm{x}$ (rounded down in case of a tie).

The economy $F^k$ is random in that applicant types are drawn identically and independently according to a full-support probability measure $\eta$ over $\Theta$;\footnote{Technically, we can weaken this condition. First, we only need positive density on $\theta \in \left[\max\{\underline{u},0\},\overline{u}\right]^C \times [0,1]^C \subset {\Theta} $. That is, any truthful ROL of length $C$ can be realized. Second, we allow for an important special case where colleges' scores are uni-dimensional, i.e., $s_1 = \dots = s_C$, as in the Serial Dictatorship. In that case, the full-support assumption holds with a reduced dimensionality of support; applicants’ scores are one-dimensional numbers in $[0, 1]$.} the resulting empirical measure is denoted $\eta^k$.

In this matching game, applicant types are private information, while $\eta$ and all other information about the economy is common knowledge. Such a specification corresponds to the matching games summarized in Table (ref) as well as many others in which admissions are based on scores Fack-Grenet-He(2015).\footnote{In these settings, applicants know their scores but do not know the scores or preferences of other applicants. Applicants may form a belief about the “typical” distribution of scores and preferences (captured by $\eta$), but are also aware that the particular distribution they face, $\eta^k$, may differ from the typical distribution. Note that our model does not apply to the setting where priorities are induced by lotteries, such as school choice in New York City abdulkadiroglu/pathak/roth:09,abdulkadiroglu/agarwal/pathak:15,che/tercieux:15b.}

We are interested in applicant behaviors and outcomes in “sufficiently large” economies and thus study the asymptotics of behaviors and outcomes in a sequence of random economies $\{F^k\}_{k \in \mathbb{N}}$. As $k\to \infty$, the number of applicants and college capacities increase proportionally, while the number of colleges is fixed. The sequence of economies $\{F^k\}$ converges in the sense that $\eta^k$ converges in probability to $\eta$ and that $\bm{S}^k$ converges to $\bm{S}$. It is, therefore, convenient, but not crucial, to view $(\eta,\bm{S})$ as the description of the continuum economy that approximates the large finite economies.

Throughout, we assume that colleges are passive and rank applicants according to their scores. By contrast, we allow applicants not to rank colleges truthfully. In each random economy, an applicant's action is to choose an ROL from the set of possible ROLs, $\mathcal{R}$. Applicant $i$'s strategy is a measurable function $\sigma_i: \Theta \mapsto \Delta(\mathcal{R})$. One example is truth-telling, or TT, $\sigma_i(\theta) = \rho(\theta)$, which is a dominant strategy under DA dubins/freedman:81,roth:82. A strategy profile for $\{F^k\}_{k \in \mathbb{N}}$, denoted by $\bm{\sigma}$, is an infinite vector of individual strategies $\bm{\sigma} = (\sigma_1,\sigma_2,\dots)$, with the interpretation that an agent $i$ participates in all economies $k \geq i$, with a fixed strategy $\sigma_i$. That is, applicant $i$'s “identity” is determined by her strategy, $\sigma_i$. Such a strategy profile enables us to keep track of a given applicant as the economy grows. By letting each applicant choose a different strategy, we allow for the possibility of an asymmetric strategy profile. We say $\bm{\sigma}$ is regular if there exists $\gamma > 0$ such that for each $i$ and each $\theta\in \Theta$, $\sigma_i(\theta)$ assigns probability of at least $\gamma$ to playing $\rho(\theta)$.\footnote{A regular strategy need not mean that every applicant reports truthfully with some probability. We can “purify” it by defining a richer type space, with a “truthful” type who always adopts TT.} We denote the truncation of a strategy profile for the economy $F^k$, which omits the strategies of applicants not in $F^k$, by $\bm{\sigma}^k = (\sigma_1,\dots,\sigma_k)$.

DA uses applicants' submitted ROLs, their scores, and college capacities to calculate an outcome. An outcome, or a matching, is defined as a mapping $\mu: C\cup \Theta\to 2^{\Theta} \cup (C\cup \Theta)$ satisfying the usual two-sidedness and consistency requirements. A stable matching is also defined in the usual way to satisfy individual rationality and no-blocking.\footnote{Individual rationality requires that no participant (an applicant or a college) receives an unacceptable match. No blocking means that no applicant-college pair exists such that the applicant prefers the college over her match and the college has either a vacant position or admits another applicant whom the college ranks below that applicant.} When all applicants are TT (i.e., submitting $\rho(\theta)$) under DA, the resulting matching is stable gale/shapley:62.

Given an outcome $\mu$, we define a cutoff vector, $\bm{p} = (p_c)_{c \in C}$, such that college $c$'s cutoff $p_c$ is the lowest score among $c$'s matched applicants, $\mu(c)$, if its capacity is reached, and zero otherwise. When an applicant's score at college $c$, $s_c$, satisfies $s_c\geq p_c$, the college is feasible to her. An outcome is stable if everyone is matched with her most-preferred feasible college. DA ensures stability with respect to submitted ROLs as well as market clearing in the sense that no college admits more applicants than its capacity. When we consider a random economy $F^k$ operated by DA, the cutoffs, which depend on applicants' realized types via $\bm{\sigma}^k$, are random. We denote random cutoffs in $F^k$ by $\bm{P}^k = (P_c^k)_{c \in \bm{C}}$.\footnote{Our analysis will also consider any arbitrary, non-random cutoff vector, $\bm{p}$, that need not clear the market. We then let applicants {\it demand} their highest-ranked feasible colleges given such $\bm{p}$ in their ROLs. }

Analysis of Robust Equilibria

To accommodate the types of dominated strategies documented in empirical studies, we introduce the following solution concept:\footnote{A number of authors adopted a similar $\epsilon$-based solution concept to analyze approximate equilibrium behavior (see kalai:04, deb/kalai:15, azevedo/budish:15, and che/tercieux:15b, for instance).}

Note that robust equilibrium relaxes the exact Bayesian Nash solution concept by allowing for mistakes that are payoff insignificant in a large economy.\footnote{In this sense, our concept of robustness differs from another notion of “robustness,” or “incentives in the large” (see che/kojima:10, liu/pycia:11, azevedo/budish:15, che/tercieux:15b, and pycia:19, for example). This latter concept refers to the property of a mechanism (rather than a solution concept) which provides asymptotic incentives for agents to report truthfully, even though truth-telling may not be an exact equilibrium behavior in a finite economy. By contrast, the current notion permits possible deviations from truth-telling even when it is a dominant strategy.} Such relaxation is necessary to accommodate mistakes in a finite economy. If cutoffs were known with certainty, a non-TT strategy, such as ranking only the most preferred feasible college with respect to the known cutoffs, may do just as well as TT in the continuum economy. However, such a strategy may not be optimal in a finite random economy because cutoffs are random, and a non-TT strategy may result in a payoff loss with a positive probability.\footnote{The distinction between fixed cutoffs and the cutoffs of a large but finite economy matters. Indeed, suppose that an applicant's score at her best feasible college $c$ is precisely this college's fixed cutoff $p_c$. Then the applicant can submit an ROL that contains only $c$ and still suffer no payoff loss. Yet, no matter how large the economy is, submitting only $c$ would entail a loss because $c$'s cutoff is random and can be above her score with positive probability.} Hence, we instead require the equilibrium strategies to entail insignificant payoff loss in any sufficiently large but finite economies.

Below we investigate the implications of this relaxation. In particular, we ask: Does the robustness concept imply that most applicants report their preferences truthfully? Our first result shows that this is not the case. In fact, a robust equilibrium need not satisfy an even weaker notion of TT, weak truth-telling (WTT), which allows applicants to truncate their truthful ROL $\rho(\theta)$ from below. To show that WTT may not hold, we construct a robust equilibrium in which all but a vanishing fraction of applicants adopt non-WTT strategies.

To begin, we define a stable-response strategy (SRS) against an arbitrary, non-random cutoff vector ${\bm{p}}$ as any strategy whereby an applicant demands the most preferred feasible college given ${\bm{p}}$ (i.e., she ranks that college ahead of all other feasible colleges). The set of SRSs is typically large. She could skip infeasible colleges, rank them ahead of feasible ones, or flip their order relative to her true preferences. For a specific example, suppose that $\bm{C}=\{1,2,3,4\}$, an applicant's true preference order is $1\-2\-3\-4$, and 2, 3 and 4 are feasible for her. Then, out of the 65 ROLs she can choose from, 21 are SRS, including ROLs 2-4-3-1, 2-4-1-3, 2-1-4-3, 1-2-4-3, and 2-4-3 which do not even respect the true preference order among the ranked colleges. For each type $\theta=(\bm{u},\bm{s})$, there exists at least one SRS that violates WTT.\footnote{This can be shown as follows. If an applicant's most preferred college is infeasible (i.e., its cutoff at ${\bm{p}}$ is above the applicant's score at that college), then she can simply drop that college and rank order the remaining colleges truthfully. The resulting strategy is SRS but fails WTT. If an applicant's most preferred college is feasible, then she can rank that college at the top of her ROL but rank the remaining colleges untruthfully (in relative rankings). Again, the resulting strategy is an SRS but violates WTT.}

Next, we consider a set of applicant types: $$\Theta^{\delta}(\bm{p}):=\left\{(\bm{u},\bm{s})\in \Theta \mid \exists j \in \bm{C} \mbox{ s.t. } |s_j - {p}_j|\le \delta\right\}.$$ Although we define this set for arbitrary cutoffs $\bm{p}$, we are interested in $\Theta^\delta(\overline\bm{p})$, where $\overline\bm{p}$ are the cutoffs in the limit economy when all applicants report truthfully; we formally define $\overline\bm{p}$ in Appendix (ref). $\Theta^\delta(\overline\bm{p})$ collects all applicants whose score is close to $\overline\bm{p}$ for at least one college. These applicants are required to be TT, but all other applicants---an arbitrarily large fraction of applicants for small $\delta$---adopt non-WTT SRSs against $\overline\bm{p}$ with an arbitrarily high probability. Theorem (ref) below shows that these strategies constitute a robust equilibrium. When the cutoffs in the sequence of random economies where applicants play such strategies converge to $\overline{\bm{p}}$, the loss from adopting the SRSs vanishes, hence Theorem (ref). It turns out that proving cutoff convergence is non-trivial, which we will revisit in Section (ref).

Since $(\delta, \gamma)$ is arbitrary, the following striking conclusion emerges.

To the extent that a robust equilibrium is a reasonable solution concept, Theorem (ref) implies that we should not be surprised to observe a non-negligible fraction of participants making “mistakes”---more precisely, playing dominated strategies---even in a strategy-proof environment. Importantly, even among the colleges that an applicant includes in her ROL, the order may not respect her true preferences. This result raises some concerns about the empirical methods relying on WTT---any particular strategy relying on ROL data for that matter---as an identifying restriction.

If strategic mistakes undermine the prediction of applicant behavior, do they also undermine the stability of the outcome? This is an important question on two accounts. First, if mistakes jeopardize stability in a significant way, the rationale for using DA---to ensure a stable matching---should be called into question. Second, stability is widely used as an empirical identification assumption Fox(2009)Palgrave,Agarwal2015, Fox_Bajari:2013,Chiappori-Salanie(2015)JEL,Fack-Grenet-He(2015), HSS. Our second theorem shows that mistakes captured by robust equilibrium leave the stability property of DA largely unscathed. We begin by defining a notion of approximate stability in large economies.

We now state the main theorem:

While Theorem (ref) already provides some justification for stability as an identification assumption for a sufficiently large economy, a question arises as to whether the concept of robust equilibrium would predict the same outcome as would emerge had all applicants reported their preferences truthfully. Our answer is in the affirmative:\footnote{This result is reminiscent of the upper hemicontinuity of Nash equilibrium correspondence fudenberg/tirole:91. The current result is slightly stronger, however, since it implies that a sequence of $\epsilon$-BNE (which is weaker than BNE) converges to an exact BNE as the economy grows large.}

Although Theorem (ref) questions TT as a behavioral prediction, Corollary (ref) supports TT as a means for predicting an outcome. In this sense, the corollary validates the vast theoretical literature on DA that assume truth-telling. This result also suggests that when one evaluates the outcome of a counterfactual scenario involving DA, one can simply assume that applicants report their preferences truthfully in that scenario, as we will do in Section (ref).

Taken together, our two theorems provide very different implications for the behavior and outcome under DA. On the one hand, the behavioral prediction exhibits multiplicity and possibly a drastic departure from truth-telling. On the other, the prediction in terms of outcome is virtually unique, and the outcome is virtually the same as if all applicants reported their preferences truthfully. This latter finding should ultimately be reassuring about the performance of DA.

The next section describes proof sketches of Theorems (ref) and (ref) and highlights the challenges in proving asymptotic stability. We also present novel results on cutoff convergence that significantly extends the existing results in azevedo/leshno:16 and may be of interest in their own right. A reader who is more interested in an in-depth discussion of the implications for empirical studies may skip to Section (ref).

Proof Sketches: Cutoff Convergence and Asymptotic Stability

To prove Theorems (ref) and (ref), we need to establish that the cutoffs in random economies, with applicants being able to unilaterally deviate, are still concentrated around those arising from TT. A crucial step towards this goal is to re-establish applicants' price-taking in large economies. Before sketching out our proof, we present an example to illustrate that such price-taking cannot be taken for granted, even in arbitrarily large economies.

One expects that this failure of price-taking behavior can be avoided with a sufficient “smoothness” in the economy. This is indeed the case with our economy where $\eta$ has full support and the types in $\eta^k$ are i.i.d.\ from $\eta$. Given this, any regular strategy profile leads to the necessary smoothness in cutoff responses when an applicant deviates to TT unilaterally. Although this seems intuitive, it is not trivial to establish the price-taking behavior formally.

To this end, we consider any arbitrary regular strategy profile $\bm{\sigma}$. For any random $k$-economy $F^k$, the truncated profile $\bm{\sigma}^k$ induces random cutoffs denoted by $\bm{P}^k_{(0)}(\bm{\sigma}) \in [0,1]^{C}$. Now suppose each applicant $i\in \mathbb{N}$ unilaterally deviates to TT. The corresponding truncated profile for $F^k$, denoted $\bm{\sigma}^k_{(i)}$, induces another set of random cutoffs $\bm{P}^k_{(i)}(\bm{\sigma}) \in [0,1]^{C}$.\footnote{Note that if $i$ is not in the $k$-economy $F^k$, i.e., $i>k$, then $\bm{\sigma}^k_{(i)} = \bm{\sigma}^k$ and $\bm{P}^k_{(i)}(\bm{\sigma}) = \bm{P}^k_{(0)}(\bm{\sigma})$.}

To establish the price-taking behavior in large economies, one needs to show that the cutoff profiles $\bm{P}^k_{(i)}(\bm{\sigma})$ for each $i\in \mathbb{N}$ become arbitrarily close to $\bm{P}^k_{(0)}(\bm{\sigma})$ uniformly with high probability as $k\to \infty$. Since $\bm{\sigma}$ could be asymmetric across all applicants, each profile $\bm{\sigma}^k_{(i)}$ is potentially distinct, making the resulting cutoff profiles $\bm{P}^k_{(i)}$ distinct across all $i\in \mathbb{N}\cup\{0\}$. Hence, price-taking behavior in a sequence of economies would hold if the infinite family of cutoffs $(\bm{P}^k_{(i)})_{i\in \mathbb{N}\cup\{0\}}$ converges uniformly almost surely to some cutoff vector $\overline {\bm{p}}$. It turns out that such convergence may not hold for an arbitrary asymmetric $\bm{\sigma}$: the example in Appendix (ref) shows that the cutoffs cycle across distinct values (instead of converging). Nevertheless, we can show that there is always a subsequence of economies such that the cutoffs induced by $\bm{\sigma}$ in that subsequence converge to some deterministic vector. This turns out to be sufficient for our purposes. On the other hand, if $\bm{\sigma}$ is symmetric, all our results can be stated for the whole sequence of economies.

Proposition (ref) is interesting in its own right as it generalizes AL's result on cutoff convergence with truth-telling applicants (part 2 of their Proposition 3). First, while the existing literature shows convergence of cutoffs when applicants adopt TT, the second part of Proposition (ref) establishes convergence for {\it any} regular symmetric strategies. We also allow for unilateral deviations and show that convergence of cutoffs is uniform over an infinite family of cutoffs resulting from such deviations. This will prove useful for our analysis. In fact, the first part establishes the same uniform convergence albeit on a subsequence of economies. Second, we do not require that $\sum_{c=1}^C S_c < 1$ (over-demanded systems); dropping this requirement may be practically important, as many matching markets, such as school choice, are not overdemanded. We also do not need that $\partial \bm{D}(\overline{\bm{p}}(\bm{\sigma}))$ is invertible, as was required by AL, where $\bm{D}(\overline{\bm{p}}(\bm{\sigma}))$ is the vector of demand for colleges at cutoffs $\overline{\bm{p}}(\bm{\sigma})$, which is to be formally defined below. It is not clear whether this property holds under an arbitrary regular symmetric strategy $\bm{\sigma}$.

Theorem (ref) builds on the second part of Proposition (ref). Recall that the strategy profile we construct for the theorem is regular and symmetric across all applicants. Hence, the cutoffs resulting from the constructed strategies as well as those resulting from the most profitable unilateral deviation (namely, to TT) all converge to some deterministic cutoff vector $\overline{\bm{p}}$. Further, the constructed strategies guarantee that all applicants adopt SRS against $\overline{\bm{p}}$ with high probability as the economy grows large. This means that the constructed strategies must form a robust equilibrium, and in that equilibrium, with high probability, all applicants must obtain their stable matches. Since our limit economy admits a unique stable matching, this means that $\overline{\bm{p}}=\overline{\bm{p}}(\bm{\rho})$, the cutoffs that would emerge in the limit if all applicants employed TT. In other words, the cutoffs from the constructed strategy profile converge to $\overline{\bm{p}}(\bm{\rho})$, even though almost no one employs TT. These observations lead to Theorem (ref).

Meanwhile, Theorem (ref) crucially uses the first part of Proposition (ref), namely the uniform convergence on a subsequence of economies. Fix any regular robust equilibrium $\bm{\sigma}$. Suppose by way of contradiction that $\bm{\sigma}$ is not asymptotically stable. Then, there must be a subsequence of economies such that, with non-vanishing probability, a non-vanishing proportion of applicants do not get their favorite feasible colleges given the prevailing cutoffs along that subsequence. Proposition (ref) then ensures that there is a cutoff vector $\overline{\bm{p}}(\bm{\sigma})$ and a further subsequence (of the subsequence) of economies such that the cutoffs induced by $\bm{\sigma}$ converge to $\overline{\bm{p}}(\bm{\sigma})$ along that sub-subsequence. Given the asymptotic instability, we can then easily identify a set of applicants who would suffer discrete payoff losses from their matches given $\overline{\bm{p}}(\bm{\sigma})$. Recall further from uniform convergence that if any such applicant were to deviate to TT, it will not alter the cutoffs much. This in turn implies that the applicant would enjoy a discrete payoff gain from the deviation. Then, $\bm{\sigma}$ could not have been a robust equilibrium, delivering a desired contradiction.

We close this section by sketching the proof of Proposition (ref). Recall the cutoffs are defined to clear markets. Hence, to study how such cutoffs behave in large economies, we must first study how the demand system behaves in large economies. To this end, we consider the “empirical” demand induced by $\bm{\sigma}$ for each college $c$ at any fixed cutoffs $\bm{p}$:

where $\arg\max_{\text{w.r.t. } R_{j}}$ picks the highest-ranked college in $R_j$ from the set of feasible colleges $\left\{c'\in C:s_{j,c'}\geq p_{c'}\right\}$ and $\mathbb{I}\{\cdot\}$ is an indicator function. In words, $D^{k}_{c}(\bm{p})$ is the fraction of applicants in economy $F^k$ for whom $c$ is the best feasible college, given a fixed strategy $\bm{\sigma}$, which we suppress in the notation below, and fixed cutoffs $\bm{p}$. These cutoffs are not necessarily market-clearing. The demands for all colleges form the vector $\bm{D}^{k}(\bm{p})$, or $\bm{D}^{k}_{(0)}(\bm{p})$. We are interested in an infinite family of demand systems $\{\bm{D}^{k}_{(i)}(\bm{p})\}_{i\in \mathbb{N}\cup \{0\}}$ which also include the demand vectors that result from a unilateral deviation of applicant $i$ to TT.

Note that, the demand system thus defined is random, but, for each $\bm{p}$, as the economy grows large, $\bm{D}^{k}_{(i)}(\bm{p})$ converges pointwise to its expectation $\overline\bm{D}^{k}_{(i)}(\bm{p})$ mcdiarmid:89. Meanwhile, the (deterministic) functions $\overline\bm{D}^{k}_{(i)}(\bm{p})$ are Lipschitz-continuous and, by the Arzela-Ascoli theorem, there is a subsequence $\overline\bm{D}^{k_\ell}_{(i)}(\bm{p})$ that converges to some Lipschitz-continuous function $\overline{\bm{D}}(\bm{p})$. Then, using an argument in the spirit of the Glivenko-Cantelli theorem, we show that the random demands $\bm{D}^{k_{\ell}}_{(i)}(\cdot)$ converge uniformly (with respect to both its argument and $i$) to $\overline\bm{D}(\cdot)$ almost surely. Note that if $\bm{\sigma}$ is symmetric, the above convergence results apply to the whole sequence.

Having established the convergence of random demand functions, we then show by induction on the steps of DA that the random cutoffs $\bm{P}^{k_\ell}_{(i)}$, which clear random demands $\bm{D}^{k_\ell}_{(i)}(\cdot)$, converge to $\overline{\bm{p}}$, which clears $\overline{D}(\cdot)$. To this end, we view $\bm{P}^{k_\ell}_{(i)}$ and $\overline{\bm{p}}$ respectively as the limiting outcomes of the monotonic cutoff adjustment processes that occur in the DA algorithms of random-$k$ and the continuum economies. Specifically, each step $m$ of the DA proposal/acceptance adjusts cutoff $P^{k_\ell,m}_{(i),c}$ or $p^m_{c}$ to clear the market tentatively. We are interested in the cutoffs arising in each step of the adjustment process because (i) they converge respectively to cutoffs $\bm{P}^{k_\ell}_{(i)}$ and $\overline{\bm{p}}$, the two key objects in Proposition (ref) and (ii) we can bound the difference between the cutoffs from each step. We obtain the upper and lower bounds by defining this adjustment process for both the applicant- and college-proposing versions of DA and using the lattice structure of cutoffs and uniqueness of stable matching in the limit economy azevedo/leshno:16.

We show that, for large enough $k_\ell$, the difference between $\bm{P}^{k_\ell,m}_{(i)}$ and $\bm{p}^{m}$ is arbitrarily small in each step of DA using an induction argument. For the step $m=1$, the argument relies on the full-support assumption and the regularity of $\bm{\sigma}$. For $m>1$, the argument uses the convergence of random demands to limit demand and the Lipschitz continuity of limit demand in cutoffs.

Summarizing the arguments in the last two paragraphs, we have established that the difference between $\bm{P}^{k_\ell,m}_{(i)}$ and $\bm{p}^{m}$ is small for all $m$, and that the former converges to $\bm{P}^{k_\ell}_{(i)}$, while the latter converges to $\overline{\bm{p}}$. Taken together, the difference between $\bm{P}^{k_\ell}_{(i)}$ and $\overline{\bm{p}}$ is small, delivering the proposition.

The argument tracking the monotonic tatonnement process, which allows us to prove the uniform convergence without imposing restrictive assumptions, is new in the large market asymptotic analysis and will be useful beyond the current context.

Implications for Market Design Research

Our theoretical results, along with existing the field evidence, suggest that non-truthful behavior may be widespread but it rarely leads to significant payoff consequences. This observation has implications for empirical market design. In simulated data, we illustrate these implications for two exercises that are common in the literature: {(a) estimation of applicant preferences and (b) analysis of a counterfactual policy.}

Estimating Applicant Preferences

There are two typical identifying assumptions in the literature for the estimation of applicant preferences.

The first is WTT Hallsten:2010,Kirkeboen_2012. Recall that applicant $i$ is WTT if her submitted ROL ranks her most-preferred colleges according to her true preferences, while every unranked college is less desirable to $i$ than any ranked college. Let $\succ_i$ denote the inferred preference relation of $i$. As an example, consider an applicant whose submitted ROL is $c_3$-$c_1$, while there are four colleges available, $\{c_1,c_2,c_3,c_4\}$. WTT infers that $c_3 \succ_i c_1 {\succ_i c_2,c_4}$.

The second assumption is stability Akyol-Krishna(2017):EER,Bucarey(2018),Fack-Grenet-He(2015),Combe_Tercieux_Terrier_2022. An outcome is stable if every applicant is matched with her most-preferred college among the feasible ones. Suppose that the aforementioned applicant has $c_2$ and $c_3$ feasible and is matched with $c_3$. Stability infers $c_3 \succ_i c_2$. In contrast to WTT, stability does not make any inference about infeasible colleges, $c_1$ and $c_4$.

According to our Theorem (ref), in a robust equilibrium, applicant $i$ may not be WTT, in which case preference inference would be incorrect. For example, she may rank more desirable but infeasible $c_4$ arbitrarily. Stability makes inference only about feasible colleges and, according to our Theorem (ref), is satisfied asymptotically. Moving from WTT to stability, we gain robustness to untruthfulness but utilize less information. Therefore, the estimation based on stability will be less efficient than WTT, yet less likely to be biased because it uses fewer possibly incorrectly inferred preference relations.

Monte Carlo Simulations

We evaluate the performance of WTT and stability in simulated data that resembles the typical college admissions studied in the previous sections. There are 12 colleges and 1800 applicants. This matching market is operated by a Serial Dictatorship, a special case of DA, in which colleges rank applicants by an ex-ante known score. Applicant preferences follow a conditional logit model. Specifically, applicant $i$'s utility from being matched with college $c$ is:\footnote{We keep our Monte Carlo setting as simple as possible to illustrate our main points. It, therefore, ignores some potential challenges in practice. For example, in a real-life setting, factors affecting an applicant’s priority scores may directly enter their preferences. This is true if priority scores depend on an applicant's distance to colleges or academic ability. This may cause issues in the non-parametric identification of applicant preferences when one assumes stability; see Fack-Grenet-He(2015) for a detailed discussion on sufficient conditions for identification.}

where $\beta_1 \cdot c$ is college $c$'s baseline quality; $d_{i,c}$ is the distance from applicant $i$'s location to college $c$; {$T_{i}\in \{0,1\}$} is applicant $i$'s type (e.g., disadvantaged or not); $A_{c}\in \{0,1\}$ is college $c$'s type (e.g., known for resources for disadvantaged applicants); $Small_c=1$ if college $c$ has a small capacity, 0 otherwise; and $\epsilon_{i,c}$ is a type-I extreme value and i.i.d.\ across $i$ and $c$.

In the simulations, $T_i$ is equal to one for two-thirds of the applicants whose score is below the median, and we thus call them disadvantaged.

We consider three data generating processes (DGPs). The first is the Truth-Telling (TT): every applicant truthfully ranks all colleges. The other two DGPs rely on a simulated cutoff distribution that we calculate from 1000 simulation samples with truth-telling applicants. Specifically, the second DGP is Payoff Irrelevant Mistakes (PIM): a fraction of applicants skip colleges with which they would never be matched according to the simulated cutoff distribution. Those never-matched colleges for an applicant are likely to be almost always out of reach to her. Hence, PIM approximates the documented behavior that applicants choose not to apply to colleges at which they have a close-to-zero chance. We expect that stability is satisfied in both TT and PIM. The last DGP is Payoff Relevant Mistakes (PRM): in addition to skipping those never-matched colleges, applicants may skip some colleges with which they have a low match probability according to the simulated cutoff distribution, leading to some payoff-relevant mistakes or violations of stability. According to our theory, such payoff-relevant mistakes, although rare, can happen in a robust equilibrium of a finite economy. The three DGPs, each of which has 150 simulation samples, are summarized in Table (ref).

With the simulated data, we estimate the four unknown parameters, $(\beta_1, \dots, \beta_4)$, in equation (ref). We apply a rank-ordered logit model when assuming WTT and a conditional logit model when assuming stability to estimate four parameters. Appendix (ref) provides more details.

\paragraph{Bias-variance tradeoff.} Figure (ref) illustrates several patterns in the estimation for one of the parameters, $\beta_1=0.3$. When applicants report truthfully, WTT and stability are both consistent but WTT is more efficient (panel a). However, WTT leads to a biased estimator whenever some applicants are not truthful, i.e., {under the PIM and PRM DGPs} (panels b--c). In contrast, stability performs well when there are no, or just a few, payoff-relevant mistakes. {These results illustrate a bias-variance tradeoff: from WTT to stability, the variance of the estimator increases while the bias decreases whenever it exists.}

\paragraph{Mis-Estimated Preferences.} A direct consequence of an inconsistent estimator is the mis-estimation of applicant preferences. As an example, let us consider colleges 10 and 11. For a disadvantaged applicant ($T_i=1$) with an equal distance to these two colleges, the true probability that she prefers college 11 to college 10 is $0.91$ (the straight, dashed line in Figure (ref)). Using the logit formula, we calculate the same probability based on the two sets of estimates, and Figure (ref) presents the average across the 150 samples given an estimation approach and a DGP. Clearly, WTT produces significant biases in PIM and PRM, while stability only leads to a small bias in PRM.

Counterfactual Analysis

Making policy recommendations based on counterfactual analysis is one of the main objectives of market design research. Our theoretical results have some implications for this objective too.

The literature has two types of approaches to counterfactual analysis. The first is based on submitted ROLs. See, for example, the analysis of the National Resident Matching Program by roth/peranson:99 and kindergarten allocation in Estonia by Veski/etal:2016. It is assumed that submitted ROLs under the existing policy are true ordinal preferences and that an applicant will submit the same ROL under the counterfactual policy. Our Theorem (ref) implies that this assumption need not hold in a robust equilibrium.

In the second type of approaches, the researcher uses estimated preferences and let every applicant submit a truthful ROL under the counterfactual policy. Assuming truth-telling in the counterfactual is justified by Corollary (ref), as any regular robust equilibrium leads to an asymptotically stable matching that is well approximated by the stable matching from truthful reporting. However, this approach crucially relies on the preference estimates being unbiased, because biased estimates will only lead to a misleading prediction about the counterfactual. Section (ref) has presented the two possible assumptions for preference estimation, WTT and stability. It is therefore important to choose the appropriate one.

As an illustration, we use the Monte Carlo simulations in Section (ref) and consider a counterfactual policy in which applicants with $T_i=1$ are given priorities over those with $T_i=0$, while applicants of the same type are still ranked according to their scores. The mechanism is still DA in which everyone can rank all colleges.

Performance in Monte Carlo Simulations

Recall that we have 150 samples in the simulations for each DGP (TT, PIM, or PRM). Additionally, for each DGP, we generate the true outcome under the counterfactual as a benchmark. That is, we assume applicants potentially make mistakes under the counterfactual policy as they do under the current policy.

We focus on the three approaches to counterfactual analysis: submitted ROLs, the WTT-based estimation, and the stability-based estimation. We calculate how each approach perform in terms of predicting the new policy's effects on outcomes and on welfare.

\paragraph{Mis-predicted Cutoffs.} An informative statistic of an outcome is college cutoffs. Figure (ref) shows, given each DGP, how the three approaches mis-predict cutoffs under the counterfactual policy. For each college, indexed from 1 to 12, we calculate the average difference between the predicted cutoffs and the true cutoffs across the 150 simulation samples.

In panel (a), the DGP is TT, and thus the submitted ROLs coincide with true ordinal preferences. Consequently, the predicted cutoffs from the submitted-ROLs approach are the true ones. The other two approaches also lead to almost the same cutoffs.

In panel (b), which corresponds to DGP PIM, only the stability-based estimation is consistent, and indeed it has the smallest mis-predictions relative to the other two. As applicants tend to omit popular colleges, which have higher indices in our setting, from their submitted ROLs in this DGP, the approaches based on WTT and submitted ROLs systematically underestimate the demand for these colleges and thus their cutoffs.

When the DGP contain payoff-relevant mistakes (PRM, in panel c), none of the approaches is unbiased. However, the stability-based estimates seem to have a negligible mis-prediction compared to the other two.

\paragraph{Mis-predicted Matches.}

Panel (a) of Figure (ref) further shows {the extent to which} each of the three approaches mis-predicts individual outcomes for applicants with $T_i=1$. Recall that the counterfactual policy is intended to help those applicants. The stability-based approach incorrectly predicts the match for $4.5$ percent of applicants on average in DGPs TT and PIM. Even in PRM, its mis-prediction rate is merely 7.7 percent. The WTT-based approach has a lower mis-prediction rate in DGP TT but under-performs relative to stability in the other two DGPs. The submitted-ROLs approach has the highest mis-prediction rates in all DGPs except TT. Among the applicants with $T_i=0$, Figure (ref) in Appendix (ref) shows that the comparison of the approaches follows the same pattern.

\paragraph{Mis-predicted Welfare Effects.}

We now investigate the welfare effects on the $T_i=1$ applicants of the counterfactual policy. Given a simulation sample and a DGP, we compare the outcomes of each applicant under the two policies. If the applicant is matched with a “more-preferred” college according to the true/estimated preferences, she is a winner; she is a loser if she is matched with a “less-preferred” one.\footnote{Because each approach to counterfactual analysis estimates applicant preferences in a unique way, an applicant's utility associated with a college can differ across the approaches. Therefore, the measured welfare effects of the counterfactual policy may differ even when an applicant is matched with the same college.}

Panel (b) of Figure (ref) shows the difference between the fractions of winners and losers, averaged across the 150 samples.\footnote{The outcome does not change for 9--28 percent of applicants. See Table (ref) for more detailed summary statistics.} Among the $T_i=1$ applicants, the stability-based estimates are almost identical to the truth, even in the DGP with payoff-relevant mistakes (PRM). In contrast, the other two approaches' predictions are close to the true value only in DGP TT; both tend to be biased toward a zero effect when applicants make mistakes (DGPs PIM and PRM). The reason for the bias is clear. Under WTT, the preferences for popular colleges are underestimated. Meanwhile, the submitted-ROLs approach ignores the likely changes in ROLs under the new policy. In particular, disadvantaged applicants find previously out-of-reach colleges now within reach, so they may include these colleges in their ROLs.

Despite being shown in simulations, these findings may provide important implications for policymaking, especially in public education. For example, many recent policy initiatives are designed to increase access to high-quality colleges and schools by traditionally disadvantaged students. Such an affirmative-action policy precisely changes popular schools from out-of-reach to within-reach for disadvantaged students. To predict the effects of such a policy, only the stability-based estimates can perform well if students may have chosen not to apply to some out-of-reach schools in the regime without affirmative action.

Conclusion

Motivated by field evidence on non-truthful behavior in strategy-proof environments, we theoretically argue, using a robust equilibrium concept, that an outcome of DA can be reliably predicted, but not participants' behavior. Moreover, in a sufficiently large economy, the outcome approximates well the one that would have emerged if every participant plays the dominant strategy. While this result justifies the vast theoretical literature that assumes truthful reporting behavior to analyze outcomes of DA, it calls into question empirical methods that take truthful reporting as a literal behavioral prediction. Our theory suggests that {the alternative approach} focusing on the stability property of the outcome may be robust to applicant mistakes. These implications are relevant to the estimation of participant preferences and counterfactual analysis.

Our paper focuses on environments where applicants know their scores according to which colleges rank them. However, the general insights can be extended to other settings, for example, where applicants are ranked by colleges according to a post-application lottery. CHH, an ongoing project, provide such an extension.

\setstretch{1.02}