| 2018 | How Lotteries in School Choice Help to Level the Playing Field
The use of lotteries is advocated to desegregate schools. We study lottery quotas embedded in the two most common school choice mechanisms, namely deferred and immediate acceptance mechanisms. Some seats are allocated based on merit (e.g., grades) and some based on lottery draws. We focus on the effect of the lottery quota on truth-telling, the utility of students, and the student composition at schools, using theory and experiments. We find that the lottery quota strengthens truth-telling in equilibrium when the deferred acceptance mechanism is used while it has no clear effect on truth-telling in equilibrium for the immediate acceptance mechanism. This finds support in the experiment. Moreover, the lottery quota leads to more diverse school populations in the experiments, as predicted. Comparing the two mechanisms, students with the lowest grades profit more from the introduction of the lottery under immediate than under deferred acceptance. | Basteck Christian,
Klaus Bettina,
Kübler Dorothea | school choice, immediate acceptance mechanism, deferred acceptance mechanism, lotteries, experiment, market design | |
| 2018 | Centralized Assignment of Students to Majors:Evidence from the University of Costa Rica
Many countries use a centralized admission system for admitting students to universities.That said, little is known about how changes to admission policies impact the allocation of students to colleges (majors). This paper uses a comprehensive dataset from the University of Costa Rica (UCR) to address this question. A central challenge in doing so is recovering students’ preferences for final assignments to majors. The reason is that, much like many centralized admission systems, UCR restricts the number of majors that students can report and, thus, gives them an incentive to manipulate their preference ranking. We propose a novel methodology to recover a minimal set of preferences that are consistent with the data. To achieve this, we treat students’ decision problem as one associated with a large population and impose two minimal rationality conditions on students’ reports. We apply this methodology to the UCR dataset and use the recovered preferences to address counterfactuals. We show that 72% of the students receive an allocation different from the one they would have received if they had reported their full preference ranking (the benchmark).The constrained mechanism also reduces the aggregate welfare from the benchmark in 8%. Finally, we consider alternate mechanisms for allocating students to seats. We show that amechanism based on an ascending auction does not generate large distortions. Under that mechanism, only 6% of the students receive an assignment different from the benchmark.Moreover, it only reduces the aggregate welfare from the benchmark in only 1%. | Allan Hernández-Chanto | Centralized Assignment, Serial Dictatorship, Preference Estimation, Constrained Choice,
Manipulability, Multi-agent Decision | |
| 2018 | First-Choice Maximal and First-Choice Stable School Choice Mechanisms
Abstract: We investigate the class of school choice mechanisms that are first-choice maximal (FCM) (i.e., they match a maximal number of students to their reported first choices) and first-choice stable (FCS) (i.e., no students form blocking pairs with their reported first choices). FCM is a ubiquitous desideratum in school choice, and we show that FCS is the only rank-based relaxation of stability that is compatible with FCM. The class of FCM and FCS mechanisms includes variants of the well-known Boston mechanism as well as certain Asymmetric Chinese Parallel mechanisms. Regarding incentives, we show that while no mechanism in this class is strategyproof, the Pareto efficient ones are least susceptible to manipulation. Regarding student welfare, we show that the Nash equilibrium outcomes of these mechanisms correspond precisely to the set of stable matchings. By contrast, when some students are sincere, we show that more students may be matched to their true first choices in equilibrium than under any stable matching. Finally, we show how our results can be used to obtain a new characterization of the Boston mechanism (i.e., the most widely used FCM and FCS mechanism). On a technical level, this paper provides new insights about an influential class of school choice mechanisms. For practical market design, our results yield a potential rationale for the popularity of FCM and FCS mechanisms in practice. | Umut Dur, Timo Mennle, Sven Seuken | Matching, school choice, Boston mechanism | |
| 2018 | Top-Ten Way to Integrate High Schools
Abstract: We investigate how “top-N percent” policies in college admission affect diversity at the high-school level. It is well understood that these policies produce incentives for students to relocate to schools with weaker competition. We show theoretically that such school arbitrage can neutralize the policy at the college level but may partially desegregate high schools. These predictions are supported by empirical evidence on the effects of the Texas Top Ten Percent Law, indicating that a policy intended to support diversity at the college level actually helped achieve it in the high schools. Thus top-N percent policies may provide a new instrument for the long sought goal of achieving high school integration. | Fernanda Estevan, Thomas Gall, Patrick Legros, Andrew Newman | Matching, affirmative action, education, college admission, high school integration, Texas Top Ten Percent | |
| 2018 | An empirical analysis of college admissions with endogenous entrance exam scores
Abstract: This paper examines centralized college admissions, where colleges sort students according to their scores from a national entrance exam. The outcomes of the college admissions with entrance exams can be represented with cutoff scores, which are the minimum scores of the matched students. The distributions of cutoff scores are good approximations for matching outcomes in large matching games rather than complicated models and students' behavior can be characterized in individual level using these distributions. In this environment, I show that students' exam preparation strategies depend on their abilities, personal college valuations, and the distribution of cutoff scores, where students approximate it using cutoff scores from the past years. This setting allows me to examine the effects of students' college preferences on their exam preparation strategies in the data. To identify the effects of students' preference on the preparation strategies and resulting exam scores, I partition colleges according to observable college characteristics and competition levels. These sets also enable to estimate the effects of preferences on exam scores. Using Turkey's college admissions data, I show that students' college preferences are significant factors in the exam preparation strategies and they account for at least 16 percent of the total variation in exam scores. This finding suggests that disregarding the effects of students' college preferences on the exam preparation strategies causes misleading interpretations of students' behavior in college admissions. In addition, admission policies (e.g. Affirmative Action) need to be reconsidered according to the effects of preferences. | Hayri Alper Arslan | College admissions contest, College choice, Students' college preferences, Deferred acceptance algorithm, Affirmative action policies | |
| 2018 | Matchings with Lower Quotas: Algorithms and Complexity
We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph G=(A∪P,E) with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (WMLQ), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of WMLQ from the viewpoints of classical polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between 𝖭𝖯
-hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota umax
as basis, and we prove that this dependence is necessary unless 𝖥𝖯𝖳=𝖶[1]
. The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee umax+1
, which is asymptotically best possible unless 𝖯=𝖭𝖯
. Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas | Ashwin Arulselvan, Ágnes Cseh, Martin Groß, David F. Manlove, Jannik Matschte | Maximum matching, Many-to-one matching, Project allocation, Inapproximability, Bounded treewidth | |
| 2017 | Top Trading Cycles, Consistency, and Acyclic Priorities for House Allocation with Existing Tenants
We study the house allocation with existing tenants model (introduced by Abdulkadiroglu and Sonmez, 1999) and consider rules that allocate houses based on priorities. We introduce a new acyclicity requirement for the underlying priority structure which is based on the acyclicity conditions by Ergin (2002) and Kesten (2006) for house allocation with quotas and without existing tenants. We show that for house allocation with existing tenants a top trading cycles rules is consistent if and only if its underlying priority structure satisfies our acyclicity condition. Moreover, even if no priority structure is a priori given, we show that a rule is a top trading cycles rule based on ownership adapted acyclic priorities if and only if it satisfies Pareto-optimality, individual-rationality, strategy-proofness, reallocation-proofness, and consistency. | Mehmet Karakaya, Bettina Klaus, Jan Christoph Schlegel | Consistency, house allocation, matching, strategy-proofness, top trading
cycles | |
| 2017 | Random Matching under Priorities: Stability and No Envy Concepts
We consider stability concepts for random matchings where agents have preferences over objects and objects have priorities for the agents. When matchings are deterministic, the standard stability concept also captures the fairness property of no (justified) envy. When matchings can be random, there are a number of natural stability / fairness concepts that coincide with stability / no envy whenever matchings are deterministic. We formalize known stability concepts for random matchings for a general setting that allows weak preferences and weak priorities, unacceptability, and an unequal number of agents and objects. We then present a clear taxonomy of the stability concepts and identify logical relations between them.Furthermore, we provide no envy / claims interpretations for some of the stability concepts that are based on a consumption process interpretation of random matchings. Finally, we present a transformation from the most general setting to the most restricted setting, and show how almost all our stability concepts are preserved by that transformation. | Haris Haziz, Bettina Klaus | Matching Theory; Stability Concepts; Fairness; Random Matching | |
| 2017 | Matching with Myopic and Farsighted Players
Abstract: We study stable sets for marriage problems under the assumption that players can be both myopic and farsighted. We introduce the new notion of the myopic-farsighted stable set, which is based on the notion of a myopic- farsighted improving path. A myopic-farsighted stable set is the set of match- ings such that there is no myopic-farsighted improving path from any match- ing in the set to another matching in the set (internal stability) and there is a myopic-farsighted improving path from any matching outside the set to some matching in the set (external stability). For the special cases where all players are myopic and where all players are farsighted, our concept pre- dicts the set of matchings in the core. When all men are myopic and the top choice of each man is a farsighted woman, we show that the singleton consist- ing of the woman-optimal stable matching is a myopic-farsighted stable set. The same result holds when all women are farsighted. We present examples where this is the unique myopic-farsighted stable set as well as examples of myopic-farsighted stable sets consisting of a core element di§erent from the woman-optimal matching or even of a non-core element. | P. Jean-Jacques Herings, Ana Mauleony,
Vincent Vannetelboschz | Marriage problems, stable sets, myopic and farsighted players. | |
| 2017 | Obvious Mistakes in a Strategically Simple College Admissions Environment: Causes and Consequences
Although many centralized school assignment systems use strategically simple mechanisms, applicants often make dominated choices. Using administrative data from Hungary, we show that many college applicants forgo the free opportunity to receive a tuition waiver. We provide causal evidence that applicants make more such mistakes when applying to programs where tuition waivers are more selective. A non-negligible share of these mistakes are consequential, costing applicants approximately 3,000 dollars. Costly mistakes transfer waivers from high- to low-socioeconomic status students, and increase the number of admitted students. Our results suggest that mistakes are more common when their expected utility cost is lower. | Ran I. Shorrer, Sándor Sóvágó | College admissions, dominated strategies, market design, obvious misrepresentation, school choice, strategy-proof | |
| 2017 | How University Admissions Can Help Integrate Secondary Schools
In recent years, several US states have introduced college admission policies that reward local rather than global relative performance by guaranteeing admission to students graduating in the top N-percent of their high school. This column examines how these policies affected socioeconomic and ethnic segregation at both the university and high school levels in the state of Texas. While the policies did not replicate the level of diversity in universities seen under earlier affirmative action policies, they did lead to a reduction in the overall level of ethnic segregation in high schools. | Fernanda Estevan, Thomas Gall, Patrick Legros, Andrew Newman | Matching, affirmative action, education, college admission, high school integration, Texas Top Ten Percent | |
| 2017 | Matching with Partners and Projects
We study a model that is a hybrid of the classical one-sided and two sided match- ing models. Agents are matched in pairs in order to undertake a project and have preferences over both the partner and the project they are assigned to. Each agent partitions the set of partners into friends and outsiders, and the set of of possible projects, into good and bad ones (dichotomous preferences). The overall preference ordering on partner, project pairs is separable. Friendship is mutual and preferences over projects among friends are correlated. We propose an algorithm, the minimum demand priority algorithm that generates stable assignments in this domain, satisfies a constrained notion of Pareto efficiency called friendship efficiency and is strategy-proof. Finally we show that stable assignments may not exist if any one of assumptions on the preferences is relaxed. | Antonio Nicolò, Aruvana Sen, Sonal Yadav | Matching, Stability, Strategy-proofness, Two-sided matching, One-sided matching | |
| 2017 | Costly Concessions: An Empirical Framework for Matching with Imperfectly Transferable Utility
We introduce an empirical framework for models of matching with imperfectly transferable utility and unobserved heterogeneity in tastes. Our framework allows us to characterize matching equilibrium in a flexible way that includes as special cases the classical fully- and non-transferable utility models, collective models, and settings with taxes on transfers. We allow for the introduction of a general class of additive unobserved heterogeneity on agents' preferences. We show existence and uniqueness of an equilibrium under minimal assumptions. We then provide two algorithms to compute the equilibrium in our model. The first algorithm operates under any structure of heterogeneity in preferences; the second is more efficient, but applies only in the case in which random utilities are logit. We show that the log-likelihood of the model has a simple expression and we compute its derivatives. An empirical illustration is provided in the appendix. | Alfred Galichon, Scott Duke Kominers, Simon | Sorting, Matching, Marriage Market, Intrahousehold Allocation, Imperfectly Transferable Utility | |
| 2017 | A Note on the Estimation of Job Amenities and Labor Productivity
This note introduces a maximum likelihood estimator of the value of job amenities and labor productivity in a single matching market based on the observation of equilibrium matches and wages. The estimation procedure simultaneously fits both the matching patterns and the wage curve. Our estimator is suited for applications to a wide range of assignment problems. | Arnaud Dupuy, Alfred Galichon | Matching, Observed transfers, Structural estimation, Value of job amenities, Value of productivity | |
| 2017 | Taxation in Matching Markets
We analyze the effects of taxation in two-sided matching markets, i.e. markets in which all agents have heterogeneous preferences over potential partners. In matching markets, taxes can generate inefficiency on the allocative margin by changing who is matched to whom, even if the number of workers at each firm is unaffected. While the allocative inefficiency of taxation need not be monotonic in the level of the tax when transfers flow in both directions, we show that it is weakly increasing in the tax rate for markets in which workers refuse to match without a positive wage.
We introduce a renormalization that allows for an equivalence between markets with taxation and markets without taxation but with adjusted match values. We use our equivalence to show additional properties of matching markets with taxation and to adapt existing econometric methods to such markets. We then estimate the preferences in the college-coach US football matching market and show through simulations of tax reforms that the true deadweight loss can differ dramatically from that measured without accounting for the preference heterogeneity of the matching market.
In addition to highlighting the potential for allocative distortions from taxation, our model provides a continuous link between canonical models of matching with and without transfers. | Arnaud Dupuy, Alfred Galichon, Sonia Jaffe, Scott Duke Kominers | Matching markets, taxation, labor markets | |
| 2017 | The Stable Roommates Problem with Short Lists
We consider two variants of the classical Stable Roommates problem with Incomplete (but strictly ordered) preference lists (sri) that are degree constrained, i.e., preference lists are of bounded length. The first variant, egald-sri, involves finding an egalitarian stable matching in solvable instances of sri with preference lists of length at most d. We show that this problem is NP-hard even if d = 3. On the positive side we give a 2d+37
-approximation algorithm for d ∈{3,4,5} which improves on the known bound of 2 for the unbounded preference list case. In the second variant of sri, called d-srti, preference lists can include ties and are of length at most d. We show that the problem of deciding whether an instance of d-srti admits a stable matching is NP-complete even if d = 3. We also consider the “most stable” version of this problem and prove a strong inapproximability bound for the d = 3 case. However for d = 2 we show that the latter problem can be solved in polynomial time. | Ágnes Cseh, Robert W. Irving, David F. Manlove | Stable matching, Bounded length preference lists, Complexity, Approximation algorithm | |
| 2017 | Beyond the Spanish MIR with Consent:
(Hidden) Cooperation and Coordination in Matching
Sequential mechanisms to solve matching problems are useful to promote (hidden) cooperation between agents. Taking as a starting point the MIR mechanism, employed in Spain to match medical students and residency programs (in privately owned hospitals), we find that: (1) In the current system, where the number of students that each program might enroll is limited, the single equilibrium allocation can be unstable. (2) When the above limit is not (formally) imposed,instability is not expected to occur. Nevertheless, the multiplicity of equilibria shows that coordination failure might emerge, generating a social welfare loss. (3) When the role of students and hospitals is reversed in the MIR mechanism, (hidden) cooperation is guaranteed. Moreover, coordination failure disappears. | José Alcalde | MIR Mechanism, Hidden Cooperation, Coordination | |
| 2017 | Need vs. Merit: The Large Core of College Admissions Markets
We study college admissions markets, where each college offers multiple levels of financial aid. Colleges subject to budget and capacity constraints wish to recruit the best qualified students. Deferred Acceptance is strategy-proof for students, but the scope for manipulation by colleges is substantial, even in large markets. Successful manipulation takes the simple form of allocating funding based on need rather than merit. Stable allocations may differ in the number of assigned students. In Hungary, where the centralized college admissions clearinghouse uses Deferred Acceptance, another stable allocation would increase the number of students accepted to college by at least 3%, and applicants from low socioeconomic backgrounds would benefit disproportionately. | Avinatan Hassidim, Assaf Romm, Ran I. Shorrer | Matching with contracts, college admissions, core | |
| 2017 | Broadening the market design approach to school choice School choice refers to policies that allow parents’ preferences to be an input to the decision of which school a student will attend. A rich body of research has developed over the past 10-15 years to study mechanisms that implement school choice. This literature has mostly taken the inputs of school choice – preferences, priorities and capacities – as exogenous. More recently, researchers have sought to embed the school choice problem into its wider context, thereby broadening the scope of market design questions and enriching the analysis. This article discusses current school choice policy issues in light of this recent literature and outlines remaining open
questions. | Estelle Cantillon | school choice, market design, policy | |
| 2017 | An Invitation to Market Design Market design seeks to translate economic theory and analysis into practical solutions to real-world problems. By redesigning both the rules that guide market transactions and the infrastructure that enables those transactions to take place, market designers can address a broad range of market failures. In this paper, we illustrate the process and power of market design through three examples: the design of medical residency matching programs; a scrip system to allocate food donations to food banks; and the recent “Incentive Auction” that reallocated wireless spectrum from television broadcasters to telecoms. Our lead examples show how effective market design can encourage participation, reduce gaming, and aggregate information, in order to improve liquidity, efficiency, and equity in markets. We also discuss a number of fruitful applications of market design in other areas of economic and public policy. | Scott Duke Kominers, Alexander Teytelboym, and Vincent P. Crawford | Matching, auctions, trading, scrip, liquidity, efficiency, equity, allocation rules, marketplaces, market design | |
| 2017 | Manipulability and Tie-Breaking in Constrained School Choice
In constrained school choice mechanisms, students can only rank a subset of the schools they could potentially access. We characterize dominant and undominated strategies in the constrained Boston (BOS) and deferred acceptance (DA) mechanisms. Using our characterization of dominant strategies we show that in constrained DA, the single tie-breaking rule outperforms the multiple tie-breaking rule in terms of both manipulability and stability. We also show that DA is less manipulable than constrained BOS in the sense of Arribillaga and Massó (2015). Using our characterizations of undominated strategies, we derive advice for the students and show that more strategies can be excluded on the basis of dominance in constrained DA than in constrained BOS.
| Benoit Decerf and Martin Van der Linden | School choice, Dominant strategy, Undominated strategy, Manipulability, Stability, Tie-breaking, Boston mechanism, Deferred acceptance mechanism | |
| 2017 | A Criterion to Compare Mechanisms When Solutions Are Not Unique, with Applications to Constrained School Choice
We introduce a new criterion to compare the properties of mechanisms when the solution concept used induces multiple solutions. Our criterion generalizes previous approaches in the literature. We use our criterion to compare the stability of constrained versions of the Boston (BOS) and deferred acceptance (DA) school choice mechanisms in which students can only rank a subset of the schools they could potentially access. When students play a Nash equilibrium, we show that there is a stability cost to increasing the number of schools students can rank in DA. On the other hand, when students only play undominated strategies, increasing the number of schools students can rank increases stability. We find similar results for BOS. We also compare BOS and DA. Whatever the number of schools students can rank, we find that BOS is more stable than DA in Nash equilibrium, but less stable in undominated strategies.
| Benoit Decerf and Martin Van der Linden | Multiple solutions, School choice, Stability, Boston mechanism, Deferred acceptance mechanism, Nash equilibrium, Undominated strategy | |
| 2016 | The Design of Teacher Assignment: Theory and Evidence
The (re-)assignment of teachers to schools is a central issue in education policies. In several countries, this assignment is managed by a central administration which faces a key constraint: making sure that teachers obtain an assignment which they weakly prefer to their current position. The Deferred-Acceptance mechanism (DA) proposed by Gale and Shapley (1962) fails to satisfy this constraint. As a solution, a variation on this mechanism has been proposed in the literature and used in practice---as for the assignment of French teachers to schools. We show that this mechanism fails to be efficient in a strong sense: one can reassign teachers in a way which makes both teachers and schools "better-off". In addition, this reassignment increases "fairness" by shrinking the set of blocking pairs. To go around this weakness, we characterize the class of mechanisms which cannot be improved upon in terms of both efficiency and fairness. Our main theoretical finding shows that this class contains an essentially unique strategy-proof mechanism. We refine these results in two ways. First, we consider a random environment where preferences and schools' rankings are drawn randomly from a rich class of distributions and show that when the market becomes large, our mechanism "perform quantitatively better" than the modified DA in terms of utilitarian efficiency and number of blocking pairs. Second, we use a rich dataset on teachers' applications to transfer in France to empirically assess the extent of potential gains associated with the adoption of our mechanisms. These empirical results confirm both the poor performance of the variation of the DA mechanism, and the significant improvement our alternative mechanisms bring in terms of both efficiency and fairness. | Julien Combe, Olivier Tercieux and Camille Terrier | Two-sided matching markets, Teacher Assignment, Fairness, Efficiency | |
| 2015 | The performance of school assignment mechanisms in practice
Theory points to a potential trade-off between two main school assignment mechanisms; Boston and Deferred Acceptance (DA). While DA is strategyproof and gives a stable matching, Boston might outperform DA in terms of ex-ante efficiency. We quantify the (dis)advantages of the mechanisms by using information about actual choices under Boston complemented with survey data eliciting students’ school preferences. We find that under Boston around 8% of the students apply to another school than their most-preferred school. We compare allocations resulting from Boston with DA with single tie-breaking (one central lottery; DA-STB) and multiple tie-breaking (separate lottery per school; DA-MTB). DA-STB places more students in their top-n schools, for any n, than Boston and results in higher average welfare. We find a trade-off between DA-STB and DA-MTB. DA-STB places more students in their single most-preferred school than DA-MTB, but fewer in their top-n, for n ≥ 2. Finally, students from disadvantaged backgrounds benefit most from a switch from Boston to any of the DA mechanisms. | Monique de Haan, Pieter Gautier, Hessel Oosterbeek, Bas van der Klaauw | School choice; Boston mechanism, deferred acceptance mechanism, strategic behavior, ex-ante efficiency, ex-post efficiency | |
| 2015 | Self-selection in School Choice: Theory and Evidence from Mexico City High School Match
We study self-selection in centralized school choice, a strategic behavior that takes place when students have to submit preferences before knowing priorities at schools. Students self-select if they decide not to apply to some schools despite being desirable. We give a theoretical explanation for this behavior: if a student believes her chances of being assigned to some schools are zero, she may not rank them even when the mechanism in place is strategy-proof. Using data from Mexico City high school match, we find evidence that self-selection exists, and has negative consequences. First, students from low socio-economic backgrounds are more likely to self-select. Second, once the uncertainty is resolved, some students who finally get a high priority are not assigned to their most preferred choice because of self-selection; and again, this happens more often among those from low socio-economic backgrounds. These findings question the effectiveness of equal access provided by school choice, and we show it can be improved by changing the timing of submission. | Li Chen and Juan Sebastián Pereyra | School choice, Incomplete Information, Self-selection, Serial Dictatorship Mechanism,
Strategy-proofness | |
| 2015 | Beyond Truth-Telling: Preference Estimation with Centralized School Choice
We propose novel approaches and tests for estimating student preferences with data from school choice mechanisms, e.g., the Gale-Shapley Deferred Acceptance. Without requiring truth-telling to be the unique equilibrium, we show the matching is (asymptotically) stable, or justified-envy-free, implying that everyone is assigned to her favorite school among those she is qualified for ex post. Having validated the approaches and tests in simulations, we apply them to Parisian data and reject truth-telling but not stability. The estimates are then used to evaluate the sorting and welfare effects of admission criteria that determine how schools rank students in centralized school choice. | Gabrielle Fack, Julien Grenet, and Yinghua He | Gale-Shapley Deferred-Acceptance Mechanism, School Choice, Stable
Matching, Student Preferences, Admission Criteria | |
| 2015 | Strategy-Proof Fair School Placement
This paper provides an 'escape route' from the efficiency-equity trade-off in the School Choice problem. We achieve our objective by presenting a weak notion of fairness, called τ-fairness, which is always non-empty.
Then, we propose the adoption of the Student Optimal Compensating Exchange Place rule, a procedure that assigns a τ-fair allocation to each problem. When students' preferences are restricted to satisfy the β-condition, the mechanism is strategy-proof. | José Alcalde and Antonio Romero-Medina | School Choice Problem, Fair Matching, Strategy-Proofness | |
| 2014 | The Naive versus the Adaptive Boston Mechanism The Boston mechanism is often criticized for its manipulability and the resulting negative implications for welfare and fairness. Nonetheless, it is one of the most popular school choice mechanisms used in practice. In this paper, we first study the traditional (naive) Boston mechanism (NBM) in a setting with no priority structure and single uniform tie-breaking. We show that it imperfectly rank dominates the strategyproof Random Serial Dictatorship (RSD). We then formalize an adaptive variant of the Boston mechanism (ABM), which is also sometimes used in practice. We show that ABM has significantly better incentive properties than NBM (it is partially strategyproof), while it shares most of NBM's efficiency advantages over RSD as markets get large. However, while a direct efficiency comparison of NBM and ABM via imperfect dominance is inconclusive, numerical simulations suggest that NBM is still somewhat more efficient than ABM, which can be interpreted as the cost of partial strategyproofness one pays when choosing ABM over NBM. Our results highlight the subtle trade-off between efficiency and strategyproofness a market designer must make when choosing between the two Boston mechanisms and RSD. | Timo Mennle and Sven Seuken | Boston mechanism, School Choice, Strategyproofness, Partial Strategyproofness, Efficiency | |
| 2014 | College Admissions with Entrance Exams: Centralized versus Decentralized We theoretically and experimentally study a college admissions problem in which colleges accept students by ranking students’ efforts in entrance exams. Students hold private information regarding their ability level that affects the cost of their efforts. We assume that student preferences are homogeneous over colleges. By modeling college admissions as contests, we solve and compare the equilibria of “centralized college admissions” (CCA) in which students apply to all colleges, and “decentralized college admissions” (DCA) in which students can only apply to one college. We show that lower ability students prefer DCA whereas higher ability students prefer CCA. The main qualitative predictions of the theory are supported by the experimental data, yet we find a number of behavioral differences between the mechanisms that render DCA less attractive than CCA compared to the equilibrium benchmark. | Isa E. Hafalir, Rustamdjan Hakimov, Dorothea Kübler and Morimitsu Kurino | College admissions, Incomplete information, Student welfare, Contests, All-pay auctions, Experiment | |
| 2014 | A new solution for the roommate problem: The Q-stable matchings The aim of this paper is to propose a new solution concept for the roommate problem with strict preferences. We introduce maximum irreversible matchings and consider almost stable matchings (Abraham et al. 2006) and maximum stable matchings (Tan 1990). We find that almost stable matchings are incompatible with the other two solution concepts. Hence, to solve the roommate problem we propose matchings that lie at the intersection of the maximum irreversible matchings and maximum stable matchings, which are called Q-stable matchings. These matchings are core consistent and we offer an efficient algorithm for computing one of them. The outcome of the algorithm belongs to an absorbing set. | Péter Biró, Elena Inarra, Elena Molis | roomates problem, almost stability, internal stability, stable partition, absorbing set | |
| 2014 | Improving College Access and Success for Low-Income Students: Evidence from a Large Need-Based Grant Program Using comprehensive administrative data on France's single largest financial aid program, this paper provides new evidence on the impact of large-scale need-based grant programs on the college enrollment decisions, persistence and graduation rates of low-income students. We exploit sharp discontinuities in the grant eligibility formula to identify the impact of aid on student outcomes at different levels of study. We find that the provision of 1,500 euros cash allowances to prospective undergraduate or graduate students increases their college enrollment rates by 5 to 7 percent. Moreover, we show that need-based grants have positive effects on student persistence and degree completion. | Gabrielle Fack and Julien Grenet | Need-based grants; College enrollment; Student persistence; Degree completion, Field Data, College admissions, France. | |
| 2014 | Overbooking in matching markets I study a model in which a finite number of schools with fixed enrollment targets and responsive preferences repeatedly interact in the same underlying matching market. In each period, (1) a completely identical population of short-lived students arrives in the market, (2) all students apply to all schools, (3) schools make one round of admissions offers, and (4) each student accepts her best offer. Schools overbook to prevent under enrollment and use information about past enrollments to adjust their admissions offers. I assume that schools are restricted to use cutoff strategies, that is, in each period a school decides on the least preferred applicant it wants to make an offer to and then offers admission to all those it weakly prefers to that applicant. A school adjusts moderately from one period to the next, if it does not change its cutoff by more than the absolute value of the difference between its most recent realized enrollment and its fixed target. I show that for any period in which all schools adjust moderately, the aggregate imbalance between realized and target enrollments weakly decreases. For the case where schools can at least temporarily refrain from changing admissions offers despite demand-supply imbalances, I introduce two simple classes of cutoff adjustment processes that always converge to market clearing. If instantaneous reaction to over- or under-enrollment is necessary, convergence to market clearing can not be guaranteed if the underlying matching market has more than one stable matching. However, if all schools adjust moderately, the supremum and the infimum of all cutoff vectors observed along a cycle are both market-clearing cutoff vectors. In particular, convergence is guaranteed when the market has a unique stable matching. While exact convergence to market clearing can no longer be guaranteed if there is more than one stable matching, the market converges to an approximately market clearing cutoff vector if adjustment magnitudes eventually become small. I also consider a simple model of the Boston mechanism with adaptive agents and show that the induced adjustment process guaranteed to converge if and only if all schools essentially evaluate all students in the same way. | Alex Westkamp | Enrollment targets, Overbooking, Cutoffs, Market clearing, Stable matchings, School Choice, Boston mechanism. |
|
| 2014 | Dynamic allocation of objects to queueing agents This paper analyzes the optimal allocation of objects which arrive sequentially to agents organized in a waiting list. Applications include the assignment of social housing, deceased donor organs and daycare slots. A mechanism is a probability distribution over all priority orders which are consistent with the waiting list. We consider three efficiency criteria: first order stochastic dominance in the vector of agents’ values, the probability of misallocation and the expected waste. We show that the strict seniority order dominates uniform random order according to the two first criteria, and the uniform random order dominates strict priority according to the third criterion. If agents values are perfectly correlated, strict priority dominates all other probabilistic mechanisms for all agents values. | Francis Bloch and David Cantala | Dynamic matching, Queuing, Queuing disciplines, Social housing, Organ transplant | |
| 2014 | Structural Estimation of a Model of School Choices: the Boston vs Its Alternatives An important debate centers on what procedure should be used to allocate students across public schools. We contribute to this debate by developing and estimating a model of school choices by households under one of the most popular procedures known as the Boston mechanism (BM). We recover the joint distribution of household preferences and sophistication types using administrative data from Barcelona. Our counterfactual policy analyses show that a change from BM to the Gale-Shapley student deferred acceptance mechanism would create more losers than winners, while a change from BM to the top trading cycles mechanism has the opposite effect. | Caterina Calsamiglia,
Chao Fu, and
Maia Güell | School Choice, Boston mechanism, Deferred Acceptance mechanism, Field data, Strategic behavior, Strategyproofness, Barcelona, Spain | |
| 2014 | College Diversity and Investment Incentives
This paper studies the aggregate economic effects of diversity policies such as affirmative action in college admission. If agents are constrained in the side payments they can make, the free market allocation displays excessive segregation relative to the first-best. Affirmative action policies can restore diversity within colleges but also affect incentives to invest in pre-college scholastic achievement. Affirmative action policies that are achievement-based can increase aggregate investment and income, reduce inequality, and increase aggregate welfare relative to the free market outcome. They may also be more effective than decentralized policies such as cross-subsidization of students by colleges. | Thomas Gall, Patrick Legros and Andrew Newman | Matching, misallocation, nontransferable utility, multidimensional attributes, affirmative action, segregation, education | |
| 2014 | Integer programming methods for special college admissions problems. We develop Integer Programming (IP) solutions for some special college admission problems arising from the Hungarian higher education admission scheme. We focus on four special features, namely the solution
concept of stable score-limits, the presence of lower and common quotas, and paired applications. We note that each of the latter three special features makes the college admissions problem NP-hard to solve. Currently, a heuristic based on the Gale-Shapley algorithm is being used in the application. The IP methods that we propose are not only interesting theoretically, but may also serve as an alternative solution concept for this practical application, and other similar applications. | Péter Biró, Iain McBride | college admissions, integer programming, stable core limits, quotas, couples | |
| 2014 | The Hospitals / Residents Problem with Couples: Complexity and Integer Programming Models. The Hospitals / Residents problem with Couples (HRC) is a generalisation of the classical Hospitals / Resident problem (HR) that is important in practical applications because it models the case where couples submit joint preference lists over pairs of (typically geographically close) hospitals. In this paper we give a new NP-completeness result for the problem of deciding whether a stable matching exists, in highly restricted instances of HRC. Further, we present an Integer Programming (IP) model for HRC and extend it the case where preference lists can include ties. Also, we describe an empirical study of an IP model or HRC and its extension to the case where preference lists can include ties. This model was applied to randomly generated instances and also real-world instances arising from previous matching runs of the Scottish Foundation Allocation Scheme, used to allocate junior doctors to hospitals in Scotland. | Péter Biró, David F. Manlove, Iain McBride | matching with couples, hospitals residents problem, integer programming, NP-hard | |
| 2014 | Gaming the Boston School Choice Mechanism in Beijing The Boston mechanism is criticized for its poor incentive and welfare performance compared with the Gale-Shapley deferred-acceptance mechanism (DA). Using school choice data from Beijing, I investigate parents' behavior under the Boston mechanism, taking into account parents' possible mistakes when they strategize.Evidence shows that parents are overcautious as they play "safe" strategies too often. There is no evidence showing that wealthier and more-educated parents are any more adept at strategizing. If others behave as in the data, an average naive parent who is always truth-telling experiences a utility loss in switching from the Boston to the DA, equivalent to an 8% increase in the distance from home to school or substituting a 13% chance at the best school with an equal chance at the second best. She has a 27% chance to be better off and a 55% chance being worse off. If instead parents are either sophisticated (always playing a best response against others) or naive, results are mixed: Under the DA, naive ones enjoy a utility gain on average when less than 80% of the population is naive, while still about 42% worse off and only 39% better off. Sophisticated parents always loose more. | Yinghua He | Boston Mechanism, Gale-Shapley Deferred-Acceptance Mechanism, School Choice, Bayesian Nash Equilibrium, Strategy-Proofness, Moment Inequalities, Beijing, China. | |
| 2014 | Driven by priorities manipulations under the Boston mechanism Inspired by real-life manipulations used when the Boston mechanism is in place, we study school choice markets where students submit preferences driven by priorities; that is, when students declare among the most preferred those schools for which they have high priority. Under this behavior assumption, we prove that the outcome of the Boston mechanism is the school-optimal stable matching. Moreover, the condition is necessary: if the outcome of the Boston mechanism is the school-optimal stable matching, then preferences are driven by priorities. Thus, under these manipulations, the final allocation of students may be purely shaped by schools' priorities. Additionally, we run some computational simulations to show that the assumption of driven by priorities preferences can be relaxed by introducing an idiosyncratic preference component, and our main results hold for almost all students. | David Cantala and Juan Sebastián Pereyra | Two-sided many-to-one matchings, school choice, Boston mechanism | |
| 2013 | Mixité sociale : le rôle des procédures d’inscription scolaire (Social diversity: the role of school choice procedure) This article analyzes the role of school choice regulation in fostering social diversity. It provides a framework for designing school choice procedures and describes the experiences with school choice regulation in French-speaking Belgium and in Ghent (this article is written in French with a policy audience in mind.) | Estelle Cantillon | diversity, school choice, priorities, Belgium, Flanders, quotas | |
| 2013 | Preference Signaling in Matching Markets Many labor markets share three stylized facts: employers cannot give full attention to all candidates, candidates are ready to provide information about their preferences for particular employers, and employers value and are prepared to act on this information. In this paper we study how a signaling mechanism, where each worker can send a signal of interest to one employer, facilitates matches in such markets. We find that introducing a signaling mechanism increases the welfare of workers and the number of matches, while the change in firm welfare is ambiguous. A signaling mechanism adds the most value for balanced markets. | Peter Coles, Alexey Kushnir and Muriel Niederle | Signaling, Cheap talk, Market design, Labor markets | |
| 2013 | Harmful Signaling in Matching Markets Several labor markets, including the job market for new Ph.D. economists, have recently developed formal signaling mechanisms. We show that such mechanisms are harmful for some environments. While signals transmit previously unavailable information, they also facilitate information asymmetry that leads to coordination failures. In particular, we consider a two-sided matching game of incomplete information between firms and workers. Each worker has either the same "typical" known preferences with probability close to one or "atypical" idiosyncratic preferences with the complementary probability close to zero. Firms have known preferences over workers. We show that under some technical condition if at least three firms are responsive to some worker's signal, the introduction of signaling strictly decreases the expected number of matches. | Alexey Kushnir | Signaling, Cheap talk, Labor markets | |
| 2013 | All About Priorities? Less School Choice with bad Schools School choice policies intend to give families the opportunity to decide the public school their children attend. Overdemand for a particular school is usually resolved by apparently innocuous, coarse priority rules given for residence in the catchment area of the school and other family socioeconomic characteristics. We study a coarse-priorities assignment problem with vertical differentiation separating good schools from a few bad schools. We show that the two most debated and used mechanisms, the Boston Mechanism (BOS) -provided some school is sufficiently bad- and Deferred Acceptance (DA), result in an assignment that closely replicates the priority structure, independently of families' preferences. Unless fully discriminated with lowest priority, families living in bad school areas barely access good schools and still block choice between good schools. The literature should therefore not take priorities as given, but incorporate them as a fundamental aspect of the design of the mechanism. | Caterina Calsamiglia and Antonio Miralles | School choice, Boston mechanism, Deferred Acceptance mechanism, Priorities, Strategic behaviour, Strategyproofness | |
| 2013 | Matching couples with Scarf’s algorithm Scarf’s algorithm (Scarf 1967) provides fractional core elements for NTU-games. Biró and Fleiner (2010) showed that Scarf’s algorithm can be extended for capacitated NTU-games. In this setting agents can be involved in more than one coalition at a time, cooperations may be performed with different intensities up to some limits, and the contribution of the agents can also differ in a coalition. The fractional stable solutions for the above model, produced by the extended Scarf algorithm, are called stable allocations. In this paper we apply this solution concept for the Hospitals Residents problem with Couples (HRC). This is one of the most important general stable matching problems due to its relevant applications, also well known to be NP-hard. We show that if a stable allocation yielded by the Scarf algorithm turns out to be integral then it provides a stable matching for an instance of HRC, so this method can be used as a heuristic. In an experimental study, we compare this method with other heuristics constructed for HRC that are applied in practice in the American and Scottish resident allocation programs, respectively. Our main finding is that the Scarf algorithm outperforms all the other known heuristics when the proportion of couples
is high | Péter Biró, Tamás Fleiner, Rob Irving | Scarf lemma, stable allocation, hospitals residents problem, matching with couples | |