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.

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.

• Item Type: MPRA Paper
• Language: English
• Keywords: two-sided matching, many-to-one 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 ; Cost-Benefit Analysis

References

[1] Biro, P., Fleiner, T., Irving, R., Manlove, D.: The college admissions problem with lower and common quotas. Theoretical Computer Science 411(34-36), 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 two-sided matching market with dis- crete concave utility functions. Discrete Applied Mathematics 154(6), 950– 970 (2006)

[5] Fujishige, S., Tamura, A.: A two-sided discrete-concave 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.: Strategy-proof 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: Priority-list based deferred acceptance mechanism (2014), mimeo (the latest version is available at http://mpra.ub.uni-muenchen.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 strategy-proofness 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 discrete-concave market. Mathematical Engineering Technical Re- ports 2013-30, 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.: Two-Sided 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 (branch-of-choice) contracts at the united states military academy. Econometrica 81(2), 451–488 (2013)