TY - JOUR
T1 - Designing matching mechanisms under constraints
T2 - An approach from discrete convex analysis
AU - Kojima, Fuhito
AU - Tamura, Akihisa
AU - Yokoo, Makoto
N1 - Funding Information:
We are grateful to the Associate Editor and two referees whose comments led to substantial revision. We also thank Peter Biro, Daniel Fragiadakis, Paul Milgrom, Herve Moulin, Muriel Niederle, Michael Ostrovsky, Bobak Pakzad-Hurson, Al Roth, Alex Teytelboym, Peter Troyan, Yuichi Yamamoto, and seminar participants at Iowa, Simon Fraser, Stanford, Tokyo, UC Berkeley, SWET 2014, The Second International Workshop on Market Design Technologies for Sustainable Development, SAET 2014, and SAGT 2014 for comments. Nathanäel Barrot, Christina Chiu, Yue Fan, Masahiro Goto, Atsushi Iwasaki, Yujiro Kawasaki, Stephen Nei, Jinjae Park, Fanqi Shi, and Akhil Vohra provided excellent research assistance. Kojima acknowledges the financial support from the National Research Foundation through its Global Research Network Grant (NRF- 2016S1A2A2912564 ) and from Sloan Foundation ( BR2013-005 ). Tamura and Yokoo acknowledge the financial support from JSPS Kakenhi Grant Number 17H00761 . Tamura also acknowledges the financial support from JSPS Kakenhi Grant Number 16K00023 .
Funding Information:
We are grateful to the Associate Editor and two referees whose comments led to substantial revision. We also thank Peter Biro, Daniel Fragiadakis, Paul Milgrom, Herve Moulin, Muriel Niederle, Michael Ostrovsky, Bobak Pakzad-Hurson, Al Roth, Alex Teytelboym, Peter Troyan, Yuichi Yamamoto, and seminar participants at Iowa, Simon Fraser, Stanford, Tokyo, UC Berkeley, SWET 2014, The Second International Workshop on Market Design Technologies for Sustainable Development, SAET 2014, and SAGT 2014 for comments. Nathanäel Barrot, Christina Chiu, Yue Fan, Masahiro Goto, Atsushi Iwasaki, Yujiro Kawasaki, Stephen Nei, Jinjae Park, Fanqi Shi, and Akhil Vohra provided excellent research assistance. Kojima acknowledges the financial support from the National Research Foundation through its Global Research Network Grant (NRF-2016S1A2A2912564) and from Sloan Foundation (BR2013-005). Tamura and Yokoo acknowledge the financial support from JSPS Kakenhi Grant Number 17H00761. Tamura also acknowledges the financial support from JSPS Kakenhi Grant Number 16K00023.
Publisher Copyright:
© 2018 Elsevier Inc.
PY - 2018/7
Y1 - 2018/7
N2 - We consider two-sided matching problems where agents on one side of the market (hospitals) are required to satisfy certain distributional constraints. We show that when the preferences and constraints of the hospitals can be represented by an M♮-concave function, (i) the generalized Deferred Acceptance (DA) mechanism is strategyproof for doctors, (ii) it produces the doctor-optimal stable matching, and (iii) its time complexity is proportional to the square of the number of possible contracts. Furthermore, we provide sufficient conditions under which the generalized DA mechanism satisfies these desirable properties. These conditions are applicable to various existing works and enable new applications as well, thereby providing a recipe for developing desirable mechanisms in practice.
AB - We consider two-sided matching problems where agents on one side of the market (hospitals) are required to satisfy certain distributional constraints. We show that when the preferences and constraints of the hospitals can be represented by an M♮-concave function, (i) the generalized Deferred Acceptance (DA) mechanism is strategyproof for doctors, (ii) it produces the doctor-optimal stable matching, and (iii) its time complexity is proportional to the square of the number of possible contracts. Furthermore, we provide sufficient conditions under which the generalized DA mechanism satisfies these desirable properties. These conditions are applicable to various existing works and enable new applications as well, thereby providing a recipe for developing desirable mechanisms in practice.
UR - http://www.scopus.com/inward/record.url?scp=85047237799&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85047237799&partnerID=8YFLogxK
U2 - 10.1016/j.jet.2018.05.004
DO - 10.1016/j.jet.2018.05.004
M3 - Article
AN - SCOPUS:85047237799
SN - 0022-0531
VL - 176
SP - 803
EP - 833
JO - Journal of Economic Theory
JF - Journal of Economic Theory
ER -