Designing matching mechanisms under constraints: An approach from discrete convex analysis

• 成果类型: Article
• 署名作者: Kojima, Fuhito; Tamura, Akihisa; Yokoo, Makoto
• 署名单位: Stanford University; Keio University; Kyushu University
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2018.05.004
• 发表日期: 2018
• 页码: 803-833
• 关键词: Two-sided matching; market design; matching with contracts; Matching with constraints; Discrete convex analysis; deferred acceptance

摘要

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-(sic)-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. (C) 2018 Elsevier Inc. All rights reserved.