Matching Without Substitutes: Theory and Applications
Sunday, Jan. 8, 2017 1:00 PM – 3:00 PM
- Chair: Paul Milgrom, Stanford University
Redesigning the Israeli Psychology Masters Match
AbstractWe review the process of redesigning the Israeli Psychology Masters Match (IPMM), with special attention given to tailoring the system to accommodate departments’ choice rules. More specifically, we document choice rules that require the full generality of the recent theory on weakening the substitutes condition while preserving the good properties of the Deferred Acceptance (DA). While the system is designed to allow departments to succinctly communicate their choice rules, the protocol does not allow specifying arbitrary substitutable choice rules. We underscore the importance of a bidding language by providing a negative result showing that it is impossible to use a polynomial number of demand oracle queries to infer the choice function. Finally, we claim that the types of choice rules we observe are not unique to the current application, but are in fact quite common. We note that while the American National Residency Matching Program (NRMP) allows reporting similar choice rules, it deviates from the resident-proposing DA in ways that may yield outcomes that are dominated from the perspective of applicants.
Dynamic Reserves in Matching Markets: Theory and Applications
AbstractIndian Engineering school admissions, which draws more than 500,000 applications per year, suffers from an important market failure: Through their affirmative action program certain number of seats are reserved for different lower castes and tribes. However, when some of these seats are unfilled they are not offered to other groups, and the system is vastly wasteful. Moreover, since students care not only about the school they are assigned to but also whether they are assigned through reserves or not, they may strategically manipulate the system by both not revealing their privilege type and changing their preferences over schools. In this paper, we propose a new matching model with contracts with the ability to release vacant seats to the use of other students by respecting certain affirmative action objectives. We design a new choice function for schools that respects affirmative action objectives, avoids waste, and increases efficiency. We propose a mechanism that is stable, strategy proof, and respects test score improvements with respect to these choice functions. Moreover, we show that some distributional objectives that can be achieved by capacity transfers cannot be achieved by slot-specific priorities.
Stability, Strategy-Proofness, and Cumulative Offer Mechanisms
AbstractWe consider the setting of many-to-one matching with contracts, where firms may demand multiple contracts but each worker desires at most one contract. We introduce three novel conditions—observable substitutability, observable size monotonicity, and non-manipulatability—and show that when these conditions are satisfied, the cumulative offer mechanism is the unique mechanism that is stable and strategy-proof (for workers). Moreover, when the choice function of some firm fails any of our three conditions, one can construct unit-demand choice functions for the other firms such that no stable and strategy-proof mechanism exists. In the final part of the paper, we characterize the class of choice functions for which the cumulative offer mechanism is guaranteed to yield a stable outcome.
- C7 - Game Theory and Bargaining Theory
- D4 - Market Structure, Pricing, and Design