Munich Personal RePEc Archive

Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis

Kojima, Fuhito and Tamura, Akihisa and Yokoo, Makoto (2014): Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis.

WarningThere is a more recent version of this item available.
[img]
Preview
PDF
MPRA_paper_62226.pdf

Download (305kB) | Preview

Abstract

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-natural-concave function, (i) the generalized Deferred Acceptance 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 for representation by an M-natural-concave function. These conditions are applicable to various existing works and enable new applications as well, thereby providing a recipe for developing desirable mechanisms in practice.

Available Versions of this Item

Logo of the University Library LMU Munich
MPRA is a RePEc service hosted by
the University Library LMU Munich in Germany.