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

Fuhito Kojima, Akihisa Tamura and Makoto Yokoo

MPRA Paper from University Library of Munich, Germany

Abstract: In this paper, we consider two-sided, many-to-one matching problems where agents in one side of the market (hospitals) impose some distributional constraints (e.g., a minimum quota for each hospital). We show that when the preference of the hospitals is represented as an M-natural-concave function, the following desirable properties hold: (i) the time complexity of the generalized GS mechanism is O(|X|^3), where |X| is the number of possible contracts, (ii) the generalized Gale & Shapley (GS) mechanism is strategyproof, (iii) the obtained matching is stable, and (iv) the obtained matching is optimal for the agents in the other side (doctors) within all stable matchings. Furthermore, we clarify sufficient conditions where the preference becomes an M-natural-concave function. These sufficient conditions are general enough so that they can cover most of existing works on strategyproof mechanisms that can handle distributional constraints in many-to-one matching problems. These conditions provide a recipe for non-experts in matching theory or discrete convex analysis to develop desirable mechanisms in such settings.

Keywords: two-sided matching; many-to-one matching; strategyproof mechanism; deferred acceptance; distributional constraints; discrete convex analysis (search for similar items in EconPapers)
JEL-codes: C71 C78 D61 (search for similar items in EconPapers)
Date: 2014-04-30
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://mpra.ub.uni-muenchen.de/56189/1/MPRA_paper_56189.pdf original version (application/pdf)
https://mpra.ub.uni-muenchen.de/62226/1/MPRA_paper_62226.pdf revised version (application/pdf)
https://mpra.ub.uni-muenchen.de/78637/9/MPRA_paper_78637.pdf revised version (application/pdf)
https://mpra.ub.uni-muenchen.de/86614/16/MPRA_paper_86614.pdf revised version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pra:mprapa:56189

Access Statistics for this paper

More papers in MPRA Paper from University Library of Munich, Germany Ludwigstraße 33, D-80539 Munich, Germany. Contact information at EDIRC.
Bibliographic data for series maintained by Joachim Winter ().