|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,|
|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
|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
|Péter Biró, Tamás Fleiner, Rob Irving||Scarf lemma, stable allocation, hospitals residents problem, matching with couples||