Kojima, Fuhito and Tamura, Akihisa and Yokoo, Makoto (2014): Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis.
There is a more recent version of this item available. 

PDF
MPRA_paper_56189.pdf Download (177kB)  Preview 
Abstract
In this paper, we consider twosided, manytoone 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 Mnaturalconcave 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 Mnaturalconcave 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 manytoone matching problems. These conditions provide a recipe for nonexperts in matching theory or discrete convex analysis to develop desirable mechanisms in such settings.
Item Type:  MPRA Paper 

Original Title:  Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis 
Language:  English 
Keywords:  twosided matching, manytoone matching, strategyproof mechanism, deferred acceptance, distributional constraints, discrete convex analysis 
Subjects:  C  Mathematical and Quantitative Methods > C7  Game Theory and Bargaining Theory > C71  Cooperative Games C  Mathematical and Quantitative Methods > C7  Game Theory and Bargaining Theory > C78  Bargaining Theory ; Matching Theory D  Microeconomics > D6  Welfare Economics > D61  Allocative Efficiency ; CostBenefit Analysis 
Item ID:  56189 
Depositing User:  Prof. Makoto Yokoo 
Date Deposited:  30 May 2014 03:37 
Last Modified:  27 Sep 2019 07:55 
References:  [1] Biro, P., Fleiner, T., Irving, R., Manlove, D.: The college admissions problem with lower and common quotas. Theoretical Computer Science 411(3436), 3136–3153 (2010) [2] Ehlers, L., Hafalir, I.E., Yenmez, M.B., Yildirim, M.A.: School choice with controlled choice constraints: Hard bounds versus soft bounds (2012), mimeo [3] Fragiadakis, D., Iwasaki, A., Troyan, P., Ueda, S., Yokoo, M.: Strategyproof matching with minimum quotas (2012), mimeo (an extended abstract ver sion appeared in AAMAS, pages 1327–1328, 2012) [4] Fujishige, S., Tamura, A.: A general twosided matching market with dis crete concave utility functions. Discrete Applied Mathematics 154(6), 950– 970 (2006) [5] Fujishige, S., Tamura, A.: A twosided discreteconcave market with pos sibly bounded side payments: An approach by discrete convex analysis. Mathematics of Operations Research 32(1), 136–155 (2007) [6] Gale, D., Shapley, L.S.: College admissions and the stability of marriage. The American Mathematical Monthly 69(1), 9–15 (1962) [7] Goto, M., Hashimoto, N., Iwasaki, A., Kawasaki, Y., Ueda, S., Yasuda, Y., Yokoo, M.: Strategyproof matching with regional minimum quotas. In: AAMAS2014 (2014) [8] Goto, M., Iwasaki, A., Kawasaki, Y., Yasuda, Y., Yokoo, M.: Improving fairness and efficiency in matching markets with regional caps: Prioritylist based deferred acceptance mechanism (2014), mimeo (the latest version is available at http://mpra.ub.unimuenchen.de/53409/) [9] Hatfield, J.W., Milgrom, P.R.: Matching with contracts. American Eco nomic Review 95(4), 913–935 (2005) [10] Kamada, Y., Kojima, F.: Stability and strategyproofness for match ing with constraints: A problem in the japanese medical match and its solution (2013), mimeo (the lateset version is available from http://ykamada.com/pdf/geography.pdf) [11] Murota, K.: Discrete convex analysis. Society for Industrial and Applied Mathematics (2003) [12] Murota, K., Yokoi, Y.: On the lattice structure of stable allocations in two sided discreteconcave market. Mathematical Engineering Technical Re ports 201330, 1–27 (2013) [13] Oxley, J.: Matroid Theory. Oxford University Press (2011) [14] Roth, A.E.: The economist as engineer: Game theory, experimentation, and computation as tools for design economics. Econometrica 70(4), 1341–1378 (2002) [15] Roth, A.E., Sotomayor, M.A.O.: TwoSided Matching: A Study in Game Theoretic Modeling and Analysis (Econometric Society Monographs). Cam bridge University Press. (1990) [16] S¨ onmez, T., Switzer, T.B.: Matching with (branchofchoice) contracts at the united states military academy. Econometrica 81(2), 451–488 (2013) 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/56189 
Available Versions of this Item
 Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis. (deposited 30 May 2014 03:37) [Currently Displayed]