2018  FirstChoice Maximal and FirstChoice Stable School Choice Mechanisms
Abstract: We investigate the class of school choice mechanisms that are firstchoice maximal (FCM) (i.e., they match a maximal number of students to their reported first choices) and firstchoice 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 rankbased relaxation of stability that is compatible with FCM. The class of FCM and FCS mechanisms includes variants of the wellknown 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  TopTen Way to Integrate High Schools
Abstract: We investigate how “topN percent” policies in college admission affect diversity at the highschool 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 topN 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 manytoone 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 manytoone 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 manytoone 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, fixedparameter 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, Manytoone 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 Paretooptimality, individualrationality, strategyproofness, reallocationproofness, and consistency.  Mehmet Karakaya, Bettina Klaus, Jan Christoph Schlegel  Consistency, house allocation, matching, strategyproofness, 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 myopicfarsighted stable set, which is based on the notion of a myopic farsighted improving path. A myopicfarsighted stable set is the set of match ings such that there is no myopicfarsighted improving path from any match ing in the set to another matching in the set (internal stability) and there is a myopicfarsighted 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 womanoptimal stable matching is a myopicfarsighted stable set. The same result holds when all women are farsighted. We present examples where this is the unique myopicfarsighted stable set as well as examples of myopicfarsighted stable sets consisting of a core element di§erent from the womanoptimal matching or even of a noncore element.  P. JeanJacques 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 nonnegligible share of these mistakes are consequential, costing applicants approximately 3,000 dollars. Costly mistakes transfer waivers from high to lowsocioeconomic 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, strategyproof  
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 Npercent 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 onesided 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 strategyproof. 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, Strategyproofness, Twosided matching, Onesided 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 nontransferable 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 loglikelihood 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 twosided 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 collegecoach 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, egaldsri, 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 NPhard 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 dsrti, preference lists can include ties and are of length at most d. We show that the problem of deciding whether an instance of dsrti admits a stable matching is NPcomplete 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 strategyproof 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 1015 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 realworld 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 TieBreaking 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 tiebreaking rule outperforms the multiple tiebreaking 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, Tiebreaking, 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 DeferredAcceptance 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 practiceas 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 "betteroff". 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 strategyproof 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  Twosided matching markets, Teacher Assignment, Fairness, Efficiency  
2015  The performance of school assignment mechanisms in practice
Theory points to a potential tradeoff 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 exante 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 mostpreferred school. We compare allocations resulting from Boston with DA with single tiebreaking (one central lottery; DASTB) and multiple tiebreaking (separate lottery per school; DAMTB). DASTB places more students in their topn schools, for any n, than Boston and results in higher average welfare. We find a tradeoff between DASTB and DAMTB. DASTB places more students in their single mostpreferred school than DAMTB, but fewer in their topn, 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, exante efficiency, expost efficiency  
2015  Selfselection in School Choice: Theory and Evidence from Mexico City High School Match
We study selfselection in centralized school choice, a strategic behavior that takes place when students have to submit preferences before knowing priorities at schools. Students selfselect 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 strategyproof. Using data from Mexico City high school match, we find evidence that selfselection exists, and has negative consequences. First, students from low socioeconomic backgrounds are more likely to selfselect. Second, once the uncertainty is resolved, some students who finally get a high priority are not assigned to their most preferred choice because of selfselection; and again, this happens more often among those from low socioeconomic 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, Selfselection, Serial Dictatorship Mechanism,
Strategyproofness  
2015  Beyond TruthTelling: 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 GaleShapley Deferred Acceptance. Without requiring truthtelling to be the unique equilibrium, we show the matching is (asymptotically) stable, or justifiedenvyfree, 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 truthtelling 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  GaleShapley DeferredAcceptance Mechanism, School Choice, Stable
Matching, Student Preferences, Admission Criteria  
2015  StrategyProof Fair School Placement
This paper provides an 'escape route' from the efficiencyequity tradeoff in the School Choice problem. We achieve our objective by presenting a weak notion of fairness, called τfairness, which is always nonempty.
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 strategyproof.  José Alcalde and Antonio RomeroMedina  School Choice Problem, Fair Matching, StrategyProofness  
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 tiebreaking. 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 tradeoff 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, Allpay auctions, Experiment  
2014  A new solution for the roommate problem: The Qstable 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 Qstable 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 LowIncome Students: Evidence from a Large NeedBased Grant Program Using comprehensive administrative data on France's single largest financial aid program, this paper provides new evidence on the impact of largescale needbased grant programs on the college enrollment decisions, persistence and graduation rates of lowincome 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 needbased grants have positive effects on student persistence and degree completion.  Gabrielle Fack and Julien Grenet  Needbased 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 shortlived 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 demandsupply imbalances, I introduce two simple classes of cutoff adjustment processes that always converge to market clearing. If instantaneous reaction to over or underenrollment 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 marketclearing 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 GaleShapley 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 firstbest. Affirmative action policies can restore diversity within colleges but also affect incentives to invest in precollege scholastic achievement. Affirmative action policies that are achievementbased 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 crosssubsidization 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 scorelimits, 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 NPhard to solve. Currently, a heuristic based on the GaleShapley 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 NPcompleteness 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 realworld 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, NPhard  
2014  Gaming the Boston School Choice Mechanism in Beijing The Boston mechanism is criticized for its poor incentive and welfare performance compared with the GaleShapley deferredacceptance 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 moreeducated parents are any more adept at strategizing. If others behave as in the data, an average naive parent who is always truthtelling 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, GaleShapley DeferredAcceptance Mechanism, School Choice, Bayesian Nash Equilibrium, StrategyProofness, Moment Inequalities, Beijing, China.  
2014  Driven by priorities manipulations under the Boston mechanism Inspired by reallife 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 schooloptimal stable matching. Moreover, the condition is necessary: if the outcome of the Boston mechanism is the schooloptimal 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  Twosided manytoone 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 Frenchspeaking 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 twosided 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 coarsepriorities 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 NTUgames. Biró and Fleiner (2010) showed that Scarf’s algorithm can be extended for capacitated NTUgames. 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 NPhard. 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  