{'fraction_non_alphanumeric': 0.03301244731620119, 'fraction_numerical': 0.01389048329698083, 'mean_word_length': 4.339579684763573, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Playing on a Level Field: Sincere and Sophisticated Players in the Boston Mechanism with a Coarse Priority Structure

Who gains and who loses from a manipulable school choice mechanism? We examine this question with a focus on the outcomes for sincere and sophisticated students, and present results concerning their absolute and relative gains under the manipulable Boston Mechanism (BM) as compared with the strategy-proof Deferred Acceptance (DA). The absolute gain of a student of a certain type is the difference between her expected utility under (an equilibrium of) BM and her utility under (the dominant-strategy equilibrium of) DA. Holding everything else constant, one type of a player has relative gain with respect to another type if her absolute gain is higher. Prior theoretical works presented inconclusive results regarding the absolute gains of both types of students, and predicted (or assumed) positive relative gains for sophisticated types compared to sincere types. The empirical evidence is also mixed, with different markets exhibiting very different behaviors. We extend the previous results and explain the inconsistent empirical findings using a large random market approach. We provide robust and generic results of the"anything goes"variety for markets with a coarse priority structure. That is, in such markets there are many sincere and sophisticated students who prefer BM to DA (positive absolute gain), and vice versa (negative absolute gain). Furthermore, some populations may even get a relative gain from being sincere (and being perceived as such). We conclude by studying market forces that can influence the choice between the two mechanisms.


Introduction
School districts all over the world are increasingly realizing the benefits of letting parents choose the educational environment that best fits their children. The move from a zoning policy to a choice-oriented process, together with the scarcity of seats in some of the most highly demanded schools, calls for a regulated procedure or an algorithm for seat assignment. The Boston mechanism (henceforth BM), also known as Immediate Acceptance, is one of the most popular mechanisms for seat allocation. The appeal of BM lies in its simplicity in terms of both intuition and implementation. The mechanism, which also takes the parents' preferences into account, first maximizes the number of students who get their first choice, then maximizes the number of students who get their second choice, and so on. When performing this step-by-step maximization, the mechanism selects who gets admitted to overdemanded schools according to some (possibly school-specific) priority ordering. This process is so simple that in some small municipalities it is carried out manually using spreadsheet software.
Despite its seemingly straightforward description, one of the unfortunate properties of BM is that it is susceptible to strategic manipulation. Students (or parents) who carefully consider the workings of the mechanism can submit a rank-order list (ROL) that does not represent their true preferences, but may help them at being admitted to one of their (true) top schools. This raises two tightly related concerns: first, do students benefit or are they harmed by the use of a manipulable mechanism, and second, do students who are more sophisticated and more informed get an unfair advantage in public-school admissions. A good way to measure gain and loss in this context is to compare the outcome of BM with that of the student-proposing Deferred Acceptance algorithm (Gale and Shapley, 1962, henceforth DA), which is strategy-proof and therefore does not give an advantage to sophisticated students (Dubins and Freedman, 1981;Roth, 1982). 1 We say that a student has a positive absolute gain (from BM) if her expected utility under (an equilibrium of) BM is higher than her utility under (the dominant-strategy equilibrium of) DA. We say that a student has relative gain with respect to another student (or to a counterfactual version of the same student) if the absolute gain of the former is higher. Conveniently, when we measure the relative gains between two types of the same student who only differ in their level of sophistication, the comparison reduces to comparing their expected utilities under BM, since their outcome under DA is the same.
The first to approach these questions were Pathak and Sönmez (2008). They show positive absolute gain for sophisticated students, by demonstrating that a sophisticated student weakly prefers her outcome under the Pareto-dominant equilibrium of BM to her outcome under DA. 2 They then prove positive relative gains for sophisticated types compared with sincere types of the same player. That is, holding everything else fixed and focusing on the Pareto-dominant equilibria of BM, a player is weakly better off when she is sophisticated compared with when she is sincere.
Both of these results, however, require that schools have strict priority orderings over 1 The comparison to DA is appealing also since it replaced BM in several school choice systems that were redesigned by economists such as in Boston (Abdulkadiroglu et al., 2005) and New York City (Abdulkadiroglu et al., 2009).
2 For sincere students the comparison is ambiguous.
students -an assumption that is often unrealistic. In most circumstances, schools have a coarse priority structure, and ties are resolved using a random tie-breaking rule. For example, kids who have siblings attending a specific school may be given higher priority, but among kids with such siblings there is no strict order, nor is there one among kids who do not have siblings at that school. Allowing for a coarse priority structure, Abdulkadiroglu et al. (2011) first prove strictly positive absolute gains when all players are sophisticated, a result which is driven by the potential of BM to better express cardinal utility levels through preference reports. 3 Abdulkadiroglu et al. (2011) then show that in the presence of both sophisticated and sincere students, sincere students may potentially experience positive absolute gains as well, as they benefit from their strategic peers' demand shading under BM, and gain higher probability of being admitted to one of their top schools (compared with the DA outcome). That being said, in their model it is always better to be sophisticated (by assumption, since sophistication level is random and unobserved), and thus their model always predicts nonnegative relative gains for sophisticated types compared with sincere types. Their results crucially rely on all players having common ordinal preferences, and on specific symmetry assumptions: in their model, cardinal utility levels are drawn i.i.d. from a random distribution, players are either sincere or sophisticated with exactly the same probability, and results only apply to symmetric equilibria. As noted by Troyan (2012), the welfare comparisons of Abdulkadiroglu et al. (2011) are also sensitive to the assumption that there is only a single priority class (which mandates symmetric tie-breaking). This paper complements, extends, and hopefully clarifies, the existing results on absolute and relative gains of sincere and sophisticated students. Regarding relative gains, we observe that under weak priorities, being sincere can sometimes be an advantage rather than a liability. In fact, it is a likely situation for many students even in large random markets. The intuition is that a sincere student is committed to list her top schools first, even if they are over-demanded, and in doing so she crowds-out the competition more than a sophisticated student would. That is, other students who are sophisticated inevitably take the sincere student's commitment into account, and therefore rationally move toward ranking other schools higher. The comparison of whether a student is better off when she is sincere or when she is sophisticated is thus similar to the decision faced by a Stackelberg leader in a meta-game in which she can either commit to one specific strategy (be sincere), or not commit to any strategy and play according to a Nash equilibrium profile (be sophisticated).
Our first main result, Theorem 3.1, demonstrates that the first-mover advantage of sincere students is prominent even in large random markets. Our model employs a random market-generating process that produces markets with heterogeneous preferences and varying demands by mixtures of sophisticated and sincere students. We show that there is in expectation a constant fraction of students who strictly prefer to be sincere. 4 Nevertheless, the sincerity advantage under BM is sensitive both to market structure and to the extent of common knowledge of players' sophistication. Roughly put, the overall effect from being sincere as compared with being sophisticated is comprised of the negative effect of not responding to excess demand (identified by Pathak and Sönmez, 2008), which manifests in both strict-priorities and weak-priorities environments, and of the positive effect of crowding-out the competition, which is completely absent in strict-priorities environments. For example, if two or more of each student's top schools are likely to be over-demanded, sincerity would allow a student to crowd-out the competition in her top school. However, a sincere student who does not get her first choice pays an implicit cost of not having ranked her second choice first, which could potentially have represented a better trade-off between utility and admission probability. This nonresponsiveness to the excess demand of the top-choice school may or may not overshadow the benefit of the crowding-out effect.
Importantly, this result should not be narrowly interpreted. First, while the result in the main text is formulated with complete information on students' sophistication levels, it in fact holds even in the presence of incomplete information (see Appendix A). Second, we do not view this result as a statement on the relative gains of individual students, but rather about relative gains of distinguishable populations. In the real world, only some of each student's traits (e.g., gender, neighborhood, socioeconomic status) are observable by others. Sophisticated students who face a student with certain traits should evaluate her probability of being sincere based on prior information on all students with similar traits. Therefore, while it is (almost tautologically) better to be sophisticated when holding everything (including others' beliefs regarding oneself) else fixed, it is possible that an entire population will benefit from most or even all of its members being sincere, and having others knowing that. This is true to the extent that even sincere members of such a group may be better off compared with the hypothetical situation in which the entire population had been sophisticated. It is important to note that another possible reason for wanting to belong to a sincere population is that in real markets one may often face members from one's own community, and their sincerity may play to one's advantage. In order to abstract away from this effect of benefiting from the actions of others whose sincerity level is correlated with one's own, we assume in the main text that each population is represented by a single student. This ensures that our results are not driven by any interaction between two students of the same population. We further simplify the arguments by treating sophistication as a binary variable. Appendix A provides details on relaxing these restrictions.
Following our study of the relative gains, we turn to study the absolute gains of each type of student. Our second main result compares equilibria of BM with the DA outcome and shows that while there are indeed many students who prefer DA to BM, there are also many students who have an opposite preference, and this prediction holds true for both sophisticated and sincere students. The key insight here is that, compared with DA, BM may reduce students' opportunities to compete on desirable (over-demanded) schools. This effect, which is once again absent in strict-priorities environments, may in fact overcome the reduced-competition effect that Pathak and Sönmez (2008) identify. We show that in large random markets there is in expectation a constant fraction of students (either sincere or sophisticated) who strictly prefer the DA outcome to any BM equilibrium, as well as a constant fraction of students who have the opposite strict preferences.
An important aspect of our work is that it can explain the very different empirical results that were documented and analyzed in recent years. Studying elementary-school choice in Cambridge MA, Agarwal and Somaini (2018) show absolute gains for both sophisticated and sincere players, with sophisticated students gaining more relative to sincere students.  present qualitatively similar results from elementary-school choice in Barcelona. He (2017) uses data on middle-school choices in a neighborhood in Beijing and that is the only paper that we know of that finds relative gains for sincere students compared with sophisticated students. Kapor et al. (2017) do not explicitly separate agents into types, but argue that subjective (and possibly inaccurate) beliefs about demand could lead to negative absolute gains. De Haan et al. (2016) use data from Amsterdam to show negative absolute gains (i.e., students get higher expected utilities under DA).
We note that all of our arguments and results apply also beyond the plain vanilla BM, and in fact hold for virtually all known variants of BM: the Corrected Boston Mechanism (Miralles, 2009), the Modified Boston Mechanism (Dur, 2015), the Secure Boston Mechanism (Dur et al., 2017), and the Adaptive Boston Mechanism (Mennle and Seuken, 2017). In fact, they even hold for the entire family of First-Choice Maximal mechanisms (Dur et al., 2018b). Our proofs do not directly apply to manipulable mechanisms outside this family, such as DA with bounded lists (when the bound is binding and prevents agents from playing truthfully).
The paper proceeds as follows. After discussing related works, we present the model in Section 2, the results regarding relative gains in Section 3, and the results regarding absolute gains in Section 4. A discussion on the applicability of the results to realistic environments follows in Section 5, and Section 6 concludes.

Additional Related Literature
The mechanism design approach to school choice begins with Abdulkadiroglu and Sönmez (2003). Since then much of the academic literature was focused on the application of DA to different environments. BM itself was brought to the attention of economists by Abdulkadiroglu et al. (2005), who redesigned Boston Public Schools' existing mechanism and replaced it with DA. Abdulkadiroglu et al. (2005) noted that BM was prone to strategic manipulation, and pointed to anecdotal evidence suggesting that indeed some parents in Boston acted strategically. Following that, strategic behavior was demonstrated both in experimental labs (e.g., Chen and Sönmez, 2006, and many follow-up designs) and in real-world environments (see, e.g., . Ergin and Sönmez (2006) show that when priorities are strict and all students are sophisticated, moving from BM to DA is weakly beneficial for all students. 5 As mentioned, Pathak and Sönmez (2008) generalize this statement, claiming that the strategic manipulability of BM also has fairness implications, as it gives an advantage to sophisticated students. An experimental finding along the same lines was recently presented by Basteck and Mantovani (2018). Similar (if inconclusive) theoretical results for an environment with boundedly sophisticated (level-k) players are described by Zhang (2016). Dur et al. (2018a) study strategic behavior of students and its implications in the field.
Finally, this paper deals with the effects of weak priorities on the workings of BM. In that it relates to a recent line of works that deal with weak priorities and tie-breaking methods for other school choice mechanisms, such as DA (e.g., Abdulkadiroglu et al., 2009;Arnosti, 2015;Ashlagi and Nikzad, 2016;Ashlagi et al., 2015;Erdil and Ergin, 2008;Kesten, 2010) and Top Trading Cycles (for example, Abdulkadiroglu and Sönmez, 1998;Carroll, 2014;Pathak and Sethuraman, 2011).

The Model
Schools, Students, and Preferences We adopt much of the notation used by Pathak and Sönmez (2008). There is a finite set of schools, S = {s 1 , . . . , s m }, and a finite set of students, I = {i 1 , . . . , i n }. Each school s j has a capacity q s j . The (vNM) utility of a student i ∈ I from being assigned to school s ∈ S is u i (s), the utility from being unmatched is (normalized to) zero, and we assume that students are risk-neutral and so wish to maximize their expected utility. Throughout the paper, we assume that the priority structure of the schools is coarse to the extent that all students belong in the same priority class in all schools. While this is a simplifying assumption, it is not far from the properties of many real-life matching markets, and the resulting phenomena efficiently convey our main messages.
The Boston Mechanism Each student must report an ROL to BM, and then the mechanism is run as follows: 0. For each school s, a strict ordering of students τ s is drawn uniformly at random from the set of all permutations over I. 6 This ordering remains unknown to the students.
1. Each students applies to the school that she ranked as her first choice. A school whose capacity is at least the number of students who applied, permanently admits all of them. A school s whose capacity is less than the number of students who applied, permanently fills its capacity with a subset of these applicants that is chosen according to τ s .
2. Each student who was not admitted in the first round applies to her second choice. A school whose remaining capacity (taking into account the slots taken by all of the students admitted in the first round) is at least the number of students who applied in this round, permanently admits all of them. A school s whose remaining capacity is less than the number of students who applied in this round, permanently fills its remaining capacity with a subset of these applicants that is chosen according to τ s . . . .
k. Each student who was not admitted in the previous rounds applies to her kth choice. A school whose remaining capacity (taking into account the slots taken by all of the students admitted in all previous rounds) is at least the number of students who applied in this round, permanently admits all of them. A school s whose remaining capacity is less than the number of students who applied in this round, permanently fills its remaining capacity with a subset of these applicants that is chosen according to τ s . . . .
The Deferred-Acceptance Mechanism Each student must report an ROL to DA, and then the mechanism is run as follows: 0. For each school s, a strict ordering of students τ s is drawn uniformly at random from the set of all permutations over I. 7 This ordering remains unknown to the students.
1. Each student applies to the school that she ranked as her first choice. A school whose capacity is at least the number of students who applied, tentatively admits all of them. A school s whose capacity is less than the number of students who applied, tentatively admits a subset of these applicants that fills its capacity and that is chosen according to τ s , and permanently rejects all other applicants. . . .
k. Each student applies to her favorite school among those that have not rejected her yet. (So a students who has been tentatively admitted to some school in the previous round, reapplies to the same school in this round.) A school whose capacity is at least the number of students who applied in this round, tentatively admits all of them. A school s whose capacity is less than the number of students who applied in this round, tentatively admits a subset of these applicants that fills its capacity and that is chosen according to τ s , and permanently rejects all other applicants. . . .
The mechanism terminates when a round with no rejections occurs, following which all tentative admissions from this round become permanent. The resulting outcome is the student-optimal stable outcome.
Sincerity and Sophistication Students are either sincere or sophisticated. Sincere students truthfully report an ROL according to their utilities, while sophisticated students can submit any ROL regardless of their utilities. When analyzing the Boston mechanism, we look at a Nash equilibrium of the preference-reporting game among the sophisticated students. (We assume truthful reporting under DA, as this constitutes a dominant-strategy equilibrium.) Utilities While some of the examples in this paper use specific given utilities for each student, our main results apply to the uniform (n; u 1 , . . . , u k ) model, which we now describe. In this model, which is defined by fixed utilities u 1 > . . . > u k and a size n, there are n students and n schools, where each of the schools has a capacity of exactly 1. For each student, we draw ordinal preferences uniformly at random, and set the utility for this student from being matched to a school that she ranks at place to be u . Formally, for each student i ∈ I we independently and uniformly draw k distinct schools s π 1 , . . . , s π k , and set u i (s π 1 ) = u 1 , u i (s π 2 ) = u 2 , etc., where u = 0 for all > k. The short-list assumption is mostly for technical convenience, and most results and proofs are easily adapted to the case of unbounded lists. Specifically, we do not rely on having many vacant schools in the market or anything of that nature. The sole exception is Theorem 4.2, whose first part requires the length of the ROLs to be bounded by some arbitrary fixed number.

Relative Gains: Sincere vs. Sophisticated
Our first main result speaks to the indeterminacy of relative gains of sophisticated students as compared with sincere students when using BM instead of DA. As mentioned, under DA both types get the same utility. Therefore, we only need to verify how many students prefer to be sophisticated and how many prefer to be sincere under BM. We show that in large random markets there are many students who prefer being sophisticated, and many who prefer being sincere. This is thus an "anything goes" kind of theorem that stands in sharp contrast to the case of strict priorities, where Pathak and Sönmez (2008) show that each student weakly prefers being sophisticated. Formally, we prove that in large random markets, for a large family of cardinal utility levels, and for any nontrivial proportions of sincere and sophisticated students, the expected number of students who prefer being sincere is linear in n, as is the expected number of students who prefer being sophisticated.
Theorem 3.1 (Relative Gains are Often Positive for Some and Negative for Others). Let k = 2, 8 and u 1 > u 2 > 2 3 · u 1 > 0. For any 0 < p < 1, there exists τ > 0 such that for any large enough n, when each student is sincere with probability p independently of other students, in the uniform (n; u 1 , u 2 ) model both of the following hold: 1. There exists a set of sincere students of expected size at least τ n, 9 such that each student in this set strictly prefers any equilibrium (among the sophisticated students and herself ) had she been sophisticated, over any equilibrium (among the sophisticated students, not including herself as she is sincere). Furthermore, each student in this set maintains this strict preference regardless of whether or not any other students become sophisticated and/or become sincere.
2. For any equilibrium (among the sophisticated students), there exists a set of sophisticated students of expected size at least τ n, 10 such that each student in this set strictly prefers any equilibrium (among the sophisticated students, not including herself ) had she been sincere, over the given equilibrium. Furthermore, each student in this set maintains this strict preference regardless of whether or not any other students in this set become sincere and regardless of whether or not any sincere students become sophisticated.
Remark 3.2. For p = 0 only the second part of the theorem holds. For p = 1 only the first part of the theorem holds.
Before presenting the proof, we provide some intuition using two examples. We first illustrate the basic idea using an example in which we restrict our focus to symmetric equilibria.
Example 3.3 (Sincerity Can be an Advantage -Symmetric Equilibrium). Let S = {s 1 , s 2 } and I = {i 1 , i 2 , i 3 }. Each s ∈ S has capacity q s = 1. Every i ∈ I has u i (s 1 ) = 3 and u i (s 2 ) = 2. Suppose i 2 and i 3 are sophisticated.
If i 1 is also sophisticated, the only symmetric equilibrium is for each student to report s 1 s 2 with probability 0.8 and to report s 2 s 1 with probability 0.2. This leaves i 1 (as well as i 2 and i 3 ) with an expected utility of 5 /3.
If i 1 is sincere (and therefore reports s 1 s 2 with probability 1), then the only equilibrium in which i 2 and i 3 play symmetrically is for each of them to report s 1 s 2 with probability 0.6 and to report s 2 s 1 with probability 0.4 (each obtaining an expected utility of 8 /5 < 5 /3). This leaves s 1 with an expected utility of 9 /5 > 5 /3. The mechanics behind Example 3.3 are as follows: in a symmetric equilibrium among all students, since each student plays a mixed strategy, her expected utilities from each of the two pure strategies s 1 s 2 and s 2 s 1 that she plays with positive probability are the same. By becoming sincere, i 1 in essence becomes a Stackelberg leader who commits to the strategy s 1 s 2 (instead of mixing it with s 2 s 1 ), and by doing so, she "crowdsout" the other (sophisticated) students in the school s 1 , breaking the equality between the expected utilities of the other students from playing s 1 s 2 and s 2 s 1 , thereby shifting their mixed strategy in the new symmetric equilibrium toward playing s 2 s 1 with higher probability and playing s 1 s 2 with lower probability. Since other students play s 1 s 2 with a lower probability, the utility of i 1 from playing s 1 s 2 given the new strategies for all other students, is higher than her utility from playing s 1 s 2 given the old strategies for all other students, which was her utility in the old equilibrium (since she played s 1 s 2 with positive probability in that equilibrium). Using this fundamental idea, Example 3.3 can be generalized for more students and/or other utilities.
While the market in Example 3.3 may seem to be very carefully crafted, e.g., in terms of alignment, Lemma 3.5 below shows that the phenomenon identified in that example is in fact generic, and occurs often in a large uniform market. Before proceeding to that lemma, we present a somewhat more complicated example where we do not restrict ourselves merely to symmetric equilibria.
Example 3.4 (Sincerity Can be an Advantage). Let S = {s 1 , s 2 , . . . , s 6 } and let I = {i 1 , i 2 , . . . , i 5 }. Each s ∈ S has capacity q s = 1. Every i ∈ I has utility 4 from being matched to her first choice, utility 3 from being matched to her second choice, and utility 0 otherwise. The preferences of the students are as follows: 1. i 1 : s 1 , s 2 , (We use this notation to mean that i 1 prefers s 1 first and s 2 second.) 2. i 2 : s 1 , s 3 , 3. i 3 : s 1 , s 4 , 4. i 4 : s 2 , s 5 , 5. i 5 : s 3 , s 6 , Suppose i 1 and i 2 are sophisticated. Regardless of whether i 3 , i 4 , and i 5 are sophisticated or not, we note that they will will rank truthfully (since the second choice of each is guaranteed). So, there are three possible equilibria: 11 (1) i 1 ranks truthfully, i 2 ranks s 3 at the top. In this case, the utility of i 1 is 4 /2 = 2 and the utility of i 2 is 3 /2.
(2) i 2 ranks truthfully, i 1 ranks s 2 at the top. In this case, the utility of i 2 is 4 /2 = 2 and the utility of i 1 is 3 /2.
(3) Each of i 1 and i 2 ranks truthfully with probability 3 /4 and ranks her second choice at the top with probability 1 /4. In this case, the utility of each of these students is 3 /2.
We note that Equilibrium (1) is strictly preferred by i 1 to the other two equilibria, and will be forced if i 1 is sincere. Similarly, Equilibrium (2) is strictly preferred by i 2 to the other two equilibria, and will be forced if i 2 is sincere. So, regardless of the equilibrium, at least one of i 1 and i 2 strictly prefers to become sincere.
Our next results shows that in a large random market and under a broad range of cardinal utilities, Example 3.4 repeats linearly many times.
Lemma 3.5 (When Sophistication is Prevalent, Sincerity is Often an Advantage). Let k = 2, and u 1 > u 2 > 2 3 · u 1 > 0. There exists a constant τ > 0 such that for any large enough n, when all students are sophisticated, in the uniform (n; u 1 , u 2 ) model the following holds: For any equilibrium among the students, there exists a set of students of expected size at least τ n, 12 such that each student in this set strictly prefers any equilibrium (among the sophisticated students, not including herself ) had she been sincere, over the given equilibrium. Furthermore, each student in this set maintains this strict preference regardless of whether or not any other students in this set become sincere.
Proof. Similarly to Example 3.4, if there exist five students z, y, x, w, v and six schools a, b, c, d, e, f such that: This example also demonstrates that a sincere student may be matched to different schools across different equilibria (here this can be observed for i 4 and for i 5 ). Furthermore, this holds even when restricting to pure-strategy Pareto-dominant equilibria, and even when looking only at utilities and not at the actual school to which the student is assigned. This phenomenon is in contrast to the case of strict priorities, where Pathak and Sönmez (2008, Proposition 2) show that each sincere student is matched to the same school across all equilibria.
12 The expectation is taken over preferences (for any given mapping from realized preferences to equilibria).
6. a, b, c, d, e, f are not preferred first or second by any other student, then either z or y strictly prefers to become sincere. (The mixed strategy in the third equilibrium is replaced with one that plays truthfully with probability t * = 3(u 1 −u 2 ) u 1 , and ranks the second choice at the top with the remaining probability.) Let us now calculate the probability that for any given z, y ∈ I, there exist x, w, v ∈ I such that the above six conditions are satisfied. Let a denote z's most-preferred school, let b denote her second-preferred school, and let c denote y's second-preferred school; this probability is: No other i ∈ I ranks a/b/c/d/e/f first or second We observe that the product of all of the multiplicands in this expression except the initial 1 /n, tends to (1 − 1 /e) 3 · 1 /e 12 when n tends to infinity Letting τ be any constant such that 4τ is slightly smaller than (1− 1 /e) 3 · 1 /e 12 , we therefore have that for large enough n the expected number of pairs z, y for which such x, w, v ∈ I exist is at least 4τ /n · n 2 = 2τ · (n − 1) ≥ τ · n. Since all such pairs are disjoint, we can pick from each pair one student who strictly prefers to become sincere over the given equilibrium, to obtain a set of students of expected size at least τ · n that satisfies the lemma.
Lemma 3.5 analyzes a random market where all students are sophisticated. In contrast, in a large uniform market where all students are sincere, it is obviously weakly beneficial to become sophisticated. As Lemma 3.6 shows, this is also strictly beneficial for linearly many students.
Lemma 3.6 (When Sincerity is Prevalent, it is Often a Disadvantage).
1. If all students are sincere, then each student weakly prefers to become sophisticated.
2. Let k = 2, and u 1 > u 2 > 2 3 · u 1 > 0. There exists a constant τ > 0 such that for any large enough n, when all students are sincere, in the uniform (n; u 1 , u 2 ) model there exists a set of students of expected size at least τ n, 13 such that each student in this set strictly prefers any equilibrium had she been sophisticated over the outcome when she is sincere. Furthermore, each student in this set maintains this strict preference (comparing to equilibrium outcomes when she is sincere) regardless of whether or not any other students become sophisticated.
Proof. Part 1 is trivial, so we will prove Part 2. We first observe that if there exist four students z, y, x, w and five schools a, b, c, d, e such that: 5. a, b, c, d, e are not preferred first or second by any other student, then z strictly prefers to be sophisticated. First note that in both cases, each of y, x, and w will rank truthfully even if she is sophisticated, since her second choice is guaranteed. Now, in this case if z ranks truthfully, then her utility will be u 1 3 , while if she ranks b first and a second, then her utility will be u 2 2 > u 1 3 . Let us now calculate the probability that for any given z ∈ I, there exist y, x, w ∈ I such that the above five conditions are satisfied. Let a denote z's most-preferred school and let b denote her second-preferred school; this probability is: some y ∈ I ranks a first (let c denote her second-preferred school) Letting τ be any constant slightly smaller than (1 − 1 /e) 3 · 1 /e 10 , we therefore have that for large enough n the expected number of students z for which such y, x, w ∈ I exist is at least τ · n, and so we have identified a set of students of expected size at least τ · n that satisfies the lemma.
We are now ready to complete the proof of Theorem 3.1.
Proof of Theorem 3.1. By a calculation similar to that in the proof of Lemma 3.6, the set of sincere students z satisfying the conditions in that proof is of expected size at least p · τ · n, where τ is as defined there, and so the first statement holds for τ 1 = p · τ (recall that under the conditions in that proof, each of y, x, w will rank truthfully even if she is sophisticated, since her second choice is guaranteed, so we only multiply by the p probability of z being sincere). By a calculation similar to that in the proof of Lemma 3.5/Example 3.4, the second statement holds for τ 2 = (1 − p) 2 · τ , where τ is as defined in Lemma 3.5 (once again, each of x, w, v will rank truthfully regardless of whether or not she is sophisticated, since her second choice is guaranteed, so we only multiply by the (1−p) 2 probability of both z and y being sophisticated). The theorem then holds with τ = min{τ 1 , τ 2 }.
Remark 3.7. The fact that the proof uses only ROLs of length 2 immediately implies that the result also holds when BM is replaced by any First-Choice Maximal mechanism (Dur et al., 2018b), and in particular with the Corrected Boston Mechanism (Miralles, 2009), the Modified Boston Mechanism (Dur, 2015), and the Adaptive Boston Mechanism (Mennle and Seuken, 2017). As for the Secure Boston Mechanism (Dur et al., 2017), the result also extends since the probability that a student is ranked first by the tie-breaking rule is only 1 /n, and the proof remains almost exactly the same.
Remark 3.8. It is possible to extend Theorem 3.1 to a model with finitely many populations and with incomplete information regarding the sophistication level of individual students (as long as the probability of being sophisticated is not too low). In this extension, each population contains a constant share of the students, and belonging to a population implies some population-specific probability for being either sincere or sophisticated. For details see Appendix A.

Absolute Gains: Boston Mechanism vs. Deferred Acceptance
In their paper, Pathak and Sönmez (2008) compare, for sophisticated students, the outcomes of BM with those of DA (the student-optimal stable mechanism). They show that sophisticated students weakly prefer the Pareto-optimal equilibrium 14 of BM over the studentoptimal stable matching. Furthermore, they show that the set of all equilibria of BM in any given economy coincides with the set of all stable matchings in an "augmented economy" where all sincere students are demoted in the priorities of the schools that they do not rank first. These two results seem to suggest that BM is "less fair" than DA, which treats all students, whether sophisticated or sincere, equally. As we will now show, these phenomena do not necessarily continue to hold in the presence of weak priorities.
Proposition 4.1 (Sophisticated Students May Prefer DA over BM). There exists a matching market with weak priorities that satisfies both of the following: 1. The set of Nash equilibrium outcomes of BM in this matching market is different from the set of stable matchings under the "augmented economy" defined by Pathak and Sönmez (2008) for this market. Furthermore, the union of the supports of all the former is different than the union of the supports of all the latter.
2. BM has only one equilibrium (which is thus a Pareto-dominant equilibrium) in this market. The utility of each sophisticated student in the equilibrium of BM is strictly lower than her utility in the DA outcome. The utility of each sincere student in the equilibrium of BM is strictly higher than her utility in the DA outcome.
Proof. Let S = {s 1 , s 2 } and let I = {i 1 , . . . , i 4 }. Each s ∈ S has q s = 1. Every i ∈ I prefers s 1 first, and has utility 4 from being matched to s 1 . Each of the students i 1 and i 2 is sincere and does not wish to be matched to s 2 . Each of the two students i 3 and i 4 is sophisticated and has utility 3 from being matched to s 2 . Note that the augmented economy in this case is the same as the original economy.
In the unique BM equilibrium, each of the sophisticated students goes to s 2 first, and so gets utility 3 /2; each sincere student therefore gets utility 4 /2 = 2 in this equilibrium. The union of the supports of all BM equilibrium outcomes is therefore the set of all matchings where some sincere student i ∈ {i 1 , i 2 } is matched to s 1 and some sophisticated student i ∈ {i 3 , i 4 } is matched to s 2 .
In the student-optimal stable mechanism, each sophisticated student goes to s 1 first, and so receives utility 1 /4 · 4 + 3 /4 · ( 1 /3 · 3 + 2 /3 · 3 /2) = 5 /2 > 3 /2; each sincere student therefore gets utility 4 /4 = 1 < 2 in DA. The union of the supports of all stable matchings (under the augmented economy) is the set of all matchings where some (not necessarily sincere) student i ∈ I is matched to s 1 and some sophisticated student j ∈ {i 3 , i 4 } with j = i is matched to s 2 .
As in the study of the trade-off between sincerity and sophistication, one may ask whether, and to what extent, the above-demonstrated preference of sophisticated students for DA over BM remains prominent in a large random market. The second main result of this paper shows that generally, both a constant fraction of any population prefers DA over BM and a constant fraction of any population prefers BM over DA, in expectation.
Theorem 4.2 (Absolute Gains are Often Positive for Some and Negative for Others). Let k = 2. There exists a constant τ > 0 such that for any large enough n, for any utilities u 1 > u 2 > 0, and for any fixed assignment of which students are sophisticated and which students are sincere, in the uniform (n; u 1 , u 2 ) model both of the following hold: 1. There exists a set consisting of an expected fraction of at least τ of the sophisticated students and an expected fraction of at least τ of the sincere students, 15 such that each student in this set strictly prefers the DA outcome over any equilibrium of BM.
2. There exists a set consisting of an expected fraction of at least τ of the sophisticated students and an expected fraction of at least τ of the sincere students, 16 such that each student in this set strictly prefers any equilibrium of BM over the DA outcome.
Furthermore, each student in each of the above sets maintains this strict preference even if the assignment of which students are sophisticated and which students are sincere changes arbitrarily (including possibly changing whether this student herself is sophisticated or sincere).
Proof. Let u 1 > u 2 > 0. We first observe that if there exist three students z, y, x and four schools a, b, c, d such that: 1. z : a, b, 2. y : a, c, The expectation is taken over preferences. 16 Once again, the expectation is taken over preferences.
4. a, b, c, d are not preferred first or second by any other student, then regardless of whether each of these students (and in fact, regardless of whether any student) is sophisticated or sincere, z strictly prefers the DA outcome over any equilibrium of BM and x strictly prefers any equilibrium of BM over the DA outcome. First note that regardless of whether each student is sophisticated or sincere, each of z, y, and x will rank truthfully under any equilibrium of BM even if she is sophisticated. For y and x this holds since her second choice is guaranteed, and for z this holds as she prefers getting a with probability 1 /2 to getting b with probability 1 /2. Now, under DA z gets utility 1 /2 · u 1 + 1 /2 · u 2 2 (since with probability one half, z beats y in the competition for a, and with the remaining one half probability it is the case that with probability one half z beats x in the competition for b) while under any equilibrium of BM z gets utility u 1 2 , which is strictly smaller. Under DA x gets utility 1 /2 · u 1 + 1 /2 · ( 1 /2 · u 1 + 1 /2 · u 2 ) (since with probability one half, z beats y in the competition for a and so x is the only applicant for b, and with the remaining one half probability, z competes with x for b and so x wins and gets b with probability one half, and loses and gets d with probability one half) while under any equilibrium of BM x gets utility u 1 , which is strictly greater.
For Part 1, let us calculate the probability that for any given z ∈ I, there exist y, x ∈ I such that the above four conditions are satisfied. Let a denote z's most-preferred school and b denote her second-preferred school; this probability is: some y ∈ I ranks a first (let c denote her second-preferred school) Letting τ be any constant slightly smaller than (1− 1 /e) 2 · 1 /e 8 , we therefore have that for large enough n, both the expected fraction of sophisticated students z for which such y, x ∈ I exist, and the expected fraction of sincere students z for which such y, x ∈ I exist, is at least τ , and so we have identified an appropriate set of students that satisfies Part 1. For Part 2, let us calculate the probability that for any given x ∈ I, there exist z, y ∈ I such that the above four conditions are satisfied. Indeed, let b denote x's most-preferred school and d denote her second-preferred school; this probability is: some z ∈ I ranks b second (let a denote her most-preferred school) 1 − n − 1 n n−1 · z does not rank d first (i.e., a = d) n − 2 n − 1 · some y ∈ I ranks a first (let c denote her second-preferred school) Since this is the same probability calculated above for Part 1, the proof of Part 2 concludes similarly to that of Part 1.
Remark 4.3. Remarks 3.7 and 3.8 also hold for Theorem 4.2. Moreover, a stronger version of Remark 3.8 actually holds, as there is no need to make any restrictions on the share of sophisticated students in the population.

The Implications of Sincerity: Crowding-Out Others vs. Not Responding to Excess Demand
The results of Section 3 demonstrate a positive effect of sincerity of a student i in BM: the ability to crowd-out others by essentially becoming a Stackelberg leader who commits to ranking according to her true preference, forcing (other) sophisticated students to respond to this commitment by reducing demand for the school in which student i is interested. We observe that this effect completely disappears when priorities are strict. Indeed, since the outcome of BM under strict priorities (given a fixed profile of students preferences) is deterministic rather than randomized, if student i is hurt by the competition of student j for a certain school (in the case of strict preferences, this means that student j has higher priority at this school), then student i committing to apply to that school does not deter student j from applying to that school, as student j has priority in that school and so will not be crowded-out by student i. Being sincere, as demonstrated by Pathak and Sönmez (2008) in the context of strict priorities, also has an adverse effect: not responding to excess demand to one's favorite school. As it turns out, this effect can still be manifested in markets with weak priorities. In fact, in some cases sincerity of a student i may not crowd-out any students whatsoever, but may nonetheless hurt student i as she does not respond to excess demand for her favorite school. This is precisely what happens in the analysis of Lemma 3.6 for student z -in that example, her sincerity does not crowd-out the competition, but does cause her to not respond to excess demand.
So, what happens when both effects of sincerity are present? Which effect dominates: the positive effect of crowding-out others or the negative effect of not responding to excess demand? In Lemma 3.6, the competition that student z faces for school a is completely decoupled from her competition for school b. As long as this feature is maintained, it is clear that by only tweaking the demand for the second choices of z's competition for school a, we may change whether, and to which extent, a sincere z is able to crowd-out the competition, without changing the expected utility of a sophisticated z from any of the schools. This way, we may easily create variants of this market where the positive effect dominates the negative one or vice versa. A more interesting question is, therefore, what happens when the markets for school a and for school b are entangled? In other words, is the lack of symmetry among the different students in Lemma 3.6 required for sincerity to be disadvantageous? To be more specific, in the extreme case: what happens when all students are symmetricwhich effect of sincerity dominates then? The following example alludes to an answer to this question.
If i 1 is also sophisticated, then in a symmetric equilibrium 17 all students get the same expected utility, and since the sum of utilities is 9 + 1 + (n − 3) · 1 2(n−3) = 10.5, then each student's expected utility is 10.5 n . If i 1 is sincere (and therefore reports s 1 s 2 s 3 with probability 1), then for large enough n, the only equilibrium in which i 2 , . . . , i n play symmetrically is for each of them to report s 1 s 3 s 2 with some probability t, and report s 2 s 3 s 1 with probability 1 − t. 18 In Appendix B, we show that t ≥ 90 101 for large enough n, which implies that as n grows large, the expected utility of i 1 becomes closer and closer to 9 1+t(n−1) < 9 tn ≤ 10.1 n , and so for large enough n the expected utility of i 1 must be strictly smaller than 10.5 n . Example 5.1 demonstrates that even when students share the same preferences and the same cardinal utility function, the crowding-out effect does not necessarily dominate the negative implications of being sincere. Sincerity turns out to be a package deal, and in this case, it is too strong a commitment. While the student i 1 , if acting sincerely, does slightly increase her chance of being admitted into school s 1 , she completely forfeits her chances of being admitted into school s 3 by approaching school s 2 in the second round, and does so even though in this round school s 2 is already very likely to be full. 17 A symmetric equilibrium exists since the game is finite and symmetric (Nash, 1951). Moreover, one can verify that when n is large enough, the only symmetric equilibrium is for each student to report s 1 s 3 s 2 with some probability t , and report s 2 s 3 s 1 with probability 1 − t .
18 An equilibrium in which i 2 , . . . , i n play symmetrically exists since the game is finite and symmetric with respect to these students (Nash, 1951). To see why only these two strategies are played for large enough n, notice that an application to s 1 or s 2 in the second stage has an exponentially small probability to succeed, and therefore when n is large enough, putting s 3 second gives higher utility as it ensures acceptance to school s 3 (since i 1 will not apply to it before the third round).

The Choice of Mechanism: Reduced Competition vs. Reduced Options
The results of Section 4 demonstrate that for a sophisticated student i, BM may have a negative effect as it may reduce the options of student i, effectively forcing her to ex-ante choose to apply to only one over-demanded school. Similarly, in a sense, to the discussion on crowding-out others in Section 5.1, we note that this negative effect also completely disappears when priorities are strict. Indeed, in an equilibrium of BM, since the outcome is deterministic rather than randomized, student i never has any reason to apply to a school she will not be (deterministically) accepted to, and therefore is not hurt by being effectively forced to ex-ante choose to apply to only one over-demanded school -as she will never be rejected from this school, she is not hurt by giving up her "plan B." Not unlike the package deal that is "being sincere," using BM also has a positive effect discussed by Pathak and Sönmez (2008) in the context of strict priorities: reduced competition (in particular, for one's top choice), which can also be seen to manifest in markets with weak priorities. This is demonstrated by the following example, which also sheds light on the interplay between this positive effect of reduced competition and the above-discussed adverse effect of reduced options.
Example 5.2 (The Positive Effects of BM Compared with DA May Dominate Its Negative Effects). Let S = {s 1 , s 2 } and for ease of presentation let the number of students n be large and divisible by 12. Each s ∈ S has capacity q s = 1. Each student has utility 1 for her most-preferred school, and utility 1 − ε, for very small ε, for her second-preferred school, with one fourth of the students preferring s 1 the most, and the remaining three fourths of the students preferring s 2 the most. Under DA, each student roughly has a chance of 1 /n to be admitted to each school, for a total expected utility of roughly 2 /n. Under BM, if a large fraction (say one half) of the students are sophisticated, then in equilibrium roughly half of the students will apply to each school, for an expected utility of roughly 2 /n for each student. If, however, only a small fraction (say one twelfth) of the students are sophisticated, then only these students and the fourth of the students who truly prefer s 1 will apply to s 1 , resulting in lower competition (at most n /3 students) for s 1 than for s 2 , and so expected utility of strictly more than 2 /n for each sophisticated student (and for each sincere student who prefers s 1 ), so in this case sophisticated students strictly prefer BM to DA.
So, which of the two effects generally dominates for a sophisticated student: reduced competition or reduced options? It seems that it boils down to whether, roughly speaking, the "overall competition" was reduced.
To give one example along the lines of Example 5.2, consider a sophisticated student i and call the prefix of her preference list that consists of overdemanded schools her "overdemanded set." If all other students have the same overdemanded set of size o (and priorities are randomly selected), then in DA, one essentially faces competition by all other students over the o schools in her overdemanded set. In BM, one faces competition by an average of 1 /o of the other students in one school, so if this competition is somehow evenly spread (weighted by the utilities of student i for the different schools), then DA and BM would give similar utility for student i, while if this competition is not evenly spread in this sense, then BM would give higher utility for student i.
To give a contrasting example to that of a shared overdemanded set, suppose that all other students have very attractive outside options, to the extent that each other student j only prefers one of the schools in student i's overdemanded set over j's outside option. In such a case, student i most certainly prefers DA, because BM, when compared with DA, reduces no competition for student i but only reduces her options. This is precisely what happens in the analysis of Theorem 4.2 for student z -in that example, BM compared with DA reduces her options without reducing her competition.

Discussion
Market designers often encounter markets that are governed by manipulable mechanisms, with BM being possibly the most prominent example. Common sense dictates that it is better to switch to a strategy-proof mechanism, as it allows the designer to directly optimize some target function (such as efficiency) subject to certain desirable constraints (e.g., stability) and to preserving incentive compatibility. When a manipulable mechanism is in place, it is difficult to predict what properties the likely outcome would satisfy, and whether the strategic situation would give an advantage to some populations over others.
In the specific case of BM, it intuitively seems that the use of this mechanism would favor players who recognize the strategic opportunities over players who ignore them. Indeed, as Pathak and Sönmez (2008) showed, in a strict-priorities environment a student would weakly prefer being sophisticated to being sincere, and BM weakly benefits sophisticated players (compared with DA). This constitute a very strong argument against BM, as strategic sophistication and access to relevant information can be highly correlated with socioeconomic status, and in any case, they are definitely not the criteria based on which the matching should be determined. However, as we show in this paper, when considering a reasonable scenario in which the school district uses a coarse priority structure rather than a strict one, there are several new effects that may reverse the previous theoretical prediction.
The question is therefore: what should we recommend to practitioners? In Section 5 we tried to convey our view that understanding the market structure is crucial for providing sound advice. That being said, it is also fair to assess that in most real-life markets, reacting to excess demand is quite straightforward in terms of strategic behavior, whereas crowding out others is more demanding as it requires a reputation for being sincere and for not shying away from competition. This suggests that, at the end of the day, while policy-makers who are focused on efficiency and absolute gains should probably adopt BM (which takes into account some students' cardinal preferences), in most markets policy-makers who are mostly interested in fairness considerations and relative gains should still tend in favor of DA. That being said, our results imply that this is not as automatic a recommendation as may have widely been believed, and should be taken with a grain of salt, as in some specific markets with special structures BM may not only benefit all players, but also provide the same or higher gain for students who are not sophisticated or not informed about the market. As such students many times come from populations from a weaker socioeconomic background, in such markets turning to BM may help keep or even increase diversity in highly coveted schools.

A Incomplete Information about Sophistication
In Theorem 3.1 we assumed that each player's probability of being sincere is p independently of other students, and that the realizations of these draws (i.e., whether each student is sincere or sophisticated) are common knowledge. Furthermore, we ignored the issue of reputation (that is, the probability of being sincere) constituting a property of populations rather than of individuals, and just assumed that no two students belong to the same population. We have made these assumptions to ease the presentation, yet the result extends even when we relax them significantly. In this appendix, we present a more robust version of Theorem 3.1 in which each student belongs to a population, each population is characterized by a probability of being sincere (and this probability is not too high), and each player's realized sophistication level is private information. We consider the following "populations model" for generating a market. We assume that there are M populations. Each student belongs to one population independently at random, and her probability of belonging to population ν is w ν ∈ (0, 1); the realization of this draw for each student is common knowledge. Conditional on her being of population ν, each student is independently at random determined to be sincere with probability p ν , and sophisticated otherwise; the realization of this draw is private and is known to no other student.
Theorem A.1. Let k = 2, 19 u 1 > u 2 > 2 3 · u 1 > 0, and set t * = 3(u 1 −u 2 ) u 1 . For any populations model where p ν < t * for every ν, there exists τ > 0 such that for any large enough n, in the uniform (n; u 1 , u 2 ) populations model both of the following hold: 1. There exists a set of students of expected size at least τ n, 20 such that each student i that belongs to population ν in this set ex-ante strictly prefers 21 any equilibrium (among students of the sophisticated types) had all students in ν been sophisticated and this was common knowledge, over any equilibrium (among students of the sophisticated types, where each student in ν is sincere with probability p ν and this probability is common knowledge). Furthermore, each student in this set maintains this strict preference regardless of whether other populations' probabilities of being sincere change.
19 As with Theorem 3.1, it is straightforward to generalize this result to arbitrary values of k, and even to preferences of unbounded length. 20 The expectation is taken over preferences and population associations. 21 That is, the strict preference is in expectation over her and others' sophistication.
2. For any equilibrium (among students of the sophisticated types), there exists a set of students of expected size at least τ n, 22 such that each student i that belongs to population ν in this set ex-ante strictly prefers 23 any equilibrium (among students of the sophisticated types) had all students in ν been sincere and this was common knowledge, over the given equilibrium (where each student in ν is sincere with probability p ν ). Furthermore, each student in this set maintains this strict preference regardless of whether or not any other students in this set individually have different probabilities of being sincere and regardless of whether or not other populations' probabilities of being sincere decrease.
Proof. For Part 1, we can still use Lemma 3.6. In its proof it is of no importance whether students y, x, and w are sophisticated or not, as each reports truthfully regardless. Since z strictly prefers being sophisticated to being sincere, she also prefers that to being sincere with any positive probability.
For Part 2, we slightly modify the argument in Lemma 3.5. It is once again of no importance whether x, w, and v are sophisticated or not, as each reports truthfully regardless. As for z and y, we need them to belong to different populations, which we denote by ν z and ν x respectively (this happens with fixed probability w νz · w νy , summed over all possible choices for distinct ν z and ν y ). The reason for having z and y belong to two different populations is that we do not want their sophistication levels to be coupled together when we change the sincerity probability of the population of one of them to 1.
In any equilibrium, within any gadget that contains players z, y, x, w, and v, there could theoretically be five possible ways in which the sophisticated types of players z and y play: (1) The sophisticated type of z ranks truthfully, the sophisticated type of y ranks her second choice at the top.
(2) The sophisticated type of y ranks truthfully, the sophisticated type of z ranks her second choice at the top.
(3) The sophisticated type of each of z and y plays a mixed strategy.
(4) The sophisticated type of each of z and y ranks truthfully.
(5) The sophisticated type of each of z and y ranks her second choice at the top.
22 The expectation is taken over preferences and population associations (for any given mapping from realized preferences and population associations, to equilibria). 23 That is, the strict preference is once again in expectation over her and others' sophistication.