Yinghua He
email: yinghua.he@gmail.com.

Thierry Magnac
email: thierry.magnac@tse-fr.eu.

Christophe Lévêque

Application Costs and Congestion in Matching Markets *

Keywords: C78, D47, D50, D61, I21 Gale-Shapley Deferred Acceptance Mechanism, Costly Preference Formation, Screening, Stable Matching, Congestion, Matching Market

A matching market often requires recruiting agents, or "programs," to costly screen "applicants," and congestion increases with the number of applicants to be screened. We investigate the role of application costs: Higher costs reduce congestion by discouraging applicants from applying to certain programs; however, they may harm match quality. In a multiple-elicitation experiment conducted in a real-life matching market, we implement variants of the Gale-Shapley Deferred-Acceptance mechanism with different application costs. Our experimental and structural estimates show that a (low) application cost effectively reduces congestion without harming match quality.

Introduction

In many commonly observed matching markets, agents on one side, called "programs" (e.g., employers or colleges), actively recruit agents on the other side, called "applicants" (e.g., employees or students). The matching process usually includes an application stage, in which applicants submit their candidacy to programs of their choice; it is followed by a screening stage, in which each program costly screens and ranks its candidates.

Due to massive advancements in both information technology and market design, there has been a welcomed trend toward applicants applying to a larger number of programs. For instance, in the job market for new graduates of PhD programs in economics, the centralized platforms -EconJobMarket and AEA Job Opening for Economists -have dramatically reduced the application cost associated with submitting a job application. As a result, hiring departments now screen many more candidates [START_REF] Nguyen | Can EconJobMarket help Canadian universities?[END_REF].

