Matching Without Substitutes: Theory and Applications

Paper Session

Sunday, Jan. 8, 2017 1:00 PM – 3:00 PM

Swissotel Chicago, Zurich B
Hosted By: American Economic Association
  • Chair: Paul Milgrom, Stanford University

Stability and Strategy-Proofness for Matching With Constraints: A Necessary and Sufficient Condition

Yuichiro Kamada
,
University of California-Berkeley
Fuhito Kojima
,
Stanford University

Abstract

Distributional constraints are common features in many real matching markets, such as medical residency matching, school admissions, and teacher assignment. We develop a general theory of matching mechanisms under distributional constraints. We identify the necessary and sufficient condition on the constraint structure for the existence of a mechanism that is stable and strategy-proof for the individuals. Our proof exploits a novel connection between a matching problem under distributional constraints and a matching problem with contracts.

Redesigning the Israeli Psychology Masters Match

Avinatim Hassidim
,
Bar-Ilan University
Assaf Romm
,
Hebrew University of Jerusalem
Ran I. Shorrer
,
Harvard University

Abstract

We 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

Orhan Aygun
,
Bogazici University
Bertan Turhan
,
Mexico Autonomous Institute of Technology

Abstract

Indian 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

John William Hatfield
,
University of Texas-Austin
Scott Duke Kominers
,
Harvard University
Alexander Westkamp
,
University of Cologne

Abstract

We 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.
Discussant(s)
Eduardo Azevedo
,
University of Pennsylvania
Muriel Niederle
,
Stanford University
Nikhil Agarwal
,
Massachusetts Institute of Technology
Yeon-Koo Che
,
Columbia University
JEL Classifications
  • C7 - Game Theory and Bargaining Theory
  • D4 - Market Structure, Pricing, and Design