While the traditional matching theory considers application cost as a market friction (see, e.g., [START_REF] Rogerson | Search-Theoretic Models of the Labor Market: A Survey[END_REF] and welcomes these new developments, a practical issue has emerged: Programs must screen many more applicants and pay a high cost, which can be considered as a symptom of market congestion. Costly screening to form preferences is common in real-life scenarios. Recruiting programs have enough information to rank applicants only after reviewing their files or conducting interviews. When programs receive too many applications, congestion occurs, and matching outcomes can be (constrained) inefficient [START_REF] Arnosti | Managing congestion in dynamic matching markets[END_REF].

These observations motivate us to consider application cost as a tool to manage congestion. Applicants apply to fewer programs when the application cost is higher, which mitigates market congestion. However, the total welfare effects, including those on match quality, are ambiguous because a high application cost may preclude some efficient matches.

In a setting of many-to-one matching without transfers, we provide the first empirical evidence on the performance of a set of popular market designs with different schemes of application costs. We hypothesize that when designed appropriately, an application cost can enhance welfare by balancing match quality and screening costs. Inspired by practical market designs, we consider two forms of application cost: A positive marginal cost and an application limit, both of which are used in real-life matching markets. 1Our research design is original in that it marries real-life, experimental data with a structural analysis. We implement a multiple-elicitation experiment in which application costs vary across market designs. The experiment allows the effects of application costs on congestion and match quality to be evaluated directly. Experimental variation in market design in the field is, however, necessarily limited, and we further conduct comprehensive counterfactual analyses based on the estimation of a structural model.

We focus on two dimensions of a matching outcome: the congestion/screening costs, measured by the number of applicants to screen, and match quality, measured by the numbers of blocking pairs, the number of unmatched applicants, and the welfare of both sides.

A pair of applicant and program blocks a matching, if both would be better off by being matched together after leaving their current matches. The stability of a matching, defined as the absence of any blocking pair, is the key to the success of matching markets (Roth, 1991). Importantly, stability implies Pareto efficiency when both sides are endowed with strict preferences [START_REF] Abdulkadiroglu | Matching markets: Theory and practice[END_REF].

Our experiment involves the real-life matching of 129 applicants to the 7 master's programs at the Toulouse School of Economics (TSE) and was conducted in May 2013 for admission in the 2013-14 academic year. The experimental market designs are three variants of the Gale-Shapley Deferred-Acceptance mechanism (DA) encountered in practice:

The traditional DA, under which applicants can apply to all programs without any cost; DA with truncation (DA-T), under which applicants can apply to no more than four programs; and DA with cost (DA-C), under which applicants must write a motivation letter for each additional application beyond the first three applications. Under each mechanism, every applicant is required to submit a rank-ordered list of programs (ROL). As applicants are informed that one of the mechanisms will be implemented, they have incentives to behave optimally under each mechanism.

Our direct experimental evaluation shows that both DA-T and DA-C reduce the screening cost of programs without significantly harming match quality. On average, relative to DA without cost which results in 75 applications per program, each program receives 13 fewer applications under DA-T and 16 fewer under DA-C. Such reductions in congestion are substantial despite the applicant preferences being rather heterogenous -85% of the applicants always obtain their most-preferred program across the market designs.

In our second empirical approach, the structural analysis, we need information on applicant and program preferences as well as applicant beliefs. Because of the strategy-proofness of DA [START_REF] Dubins | Machiavelli and the Gale-Shapley Algorithm[END_REF][START_REF] Roth | The Economics of Matching: Stability and Incentives[END_REF] and because we announce in the experiment that it is optimal for applicants to report their true preferences under DA, ROLs submitted by applicants under DA are assumed to reveal their true ordinal preferences.

We supplement this information with a survey in which each applicant reports whether a program is unacceptable to her. This leads to an extended version of the exploded logit model for the estimation of applicant cardinal preferences. Furthermore, program preferences are estimated using their observed ranking of applicants. Applicant beliefs are derived from an applicant's (incomplete) information on other applicants' preferences and on how each program ranks her. Assuming rational expectations and a common prior, we construct applicant beliefs from estimated parameters governing program and applicant preferences.

We then simulate the equilibrium outcomes of various configurations of DA-T and DA-C. DA-T can be of any degree K, where K t1, ..., 7u is the number of choices an applicant is allowed to submit. Constant marginal costs for every application in DA-C take various values over a wide range. In equilibrium, applicants choose an optimal strategy under each market design, while the ranking of applicants by programs is assumed to be constant.

The results show that relative to DA without cost, DA-C with a low cost reduces screening costs by half without harming match quality; a less-restrictive DA-T, e.g., DA-T-5 and DA-T-6, does not affect match quality, either, but the reduction in congestion is not as substantial. As expected, a high-cost DA-C or a highly restrictive DA-T results in lower match quality because a prohibitively high application cost prevents applicants from applying to a sufficient number of programs. This leads to a large number of blocking pairs and unmatched applicants.

These findings show that application costs have promising potential for combating congestion even if the application cost is purely wasteful, and more so when it is a monetary transfer.

Organization of the paper. We complete this section by a brief review of the related literature. Section 2 formalizes the many-to-one matching and summarizes the theoretical predictions. The experiment conducted at TSE is described in Section 3, and Section 4 summarizes the data and provides a direct evaluation. Our structural evaluation is presented in Section 5. The paper concludes in Section 6 with a discussion of our findings.

Related literature. Congestion in matching markets has been studied extensively, but often theoretically. One of the earliest papers on the topic is Roth and Xing (1997), who show that thick markets may suffer from congestion. Search and screening costs hinder the evaluation of all potential matches by both sides.

Most related to our research, [START_REF] Arnosti | Managing congestion in dynamic matching markets[END_REF] study the regulation of market congestion using application costs and provide a comprehensive survey of the literature. Their paper considers a dynamic model of one-to-one matching in which agents (applicants and employers) arrive and depart over time. All applicants and employers are homogenous. As in our paper -but in a decentralized setting -each applicant applies to programs at a cost, and each employer pays a screening cost to verify whether an applicant is compatible. If the applicant is compatible, the employer makes her an offer without knowing if she has already been hired by someone else. If she receives an offer, the applicant accepts or rejects it.

These authors also consider imposing application limits that restrict the maximum number of applications allowed per applicant.

Application limits are considered by [START_REF] Che | Decentralized College Admissions[END_REF], who model a college admissions game in which colleges manage yield by strategically targeting applicants who are less likely to receive other offers. Application costs are present in [START_REF] Chade | Student portfolios and the college admissions problem[END_REF].

More recently, in a model of matching economics PhDs to university positions, [START_REF] Nguyen | Can EconJobMarket help Canadian universities?[END_REF] note that a reduced application cost increases the probability of application. Furthermore, they show that this reduced cost causes an increase in the probability that offers are turned down by applicants and an increase in the probability that positions remain unmatched. As a result, some universities' welfare may decrease.

Application limits are often observed in centralized school choice. [START_REF] Pathak | School Admissions Reform in Chicago and England: Comparing Mechanisms by Their Vulnerability to Manipulation[END_REF] show that more applicants find it profitable to misreport their preferences under DA-T-K when K decreases. Their study focuses more on a mechanism's vulnerability to preference-misreporting, while ours looks at the outcome of a matching market in terms of congestion and match quality. In a laboratory experiment, Calsamiglia, Haeringer and Klijn (2010) make K decrease from 7 to 3 in DA-T-K and find that more subjects do not report their true preferences. There are also more blocking pairs and larger efficiency losses. Our results on DA-T are consistent with theirs, while we consider a wider range of K in our counterfactual analysis.

Another way educational institutions mitigate screening costs is to organize entrance exams. For example, in the 2000s, certain Brazilian universities used a low-cost first-round exam to screen out applicants who were unlikely to qualify, while a second-round exam, which was costlier and more informative, refined the selection (Carvalho, Magnac and Xiong, forthcoming). This two-tier screening device, a centralized exam followed by a costlier decentralized exam, is also used in Japan [START_REF] Hafalir | College admissions with entrance exams: Centralized versus decentralized[END_REF].

Our paper also sheds light on the design of online platforms, an extensively studied topic [START_REF] Fradkin | Search frictions and the design of online marketplaces[END_REF][START_REF] Halaburda | Competing by restricting choice: the case of search platforms[END_REF][START_REF] Horton | Supply constraints as a market friction: Evidence from an online labor market[END_REF]. That literature often shows in different contexts that limiting the number of potential matches might have desirable properties in terms of aggregate welfare because of decreased screening costs. For example, in a dynamic search model with costly discovery of match quality, [START_REF] Kanoria | Facilitating the search for partners on matching platforms: Restricting agent actions[END_REF] find that a platform can mitigate wasteful competition in match-partner search via restricting what agents can see/do.

Signaling in matching markets also relates to the issues we study [START_REF] Coles | Preference signaling in matching markets[END_REF][START_REF] Lee | Interviewing in two-sided matching markets[END_REF]. Programs can target applicants by letting applicants signal their interests in specific programs. To avoid cheap talk, signals are made costly or are limited in terms of the total number of signals permitted. This step may improve welfare in equilibrium because offers are made to applicants who have a higher probability of accepting the offer [START_REF] Coles | Preference signaling in matching markets[END_REF]. In decentralized settings, pre-match interviews can be organized between applicants and programs [START_REF] Lee | Interviewing in two-sided matching markets[END_REF], which are costly for both sides in terms of application costs and screening costs. Focusing on the information about their preferences agents need to learn and communicate with others to form the final matching, Ashlagi, Braverman, [START_REF] Ashlagi | Clearing Matching Markets Efficiently: Informative Signals and Match Recommendations[END_REF] explore signaling and recommendation protocols with which a market reaches a desirable equilibrium outcome with a small communication cost.

Our study is also related to the literature on labor markets with costly search (for a survey, see [START_REF] Rogerson | Search-Theoretic Models of the Labor Market: A Survey[END_REF]. However, in that setting, decreasing individual search costs leads to better prospects for programs, while in our setting, decreasing these costs can be detrimental to program welfare because of screening costs. An exception in this literature is [START_REF] Seabright | Statistical Externalities and the Labour Market in the Digital Age[END_REF]. In their theoretical model, a reduction in application costs can lower a firm's payoff, because it attracts lower quality applicants.

In terms of theoretical tools, the two-sided matching framework we study is well analyzed and summarized in Roth and Sotomayor (1990). More specifically, our model builds on the theoretical results derived by [START_REF] Haeringer | Constrained School Choice[END_REF] and Fack, Grenet and He (Forthcoming) in which the equilibrium properties of the DA mechanism with truncation and/or application costs are investigated.

The estimation of applicant preferences from applicants' submitted ROLs is an important building block of our empirical analysis. In a strand of the recent empirical school choice literature, applicants are assumed to report their true preferences, as in our experiment under DA. Standard discrete choice methods are extended -e.g., as an exploded logit -to utilize the identifying information contained in ROLs [START_REF] Hastings | Heterogeneous Preferences and the Efficacy of Public School Choice[END_REF]Abdulka-diroglu, Agarwal and Pathak, 2017;Pathak and Shi, 2017). Another strand of this literature explicitly considers possible strategic applicant behavior, for example, using data from the Boston immediate-acceptance mechanism (Agarwal and Somaini, Forthcoming;[START_REF] Calsamiglia | Structural Estimation of a Model of School Choices: the Boston Mechanism vs. Its Alternatives[END_REF][START_REF] He | Gaming the Boston School Choice Mechanism in Beijing[END_REF][START_REF] Hwang | How does heterogeneity in beliefs affect students in the Boston Mechanism[END_REF] or from DA-T [START_REF] Ajayi | School Choice and Educational Mobility: Lessons from Secondary School Applications in Ghana[END_REF]Carvalho et al., forthcoming;Fack et al., Forthcoming). In contrast to our study of both sides' welfare, this literature often focuses on student welfare only.

More generally, this paper builds on a growing body of literature in which structural methods are applied to real-life, experimental data and thus enlarge the span of counterfactual policy analyses (for a survey, see [START_REF] Blundell | What Have We Learned from Structural Models?[END_REF].

2 Many-to-one Matching: Set-up A many-to-one matching market in which applicants are to be matched with programs is denoted by

3 rv i,j s iI,jJ t0u , rs i,j s iIt0u,jJ , rq j s jJ , C A p¤q , C P p¤q A ,
where I t1, ..., Iu is the set of applicants and J t1, ..., Ju is the set of programs, with the addition of 0 as an outside option or the option of being unmatched. Applicant i receives a von Neumann-Morgenstern utility v i,j R if matched with j; and v i pv i,0 , v i,1 , . . . , v i,J q.

Programs have responsive preferences, and more specifically, program j values its match with i at s i,j R regardless of who else is matched with j. Let s i ps i,0 , . . . , s i,J q. Each applicant can be matched with at most one program, and each program has a capacity of q j identical positions. There is no indifference in preferences on either side. Program j is acceptable to i if v i,j ¥ v i,0 , and otherwise, it is unacceptable. Program j finds applicant to be qualified if s i,j ¥ s 0,j ; otherwise, i is unqualified for j. Moreover, applicant i is qualified for program j if and only if i meets j's prerequisites.

Deviating from the previous literature, we assume that it is costly for an applicant to "apply" to programs, C A p¤q ¥ 0, while every program has to conduct a costly screening of its candidates to form its preferences, C P p¤q ¥ 0. Both cost functions, which are defined below, are homogeneous across i and j, respectively.

We consider a centralized market. Programs first announce their capacities and prerequisites, and every applicant then submits a rank-ordered list (ROL) of K i ¤ J programs, denoted by L i l 1 i , ..., l K i i ¨, where l k i J is i's k th choice. An ROL defines a relationship ¡ L i such that j ¡ L i j I if and only if j is ranked above j I in L i . The set of all possible ROLs, L, includes all ROLs that rank at least one program. We define program j's candidates as the set of applicants who include program j in their submitted ROLs.

Application cost and screening cost. When submitting ROL L, an applicant incurs a cost that is assumed to depend on the number of programs being ranked in L, denoted by |L|, but not on how they are ranked, C A p|L|q : t0, . . . , Ju Ñ R r0, Vs. Similarly, upon receiving an application, a program pays a screening cost to learn its value of being matched with the applicant. The total screening cost of forming preferences over the (subset of) candidates I j is C P p|I j |q : t0, . . . , Iu Ñ R . For simplicity, we assume that a program always pays the cost of forming preferences over all its candidates. In other words, programs do not strategically choose to remain uninformed about their preferences over (a subset of) its candidates. Moreover, as we shall see in Section 4.4, programs in centralized markets are often prohibited from using information on candidates' ROLs to screen them, while in decentralized markets, applicants do not disclose their ROLs to any party.

Both the application cost and the screening cost monotonically increase such that for all n ¥ 0, C A pn 1q ¥ C A pnq and C P pn 1q ¥ C P pnq. These specifications are rather flexi- ble, and in particular, such application cost captures many common practices of matching markets, as we show shortly.

Matching and Matching Mechanisms

We define a matching µ : I Ñ J t0u such that (i) µ piq j if applicant i is matched with j; (ii) µ piq 0 if applicant i is unmatched; and (iii) µ ¡1 pjq is the set of applicants matched with j, while |µ ¡1 pjq| is the number of applicants matched with j and does not exceed j's capacity.

A matching µ is individually rational if each applicant prefers her current match to remaining unmatched and if each program prefers each of its currently matched applicants to having a vacant position. Given matching µ, pi, jq form a blocking pair if i prefers j over her matched program µpiq, while i is preferred by j to either having a vacant position or keeping the least-preferred applicant of the currently matched ones. µ is stable if there is no blocking pair and if it is individually rational. Stability implies Pareto efficiency when both sides have strict preferences, 2 and stability is essential to the success of many matching 2 Abdulkadiroglu and Sönmez (2013) show this result for one-to-one matching, and we can extend it to many-to-one matching with responsive preferences. Suppose that µ I Pareto dominates a stable matching µ. There must exist a program or an applicant who is strictly better off in µ I . Begin by assuming that applicant i strictly prefers µ I piq to µpiq. Because µ is stable and because program preferences are strict, program µ I piq must be strictly worse off in matching µ I than in matching µ; otherwise, i and µ I piq could form a blocking pair in µ. This situation contradicts the Pareto domination presumption. We would reach markets (Roth, 1991).

Deferred Acceptance and its variants. The applicant-program match is solved by a mechanism. As a computerized algorithm, the applicant-proposing DA works as follows:

Round 1. Every applicant applies to the first choice listed in her ROL. Each program rejects unqualified applicants and the least-preferred applicants in excess of its capacity and tentatively holds the other applicants.

Generally, later rounds are described as follows:

Round k. Every applicant who is rejected in Round pk ¡ 1q applies to the next choice on her ROL. Each program, pooling new applicants and those who were held in Round pk ¡ 1q, rejects unqualified applicants and the least preferred applicants in excess of its capacity.

Those who are not rejected are tentatively held by the programs.

The process ends after the round in which rejections are no longer issued. Each program is then matched with the applicants it is currently holding.

The three variants of DA that we consider differ only in their application costs. In the traditional DA mechanism, denoted by DA, the application cost is always zero: Cp|L|q 0 for all L L. The DA with truncation, denoted by DA-T, does not allow applicants to apply to more than K t1, . . . , Ju programs, which is defined as DA-T of degree K and denoted by DA-T-K. Therefore, C p|L|q 0 whenever |L| ¤ K; otherwise, C p|L|q V.

The last is DA with costs, denoted by DA-C, under which applicants must pay a cost for each program beyond their top K choices. In this case, C p|L|q c ¢p|L|¡Kq¢1p|L| ¡ Kq if the marginal cost of application beyond K is c, a positive constant.

Timeline, Information, Strategy, and Equilibrium Concept

We consider a matching game with incomplete information and a timeline depicted in Fig- ure 1. First, at the "announcement" stage, a mechanism is chosen and made public to both programs and applicants; in addition, programs reveal their capacities and prerequisites.

Prerequisites define the necessary and sufficient conditions for qualification.

Second, at the "application" stage, applicant preferences (v i ) are private information, while the distribution of applicant preferences -conditional on some common-knowledge applicant characteristics (denoted by X rx i s iI ) -is common knowledge. For example, X includes information previously announced by programs.

the same contradiction had we begun by assuming that there exists program j that strictly prefers µ I¡1 pjq to µ ¡1 pjq. Therefore, the stable matching µ is Pareto efficient.

ANNOUNCEMENT

The mechanism is chosen and made public. Each program truthfully announces its capacity and prerequisites.

APPLICATION

With common knowledge X and private information v i , applicant i submits an ROL under uncertainty about (i) other applicants' preferences & (ii) program preferences.

MORE INFORMATION

More information about applicants (Z) becomes available to programs. In our setting, programs learn applicants' final grades.

SCREENING

With all available information (X, Z), each program screens and ranks all its candidates. Program preferences are submitted to the mechanism.

MATCHING

The matching mechanism uses submitted ROLs and program preferences to solve the matching. After applications are submitted in the form of ROLs, more information about applicants, denoted by Z, can become available to programs. In our experiment, applicants' final grades are realized and learned by programs after applicants have submitted their ROLs.3 With information on pX, Zq, a program always behaves truthfully at the "screening" stage, in which it screens all its candidates who, as defined above, are the applicants including it in their ROLs. Each program then submits its preferences over its candidates.

Finally, at the "matching" stage, the mechanism finds a matching by considering submissions from both sides.

Strategies and equilibrium. The following assumption is imposed on programs' behavior. As we shall see in Section 3, this assumption is plausible in our experiment.

Assumption 1 Programs do not behave strategically in the following sense: (i) Each program truthfully reports its capacity and prerequisites, (ii) screens all its candidates, and (iii) reports to the mechanism its true preference ranking over all its candidates.

To mitigate the issue of multiple equilibria, we also impose several assumptions on applicant strategy as an equilibrium refinement.

Assumption 2 Applicants do not apply to any unacceptable program or to any program for which they are not qualified.

Because applicants always have access to their outside options, the marginal benefit of applying to unacceptable programs is zero; similarly, applying to a program for which an applicant does not qualify or meet the prerequisites brings zero payoff because the program will never accept an unqualified applicant. Assumption 2 therefore regulates how applicants behave when they have multiple best responses and is binding only when the marginal application cost is zero. With this assumption, we may possibly underestimate congestion in markets without application cost, because applicants may apply to unacceptable programs in real life (see, e.g., [START_REF] He | Gaming the Boston School Choice Mechanism in Beijing[END_REF]. As a result, our estimated effect of application costs on congestion is likely to be a lower bound.

We focus on symmetric pure strategies such that σpv i , x i , Xq : R J 1 ¢R |x i | ¢R I|x i | Ñ L i , where x i is i's characteristics/information that are common knowledge and L i L are all the ROLs consistent with Assumption 2. When playing the game, an applicant's beliefs are equated with her probability of acceptance by each program and depend on her information set. The probability that applicant i is accepted by program j when submitting list L i is denoted by π j pL i |X, σq, which is conditional on common knowledge X and on others' strategy σ. A Bayesian Nash equilibrium is σ ¦ such that for all pv i , x i , Xq, σ ¦ pv i , x i , Xq arg max

σpv i ,x i ,XqL i jJ π j pσpv i , x i , Xq|X, σ ¦ q maxpv i,j , v i,0 q ¡ C A p|σpv i , x i , Xq|q,
where π j p¤|X, σ ¦ q is the probability of acceptance by program j consistent with σ ¦ . In other words, given that everyone plays strategy σ ¦ , when i submits a list L, the probability that i is accepted by j is exactly π j pL|X, σ ¦ q. Furthermore, only maxpv i,j , v i,0 q matters in utility terms because i can always take the outside option whenever matched with an unacceptable program. The existence of a Bayesian Nash equilibrium in pure strategies can be established by applying Theorem 4 in [START_REF] Milgrom | Distributional Strategies for Games with Incomplete Information[END_REF]. Moreover, we can solve for equilibrium, and thus π j p¤|X, σ ¦ q, following the steps in Appendix D.1.

Before discussing equilibrium properties, we introduce the following assumption.

Assumption 3 Equilibrium acceptance probabilities are non-degenerate for qualified applicants: π j pL|X, σ ¦ q p0, 1q for every j L and for all i and L L i .

In other words, there is sufficient uncertainty in other applicants' preferences and in program preferences such that every applicant has some chance of being accepted by any program to which she applies as long as she meets the prerequisites. This assumption is satisfied in our econometric model because we assume that both applicant and program preferences (v i , s i ) have full support on the real line (see Section 5).

Given Assumptions 1, 2, and 3, the literature provides the following results:

(i) Under DA, i.e., C A p|L|q 0 for all L, there is a unique Bayesian Nash equilibrium in which every applicant truthfully ranks all of the acceptable programs for which she qualifies [START_REF] Dubins | Machiavelli and the Gale-Shapley Algorithm[END_REF][START_REF] Roth | The Economics of Matching: Stability and Incentives[END_REF]. The equilibrium outcome is the applicant-optimal stable matching that Pareto dominates all other stable matchings in terms of applicant welfare [START_REF] Gale | College Admissions and the Stability of Marriage[END_REF].

(ii) Under DA-T-K for K t1, . . . , Ju, it is a dominated strategy if one submits ROL L that does not truthfully rank programs included in L [START_REF] Haeringer | Constrained School Choice[END_REF]). An equilibrium matching outcome is not necessarily stable; for any applicant-program pair pi, jq, the probability of pi, jq forming a blocking pair is bounded above by a function that is decreasing in K and equal to zero when K J (Fack et al., Forthcoming).

(iii) Under DA-C, it is a dominated strategy if one submits ROL L that does not truthfully rank programs included in L. An equilibrium matching outcome is not necessarily stable; in the case of a constant marginal cost (c), for any applicant-program pair pi, jq, the probability that pi, jq forms a blocking pair is bounded above by a function that is increasing in c and equal to zero when c 0 (Fack et al., Forthcoming).

We use these results to guide our experimental and research design and, in particular, the mechanisms considered in counterfactual analysis.

Evaluation Criteria

Our analysis evaluates the performance of a market design with five criteria. The first is about congestion or screening cost, while the last four are about match quality.

(i) Congestion/screening costs: Recall that by assumption, every program screens all its candidates. In the absence of direct information on screening technology, we measure a program's screen costs by the number of applications it receives (and thus screens).

(ii) Stability (number of blocking pairs): In two-sided matching, both sides' welfare matter. Stability is therefore a natural welfare criterion. 4 Although finding all blocking pairs unrealistically requires that every applicant and program know everyone's preferences, we use this concept in the sense that no blocking pair implies Pareto efficiency when both sides have strict preferences. Moreover, blocking pairs may affect the survival of a market design in the future, because such pairs can sometimes be identified and thus reveal some drawbacks of the existing design.

(iii) Number of unmatched applicants: An extreme form of match inefficiency is some applicants being unmatched, especially when everyone can be matched. Indeed, our setting is such a matching market, as we shall see shortly. The number of unmatched applicants therefore provides a measure of match quality.

(iv) Applicant welfare: We evaluate applicant welfare both ordinally and cardinally. The ordinal measure uses the applicants' true ordinal preferences revealed under DA, while the cardinal measure relies on an estimation of cardinal preferences. An advantage of the cardinal measure is that we can explicitly consider application costs and measure applicant welfare net of costs.

(v) Program welfare: Measuring program welfare over their assigned applicants is more demanding. In the data, we observe program ordinal preferences over individual applicants; even with this information and assuming responsive program preferences, we may still fail to construct program preferences over sets of applicants. We report program ordinal preferences whenever the comparison is conclusive. In addition, we construct two approximations to cardinal preferences -one based on applicants' grades, the other using program ordinal preferences.

3 Experiment at the Toulouse School of Economics

Background and Experimental Design

TSE organizes its master's programs into two years of study, M1 and M2. In the first year, it admits approximately 150 students, who are placed into three M1 programs: Law and economics, statistics and econometrics, and economics. M1 students are allowed to apply to the seven M2 programs for their second year of study. The names of the programs, which indicate their differentiated foci, are described in Table 1. In the rest of the paper, the programs are randomly ordered and labeled as P1 to P7. Our study focuses on the matching between applicants and programs.

In partnership with the TSE administration, we conducted an experiment in May 2013 aimed at improving the market design for the applicant-program match. Previously, for example, in 2011 and 2012, the match was organized in a semi-centralized but rather ad-hoc fashion. Applicants submitted two ranked choices without being provided explicit guidelines on how these two choices would be used. Given applicants' choices and academic files, the program directors met to decide who could be matched with which program. During Notes: The programs are listed in alphabetical order, according to their acronyms. This order does not correspond to P1-P7.

The prerequisites for Program STA include some courses in statistics and econometrics; those for Program ECL include certain courses in law.

the meeting (and sometimes multiple meetings), each program director screened its candidates and decided whether to accept them. Because every applicant was guaranteed the opportunity to continue his/her study at TSE, the costliest part of this process was finding solutions for applicants who were ranked low and were rejected by their two choices. As its main disadvantages, this market design was time-consuming for the program directors and even created adversarial relationships among some of them.

In our experiment, the "subjects" come from two sides of the matching market in 2013:

The seven M2 programs, which are represented by their directors, and the 129 applicants who were finishing their M1 study at TSE and were applying for admission to TSE's M2

programs. As depicted in Figure 2, the matching game in the experiment is played in five stages:

ANNOUNCEMENT

The four matching mechanisms are made public. Each program announces its capacity and prerequisites.

APPLICATION

Applicant i submits four ROLs, one for each mechanism.

MORE INFORMATION

Applicants' final grades become available.

SCREENING

Independent of the mechanisms, we send to each program the list of its candidates, preselecting a subset of them for screening. Each program screens its candidates and send us its preferences.

MATCHING

Each mechanism uses the program preferences and the corresponding submitted ROLs to output a matching. The four matching outcomes are submitted to the TSE administration. (ii) Application: Under each mechanism, applicants submit an ROL on an official university website that is also used for all coursework.

(iii) More Information. After applicants submit their ROLs, they take their final exams and obtain their final grades, which are weighted averages of all courses taken during the academic year.

(iv) Screening. To each program, we send a list of the applicants who have included the program in at least one of her four submitted ROLs. We also attach the information on their final grades and their grades for each individual course, but we do not inform the programs about how each applicant ranks them or the motivation letters that may have been written under DA-C. To save the programs screening costs and convince them that engaging in the experiment is not too costly for them, we, as the market designer and the clearinghouse, pre-select a subset of the program's candidates for screening. Meanwhile, the program directors are explicitly encouraged to screen all applicants. The programs then rank applicants and send us their rankings.

(v) Matching. After receiving the programs' rankings over applicants, we calculate the matching under each of the four mechanisms and send the outcomes to the administration. The TSE administration chooses one of the four matchings to be implemented (which happens to be the one from DA).

The above information and the instructions of the experiment are all explained on the application website, and we provide screenshots in Appendix A.

Applicant incentives in the experiment. It is announced that one of the mechanisms will be chosen for the final matching, so the applicants have incentives to behave under each mechanism as if that mechanism is implemented. 6 That is, under each mechanism, it is in applicants' best interest to behave optimally as if that mechanism were actually implemented. On the website, we also make this point explicit (see the screenshots in

Figures E.1-E.5 in Appendix E).
One may be concerned that, under DA-C, applicants must pay the cost before knowing if the mechanism will be chosen. In other words, the return to writing a motivation letter is discounted by the probability that DA-C is chosen, which amounts to inflating the application cost. In any case, the application costs under DA-C remain subjective.

Information on the mechanisms. We provide applicants with definitions of the mechanisms and explicit tips on how to play the game under each mechanism. Under DA, we emphasize that truth-telling, i.e., ranking programs according to their true preferences, is a dominant strategy. Under DA-T-4 and DA-C, it is noted that while truth-telling is no longer a dominant strategy, it is still in the applicants' best interest to order the ranked programs truthfully [START_REF] Haeringer | Constrained School Choice[END_REF]. The screenshots in Appendix E

(Figures E.1-E.5)
show what applicants could see on the website.

Information to the directors. When screening applicants, the directors are not informed about the submitted ROLs or any signals thereof or which mechanism will be chosen. This makes it more plausible that they behave truthfully and that Assumption 1 is satisfied.

Screening cost depends on whether the programs can screen applicants round by round, and crucially, this possibility relies on how programs can use information about applicants' submitted ROLs. For various reasons, some programs may prefer to take into account the applicants' preferences or their ROLs when screening them. This would, however, create incentive problems for the applicants. To preserve the strategy-proofness of DA, it is usually required that applicants' ROLs are not seen by the programs. For example, the National Resident Matching Program (NRMP) -the clearinghouse that matches medical residents 6 When implementing the experiment, no one in any party involved in the experiment (including the experimenters, the TSE administration, the program directors, and the applicants) had a clear prediction on which mechanism would be chosen. Although the TSE administration had the final say, the choice could be influenced by various factors. In particular, the program directors, with opposing objectives, could lobby or protest. Besides, the administration would also be choosing a mechanism for the future. Our understanding of the objectives of the TSE administration is that both match quality and screening cost were important. These ex-ante considerations convinced us to state the following in the experiment instructions "to the best of our knowledge, we believe that every mechanism has an almost equal probability to be chosen." See Figures E.1 in Appendix E for a screenshot of the instructions.

with hospitals -states that "[y]our rank order list is confidential and never will be shared with the programs." One way to keep ROLs confidential is to ask the programs to screen the applicants all at once before running the mechanisms, which is the practice in, for example, university admissions in Germany and Victoria, Australia and the NRMP, where certain variants of DA are used.

To reduce screening costs and to make this experiment feasible, we use applicants' submitted ROLs to identify a subset of applicants over whom the program's strict preferences are required to calculate the matching. It should be emphasized that the applicants are not informed of this pre-selection at any stage. It is therefore impossible that their behavior is affected by this practice. Moreover, every program is encouraged to screen everyone. When the mechanisms were actually run, no program had to accept or reject an applicant who was not pre-selected for that program. More details are provided in Appendix A.3.

Randomized orders of programs and mechanisms.

To prevent potential framing effects, we randomly assign the 129 applicants into 7 groups, each of which has a unique order of programs presented on the website. Each of the 7 programs is presented as the first to a unique group of applicants and presented as the last to another. Moreover, applicants

Length of ROL and Unacceptable Programs

In the experiment, applicants are required to rank all 7 programs under DA, 4 programs under DA-T, and at least 3 programs under DA-C, as the web design makes it cumbersome to allow applicants to rank a flexible number of programs. To alleviate this constraint, we also elicit information from every applicant on whether a program is acceptable to him/her. When evaluating the programs' screening costs, we assume that applicants never apply to unacceptable programs (Assumption 2).

Before beginning the application process, every applicant must answer the following question for each program: "If you are accepted (and only accepted) by program name, will you stay at TSE and register for the program in September 2013? "

In the survey, "program name" is replaced by the full name of one of the seven programs.

An applicant must tick one of the three possible answers, "Yes," "No," and "I Don't Know."

We relabel these responses as "definitely acceptable," "unacceptable," and "possibly acceptable", respectively, whereby a possibly acceptable program is less preferred than a definitely acceptable one but more preferred than an unacceptable one. The same question is repeated for all seven programs, and we clarify that this information is not used in the actual matching process, although we use it in this research. In the following, we sometimes refer to the "definitely acceptable" and "possibly acceptable" categories collectively as "acceptable".

The responses to these questions are summarized in Table 2. Two findings stand out from the table, which shows the heterogeneity of applicant preferences: Program P4 is definitely acceptable to 81% of the applicants and unacceptable to only 7% of them; in contrast, program P6, which is more specialized and has prerequisites, is unacceptable to the majority of applicants (78%).

Experimental Data and Direct Evaluation

In addition to observing applicant behaviors in the experiment, we also collect administrative data on applicants' grades from M1 courses (from the first semester and from both semesters), demographic information, and scholarship status. The key variables are summarized in Table 3. Notes: In total, there are 129 observations. Scholarship equals one if the applicant holds a scholarship from TSE or from the French government. Out of a total of 20 points, the grades are the credit-weighted average of grades from the courses taken during their first-semester or two-semester M1 study.

We now turn to applicant strategies and outcomes under each mechanism. As discussed in Section 2.3, we focus on two types of measures, match quality and screening cost. The first type includes stability, unmatched applicants, applicant welfare, and program welfare.

Screening cost, or congestion, is measured by the number of candidates to be screened.

Under the assumption that applicants report truthfully under DA, we take applicants' reported ROLs under DA as their true ordinal preferences. There is a recent literature documenting that some applicants do not report truthfully under DA (e.g., [START_REF] Hassidim | Strategic" Behavior in a Strategy-proof Environment[END_REF][START_REF] Artemov | Strategic 'Mistakes': Implications for Market Design Research[END_REF]Shorrer and Sóvágó, 2017). The truth-telling assumption is plausible in our setting for the following reasons: (i) On the experiment website, we explicitly announce that truth-telling under DA is in their best interest (see the screen shots in Figure E.3), and provide the details of the algorithm as well as an example on a linked help page; together with the fact that our applicants are graduate students in economics and have a few weeks to make a decision, it is plausible that the applicants understand/believe the strategy-proofness of DA. (ii) In contrast to other settings, our applicants do rank all programs. (iii) Comparing their submitted ROLs under DA with the survey responses on program acceptability, we identify only 9 instances of inconsistency, among which 8 involves the response "I don't know" (see Appendix B).

In this section, we do not make further assumptions on applicants' strategies under DA-T-4 or DA-C and instead evaluate what is observed. Recall that we assume that applicants do not apply to the programs that are deemed unacceptable or for which they do not meet the prerequisites. Therefore, we remove these programs from the ROLs when analyzing congestion. This removal does not affect the matching outcome in the data and therefore mitigates market congestion only, especially for DA (without cost).

Statistical Inference

The focus of the study is the matching game consisting of agents on both sides, applicants and programs. Therefore, in an ideal experiment, we would have the same game independently played multiple times by different sets of agents under different mechanisms. In other words, the unit of observation in the experiment is a game play or a matching market. However, our data contain outcomes from only one market under several mechanisms. Thus, careful consideration is necessary when making statistical inferences.

This leads us to resampling (or bootstrapping): We randomly resample applicants with replacement; the size of the resample is equal to the size of the original dataset; and in each resample, the programs are always kept the same. Implicitly, we assume that the empirical distribution of applications (types and strategies) is a good approximation of the theoretical distribution; by drawing from the empirical distribution independently, we create an independent play of the same game in each resample. In a given resample, multiple observations may originate from the same applicant in the original data; when programs rank the applicants, the ties among them are broken randomly.7 Standard errors and testing results in this section are based on 10, 000 resamples.

This resampling procedure is justified for standard statistics but not for extremal statistics. This literature is reviewed in [START_REF] Bickel | On the choice of m in the m out of n bootstrap and confidence bounds for extrema[END_REF] who also propose another resampling procedure in these non-standard cases. We leave them for further research given the small size of our sample.

Applicant Strategies

Table 4 presents the distribution of the number of programs ranked under each mechanism.

By imposing a cost, both DA-T-4 and DA-C discourage the applicants from ranking too many programs. As a result, every applicant ranks 0.7 (0.9) programs fewer on average under DA-T-4 (DA-C) than under DA. The differences between these numbers of applications are all statistically significant (p-value 0.01), as is the difference between DA-T-4 and DA-C (p-value 0.05). Notes: This table shows the distribution of the numbers of programs in the submitted ROLs under each mechanism. Each number -except those in the last column -represents the percentages of the applicants who rank that many programs in their ROLs. We remove from the ROLs the unacceptable programs and those for which the applicant is not qualified. Bootstrap standard errors from 10, 000 samples are in parentheses. a From t-tests, the differences in the numbers of applications under DA, DA-T-4, and DA-C are all statistically significant (p-value 0.05). Specifically, the difference is 0.71 (s.e. 0.07) between DA and DA-T-4, 0.88 (s.e. 0.09) between DA and DA-C, and 0.17 DA-T-4 allows applicants to freely rank four programs, and therefore, the mode of the number of ranked programs is four, accounting for 57 percent of the applicants. Moreover, 22 percent of them do not adopt a "truncation" strategy; that is, these applicants' submitted ROLs do not coincide with the top portion of their true ordinal preferences. Under DA-C, this statistic is 7 percent.

Recall that it is free to rank the first three programs under DA-C, while the applicant has to pay a cost by writing a motivation letter for each of the fourth to seventh choices.

Unsurprisingly, the mode is three; however, 26 percent of the applicants choose to pay some costs and rank more than three programs.

Match Quality

Applicants' submitted ROLs and programs' rankings over applicants allow us to calculate the matching outcome under each mechanism. In terms of applicant welfare, 85 percent of the applicants are assigned to their most preferred program, as shown in Table 6. DA and DA-T-4 perform equally well on this dimension, while DA-C performs worse due to the applicant left unmatched with this mechanism. The ordinal welfare distribution barely varies across the 10, 000 resamples under either mechanism. These statistics imply that applicant preferences are sufficiently heterogeneous. One would expect that in such a market, congestion should be less of a concern.

Yet, as we shall see in Section 4.4, program screen costs can still be significantly lowered without harming match quality. Notes: This table shows how the matching outcome under each mechanism is different from the applicant-optimal stable matching (i.e., the DA outcome). There are 129 applicants in total. Blocking pairs are defined with respect to applicants' true preferences revealed under DA. Bootstrap standard errors from 10, 000 samples are in parentheses. a Standard errors are not calculated for these two statistics because a program's welfare change cannot always be labelled as better off or worse off in every bootstrap sample (although it is feasible in the experimental data). Recall that a program is better off if all the matched applicants are (weakly) better than those matched in the old matching.

Table 7 compares the matchings from DA-T-4 and DA-C to that from DA. DA gives us the applicant-optimal stable matching, which also happens to coincide with the programoptimal matching in our data. DA-T-4 and DA-C lead to 3 and 4 applicants having different outcomes, respectively. Moreover, the number of applicants who are worse off is greater than the number of those who are better off.

The right side of Table 7 shows the number of programs that have different matching In summary, both applicant welfare and program welfare differ across the mechanisms, but the magnitude is small or even negligible. However, as we emphasize, programs' screening cost is another important factor, and we now investigate the screening costs that programs must pay under each mechanism.

Programs' Screening Costs

Recall that each program screens its candidates all at once and that we make no assumptions about screening cost except that it strictly increases with the number of candidates to be screened (see Section 2 for more details). Given these assumptions, Table 8 shows, on average, how many candidates a program screens under each mechanism or, equivalently, how many applicants include a given program in their submitted ROLs under each mechanism.

When the application cost increases from DA to DA-T-4 (DA-C), the number decreases from 75 to 62 (59), while the differences are all significant at the 2% level based on t-tests.

We further normalize each program's screening cost by its capacity. Figure 3 shows Notes: Each row of this table shows the summary statistics of the number of candidates to be screened across the seven programs in the experimental data. In other words, these statistics are not based on resampling. Treating each program under a given mechanism as an observation (and not using resampling), t-tests show that the difference between any two mechanisms is significant at the 2% level.

the number of candidates per opening (i.e., per available seat) to be screened by each In conclusion, among the three mechanisms, the increases in application cost does not significantly affect match quality but greatly reduces programs' screening costs.

Evaluation Based on Structural Estimation

The set of market designs that we can directly evaluate is necessarily restricted because we implement only one instance of DA-T and one instance of DA-C in the experiment.

In order to draw a complete picture of the trade-offs between screening costs and match quality, we would like to evaluate many other market designs with different parameters governing truncation and application costs. Building on the rich information on both programs and applicants we observe, this section implements a structural estimation and conducts evaluations using counterfactual analysis.

To achieve this goal, our structural estimation contains several stages. When DA is replaced by DA-T or DA-C, an applicant's optimal strategy is no longer truthful reporting, and instead, it depends on other applicants' actions. Recovering the cardinal preferences of all agents becomes necessary. First, we use experimental data to estimate applicants' cardinal preferences. In particular, we combine applicants' submitted ROLs under DA with the survey data on program acceptability; we also make use of the fact that truthfully ranking acceptable, qualified programs is the unique equilibrium (Assumption 3). Recall that applicant ordinal preferences are truthfully revealed under DA (see the discussion in Section 4).

Second, we estimate program preferences over applicants from programs' submitted rankings of applicants, given the assumption that programs truthfully report their preferences (Assumption 1). We next use data on final grades to estimate applicants' beliefs about their probabilities of acceptance by each program.

Optimal strategies of applicants depend on the solution concept that we retain. We specify the structure of incomplete information of the game that applicants are assumed to play, leading to use a Bayesian Nash equilibrium as defined in Section 2. That is, when submitting ROLs, we assume that each applicant knows her own preferences but not others', even though she is aware of their distribution. Moreover, in spite of knowing what criteria programs use to rank applicants, she is uncertain about how she is ranked by programs. This game may seem combinatorially complex, because an applicant can choose from a large set of ROLs. However, under DA-T and DA-C, optimal strategies are to drop some programs from the true preference order [START_REF] Haeringer | Constrained School Choice[END_REF], which makes it simpler to play.

Finally, we simulate the counterfactual equilibria attained when different versions of DA-T and DA-C are used.

The rest of this section formalizes the game of incomplete information. We first specify the following key elements: (i) The estimation of applicants' cardinal preferences, (ii) the estimation of program preferences, (iii) the information structure and solution concept, and

(iv) applicants' beliefs about program preferences. For counterfactual analyses, we also explain the procedure for computing equilibria under each of these mechanisms.

Applicant Preferences

For each applicant, we observe a submitted ROL under DA, pl ¦,1 i , . . . , l ¦,J i q, which corresponds to her true ordinal preferences and from the survey, we observe whether each program is definitely acceptable, possibly acceptable, or unacceptable to the applicant. To reiterate, we do not use the data from DA-T-4 and DA-C, because the applicants may not play an equilibrium strategy in the experiment (see the discussion in Section 4).

Econometric model. Suppressing subscript i, we first postulate that the utility function associated with each program, j t1, . . . , Ju, is:

v j xβ j ε j , (1)
in which ε j is extreme-value distributed and independent across programs. The parameters, β j , are program-specific but not individual-specific, an assumption that we maintain throughout the paper. Furthermore, we model acceptability using an outside option whose value is the sum of two terms. The first term is observed at the moment of the application decision and is written as

v 0 xβ 0 ε 0 .
(2)

To model programs as "definitely acceptable", "possibly acceptable", or "unacceptable", we posit that final acceptability is determined by adding to v 0 the value of another random variable, η rxβ f η, xβ f ηs, which is revealed after the matching process.9 Program j is said to be definitely acceptable if and only if it has a value higher than the best possible outside option:

v j ¡ v 0 xβ f η for any η, that is, v j ¡ v 0 xβ f η.
Similarly, the program is deemed (definitely) unacceptable if and only if it is always dominated by the worst possible outside option:

v j v 0 xβ f η.
Otherwise, the applicant considers the program possibly acceptable if

v j rv 0 xβ f η, v 0 xβ f ηs.
(3)

Let the ranking information be described as the ROL complemented with the max/min outside options pO, Oq so that the observation is now an extended ROL:

pl ¦,1 , . . . , l ¦,J , O, l ¦,J 1 , . . . , O, l ¦,J , . . . , l ¦,J q, in which l ¦,J J for 1 ¤ J ¤ J is the lowest-ranked definitely acceptable program. When J 0, there is no definitely acceptable program, and when J J, all programs are definitely acceptable. Similarly, l ¦,J J for 1 ¤ J ¤ J is the highest-ranked unacceptable program so that J ¡ J and that J ¡ J implies an absence of unacceptable programs.

Identification and likelihood function. A location normalization is needed, and the simplest one sets the lower bound of the outside option to zero:

pβ 0 β f q 0, η 0.
The upper bound, η, is to be estimated. The scale normalization is given by the usual logit assumption. The parameter vector is thus described by θ ppβ j q j1,...,J , ηq. If the survey information on program acceptability were not available, the choice probability of ROL pl 1 , . . . , l J q would be described by an exploded logit [START_REF] Beggs | Assessing the potential demand for electric cars[END_REF]:

Prpv l 1 max jt1,...,Ju v j , v l 2 max jt2,...,Ju v l j , . . . , v l J¡1 max jtJ¡1,Ju v l j q ¹ j1,...,J¡1
exppxβ l j q °J kj exppxβ l k q . When we introduce information on program acceptability, the likelihood function can be written as a sum of exploded logit terms (see Appendix C).

Results. We consider various sets of explanatory variables taken from administrative information on grades, M1 program (Economics, Econometrics and Statistics, Economics and Law), gender, age, and having a scholarship or not. There are many course grades that can be used at a fine level of detail. Because of the timing of the application decision, we opt to use the M1 first-semester grade as the main explanatory variable. At the time of application, no applicant knows his/her final grades, the weighted sum of his/her first-and second-semester grades.

The results are presented in Table 9. A clear pattern is that one's M1 program have some power to predict her preferences over the M2 programs, as the coefficients of "M1 Economics" and "M1 Statistics" have different signs across M2 programs. Upper bound of shocks to the outside option: 0.707 (0.07) Notes: Estimation is based on applicants' submitted ROLs under DA supplemented with survey information on program acceptability. The likelihood function is specified in Appendix C and can be considered as an extended version of the multinomial logit with rank-ordered data combined with acceptability. The McFadden pseudo-R-squared is equal to 0.078.

Program Preferences

Program j sets a latent score for each applicant, s i,j , according to which applicants are ranked. Conditional on meeting prerequisites p i,j (a binary variable), s i,j is assumed to depend only on the final grade (the credit-weighted average of grades from two semesters), F inalGrade i , and some noise,

s i,j F inalGrade i σξ i,j , (4)
in which ξ i,j is extreme value distributed. The term ξ i,j stands for the additional information that programs can use beyond final grades. ξ i,j is assumed to be independent of F inalGrade i and the covariates, x i . Based on our robustness checks, including additional covariates leads to similar results.

Program prerequisites are common knowledge, and applicants condition their decision on p i,j . Program preferences are therefore lexicographical and rank the subsample p i,j 1 first, the subsample p i,j 0 second, and according to s i,j within the first subsample.10

Given the structure of the experiment, we can estimate the parameters governing program preferences using a rank-ordered logit on the subsample of applicants satisfying the prerequisites, p i,j 1. Nonetheless, the rank-ordered logit procedure is fragile when many alternatives -or applicants -are considered, as we do here, in a small sample of seven programs. Therefore, we consider a limited information procedure using only length-K rankings among applicants with K ¥ 2.

Specifically, let the full ranking of applicants for program j be pi pjq 1 , ., i pjq I q, and partition this length-I vector into IpKq vectors starting with pi 1, ., i K q, then pi K, ., i 2K¡1 q, etc. We write the pseudo-likelihood function corresponding to these J ¢ IpKq observations treated as ROLs while neglecting possible correlations across observations. This process does not affect the consistency of the estimates [START_REF] Avery | Multiperiod Probit Models and Orthogonality Condition Estimation[END_REF], although standard errors should be computed using a sandwich formula.11

Results. The estimation of the latent score, equation ( 4), depends on how we choose K to form length-K ROLs. We present results for three different K's, while the results from K 2 are used in the counterfactual analysis. The estimates for K t2, 3, 4u are as follows:

K 2: si,j F inalGrade i 0.058 p.022q ¢ ξ i,j , McFadden pseudo R 2 0.337; K 3: si,j F inalGrade i 0.056 p.020q ¢ ξ i.j , McFadden pseudo R 2 0.391; K 4: si,j F inalGrade i 0.049 p.015q ¢ ξ i,j , McFadden pseudo R 2 0.496.

Solution Concept and Information Structure

We first clarify the solution concept and evaluation approach that are used in counterfactual analysis. Solution concepts depend on the information that each applicant has, as Panel A of Table 10 shows. A possibility is to assume complete information in our matching game. That is, both applicant and program preferences are common knowledge to every applicant, which leads us to Nash equilibrium as the solution concept. However, the complete-information assumption may be too restrictive in our setting because it is unlikely that every applicant knows everyone else's cardinal preferences or can predict her final grade and program preferences perfectly (cf. Figure 1). Indeed, for this reason, our model in Section 2 specifies a game of incomplete information, which leads to Bayesian Nash equilibrium. An outcome is evaluated conditional on X and on the observed ordinal preferences of applicants and programs. That is, we consider only random draws of preference shocks consistent with the observed ordinal preferences. Each simulated applicant (with simulated cardinal preferences) plays an equilibrium strategy according to either Nash equilibrium (A1) or Bayesian Nash (A2).

B2. No (population-specific)

An outcome is evaluated conditional on X but unconditional on the observed ordinal preferences of applicants and programs.

That is, we consider random draws of shocks from the assumed distribution. Each simulated applicant (with simulated cardinal preferences) plays an equilibrium strategy according to either Nash equilibrium (A1) or Bayesian Nash (A2).

In addition, multiple methods are available to evaluate counterfactual outcomes, depending on the use of information available to researchers. First, we always use commonknowledge information X. As Panel B of Table 10 shows, the outcome under any given market design can be evaluated with or without information on applicants' and programs' observed ordinal preferences. If the information in the data on ordinal preferences is utilized, we have a "sample-specific" evaluation; otherwise, when this information is not used, the method is "population-specific".

In addition to choosing Bayesian Nash equilibrium (A2) as our solution concept, we adopt the "sample-specific" evaluation (B1). This evaluation facilitates the comparison between our experimental results and the counterfactual analyses, as the former is obviously conditional on applicants' and programs' realized ordinal preferences.

To summarize, when solving for a Bayesian Nash equilibrium, we need every applicant to best respond to others with incomplete information on other applicants' and programs' preferences. The distributions of applicant and program preferences are modeled and estimated in the previous two subsections. However, programs form preferences with information on final grades that is not available to applicants at the time of application (cf. Figure 2). It is therefore necessary to consider the uncertainty in final grades when we estimate applicants' beliefs about program preferences, which is what we turn to next.

Applicant Beliefs on Program Preferences

When forming beliefs about program preferences, applicant i observes her own characteristics, x i , including her grades during the first semester and the prerequisites of each program (p i,j 1 if i satisfies the prerequisites of program j and 0 otherwise). These prerequisites consist of choices of courses that are made well in advance and are partially determined by one's M1 program. We therefore consider them as fixed in the statistical model.

We assume that applicants have rational expectations and expect that (i) The information structure detailed above is common knowledge and, in particular, program preferences are formed according to the model above.

(ii) Applicant i predicts her final grade F inalGrade i as a function of characteristics x i , using the following equation:

F inalGrade i x i γ ν i , (5)
in which x i includes the characteristics used in the modified exploded logit model above and also the first-semester grade in particular; ν i is assumed to have a normal distribution.

The specifications of applicant and program preferences and the grade equation guarantee that any possible applicant preference ranking and program preference ranking among qualified applicants have a positive probability of occurrence. It is straightforward to show that equilibrium acceptance probabilities are non-degenerate for any qualified applicant, and therefore, Assumption 3 is satisfied.

Estimation. The rational-expectation assumption implies that applicant beliefs are consistent with the distribution of final grades and program preferences.

Equation ( 5) is estimated by standard ordinary least squares (OLS), and the results are shown in Table 11. Not surprisingly, the main determinant of the final grade is the first-semester grade. One may notice that the coefficient on "Scholarship" is significantly negative, which may be explained by the fact that scholarship is often need-based. For the residual ν i in the grade equation, the assumption of normal distribution is reasonable, as

shown by a quantile-quantile plot of the residuals, which is available upon request. Based on these results, in the counterfactual analysis, we simulate applicant beliefs about program preferences by drawing ν i from a normal distribution and ξ i,j from extreme value distributions. Furthermore, the prerequisites of P3 and P6 are held constant, because they are decided well in advance. As programs' strategic behavior is assumed away, the above procedure describes the set-up for simulating applicant beliefs about program preferences.

Counterfactual Analysis of Market Designs

Simulating Equilibrium Outcomes: Procedures

We solve for a Bayesian Nash equilibrium (case A2 in Table 10) under each mechanism and then evaluate the sample-specific counterfactual outcomes (case B1 in Table 10).

Counterfactuals under DA-T and DA-C. We perform counterfactual analysis under DA-T with degrees of truncation varying from 1 to 6. Under DA-C, the application cost has the following form in the counterfactual analysis:

Cp|L|q c ¢ p|L| ¡ 1q ¢ 1t|L| ¡ 1u,
in which c is the constant marginal cost for second and further choices and c can take one of the 11 values in t10 ¡5 , 3.1 ¢ 10 ¡5 , 10 ¡4 , 3.1 ¢ 10 ¡4 , ..., 0.01, 0.31, 1u, increasing on a logarithmic scale. We have Cp|L|q 0 for |L| ¤ 1 to avoid distorting the applicants' participation decisions. 12 Although application costs are homogenous across applicants, applicant responses can be heterogenous. They depend on the marginal benefit of an application which is determined jointly by applicant preferences and acceptance probabilities.

To make sense of the magnitude of application costs, one may consider the following thought experiment: A "possibly acceptable" program can be improved to "definitely acceptable" by adding at most 0.707, which is the estimate of the maximum shock to outside option (η in equation 3); the same program can be demoted to "unacceptable" by subtracting 0.707 at most. Moreover, the variance of utility shocks is π 2 {6p 1.645q. From this perspective, most of the above costs, especially those below 0.031, are quite small.

Computation of equilibrium. For both DA-T and DA-C, an equilibrium must be solved as a fixed point in terms of cutoff distribution. A program's cutoff in a given matching is the lowest rank among the applicants accepted by the program if it has no vacancy; otherwise, the cutoff is zero. A Bayesian Nash equilibrium can be summarized by the joint distribution of the cutoffs of programs [START_REF] Azevedo | A Supply and Demand Framework for Two-Sided Matching Markets[END_REF]. Given a particular draw of random shocks, an applicant ranked above a program's cutoff can be accepted by this program.

Solving for a Bayesian Nash equilibrium can then be achieved by finding a fixed point of the cutoff distribution. We provide the details of computation in Appendix D.1.

Sample-specific counterfactual actions and outcomes. We evaluate the counterfactual welfare conditional on applicants' and programs' observed ordinal preferences, which is case B1 in Table 10 in Section 5.3. That is, the shocks to applicant preferences (ε) are simulated conditional on the observed ROLs submitted by applicants under DA, and program ordinal preferences are also held constant at their observed values. In this way, we answer the following question: Based on all the information observed by the researcher, what is the best prediction of the counterfactual outcome if a counterfactual market design had been implemented at TSE in 2013? There are certainly many alternative counterfactual questions that one can ask. Our choice makes it easier to compare simulated equilibrium outcomes with the observed outcomes, because the latter certainly are derived from the realized ordinal preferences of applicants and programs.

More specifically, we adopt the following procedure to simulate a new set of samples:

(i) In each simulation sample m, we compute applicants' cardinal and therefore ordinal preferences by inputting the simulated shocks ε pmq i , estimated coefficients, and observed characteristics into the utility functions specified in equations ( 1) and ( 2). As spelled out in Section 5.3, we now compute shocks to applicant preferences (ε pmq i ) condition-ally on the ordinal preferences observed in the sample using a Gibbs sampler described in Appendix D.2.

(ii) Each applicant submits the ROL that maximizes her expected utility, given the equilibrium distribution of the cutoffs, Φ e . Again, an applicant's optimal ROL can be found by dropping some programs from her true preference order. This process is conducted separately for each version of DA-T and DA-C.

(iii) In each simulation sample, we run the DA algorithm with the optimal ROLs submitted by applicants and the observed program preferences.

Similar to the direct evaluation, we measure the performance of each design on several dimensions: (i) Match quality, which is summarized by stability (or the incidence of blocking pairs) and unmatched applicants, 13 and (ii) screening costs. In addition to examining applicants' and programs' ordinal welfare, we evaluate their cardinal welfare, given that our preference estimates have cardinal implications.

Counterfactual Analysis: Results

Our first set of results is summarized in Figure 4, which shows the effects of market design on screening costs, measured as the number of candidates screened per opening, and on match quality, measured as the number of blocking pairs and the number of unmatched applicants. 14 Subfigure (a) depicts the effects of DA-T of different degrees. DA-T-K, for K t1, 2, ..., 7u, means that applicants are allowed to freely rank only up to K choices; therefore, DA-T-7 is DA (without truncation). The outcomes under DA with no cost are always constant in our sample-specific counterfactual analysis. In the figure, when increasing the application limit from DA-T-7 to DA-T-3, match quality remains (almost) the same as the applicantoptimal stable matching, while screening costs decrease monotonically from screening 4.16 candidates per opening to screening 2.56 per opening. When the application limit tightens further, the screening costs decrease further to 1.75 and 0.91 candidates per opening under DA-T-2 and DA-T-1, respectively. However, this result comes at the expense of match quality: The number of blocking pairs increases from 0.5 under DA-T-3 to 4.10 under DA-T-2 13 Note that the stable matching in our data is unique in all simulation samples, given the ordinal preferences of applicants and programs (c.f., Section 4). In other words, the applicant-optimal stable matching and the program-optimal stable matching coincide.

14 The confidence intervals shown in Figure 4 consider the uncertainty in applicant preferences but not the uncertainty in the estimated coefficients, due to significant computational costs. Our simulations of DA-T taking into account both sources of uncertainty, being computational less costly, show similar results to Figure 4a. Several interesting patterns emerge. First, the screening costs drop dramatically, even when there is a very low application cost: Imposing an application cost of 10 ¡5 decreases the number of candidates screened per opening by 50%, while match quality remains the same. Second, the reduction in screening costs by this low application cost is larger than that of DA-T-3 (although smaller than that of DA-T-2). When the cost rises, screening costs further decrease, but the match quality begins to be impacted only when the cost is above 0.0031. Third, when the application cost is 1, the outcome is almost identical to DA-T-1 because the cost is so high that it is not worth ranking a second program.

In summary, Figure 4 describes the trade-off between screening costs and match quality; most importantly, imposing a mild application cost in DA-T, and more so in DA-C, can significantly decrease screening costs without harming match quality. It should be emphasized that our equilibrium analysis considers all effects of application cost and measures the net effect. For example, in addition to the potentially negative effects on match quality, application costs can benefit some applications and increase their chance of being matched, because costs reduce the competition among some applicants when other applicants stop applying to some programs.

One may be concerned that our analysis of DA-C does not consider the costs that are actually paid by applicants. We note that application costs can be designed as a transfer, e.g., a fee paid to programs, rather than being purely wasteful, e.g., writing a motivation letter. In the following, we study how applicant welfare is affected by such costs.

Applicants Welfare

We investigate how many applicants are better off or worse off under different market design.

The advantage of this welfare measure is that it does not compare welfare across applicants.

The results are summarized in Table 12. DA-T-6 0.00 0.00 0.00 0.00 0.00001 0.00 0.00 0.00 0.00 DA-T-5 0.00 0.00 0.00 0.00 0.000031 0.00 0.04 0.00 0.04 DA-T-4 0.00 0.00 0.00 0.00 0.0001 0.00 0.05 0.00 0.05 Notes: The calculations are based on 4000 simulations. In each simulation, the shocks to applicants' cardinal preferences are drawn conditional on the observed true ordinal preferences (i.e., the submitted ROLs under DA, supplemented with the program acceptability information). More details are provided in Appendix D.2. In each simulation sample, we calculate cardinal welfare per application (i.e., the average of applicant welfare); the table reports the means and standard deviations of per-applicant welfare across simulation samples. Therefore, the standard deviation measures the variation across simulation samples but not across applicants. When simulating matching outcomes, program preferences are always fixed at the observed values. a In counterfactual analysis, applicants play an equilibrium strategy in each simulation sample, while the equilibrium is solved numerically, as in Appendix D.1. Given the realization of cardinal preferences, applicants may play different actions across samples, as dictated by the equilibrium strategy. b For these calculations, applicants always take the actions played in the experiment across all simulation samples. In the experiment, DA-C allows the applicant to rank up to three choices, and a motivation letter is required for each additional choice. However, we do not have a measure of the magnitude of the cost. c In the counterfactual analysis, DA-C allows applicants to rank one choice but requires a constant marginal cost for additional choices.

In each simulation sample, we calculate how many applicants are better off (or worse off) relative to their individual outcome under DA -the applicant-optimal stable matching.

This welfare comparison does not take into account the application costs paid by applicants.

The table then reports the means and standard deviations across simulation samples.

As shown in the table, applicants (almost) always obtain the applicant-optimal stable outcome when the application cost is low (i.e., under DA-T-3 to DA-T-6 or DA-C with a marginal cost of no more than 0.01). However, whenever the outcomes deviate from the applicant-optimal stable outcome, there are more "losers" than "winners." Noticeably, when the application cost is prohibitively high, such as in DA-T-1 or DA-C with a cost of 1, there are more than 10 applicants who are worse off. This highlights the detrimental effects of high application costs.

We present additional results on applicant cardinal preferences in Appendix Table D.2.

Allowing inter-personal comparison of utility, we draw similar conclusions. See Appendix D.3 for a detailed discussion.

Program Welfare in Matching Outcomes

Given the two-sided nature of the matching game, we are also interested in program welfare from matching outcomes without taking into account screening costs.

We define two measures of program welfare while maintaining the assumption that programs have responsive preferences. 15 The first measure is the sum of the final grades of all of the program's matched applicants. That is, for program j, its welfare given matching µ is °iµ ¡1 pjq F inalGrade i . The second measure takes into account programs' ordinal preferences, °iµ ¡1 pjq r i,j for each j. Namely, j receives 129 points if matched with its top applicant and 1 point if matched with its lowest-ranked applicant. By construction, both measures take into account the quantity and quality of matched applicants.

Similar to the analysis of applicant welfare, we compute the number of "winners" and "losers" according to the two welfare measures (Table 13). It should be emphasized that this welfare analysis does not consider screening costs.

Table 13 shows that there are more "losers" than "winners" when the application cost increases. This pattern holds true with both of the welfare measures. When the application cost is low, the effects on program welfare are negligible.

We present additional results on program cardinal preferences in Appendix Table D.3.

of applying to an additional acceptable program, which can be small, is always positive because of the full-support assumption on applicant and program preferences. Therefore, applicants always optimally apply to K programs under DA-T-K whenever they have at least K acceptable programs. In comparison, under DA-C, an applicant considers the positive marginal cost for additional applications and therefore may choose not to apply to an acceptable program.

Second, the programs to which an applicant chooses not to apply under DA-C must have marginal benefits lower than the marginal costs, implying that the expected loss in match quality is bounded by application cost. DA-T does not offer such an opportunity for bounding losses. This observation implies the possibility that the market designer, with little information on applicants' and programs' preferences, chooses a very low application cost and reduces congestion significantly without sacrificing match quality.

Third, although neither DA-T nor DA-C is strategy-proof, DA-C offers an opportunity for less strategic applicants to play safe by paying application costs. This is a desirable feature as non-strategic applicants may lose to sophisticated applicants in a non-strategyproof mechanism (Pathak and Sönmez, 2008). DA-T can only provide such a safety measure when it does not substantially restrict the number of applications, in which case it is not effective in reducing congestion.

Fourth, DA-C is also more flexible in the sense that application costs can be non-linear or program-specific. For instance, a popular program can impose a high application cost.

Fifth, although application costs and pollution taxes are essentially the same, application limits, or DA-T, do not resemble a cap-and-trade scheme, because there is no trading of rights to submit applications in a matching market. Therefore, the equivalence between regulating prices and fixing quantities in the setting of [START_REF] Weitzman | Prices vs. Quantities[END_REF] no longer holds in our matching model.

Lastly, application costs may have potential in combatting congestion in decentralized market. For example, consistent with our results, [START_REF] Pallais | Small Differences That Matter: Mistakes in Applying to College[END_REF] documents that application costs significantly influence the number of per-student applications in decentralized U.S. college admissions.

Regarding research design, our study marries real-life, experimental data with a structural analysis. This choice of research design deserves some discussion, especially in terms of experimental design, assumptions in the structural analysis, and external validity.

One might argue that, given the realized preferences of both applicants and programs, our choice of mechanisms, DA-T-4 and a version of DA-C under which it is free to submit up to three choices, is too conservative. In the end, 99 percent of the applicants are matched with their top-3-preferred programs. At the time of designing the experiment, we were not willing to gamble on the match quality in exchange for uncertain screening costs, given that it was the first time this formal centralized match was implemented in our specific setting. It is true that, had we known the structure of preferences, we might have tried more restrictive DA-T and DA-C. In a sense, because it is a field experiment, we have mimicked what would happen in real life in order to learn about the structural parameters.

In the structural analysis, we assume that every applicant behaves rationally. However, our data from the experiment indicate that applicants are not fully optimizing, probably because of the complexity of the game. Importantly, the conclusions drawn from the experiment and those from the structural analysis are similar, both qualitatively and quantitatively. This implies that deviations from full rationality, which is a topic outside the scope of this paper, have no significant consequences on the conclusions of our study.

The question of external validity is difficult to address without considering specific benchmarks. In our experiment, applicant preferences are highly heterogeneous (i.e., "horizontal" applicant preferences), while programs have similar ordinal preferences over applicants (i.e., "vertical" program preferences). Such preference patterns are also documented or considered in the literature, for example, [START_REF] Agarwal | An empirical model of the medical match[END_REF] on the medical match in the US, Carvalho et al. (forthcoming) on university admissions in Brazil, and [START_REF] Che | Decentralized College Admissions[END_REF] on decentralized college admissions. One may expect that congestion should be less likely to happen in these settings, and yet it does occur in our experiment. One may further argue that application costs would be less effective in other settings, e.g., those with more homogeneous applicant preferences. Although the exact effects of application costs would depend on the context, the way how application costs work remains the same: an application cost will discourage an applicant from applying to programs that are unlikely to accept her and/or are not so attractive to her.

(For Online Publication)

Appendix to

program director received a program-specific file and was asked to rank all the applicants within it. We explained that the pre-selected applicants were those who would be considered by the program with a high probability, while the others were unlikely to be considered. At the same time, we strongly encouraged them to screen as many candidates as possible. When ranking candidates, the program directors had flexibility: They did not have to respect the ranking by grades; the ranking could be weak; and if necessary, ties in the mechanisms would be broken by grades.

We pre-selected applicants by running the four mechanisms with "fictitious" program preferences and capacities. We created those program preferences by adding noises to applicants' final grades. For each program, the pre-selected applicants were those who had ever been "considered" (either accepted or rejected) by the program in these simulations.

Among the seven programs, the number of pre-selected candidates ranged from 27 to 52, with a mean of 41. No director screened more candidates beyond the pre-selected ones.

This process was proven "successful" in the sense that beyond the pre-selected applicants for a program, no one was ever "considered" by the program under any mechanism.

It should be emphasized that the applicants are not informed of this pre-selection at any stage. It is therefore impossible that their behavior is affected by this practice. Moreover, every program is encouraged to screen everyone, and the properties of each market design presented in Section 2.2 are thus invariant to pre-selection.

Motivation letters. The directors did not have access to the motivation letters because receiving a letter from an applicant would imply that the applicant did not rank the program within their top three choices. We planned to transmit the letters to the directors if (a)

there were a large number of applicants assigned to the fourth or lower choices under DA-C and (b) if the administration would choose the DA-C outcome upon seeing the tentative DA-C outcome together with the outcomes from the other three mechanisms. Ultimately, all applicants except one -who was unmatched -were matched with one of their top three choices (see Table 6). Therefore, the tentative DA-C outcome was very similar to the "real one" that could have been obtained had the directors had access to the letters. A.2 Moreover, upon seeing the results, the TSE administration did not choose DA-C.

A .2 Had the directors seen the letters, the unmatched applicant would not have had a different outcome because she/he submitted only three choices.

We detail our modifications in Table B.1. The principle is as following: Given an applicant, her submitted ROL is taken as the true preference order; therefore, the ROL should always rank "definitely acceptable" programs above "possibly acceptable" ones which are above "unacceptables." In other words, program acceptability should never increase when we move down in the ROL. When there is a violation between a pair, say l k and l k 1 such that l k 1 's acceptability is higher than l k 's, we change l k 1 's acceptability to l k 's. It turns out that we only need to make one modification like this in each of the nice ROLs (Table B.1).

) 1 -1 1 1 -1 0 0 1 -1 1 1 -1 -1 0 2 (P3, P4, P7, P2, P5, P6, P1) -1 1 1 1 -1 -1 0 -1 0 1 1 -1 -1 0 3 (P4, P3, P2, P5, P6, P1, P7) 0 0 0 1 0 -1 -1 -1 0 0 1 0 -1 -1 4 (P3, P1, P7, P4, P2, P5, P6) 1 -1 1 1 -1 -1 0 1 -1 1 0 -1 -1 0 5 (P2, P1, P4, P5, P3, P7, P6) 1 1 0 0 0 0 -1 1 1 0 0 0 -1 -1 6 (P2, P5, P3, P1, P4, P6, P5) 0 1 1 1 0 0 1 0 1 1 0 0 0 1 7 (P4, P5, P1, P2, P7, P3, P6) 1 1 1 1 1 -1 0 1 1 0 1 1 -1 0 8 (P1, P4, P3, P2, P7, P5, P6) 1 0 1 1 0 -1 1 1 0 1 1 0 -1 0 9 (P2, P4, P1, P3, P5, P6, P7) 1 1 1 1 -1 1 -1 1 1 1 1 -1 -1 -1
Notes: Modified program acceptability is in red boldface.

B.2.2 Repeated Choices in DA-C

Under DA-C, the applicant interface on the web site allows one to repeatedly rank the same program multiple times. Indeed, there are two applicants (i and i I ) following this pattern.

We change their strategies in the following way:

pl 1 i , l 2 i , l 3 i , l 1 i , l 1 i , l 1 i q Ñ pl 1 i , l 2 i , l 3 i q, pl 1 i I, l 2 i I, l 3 i I, l 4 i I, l 4 i I, l 5 i Iq Ñ pl 1 i I, l 2 i I, l 3 i I, l 4 i I, l 5 i Iq.
The two applicants do not provide additional motivation letters for repeated choices, and both of them are assigned to their respective first choice under DA-C.

C.2 The Rank-Ordered Multinomial Logit

To simplify notations, we define v j xβ j ε j b j ε j , omitting the index for applicants.

Furthermore, consider:

Prpv J¡1 ¡ v J q E J¡1 ¢» ε J¡1 b J¡1 ¡b J ¡V expp¡tq expp¡ expp¡tqqdt E J¡1 pGpε J¡1 b J¡1 ¡ b J , 1, 1qq , E J¡1 pGpε J¡1 , exppb J ¡ b J¡1 q, 1q , Gp V, 1 exppb J ¡ b J¡1 q, 1 1 exppb J ¡ b J¡1 q q 1 1 exppb J ¡ b J¡1 q exppb J¡1 q exppb J¡1 q exppb J q .
Iterating:

Prpv J¡2 ¡ v J¡1 , v J¡1 ¡ v J q E J¡2 ¢ G ¢ ε J¡2 b J¡2 ¡ b J¡1 , 1 exppb J ¡ b J¡1 q, 1 1 exppb J ¡ b J¡1 q E J¡2 ¢ G ¢ ε J¡2 , exppb J¡1 ¡ b J¡2 q exppb J ¡ b J¡2 q, 1 1 exppb J ¡ b J¡1 q G £ V, 1 exppb J¡1 ¡ b J¡2 q exppb J ¡ b J¡2 q, 1 1 exppb J ¡b J¡1 q ¤
1 1 exppb J¡1 ¡b J¡2 q exppb J ¡b J¡2 q exppb J¡2 q exppb J¡2 q exppb J¡1 q exppb J q ¤ exppb J¡1 q exppb J¡1 q exppb J q , which is the usual rank-ordered logit (or exploded logit) formula. By extension:

Prpv J¡K ¡ v J¡K 1 , ., v J¡1 ¡ v J q E J¡K pGpε J¡K , λ J¡K , µ J¡K qq Gp V, λ J¡K¡1 , µ J¡K¡1 q µ J¡K¡1 ,
in which λ j expp¡pb j ¡ b j 1 qqp1 λ j 1 q and λ J 0. This yields:

λ j ķ¡j exppb k ¡ b j q. A.8
Furthermore, µ j µ j 1 1 λ j 1 and µ J¡1 1 so that:

µ j ¹ m¥j 1 1 1 °k¡m exppb k ¡ b m q .
Further iteration yields:

Prpv 1 ¡ v 2 , ., v J¡1 ¡ v J q µ 0 ¹ m¥1 1 1 °k¡m exppb k ¡ b m q ¹ m¥1
exppb m q °k¥m exppb k q .

C.3 Derivation of Likelihood Function

To further simplify notations, without loss of generality, we let the extended rank-order list L f be p1, ..., J, O, J 1, ..., J ¡ 1, O, J, ..., Jq. We derive the following likelihood:

L Prpv 1 ¥ ... ¥ v J ¥ v 0 ¥ v J 1 ¥ ... ¥ v J¡1 ¥ v 0 ¥ v J ¥ ... ¥ v J q,
where v 0 and v 0 are the max and min value of outside option. Moreover, by normalization, v 0 ε 0 . From the above results, the term at the right of v 0 equals:

Prpε 0 ¡ v J , ., v J¡1 ¡ v J q E ε 0 Gpε 0 , λ p0q , µ p0q q, in which: λ p0q ķ¥J exppb k q, µ p0q ¹ m¥J exppb m q °k¥m exppb k q . Nonetheless, the term Prpv J ¥ v ¥ v J 1 ¥ . ¥ v J¡1 ¥ v ¥ v J ¥ . ¥ v J q requires a different
evaluation from above because ε 0 affects both v 0 and v 0 .

We start from the case in which there are more than two "possibly acceptable" alternatives and show that it applies as well to the case in which there are fewer "possibly acceptable" alternatives.

C.3.1 Two or More "Possibly Acceptable" Alternatives

Consider that there are h "possibly acceptable" alternatives i.e. J 1 J ¡ h, ., J ¡ 1 are associated to don't know.

A.9

A backward induction mechanism. Start the induction from :

M pε J¡2 q Gpε 0 , λ p0q , µ p0q q » ε J¡2 b J¡2 ¡b J¡1 ε 0 ¡b J¡1 f pε J¡1 qdε J¡1
Gpε 0 , λ p0q , µ p0q q pGpε J¡2 , exppb J¡1 ¡ b J¡2 q, 1q ¡ Gpε 0 , exppb J¡1 q, 1qq , Gpε J¡2 , exppb J¡1 ¡ b J¡2 q, 1qG 0 pε 0 , λ p0q , µ p0q q ¡ Gpε 0 , exppb J¡1 q λ p0q , µ p0q q, to posit that, by analogy:

M pε J¡1¡j q ε J¡1¡j b J¡1¡j ¡b J¡j » ε 0 ¡b J¡j f pε J¡j qdε J¡j ... ¤ ¦ ¥ ε J¡2 b J¡2 ¡b J¡1 » ε 0 ¡b J¡1 f pε J¡1 qdε J¡1 .Gpε 0 , λ p0q , µ p0q q , j p1
σ tp1u Gpε J¡1¡j , λ pεq p,j , µ pεq p,j qK p¡1 pε 0 q ¡ K j pε 0 q, in which:

σ tp1u 5 1 if p 1, ¡1 otherwise.
The initialization is such that:

λ pεq 1,1 exppb J¡1 ¡ b J¡2 q, µ pεq
1,1 1, K 0 pε 0 q G 0 pε 0 , λ p0q , µ p0q q, (A.1) K 1 pε 0 q Gpε 0 , exppb J¡1 q λ p0q , µ p0q q.

A.10 By induction, for j ¥ 1:

M pε J¡2¡j q » ε J¡2¡j b J¡2¡j ¡b J¡1¡j ε 0 ¡b J¡1¡j f pε J¡1¡j qMpε J¡1¡j qdε J¡1¡j j p1 σ tp1u ¤ ¦ ¥ Gpε J¡2¡j b J¡2¡j ¡ b J¡1¡j , 1 λ pεq p,j , µ pεq p,j 1 λ pεq p,j q ¡Gpε 0 ¡ b J¡1¡j , 1 λ pεq p,j , µ pεq p,j 1 λ pεq p,j q Kp¡1pε0q ¡ £ Gpε J¡2¡j b J¡2¡j ¡ b J¡1¡j , 1, 1q ¡Gpε 0 ¡ b J¡1¡j , 1, 1q K j pε 0 q j p1 σ tp1u ¤ ¦ ¥
Gpε J¡2¡j , exppb J¡1¡j ¡ b J¡2¡j qp1 λ pεq p,j q, µ pεq p,j 1 λ pεq p,j q ¡Gpε 0 , exppb J¡1¡j qp1 λ pεq p,j q, µ pεq p,j 1 λ pεq p,j q Kp¡1pε0q ¡ £ Gpε J¡2¡j , exppb J¡1¡j ¡ b J¡2¡j q, 1q ¡Gpε 0 , exppb J¡1¡j q, 1q K j pε 0 q.

which we equalize to:

M pε J¡2¡j q j 1 p1 σ tp1u Gpε J¡2¡j , λ pεq p,j 1 , µ pεq p,j 1 qK p¡1 pε 0 q ¡ K j 1 pε 0 q.
Identifying first the terms a function of ε J¡2¡j , we have, for 0 p ¤ j:

λ pεq p,j 1 exppb J¡1¡j ¡ b J¡2¡j qp1 λ pεq p,j q, µ pεq p,j 1 µ pεq p,j 1 λ pεq p,j , and
λ pεq j 1,j 1 exppb J¡1¡j ¡ b J¡2¡j q, µ pεq j 1,j 1 1.
This yields for 0 p ¤ j:

1 λ pεq p,j 1
Cpb J¡1¡j ; pb J¡k q p¤k¤j 1 q , and, using the convention that the product Cpb J¡m ; pb J¡k q p¤k¤m q.

A.11

Finally, identifying the terms in ε 0 :

K j 1 pε 0 q j p1 σ tp1u Gpε 0 , exppb J¡1¡j qp1 λ pεq p,j q, µ pεq p,j 1 λ pεq p,j qK p¡1 pε 0 q ¡ Gpε 0 , exppb J¡1¡j q, 1qK j pε 0 q j p1 σ tp1u Gpε 0 , exppb J¡1¡j qp1 λ pεq p,j q, µ pεq p,j 1 qK p¡1 pε 0 q ¡ Gpε 0 , exppb J¡1¡j q, 1qK j pε 0 q.

Let us postulate that:

K j pε 0 q Gpε 0 , 1¤k¤j
exppb J¡k q λ p0q , µ p0q j q.

Because of equation (A.1), this property is true for j 0 and j 1 with:

µ p0q 0 µ p0q 1 µ p0q .
Suppose that it is true for j and write:

K j 1 pε 0 q j p1 σ tp1u Gpε 0 , exppb J¡1¡j qp1 λ pεq p,j q, µ pεq p,j 1 qGpε 0 , 1¤k¤p¡1 exppb J¡k q λ p0q , µ p0q p¡1 q ¡Gpε 0 , exppb J¡1¡j q, 1qGpε 0 , 1¤k¤j exppb J¡k q λ p0q , µ p0q j q.

By the above: exppb J¡1¡j qp1 λ pεq p,j q exppb J¡1¡j q Cpb J¡1¡j ; pb J¡k q p¤k¤j 1 q p¤k¤j 1 exppb J¡k q, so that:

K j 1 pε 0 q j p1 σ tp1u Gpε 0 , p¤k¤j 1 exppb J¡k q 1¤k¤p¡1
exppb J¡k q λ p0q , µ pεq p,j 1 µ p0q p¡1 q ¡Gpε 0 , 1¤k¤j 1 exppb J¡k q λ p0q , µ p0q j q Gpε 0 , 1¤k¤j 1 exppb J¡k q λ p0q , µ p0q j 1 q,

A.12 since second arguments of all G elements are equal. Additionally:

µ p0q j 1 j p1 σ tp1u µ pεq p,j 1 µ p0q p¡1 ¡ µ p0q j , (A.2) j p1 σ tp1u ¹ p m¤j 1
Cpb J¡m ; pb J¡k q p¤k¤m qµ p0q p¡1 ¡ µ p0q j .

As a summary, we have:

M pε J¡1¡j q j p1 σ tp1u Gpε J¡1¡j , λ pεq p,j , µ pεq p,j qGpε 0 , 1¤k¤p¡1 exppb J¡k q λ p0q , µ p0q p¡1 q ¡Gpε 0 , 1¤k¤j exppb J¡k q λ p0q , µ p0q j q.

Integration As in the previous section, we have:

G ¦ pε 0 q » ε 0 η¡b J 1 ε 0 ¡b J 1 M pε J 1 qfpε J 1 qdε J 1 ε 0 η¡b J 1 » ε 0 ¡b J 1 " " ! h¡1 °p1 σ tp1u Gpε J 1 , λ pεq p,h¡1 , µ pεq p,h¡1 qGpε 0 , °1¤k¤p¡1 exppb J¡k q λ p0q , µ p0q p¡1 q ¡Gpε 0 , °1¤k¤h¡1 exppb J¡k q λ p0q , µ p0q h¡1 q. ( 0 0
) f pε J 1 qdε J 1 , in which we have set J ¡ 1 ¡ j J 1 i.e. j J ¡ 2 ¡ J h ¡ 1 and h ¥ 2. Note that J ¡ h J 1. Then:

G ¦ pε 0 q h¡1 p1 σ tp1u ¤ ¦ ¥ Gpε 0 η ¡ b J 1 , 1 λ pεq p,h¡1 , µ pεq p,h¡1 1 λ pεq p,h¡1 q ¡Gpε 0 ¡ b J 1 , 1 λ pεq p,h¡1 , µ pεq p,h¡1 1 λ pεq p,h¡1 q Gpε0, 1¤k¤p¡1 exppb J¡k q λ p0q , µ p0q p¡1 q ¡ £ Gpε 0 η ¡ b J 1 , 1, 1q ¡Gpε 0 ¡ b J 1 , 1, 1q Gpε 0 , 1¤k¤h¡1 exppb J¡k q λ p0q , µ p0q h¡1 q h¡1 p1 σ tp1u ¤ ¦ ¥ Gpε 0 , exppb J 1 ¡ ηqp1 λ pεq p,h¡1 q °1¤k¤p¡1
exppb J¡k q λ p0q , µ pεq p,h µ p0q p¡1 q ¡Gpε 0 , exppb J 1 qp1 λ pεq p,h¡1 q °1¤k¤p¡1 exppb J¡k q λ p0q , µ pεq p,h µ p0q

p¡1 q ¡ ¤ ¦ ¥ Gpε 0 , exppb J 1 ¡ ηq °1¤k¤h¡1
exppb J¡k q λ p0q , µ p0q h¡1 q ¡Gpε 0 , exppb J 1 q °1¤k¤h¡1 exppb J¡k q λ p0q , µ p0q h¡1 q

A.13

By the same principle as above:

exppb J 1 qp1 λ pεq p,h¡1 q exppb J 1 q Cpb J 1 ; pb J¡k q p¤k¤h q p¤k¤h exppb J¡k q, so that the second and fourth terms can be combined to obtain:

Gpε 0 , 1¤k¤h exppb J¡k q λ p0q , h¡1 p1 σ tp1u µ pεq p,h µ p0q p¡1 q ¡ Gpε 0 , 1¤k¤h exppb J¡k q λ p0q , µ p0q h¡1 q Gpε 0 , 1¤k¤h exppb J¡k q λ p0q , h¡1 p1 σ tp1u µ pεq p,h µ p0q p¡1 ¡ µ p0q h¡1 q Gpε 0 , 1¤k¤h exppb J¡k q λ p0q , µ p0q h q,
where we use the definition of µ p0q h from equation (A.2). Because:

exppb J 1 ¡ ηqp1 λ pεq p,h¡1 q expp¡ηq exppb J 1 q Cpb J 1 ; pb J¡k q p¤k¤h q expp¡ηq p¤k¤h exppb J¡k q, we can then write: G ¦ pε 0 q h¡1 p1 σ tp1u Gpε 0 , expp¡ηq p¤k¤h exppb J¡k q 1¤k¤p¡1 exppb J¡k q λ p0q , µ pεq p,h µ p0q p¡1 q ¡Gpε 0 , 1¤k¤h exppb J¡k q λ p0q , µ p0q h q ¡Gpε 0 , exppb J 1 ¡ ηq 1¤k¤h¡1 exppb J¡k q λ p0q , µ p0q h¡1 q

Final Derivation We end up with considering that:

Prpv J ¥ v 0 ¥ v J 1 ¥ ... ¥ v J¡1 ¥ v 0 ¥ v J ¥ ... ¥ v J q E J H phq pε J q ¨,
in which

H phq pε J q » ε J b J ¡η ¡V f pε 0 qG ¦ pε 0 qdε 0
and therefore:

H phq pε J q h 1 p1 σ tp1u Gpε J , λp0q p , μp0q p q, in which: λp0q p exppη ¡ b J qp1 expp¡ηq p¤k¤h exppb J¡k q 1¤k¤p¡1
exppb J¡k q λ p0q q A.14 because J ¡ h J 1. We can then write: λp0q p expp¡b J qpexppηq p¤k¤h exppb J¡k q 1¤k¤p¡1 exppb J¡k ηq exppηqλ p0q q and: 1 λp0q p 1 Cppb J ; η, pb J¡k q p¤k¤h q, pb J¡k ηq 1¤k¤p¡1 q, pb k ηq k¥J q . We also have for 1 ¤ p h: μp0q p 1 p1 expp¡ηq °p¤k¤h exppb J¡k q °1¤k¤p¡1 exppb J¡k q λ p0q q µ pεq p,h µ p0q p¡1 Cpη; η, pb J¡k q p¤k¤h , pb J¡k ηq 1¤k¤p¡1 , pb k ηq k¥J q ¢ ¹ p m¤h Cpb J¡m ; pb J¡k q p¤k¤m qµ p0q p¡1 .

which is also valid for p h because: μp0q h 1 1 exppb J 1 ¡ ηq °1¤k¤h¡1 exppb J¡k q λ p0q µ p0q h¡1 , Cpη; η, pb J¡k q p¤k¤h , pb J¡k ηq 1¤k¤p¡1 , pb k ηq k¥J qµ p0q h¡1 .

When p h 1, we have: μp0q h 1 1 1 °1¤k¤h exppb J¡k q λ p0q µ p0q h Cp0; 0, pb k q k¥ J 1 qµ p0q h .

To derive the likelihood Prpv

1 ¥ ... ¥ v J ¥ v 0 ¥ v J 1 ¥ ... ¥ v J¡1 ¥ v 0 ¥ v J ¥ ... ¥ v J q, we
reconsider the backward induction as in the previous sections: λj,p expp¡pb j ¡ b j 1 qqp1 λj 1,p q, μj,p μj 1,p 1 λj 1,p , so that:

1 λj,p 1 Cppb j ; pb k q j¤k¤ J , η, pb J¡k q p¤k¤h , pb J¡k ηq 1¤k¤p¡1 , pb k ηq j¥J q , and therefore if p ¤ h: μ0,p ¹ 1¤m¤ J Cpb m ; ppb k q m¤k¤ J q, η, pb J¡k q p¤k¤h , pb J¡k ηq 1¤k¤p¡1 , pb k ηq k¥J q ' ¢Cpη; η, pb J¡k q p¤k¤h , pb J¡k ηq 1¤k¤p¡1 , pb k ηq k¥J q ¢ ¹ p m¤h

Cpb J¡m ; pb J¡k q p¤k¤m qµ p0q p¡1 ,

(ii) We also identify all ROLs tL pmq i,n u n1,...,N i for all i such that (a) L pmq i,n ranks no more than K programs; (b) L pmq i,n is a partial order of the true preference order, i.e., the programs included in L pmq i,n are ranked according to the true ordinal preferences; and (c) L pmq i,n does not include any unacceptable or unqualified program. We only need to focus on these ROLs to find an optimal ROL because all other ROLs are strictly dominated (see Section 2).

(iii) We attribute to each program the same capacity as in the experiment and compute its "cardinal" preferences over applicants by plugging the simulated shocks (ν pmq i and ξ pmq i,j ), estimated coefficients, and observed first-semester grades into the grade function (equation 5) and the latent score function (equation 4). These preferences are then translated into rankings over applicants in increasing order of preference from 1 to I, denoted by r pmq i,j .

• Iteration: For t t1, 2, . . .u, given µ m,t¡1 and pκ pm,t¡1q j q jJ for all m (i.e., Φ t¡1 ), iteration t goes through the following steps to find the optimal ROL for each applicant:

(i) Define A pm,tq i tj J : r pmq i,j ¥ κ pm,t¡1q j u for each i and each m. That is, A pm,tq i is the set of programs that have lower cutoffs in iteration t ¡ 1 than i's ranks in sample m.

(ii) Compute for each L pmq i,n the expected utility: A.3 W pm,tq A.3) in which the expectation is taken with respect to the ex-post shock, η, on the outside option and "j is L pmq i,n -preferred in A pl,tq i " is defined such that j is ranked higher than j I for all j I L pmq i,n A pl,tq i .

i,n 1 M M ļ1 J j1 1 tj is L pmq i,n -preferred in A pl,tq i u E η maxtx i β j ε pmq i,j , η ε p0q i,j qu ' , (
(iii) Find the optimal ROL L pm,tq i,¦ arg max n1,...,N i W pm,tq i,n . If there are ties, we choose the unique longest list among them. Given Assumption 3, there is always a positive marginal benefit to apply to more programs, as long as the total number applications is not more than K. Ties occur due to the discrete number of simulations.

A .3 This calculation amounts to assuming that i plays against a distribution of others' actions (which is approximated by their actions in iteration t ¡ 1 in all samples). Notice that i is present in every sample, although ideally one could take i out. Besides, we use sample m also notwithstanding the introduction of spurious correlation. These two simplifications speed up the computation, while the error introduced is either Op1{nq or Op1{M q and is therefore negligible.

A.19

We then calculate the matching outcome in each sample and update the cutoff distribution:

(i) With L pm,tq i,¦ and r pmq i,j for all applicants and programs, we run the DA algorithm to find the new matching µ pm,tq in each simulation sample.

(ii) We calculate the new cutoffs κ pm,tq j for all j based on µ pm,tq and the difference between two distributions of cutoffs:

d ptq 1 M j,m ¡ κ pm,tq j ¡ κ pm,t¡1q j © 2
• Stopping rule: Stop when d ptq is small enough.

Suppose that we stop at t t f . This leads to a joint distribution of cutoffs across simulation samples, tκ pm,t f q j u for all j and m, which is defined as Φ e in the main text and "describes" an equilibrium under DA-T-K.

Welfare computations. In counterfactual analysis, we use a different set of simulation samples and also need to find best response for each applicant with given cardinal preferences. Recall that ordinal preferences of applicants and programs are fixed at the value observed in the experimental data (cf. Table 10). However, across the simulation samples for counterfactual analysis, applicant cardinal preferences can differ. The procedure for conditional drawings of preference shocks are detailed below in Appendix D.2.

Given the simulated cardinal preferences in a simulation sample (x i β j ε i,j for all j), i's best response under DA-T-K is found through the following steps:

(i) Given the equilibrium cutoff distribution solved above, tκ pm,t f q j u for all j and m, we define A pm,t f q i tj J : r pmq i,j ¥ κ pm,t f q j u for each i.

(ii) We identify all ROLs tL pmq i,n u n1,...,N i for all i such that (a) L pmq i,n ranks no more than K programs; (b) L pmq i,n is a partial order of the true preference order; and (c) L pmq i,n does not include any unacceptable or unqualified program.

(iii) Compute for each L m i,n the expected utility:

W pt f q i,n 1 M M m1 J j1 1 tj is L m i,n -preferred in A pm,t f q i u E η maxtx i β j ε pmq i,j , η ε p0q i,j qu ' ,
where "j is L m i,n -preferred in A pm,t f q i " is defined such that j is ranked higher than j I for all j I L m i,n A pm,t f q i . A.20

(iv) i's best response is the optimal ROL L m i,¦ arg max n1,...,N i W pt f q i,n . If there are ties, we choose the unique longest list.

D.1.2 Solving Bayes-Nash equilibrium under DA-C

Similar to DA-T, equilibrium under DA-C also has to be solved as a fixed point. The application cost has the following form in the counterfactual analysis:

CpLq 6 8 7 0 if |L| ¤ 1, c|L| if |L| ¡ 1;
in which c is the constant marginal cost for second and later choices; and c can take one of the 11 values in t10 ¡5 , 3.1 ¢ 10 ¡5 , 10 ¡4 , 3.1 ¢ 10 ¡4 , ..., 0.01, 0.31, 1u.

For a given c, we adopt an iterative process almost the same as the one for DA-T and we do not repeat here except that the expected utility, equation (A.3), is replaced by: W pm,tq

D.2 Simulating Preference Shocks: Conditional Drawings

Having solved equilibrium strategy numerically, we conduct counterfactual welfare analysis.

Our simulation experiment is to answer the following question: Had a counterfactual market design been implemented at TSE in 2013, what is our best prediction of the counterfactual outcome, based on all the information that is observed by the researcher?

Therefore, we take the observed applicant and program ordinal preferences as given, although their cardinal preferences can vary while being compatible with the ordinal ones.

To simplify notations, we define v j xβ j ε j b j ε j for j 1, 2, . . . , J, omitting the index for applicants. Recall that v 0 ε 0 . For a given applicant, write ε pε 0 , ε 1 , . . . , ε J q;

L f is an extended rank-order list (i.e., an applicant's submitted ROL under DA combined with program acceptability). Define ε ¡j pε 0 , . . . , ε j¡1 , ε j 1 , . . . , ε J q and also the following set:

SpL f q tε R J 1 : ε is compatible with L f given pb j q jJ u.

This means that we draw the vector ε into the density function given by: 1tε SpL f quΠ J j0 f pε j q PrpL f q .

A.21

Note that the conditional distribution of ε j given ε ¡j is given by: f pε j q1tpε j , ε ¡j q SpL f qu Prppε j , ε ¡j q SpL f q | ε ¡j q .

For j $ 0, the set pε j , ε ¡j q SpL f q given ε ¡j is an interval which can be open or not on the left or on the right according to the following cases:

(i) Program j is ranked first and therefore if the second ranked is l, the only constraint that SpL f q imposes on ε j is :

b j ε j ¡ b l ε l .

(ii) Program j is ranked last and therefore if the before-the-last ranked is u, the only constraint that SpL f q imposes on ε j is :

b j ε j b u ε u .
(iii) If program j has two neighbors, from below, l and from above u, then the only constraint is:

b l ε l b j ε j b u ε u .
For j 0, the set pε 0 , ε ¡0 q SpL f q is slightly more complicated but follows the same principles. Suppose the ranking of programs is given by p1, . . . , J, O, J 1, . . . , O, J, . . . , Jq.

It translates into the set of inequalities on ε 0 :

b J ε J ¡ η ε 0 ¡ b J 1 ε J 1 , b J¡1 ε J¡1 ¡ ε 0 ¡ b J ε J ,
using the conventions that b 0 V and b J 1 ¡V. This means that:

ε 0 maxpb J 1 ε J 1 ¡ η, b J ε J q, minpb J ε J ¡ η, b J¡1 ε J¡1 q $ ,
and the interval is not empty since ε SpL f q.

Defining all these domain intervals as I j pε ¡j , L f q, the conditional distribution of ε j given ε ¡j and L f is given by: f pε j q1tε j I j pε ¡j , L f qu Prpε j I j pε ¡j , L f q | ε ¡j q . It is easy to simulate since F pε j q expp¡ expp¡ε j qq and therefore for δ p0, 1q: F ¡1 pδq ¡ logp¡ logpδqq.

A.22

Assume that I j pε ¡j , L f q ra j pε ¡j q, b j pε ¡jq s and draw u U r0,1s then: ε ¦ j ¡ logp¡ logpF pa j pε ¡j qq upF pb j pε ¡j qq ¡ F pa j pε ¡j qqqq (A.4) is distributed as ε j given ε ¡j and L f . For Gibbs sampling, the Markov chain that we use is the following:

b J ε J ¡ η ε 0 , b J¡1 ε J¡1 ¡ b J ε J , etc.
(b) Between O and O, draw ε p0q j sequentially in the order of J 1, . . . , J ¡1 imposing the constraints sequentially:

η ε 0 ¡ b J 1 ε J 1 ¡ ε 0 , b J 1 ε J 1 ¡ b J 2 ε J 2 ¡ ε 0 , etc.
(c) Below O, draw ε p0q j sequentially in the order of J, . . . , J imposing the constraints sequentially:

ε 0 ¡ b J ε J , b J ε J ¡ b J 1 ε J 1 , etc.
In this way, ε p0q SpL f q.

(ii) For t t1, 2, . . .u, repeat the steps in which ε ptq 0 is drawn according to equation (A.4) given ε pt¡1q ¡0 , and then follow the same order for drawing ε ptq j as in steps (ia) to (ic) that is the order of drawings given by: J, . . . , 1, J 1, . . . , J; in the meantime, impose the exact intervals I j pε ¡j , L f q. Note that at every step, the ε of interest belongs to SpL f q since we draw in the correct intervals.

(iii) If the chain is long enough, then the distribution of ε is the distribution of interest and expectations of all ε j can be approximated.

TSE completely understands that trying four mechanisms imposes an additional cost on all of you. We would have chosen just one of them had we known which of them would be the best for you and TSE. Even from the frontier of economic research, we do not have the answer. We do not want to pick a random mechanism that will end up with a bad outcome. We therefore ask for some sacrifice from you, so that in the future, we can improve our application system.

TSE appreciates your understanding and your contribution!

Standard Track and Doctoral Track

This year, students apply to M2 programs first without indicating standard or doctoral track, and programs will accept students without considering track assignment.

After everyone is assigned to a M2 program, if you want to be considered by the doctoral track of your assigned M2 program, you will have the chance to contact the director. If your application is not approved by the director, or if you do not do anything, you stay in the standard track of your assigned program.

Only Your Last Submitted Rank-Order Lists Matters

After you submit your rank-order lists, you may come back to the system before it closes and submit new lists. In that case, only your rank-order lists that are submitted at the latest time will be taken into account in les masters, seul un des 4 mécanismes sera retenu. A priori, les quatre mécanismes ont les mêmes chances d'être retenu. Nous garantissons que chaque étudiant sera traité de façon identique et fera face aux mêmes règles de sélection. TSE a conscience que considérer quatre mécanismes vous impose un coût supplémentaire. Si nous avions su quel mécanisme était le meilleur pour TSE et pour vous, nous n'en aurions sélectionné qu'un. Cependant, la recherche économique ignore encore quel mécanisme est le meilleur et nous ne souhaitons pas en choisir un au hasard qui donnerait de mauvais résultats. C'est pourquoi nous vous demandons ce sacrifice afin que dans l'avenir nous puissions améliorer notre système de candidature.

TSE vous remercie de votre compréhension et de votre contribution.

Voie Standard et Voie Doctorale

Cette année, les étudiants postulent dans les programmes de Master sans préciser s'ils souhaitent suivre le parcours standard ou la voie doctorale. Dans un premier temps, les programmes accepteront les étudiants sans tenir compte de la voie.

Après que vous avez été assigné à un programme de Master et si vous souhaitez rejoindre la voie doctorale de votre Master d'assignation, vous pourrez contacter le directeur de votre master. Si votre directeur de Master refuse de vous accepter en voie doctorale ou si vous n'effectuez aucune démarche, vous serez assigné au parcours standard.

Your Privacy

The information you input here will only be used for research purposes to improve the matching procedure, and your identity will only be revealed to the TSE researchers and administrative staff who are directly involved in this assignment procedure. In particular, program directors will not be given the information about your rank-order lists.

Have Questions or Need Some Help You may send an email to: scoltsem2@ut- capitole.fr.

In the following, we ask you to fill out some forms step-by-step. To continue to Step 1, please click here.

Seul votre dernier choix compte

Après avoir enregistrer vos choix, vous pourrez toujours recommencer la procédure et enregistrer de nouveau choix. Dans ce cas, seul le dernier choix enregistré sera pris en compte.

Données et informations privées

Les informations que vous donnerez durant cette expérimentation seront utilisées uniquement à des fins de recherche et ceci afin de déterminer la meilleure procédure d'appariement étudiant/Master2. Votre identité sera révélée uniquement aux chercheurs et membres du personnel administratif directement impliqués dans la procédure d'appariement. En particulier, les directeurs de programmes n'auront pas accès à l'information sur vos choix.

Si vous avez des questions

Vous pouvez envoyer un mail à : scoltsem2@ut-capitole.fr.

Nous allons maintenant vous guider étape par étape.

Pour commencer l'étape 1, veuillez cliquer ici.

Last modified: Thursday, July 25, 2013, 3:13 PM http://cours.ut-capitole.fr/mod/page/view.php?id=8818 Notes: This is the first screen an applicant sees when participating in the experiment. It shows, in both English and French, (1) the purpose of the experiment (i.e., trying four mechanisms instead of adopting only one mechanism), (2) some information about the process (deadline, change application during the process, etc.), and (3) the link to the next step. This screen is the same for every applicant, except that the link to the next screen is randomized.

Figure 1 :

 1 Figure 1: Timeline of the Matching Game under a Given Mechanism

Figure 2 :

 2 Figure 2: Timeline of Matching Applicants with M2 Programs at TSE in the Experiment

  in a given group play the four mechanisms in one of the following four sequences (DA, DA-T-4, DA-C, IA), (DA, DA-C, DA-T-4, IA), (IA, DA, DA-T-4, DA-C), and (IA, DA, DA-C, DA-T-4). We decide to have DA-T-4 and DA-C immediately follow DA in order to avoid potential confusion about the mechanisms.

  (s.e. 0.07) between DA-T-4 and DA-C.

  outcomes under DA-T-4/DA-C relative to DA. 3 (4) programs' outcomes are affected by DA-T-4 (DA-C), and more programs are worse off than better off under DA-T-4/DA-C. 8

Figure 3 :

 3 Figure 3: Number of Candidates Screened by Each Program per Opening Notes: This figure shows the total number of candidates screened by each program per opening under each mechanism. Programs must screen all their candidates at once before the mechanism is implemented. The average number of candidates screened across the seven programs is 3.69 under DA 3.04 under DA-T-4, and 2.90 under DA-C. The error bars indicate the 90% confidence intervals from 10, 000 bootstrap samples.

  Figure 4: Match Quality under DA with Truncations or Finite Application CostsNotes: This figure shows the counterfactual analysis of the effects of market design on match quality (measured by the number of blocking pairs and the number of unmatched applicants) and screening costs (measured by the number of candidates screened per opening). Subfigure (a) depicts the effects of DA-T with different degrees, where DA-T-K, K t1, 2, ..., 7u, meaning that applicants are allowed to freely rank only up to K choices. Therefore, DA-T-7 is DA (without truncation). Subfigure (b) presents the effects of DA-C with a constant marginal cost for second and later choices and a zero cost of ranking the first choice. The constant marginal cost varies from 0 to 1 on a logarithmic scale, and it becomes DA when the cost is zero. The dashed lines are the 90% confidence intervals from the 4000 simulation samples. There is no variation in simulating the outcome under DA because all simulated applicant and program preferences are conditional on the observed ordinal preferences.

  (i) Draw ε p0q 0 in the type-I extreme value distribution. (a) Above O, draw ε p0q j sequentially in the reverse order of 1, . . . , J imposing the constraints sequentially:

  cours.ut-capitole.fr/mod/page/view.php?id=8818 My home► My courses► Enseignements► École d'économie de Toulouse -TSE► M1► TSE-M1-ChoixM2► General► Welcome Page -Accueil Moodle Docs for this page You are logged in as HE YINGHUA (Logout) the assignment process.

Figure E. 1 :

 1 Figure E.1: First Screen: Welcome Page of the Experiment

Table 1 :

 1 Program Names and Prerequisites

	Program Acronym	Prerequisites	Program Name in English (French)
	ECL	Yes	Economics and Competition Law
			(Economie et Droit de la Concurrence)
	EMO	No	Economics of Markets and Organizations
			(Economie des Marchés et des Organisations)
	ERNA	No	Environmental and Natural Resources Economics
			(Economie de l'environnement et des ressources naturelles)
	ETE	No	Economic Theory and Econometrics -PhD Track
			(Economie Mathématique et Econométrie)
	MIF	No	Financial Markets and Intermediaries
			(Marchés et Intermédiaires Financiers)
	PPD	No	Development Economics and Public Policies
			(Politique Publique et Développement)
	STA	Yes	Statistics and Econometrics
			(Statistique et Econométrie)

Table 2 :

 2 How the Applicants Consider the Programs: Percentages This table shows the percentages of 129 applicants who consider each program as "unacceptable," "possibly acceptable," and "definitely acceptable". The results are calculated from the applicants' responses to survey questions that are not used in the actual matching process. Bootstrap standard errors from 10, 000 samples are in parentheses.

	Program Unacceptable Possibly Acceptable Definitely Acceptable
	P1	22	10	67
		(3.63)	(2.62)	(4.06)
	P2	29	19	53
		(3.98)	(3.43)	(4.39)
	P3	38	18	44
		(4.30)	(3.34)	(4.40)
	P4	7	12	81
		(2.23)	(2.89)	(3.46)
	P5	33	24	43
		(4.15)	(3.74)	(4.38)
	P6	78	7	16
		(3.69)	(2.26)	(3.17)
	P7	40	18	43
		(4.27)	(3.34)	(4.30)
	When assuming that applicants do not apply to unacceptable programs, we notice that
	one applicant is matched with an unacceptable program under all mechanisms (and is en-
	rolled in this program in September 2013). Since dropping the applicant's unacceptable
	programs from his/her ROLs would change the matching outcome under every mechanism,

Notes:

we instead re-categorize the program to be "possibly acceptable" to this applicant. Furthermore, there are 9 applicants whose ROLs under DA are not consistent with the survey responses, provided that they report true preferences under DA. For example, one ranks an unacceptable program before a possibly acceptable one. For these applicants, we update some of the programs' acceptability to restore consistency. More details on this data cleaning are available in Appendix B.

Table 3 :

 3 Summary Statistics

	Variable Mean S.D. Min	Max
	M1 Grades: First semester 11.66 2.21 6.01 17.40
	M1 Grades: Final (2 semesters) 12.27 2.04 8.02 17.68
	Age 24.47 1.73 20.96 33.57
	M1 Program: Economics	0.57	0.50	0	1
	M1 Program: Statistics	0.34	0.48	0	1
	Female	0.45	0.50	0	1
	Scholarship	0.28	0.45	0	1

Table 4 :

 4 Number of Programs Ranked by Applicants (in percentages)

	Mechanism	1	2	# of programs ranked 3 4 5	6	Average number of 7 programs ranked a
	DA	4	10	17	26	28	15	0	4.09
		(1.69) (2.62) (3.31) (3.87) (3.95) (3.14) -	(0.12)
	DA-T-4	4	11	29	57	-	-	-	3.38
		(1.69) (2.70) (3.98) (4.34)	-	-	-	(0.07)
	DA-C	5	14	56	12	9	5	0	3.21
		(1.84) (3.02) (4.42) (2.87) (2.54) (1.85) -	(0.10)

Table 5 :

 5 Number of Matched Applicants by Program under Each MechanismThis table shows the number of applicants matched with each program under each mechanism. The total capacity is 142. Three programs, P5-P7, do not meet their capacities. Bootstrap standard errors from 10, 000 samples are in parentheses.

	Program	Capacity	#Matched Applicants under DA DA-T-4 DA-C
	P1	14	14	14	14
			(0.06)	(0.12)	(0.06)
	P2	22	22	22	22
			(1.30)	(1.28)	(1.48)
	P3	22	22	22	22
			(2.30)	(2.01)	(2.00)
	P4	28	28	28	28
			(0.02)	(0.02)	(0.02)
	P5	22	12	12	11
			(3.08)	(3.21)	(3.09)
	P6	12	10	10	10
			(2.31)	(2.31)	(2.31)
	P7	22	21	21	21
			(2.07)	(2.15)	(2.35)
	Total Unmatched		0	0	1
			(1.27)	(1.90)	(1.99)

Notes:

Table 6 :

 6 Ordinal Welfare of the Applicants under Each MechanismNotes: This table shows the numbers of applicants matched with their most preferred program, second most preferred one, etc., under each mechanism. The applicants' true ordinal preferences are what they reveal under DA. No applicant is matched with his/her 5th or less preferred program. Bootstrap standard errors from 10, 000 samples are not reported, but are all less than 0.05.

		Fraction of Applicants Matched with Most Preferred 2nd Preferred 3rd Preferred 4th Preferred	Unmatched
	DA	85	10	4	1	0
	DA-T-4	85	10	4	1	0
	DA-C	85	10	4	0	1

Table 7 :

 7 Table 7 further investigates individual matches. The left side of the table reports the Deviation from the Optimal Stable Matching under Each Mechanism

	Mechanism	Blocking Pairs #pairs #app. #prog.	App. w/ Diff. Match Total Worse off Better off	Prog. w/ Diff. Match Total Worse off a Better off a
	DA-T-4	1	1	1	3	2	1	3	2	1
		(1.87) (1.73)	(0.85)	(3.36)	(2.24)	(1.45)	(1.74)
	DA-C	2	2	2	4	3	1	4	3	1
		(2.64) (1.92)	(1.07)	(3.41)	(2.32)	(1.46)	(1.62)

frequency of blocking pairs under the two mechanisms. DA-T-4 leads to one blocking pair only, and DA-C results in two blocking pairs formed by two applicants and two programs. Furthermore, we investigate individual welfare across mechanisms. The middle part of

Table 8 :

 8 Summary Statistics: Number of Candidates to Be Screened

		mean	s.d.	min max
	DA	75.29 37.39	11	120
	DA-T-4 62.29 33.97	11	117
	DA-C	59.14 31.14	11	107

Table 9 :

 9 Estimation of Applicant Preferences

		P1	P2	P3	P4	P5	P6	P7
	Grade: First semester	0.28	0.10	0.00	0.10	0.00	-0.04	-0.01
		(0.08) (0.07) (0.07) (0.06) (0.06) (0.08) (0.08)
	M1 Program: Economics	0.58	-0.37	0.83	-0.12 -0.027 -6.65	0.016
		(0.50) (0.49) (0.98) (0.78) (0.55) (1.16) (0.51)
	M1 Program: Statistics	1.13	-0.71	2.73	-0.31	-0.02	-6.43	0.58
		(0.51) (0.52) (1.02) (0.81) (0.59) (1.18) (0.54)
	Female -0.39	0.95	0.55	-0.54	0.672	0.51	-0.04
		(0.31) (0.30) (0.30) (0.31) (0.27) (0.36) (0.32)
	Scholarship -0.57	-0.99 -0.024 -0.58	0.00	-0.32	-0.70
		(0.36) (0.37) (0.27) (0.35) (0.27) (0.40) (0.33)
	Intercept	1.11	0.71	0.377	1.88	0.55	-0.87	0.40
		(0.16) (0.16) (0.18) (0.16) (0.14) (0.19) (0.16)

Table 10 :

 10 Solution Concepts and Evaluation Methods

		Panel A. Solution concepts
	Complete information?
	A1. Yes (Nash equilibrium)	Applicant and program preferences are common knowledge. Ev-
		ery applicant best responds to others' actions in equilibrium.
	A2. No (Bayesian Nash)	Applicant and program preferences are private information, but
		their distributions and X are common knowledge. Every ap-
		plicant best responds to the distribution of others' actions in
		equilibrium, conditional on common knowledge.
	Panel B. Methods for Outcome Evaluation (conditional on common knowledge X)
	Conditional on observed applicant
	& program ordinal preferences?
	B1. Yes (sample-specific)

Table 11 :

 11 Estimation of the Grade Equation

		Grade (1st semester) Economics Statistics M1 Program	Female Scholarship Intercept
	Estimate	0.86	-0.42	-0.73	0.08	-0.37	2.83
	Std. Error	(0.03)	(0.25)	(0.26)	(0.14)	(0.15)	(0.42)
	Notes: Number of observations: 129; Residual standard error: 0.76 on 123 degrees of freedom; R-squared: 0.87; Adjusted R-squared: 0.86; F-statistic: 158.1 on 5 and 123 degrees of freedom, p-value: 2.2e ¡ 16.

Table 12 :

 12 Applicant Ordinal Welfare under Different Market Designs:

	Counterfactual Analysis; Relative to the Applicant-Optimal Stable Matching
	DA-T of diff. degrees	DA-C w/ diff. marginal application cost
	Better off Mean s.d. Mean Worse off s.d.	Marginal cost	Better off Mean s.d.	Worse off Mean s.d.

Table B .

 B 1: Modifications to the Survey Data on Program Acceptability

		Submitted ROL	Original Program Acceptability	Modified Program Acceptability
	App.	under DA	P1 P2 P3 P4 P5 P6 P7	P1 P2 P3 P4 P5 P6 P7
	1	(P3, P1, P4, P7, P2, P6, P5

In practice, applicants pay a constant marginal cost if one applies to more programs beyond a limited number of choices, e.g., NRMP in the U.S. and university admissions in Hungary. An application limit usually allows applicants to submit a prescribed number of applications. For example, it is adopted in school choice in New York City and Paris and university admissions in Brazil, Chile, and China.

It is important however to ensure that when they screen candidates, programs are not informed of actual ROLs or any signal thereof.

In contrast, the recent literature on school choice is mostly interested in the welfare of one side, students (see, for a survey,[START_REF] Pathak | The mechanism design approach to student assignment[END_REF]. In that setting, schools are passive and only endowed with priorities instead of preferences.

The Immediate Acceptance mechanism, also known as the Boston mechanism, is sometimes used for school choice in practice. The definition of the mechanism is given in Appendix A.1. Although also being included in the experiment that we conduct, this mechanism is not the focus of the current study. We therefore do not present the results of this mechanism.

We use a lottery to break ties for each program. Because ties involve the same applicant being sampled multiple times in a resample, how ties are broken does not affect our outcome. Relatedly, because some variables, X, are assumed to be common knowledge among all applicants, re-sampling should be conditional on X. As this would deflate standard errors and potentially lead to small sample issues, we present the results from random resampling which would tend to be conservative.

Given two matchings, µ and µ I , program j is better off if the newly matched applicants, µ I¡1 pjqzpµ ¡1 pjq µ I¡1 pjqq, dominate the displaced applicants, µ ¡1 pjqzpµ ¡1 pjqµ I¡1 pjqq, i.e., element-wise µ I¡1 pjqzpµ ¡1 pjq µ I¡1 pjqq ¡ j µ ¡1 pjqzpµ ¡1 pjq µ I¡1 pjqq when the matched applicants in these two sets are ordered according to j's ordinal preferences, ¡ j .

This formalization to take into account the three types of acceptability differs from our theoretical framework in Section 2. However, as long as we categorize both "definitely acceptable" and "possibly acceptable" as acceptable, our theoretical results still hold true.

Because no one with p i,j 0 is accepted by program j, how we rank the applicants with p i,j 0 does not matter, as long as they are ranked after those with p i,j 1.

An alternative is to consider sequences pi 1, ., i K q, pi K 1, ., i 2K q, etc., in which independence may be satisfied but information is more limited.

This restriction can be relaxed in a more general setting. If it is costly to submit a one-choice ROL, some applicants may choose not to participate in the matching when their expected benefit is less than the application cost.

We choose not to use the estimate of the latent score (equation 4) to measure programs' cardinal preferences because (i) only the ordinal information in program preferences matter in the game (not the cardinality) and (ii) the only observable determining the latent score is applicants' final grade. The latter justification motivates our first measure of program welfare.

This study was approved by the Toulouse School of Economics Research Ethics Committee (# 27052013). We gratefully acknowledge financial support from the European Research Council under the European Community's Seventh Framework Program FP7 2007-2013 grant agreement N o 295298. The usual disclaimer applies.

A. Program Welfare Definition 1: Grades b DA-T-6 0.00 0.00 0.00 0.00 0.00001 0.00 0.00 0.00 0.00 DA-T-5 0.00 0.00 0.00 0.00 0.000031 0.00 0.01 0.00 0.01 DA-T-4 0.00 0.00 0.00 0.00 0.0001 0.00 0.01 0.00 0.01 DA-T-3 0.01 0.03 0.03 0.07 0.00031 0.00 0.01 0.00 0.02 DA-T-2 0.12 0.06 0.29 0.10 0.001 0.00 0.03 0.01 0.04 DA-T-1 0.26 0.13 0.55 0.12 0.0031 0.02 0.05 0.03 0.08 0.01 0.05 0.08 0.08 0.13 0.031 0.11 0.10 0.21 0.16 0.1 0.18 0.11 0.41 0.11 0.31 0.27 0.12 0.48 0.11 1 0.28 0.13 0.54 0.11 B. Program Welfare Definition 2: Rank b DA-T-6 0.00 0.00 0.00 0.00 0.00001 0.00 0.00 0.00 0.00 DA-T-5 0.00 0.00 0.00 0.00 0.000031 0.00 0.01 0.00 0.01 DA-T-4 0.00 0.00 0.00 0.00 0.0001 0.00 0.01 0.00 0.01 DA-T-3 0.01 0.03 0.03 0.07 0.00031 0.00 0.01 0.00 0.02 DA-T-2 0.16 0.09 0.26 0.11 0.001 0.00 0.03 0.01 0.04 DA-T-1 0.36 0.15 0.45 0.12 0.0031 0.02 0.05 0.03 0.08 0.01 0.05 0.08 0.08 0.13 0.031 0.12 0.10 0.21 0.16 0.1 0.20 0.11 0.39 0.11 0.31 0.33 0.13 0.42 0.12 1 0.36 0.13 0.45 0.12 Notes: The counterfactual simulation is the same as that in Table 12; the notes therein provide more details. In each of the 4000 simulation samples, we first calculate how many programs are better off (or worse off) relative to the program-optimal matching according to two measures. The first is the sum of final grades of all applicants matched with the given program, and the second is the sum of matched applicants' rankings by the program (129 points if matched with the top-ranked applicant, 1 point if matched with the lowest-ranked applicant). Under a given market design, the table then reports the means and standard deviations of the measures on welfare changes across simulation samples.

Allowing inter-program comparison of welfare, we draw similar conclusions. See Appendix D.3 for a detailed discussion.

Conclusion and Discussion

This paper investigates the market design for a two-sided many-to-one matching market with the application cost as a tool to reduce congestion and lower the screening costs of programs.

Both forms of application cost, DA-T (an application limit) and DA-C (a positive marginal cost of application), are effective in reducing congestion. However, some key differences should be noted.

First, under DA-T of degree K, the marginal cost of applying to an additional program is zero when the total number of applications is below K. However, the marginal benefit

Application Costs and Congestion in Matching Markets

Yinghua He Thierry Magnac

February 1, 2019 Appendix A Experiment: Design and Implementation

List of Appendices

A.1 The Boston Immediate Acceptance Mechanism

A popular mechanism is the Immediate Acceptance mechanism (IA), also known as the Boston mechanism, which solicits ROLs from applicants, uses programs' strict rankings over applicants as inputs, and includes multiple rounds:

Round 1. Each program considers all the applicants who rank it first and assigns its positions in the order of the program's preferences until either no positions remain or no applicant who has listed it as his/her first choice remains.

Generally, in

Round k (k ¡ 1). The k th choice of applicants who have not yet been assigned is considered. Each program that still has available positions assigns the remaining positions to applicants who rank the program as their k th choice in the order of that program's preferences until either no positions remain or no applicant who has listed it as his/her k th choice remains.

The process terminates after any round k in which every applicant is assigned a position at some program or if the only applicants who remain unassigned listed no more than k choices.

A.2 Design: Interface for Applicants

The experiment provides applicants with an interface hosted on the official website that Université Toulouse 1 Capitole uses for coursework. With screenshots from the website (Figures E.1-E.5), this appendix details each step of the experiment involving applicants.

To minimize the potential "framing" effects, we randomize on three dimensions: (1) The order of the programs in the survey questionnaire on acceptability, (2) the order of the programs when applicants are asked to rank them under the four mechanisms, and (3) the order of mechanisms in which applicants play. First, applicants are randomly and

(almost) evenly divided into seven groups. Second, for each group, we assign an order of the seven programs to be presented when asking applicants to report acceptability. The seven program orders are such that each program is presented once first, once last, and the rest at random positions. Third, each group faces the "reverse" program order when asked to rank the programs under the four mechanisms. That is, if P1 is the first to be shown in the acceptability survey, it is presented last when the applicant decides her ROL, and vice versa.

Moreover, these seven program orders are the same ones used in the survey. Finally, each group of applicants plays the four mechanisms following one of the four orders conditional on DA-C and DA-T always being after DA.

A.2

The experiment begins with the welcome page (Figure E.1) to which applicants have access after being notified by email. It describes in both English and French the purpose of the experiment (i.e., trying four mechanisms instead of adopting only one mechanism) and explains important dates and other information. The above content is the same for every applicant; then, every applicant clicks the link that takes her to the next screen, which differs across applicants.

On the second webpage, we implement a survey on program acceptability (Figure E.2).

For each given program, applicants reveal their enrollment decision under the assumption that they were only accepted by that program. It is emphasized that the answers to survey questions are not used in the actual matching mechanisms. The order of the programs is randomized to avoid potential framing effects. Similarly, the link to the next step is also randomized such that one may play either IA or DA first.

Once they have reached the webpage to submit an ROL under a given mechanism, applicants are given suggestions on how to play the specific game . It is also emphasized that each ROL submitted under a given mechanism is used if and only if the mechanism is selected for the final assignment. Under every mechanism, all the programs are listed for applicants to rank and the order of the programs is randomized.

A.3 Programs' Involvement in the Experiment

When designing the experiment, all the program directors were informed about the experiment and its intended purposes. The seven directors were involved at all stages of the experiment.

Pre-experiment stage. Each director was asked to provide a short description of the program, prerequisites (if any), and a capacity. This information was then uploaded to the website for the experiment.

Screening candidates. We did not simply forward applicants' submitted ROLs under the four mechanisms to the program directors. There were several concerns. First, we intended to prevent the directors from learning applicants' ROLs (i.e., how each applicant ranked the programs). Second, providing all ROLs would require the directors to screen too many candidates (c.f., Table 8).

Instead, in the files containing all the applicants, their grades and their M1 program enrollment information, we pre-selected a subset of applicants for each program. A.1 Each

A .1 This pre-selection resembles the service provided by recruiting firms to employers. Although it may have potentials in reducing congestion, this practice is beyond the scope of our study.

Appendix B Data

B.1 Programs' Ranking over All Applicants

As discussed in Appendix A.3, the program directors did not rank all applicants, while a complete order that ranks all applicants by each program is needed for counterfactual analysis. We construct the complete order by the following steps:

(i) The partial orders of applicants that are submitted by the program directors are always respected in the constructed complete orders.

(ii) For the two programs with prerequisites, every applicant who does not meet the prerequisites is ranked at the bottom in a descending order of their final grades.

(iii) For each program, the complete order by applicants' final grades is respected whenever it is not in conflict with the program's submitted partial order. When there is a conflict, we do the following adjustment: Suppose applicant i is moved up in the submitted partial order and is just above applicant i ¦ . This implies that i's final grade is lower than i ¦ 's. In the constructed complete order, i is also just above i ¦ . We iterate this process for each conflict between the ranking by final grades and the submitted partial order.

B.2 Data Cleaning

B.2.1 Acceptability and Applicant Strategies

The survey data on program acceptability and applicants' submitted true preferences under DA are not always consistent with each other. Because we emphasize to applicants that the survey data is not used in the matching mechanisms, the DA data should have a greater weight. Below, we describe how we make some modifications, but as few as possible, in the survey data to restore consistency.

According to the original survey data, one applicant is matched with an unacceptable program (the third choice in the submitted DA ROL) under the three versions of the DA mechanism and with another under IA (the fourth choice in the submitted DA ROL). Moreover, we observe that the applicant enrolls in the matched program under DA in September 2013. We therefore change the applicants' third and fourth choices to be "possibly acceptable."

Another type of inconsistency occurs when an applicant ranks an unacceptable program above an acceptable or puts a "possibly acceptable" program above a "definitely acceptable" in the submitted DA ROL. There are in total nine applicants who have this inconsistency.

Appendix C Likelihood Function based on the Extended

Rank-Order List

This appendix details the derivation of the likelihood function based on the extended rankorder list which is the ROL submitted under DA supplemented by information on program acceptability.

C.1 Notations and Properties

Let:

Gpx, λ, µq µ expp¡λ expp¡xqq.

Note that a Type I extreme value random variable is such that: Prpε yq Gpy, 1, 1q » y ¡V expp¡xq expp¡ expp¡xqqdx, and:

Gpx a, λ, µq Gpx, λ expp¡aq, µq.

We also have:

and Gp V, λ, µq µ Furthermore:

Gpy, 1 λ, µ 1 λ q, so that:

These properties are used below.

and if p h 1: μ0,h 1 ¹ 1¤m¤ J Cpb m ; ppb k q m¤k¤ J q, η, pb J¡k ηq 1¤k¤h , pb k ηq k¥J q ' Cp0; 0, pb k q k¥ J 1 qµ p0q h , Finally:

Possible mistakes are checked by summing over all possible cases under different scenarios of variables and coefficients and assessing that the sum of probabilities is equal to one. In an additional note which is available upon request, cases for h 0, 1 and 2 are written directly, and we have checked that the formula above applies as well. Cases h 0 and h 1 are derived below.

h=0 We have by application of the above a single term p h 1 1:

Cpb m ; pb k q k¥m q.

h=1 We have by application of the above two terms p 1 and p h 1 2:

Cpb m ; pb k q k¥m q, μ0,2 ¹ 1¤m¤ J Cpb m ; ppb k q m¤k¤ J q, η, pb k ηq k¥ J 1 q ' ¢Cp0; 0, pb k q k¥ J 1 q ¹ m¥J Cpb m ; pb k q k¥m q, because µ p0q

1 µ p0q ± m¥J Cpb m ; pb k q k¥m q.

Appendix D Counterfactual Analysis

D.1 Solving Equilibrium

This appendix specifies the algorithm to numerically solve an equilibrium under DA-T of different degrees or DA-C with various marginal costs.

We begin with drawing M p 4000q samples of size I (number of applicants) in which random shocks to applicant preferences (ε pmq i ), to applicants' final grades (ν pmq i ), and to program preferences (ξ pmq i,j ) are generated. Using these simulated shocks as well as estimated coefficients and observed characteristics, we compute applicant and program preferences, both cardinal and ordinal; moreover, program preferences are translated into rankings over applicants from 1 to I denoted by r pmq i,j , with larger r pmq i,j indicating being more preferred.

D.1.1 Solving Bayesian Nash Equilibrium under DA-T

For DA-T of degree K t1, 2, . . . , 6u, we adopt an iterative process defined by index t p 0, 1, . . .q:

• Initialization: We first initialize the cutoff distribution, Φ 0 . For each simulation sample m:

(i) We let the matching outcome µ pm,0q (artificially) be μDA , where μpDAq is the applicant-optimal stable matching observed in our real data (i.e., the outcome from DA as calculated in Section 4);

(ii) We then calculate the distribution of cutoffs Φ 0 by setting the cutoff of each program in each simulation sample, κ pm,0q

Because µ pm,0q μpDAq for all m, κ pm,0q j is constant across all simulation samples.

This leads to a degenerate distribution, Φ 0 .

We then calculate the simulated preferences of applicants and programs:

(i) We compute applicants' cardinal and therefore ordinal preferences by inputting the simulated shocks ε pmq i , estimated coefficients, and observed characteristics into the utility functions specified in equations ( 1) and ( 2). Note that shocks to applicant preferences (ε pmq i ) are drawn unconditionally on ordinal preferences observed in the sample.

D.3 Counterfactual Analysis of Cardinal Welfare D.3.1 Applicants Cardinal Welfare

Table D.2 provides an evaluation based on the estimated cardinal preferences while explicitly taking into account the application costs. For each given market design, we first calculate cardinal welfare per applicant in each simulation sample and then measure its mean and standard deviation across all simulation samples. When doing so, we ignore the "strategizing" cost that an applicant has to incur to find an optimal ROL.

Panel A first presents per-applicant cardinal welfare across the DA-T of different degrees under which an applicant can submit a limited number of choices. The results confirm Figure 4 and show that DA-T-6 to DA-T-4 achieve the exact DA outcome, while DA-T-3 incurs a small welfare loss. Surprisingly, DA-T-2 obtains a welfare gain that is comparable to re-assigning 1.5 applicants from an "almost" unacceptable program to an "almost" definitely acceptable one (see Section 5.5.1 for a discussion on this cardinality measure). This outcome occurs even though DA-T-2 leaves 0.86 applicants unmatched on average, as partially reflected in the increase in the standard deviation of applicant welfare. DA-T-1 brings the lowest applicant welfare with the highest variance, consistent with the large number of unmatched applicants (4.56). Relative to DA, the welfare loss in DA-T-1 is comparable to moving 2.9 applicants from an almost unacceptable program to an almost definitely acceptable one.

The analysis of DA-C can also be found in Panel A of Table D.2. In addition to describing the per-applicant welfare produced by matching outcomes, we also report the application costs paid by applicants and their net welfare. In terms of matching outcomes, per-applicant welfare has a non-linear relationship with application cost: Welfare increases with the application cost when the cost is not too high (¤ 0.31), but it drops to the lowest when it is prohibitively high ( 1). In contrast, the standard deviation of per-applicant welfare monotonically increases with cost, consistent with the monotonically increasing number of unmatched applicants. Among all DA-T and DA-C configurations, the maximum welfare gain relative to DA is obtained for DA-C with a cost 0.31, equivalent to re-assigning 5.8 applicants from an almost unacceptable program to an almost definitely acceptable one. The largest welfare loss (under DA-T-1) amounts to moving 1.1 applicants from an almost definitely acceptable program to an almost unacceptable one.

The costs actually paid by applicants follow the same pattern as the welfare. Applicants pay higher costs when the cost increases but remains moderate, and they stop applying to additional programs once the cost is prohibitively high. The maximum costs are paid when the marginal cost is 0.31: The magnitude is equivalent to re-assigning 7.8 applicants from A.24 an almost definitely acceptable program to an almost unacceptable one.

As discussed earlier, we can consider the application cost as a transfer from applicants to programs, e.g., a transfer of monetary fees. Nonetheless, one may be interested in applicants' net welfare, given the application cost they pay. Panel A of Table D.2 shows that the net welfare is monotonically decreasing in application cost. Relative to DA, the maximum welfare loss (at marginal cost 1) amounts to re-assigning 2.5 applicants from an almost definitely acceptable program to an almost unacceptable one, which is still slightly lower than the loss under DA-T-1.

Notes:

The counterfactual simulation is the same as that in Table 12; the notes therein provide more details. In each of the 4000 simulation samples, we first calculate the number of applicants who are better off (or worse off) relative to the DA outcome, which is the applicant-optimal stable matching. The table then reports the means and standard deviations of these two ordinal welfare measures under a given market design across simulation samples.

In summary, Panel A confirms that the welfare loss due to application costs (in the form of DA-T or DA-C) is negligible when the cost is low. Moreover, combined with Figure 4, DA-C appears to be a better choice than DA-T: We can set the marginal cost as high as 0.01 so that there is almost no loss in match quality, and the number of candidates screened is 1.44 per opening. To reach a comparable screening cost, DA-T has to be of degree 2 While this prediction is true in simulations of equilibrium outcomes, it is not true in the actual game played. A.4 The welfare loss is due largely to the unmatched applicant under DA-C in the experiment, which may be explained by the fact that applicant actions, which are held constant across simulation samples, can be suboptimal in some samples. Moreover, this loss may indicate that applicants do not use equilibrium strategies in the experiment.

D.3.2 Program Cardinal Welfare

Similar to the analysis of applicants' cardinal welfare, we first study per-program welfare (Table D.3). Recall that this welfare analysis does not consider screening costs. A .4 When simulating the experimental configuration of DA-C, almost no applicants rank more than three choices, even when the cost is negligible. Therefore, this simulation leads to the same outcome as DA-T-3, which obtains (almost) the same outcome as DA.

A.26 or 9.29, according to the two welfare measures, respectively. For example, under DA-T-1, 4.11 applicants on average are unmatched (Figure 4), which leads to a welfare loss of approximately 7 or 38. The actual loss is smaller because unmatched applicants tend to have lower final grades and/or to be ranked lower by programs.

Nonetheless, Table D.3 shows that the loss in program welfare is negligible when the application cost is low. Even in the extreme, under DA-T-1 or DA-C with a marginal cost equal to one, on average, the loss to a program's welfare amounts to losing an applicant with a final grade ranging from 5.93 to 6.61 or one ranked 109th. On the other hand, the standard deviation indicates that the effect on program welfare varies more significantly across simulation samples when the application cost increases.

Search courses

Sub

Choosing Your M2 Program

As the first year of your master's program has ended, it is time for you to choose an M2 program to continue your education at TSE. The online application system is open from June 12, 0:00 to June 18, 12:00 (noon).

Choose Your M2 Program and Help TSE Improve the Matching Process

Please note that you will be asked to submit four (4) rank-order lists each of which is under a specific mechanism. The four (4) mechanisms are well-known and will be explained in detail during the application process. For the final assignment, only one of them will be chosen, and to the best of our knowledge, we believe that every mechanism has an almost equal probability to be chosen. We guarantee that every

Choisissez votre programme de M2

Comme l'année de M1 touche à sa fin, il est temps pour vous de choisir les programmes de M2 auxquels vous souhaitez candidater.

Les candidatures se feront sur internet entre le 12 juin à 0h00 et le 18 juin à 12h00 (midi).

Choisissez votre programme de M2 et aidez TSE à améliorer ses procédures de sélections.

Avant tout, veuillez noter que nous vous demandons d'inscrire quatre (4) listes de choix, chaque liste s'appliquera à un mécanisme d'allocation différent. Les quatre (4) mécanismes utilisés sont bien connus en théorie économique et seront expliqués en détail durant la procédure d'assignation. Pour l'assignation finale des étudiants dans

Choix des programmes M2

The application system has been closed. Submissions after June 18, 12:00 will not be taken into account.

Search courses

Sub

Choix des programmes M2

Step 1: Unacceptables

Step 1: Are there any M2 programs which do not fit your interests?

Before you start, it is very important for you to know your own interests and to know more about the M2 programs offered by TSE.

Information on the M2 Programs:

You may find a description of the seven programs here. It also provides each program's minimal requirements and tentative quota (number of seats).

Please make sure whether there is any program that does not fit your interests. In other words, if you were assigned to one of such programs, you would rather leave TSE to pursue other possibilities.

To facilitate your decision making, we would like to ask you the following questions.

Please note that your answers to the following questions will not be used in the admission process and will not affect your possible study at TSE in the future.

Please choose one and only one of the three answers for each question. Etape 1 : Y a-t-il des programmes de M2 qui ne vous intéressent pas?

En premier lieu, il est important que vous connaissiez vos centres d'intérêts et vos préférences envers les différents M2 offerts par TSE.

Information sur les programmes de M2:

Vous pouvez trouver les descriptions et informations sur les programmes de M2 en cliquant ici. Ces liens fournissent également des informations sur les prérequis de chaque programme ainsi que le nombre de places disponibles dans chacun Notes: This is the second screen an applicant sees when participating in the experiment. It provides, in both English and French, (1) a survey on program acceptability, (2) explanations that the survey answers are not used in the assignment mechanism, and (3) the link to the program descriptions and the link to the next step. The content of the screen is the same for every applicant, but the order of survey questions (i.e., the order of the programs) and the link to the next step are randomized. Therefore, applicants play the four mechanisms in a randomized order.

A.29

Search courses

Sub

Choix des programmes M2

Step 2: DA 1

Step 2: Please Rank the M2 Programs

Scenario: Deferred Acceptance mechanism

Please rank the seven M2 programs offered by TSE using the form at the bottom of the page.

Your rank order list submitted here will be used to calculate your assignment if and only if the Deferred Acceptance algorithm is chosen to be the matching procedure.

We guarantee that all M1 students face the same rules in this procedure.

Based on well-known scientific research results, we make the following suggestions: In the above form, "1" means your number 1 choice, "2" means number 2, and so on.

Dans le tableau précédent, le programme classé "1" correspond à votre choix numéro 1, le programme classé "2" correspond à votre choix numéro 2, etc.

-----Page Break -----http://cours.ut-capitole.fr/mod/questionnaire/preview.php?id=8827

Figure E.3: The Deferred-Acceptance Mechanism

Notes: This is the screen where an applicant submits her application under the Deferred-Acceptance mechanism. It presents, in both English and French, (1) explanations that the application is used if and only if the Deferred-Acceptance mechanism is chosen, (2) some tips that can be derived from the literature, (3) the links to the pages describing the mechanism and the programs, and (4) the programs that each applicant can rank. This screen is the same for every applicant, except that (1) the link to the next screen is randomized, (2) the order of the programs presented is randomized, and (3) each applicant may reach this screen at different stage in the experiment.

A.30

Search courses

Sub

Choix des programmes M2

Step 2: DA-E 1

Step 2: Please Rank the M2 Programs Scenario: Deferred Acceptance mechanism with motivation letters. Please rank the seven programs using the form at the bottom of the page. Please note that you have to write a motivation letter for your choices 4, 5, 6, and 7, if you decide to rank more than 3 programs.

Your rank order list submitted here will be used to calculate your assignment if and only if the Deferred Acceptance mechanism, where motivation letters are required, is chosen to be the matching procedure. We guarantee that all M1 students face the same rules in this procedure. We think that "Actions speak louder than words". Therefore, we do not ask you to write letters for your top three choices. Based on well-known scientific research results, we make the following suggestions: 1. If you do not mind writing motivation letters, it is in your best interest to rank more programs and rank them according to your true preferences.

2. If there are any programs in which you are absolutely not interested (and you answered "No" in the first step), it is always optimal to put them at the bottom of your ranking or not to rank them.

3. Among those programs that are ranked by you, it is optimal to rank them according to your true preference order. 4. A recommended decision process may be: In the above form, "1" means your number 1 choice, "2" means number 2, and so on.

Dans le tableau précédent, le programme classé "1" correspond à votre choix numéro 1, le programme classé "2" correspond à votre choix numéro 2, etc. Notes: This is the screen where an applicant submits her application under the Deferred-Acceptance mechanism with costs (in terms of writing a motivation letter). Part of the screen, between parts III and IV is omitted in the figure, but the information on that part is a continuation of that on part III. It presents, in both English and French, (1) explanations that the application is used if and only if the Deferred-Acceptance mechanism with costs is chosen, (2) some tips that can be derived from the literature, (3) the links to the pages describing the mechanism and the programs, and (4) the programs that each applicant can rank. This screen is the same for every applicant, except that (1) the link to the next screen is randomized, (2) the order of the programs presented is randomized, and (3) each applicant may reach this screen at different stage in the experiment.

A.31 Please rank the 7 M2 programs using the form at the bottom of the page. Please note that you are only allowed to rank 4 programs.

Your rank order list submitted here will be used to calculate your assignment if and only if the so-called Deferred Acceptance mechanism, where everyone is allowed to rank up to 4 programs, is chosen to be the matching procedure. We guarantee that all M1 students face the same rules in this procedure.

Based on well-known scientific research results, we make the following suggestions: 1. It may not be optimal to report your true preferences. In the above form, "1" means your number 1 choice, "2" means number 2, and so on.

Dans le tableau précédent, le programme classé "1" correspond à votre choix numéro 1, le programme classé "2" correspond à votre choix numéro 2, etc.

-----Page Break -----http://cours.ut-capitole.fr/mod/questionnaire/preview.php?id=8829 Notes: This is the screen where an applicant submits her application under the Deferred-Acceptance mechanism with truncation (i.e., submitting no more than 4 choices). It shows, in both English and French, (1) explanations that the application is used if and only if the Deferred-Acceptance mechanism with truncation is chosen, (2) some tips that can be derived from the literature, (3) the links to the pages describing the mechanism and the programs, and (4) the programs that each applicant can rank. This screen is the same for every applicant, except that (1) the link to the next screen is randomized, (2) the order of the programs presented is randomized, and (3) each applicant may reach this screen at different stage in the experiment.