Kojima, Fuhito and Tamura, Akihisa and Yokoo, Makoto (2014): Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis.
Preview 
PDF
MPRA_paper_62226.pdf Download (305kB)  Preview 
Abstract
We consider twosided 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 Mnaturalconcave function, (i) the generalized Deferred Acceptance mechanism is strategyproof for doctors, (ii) it produces the doctoroptimal 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 Mnaturalconcave 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.
Item Type:  MPRA Paper 

Original Title:  Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis 
Language:  English 
Keywords:  twosided matching, manytoone matching, market design, matching with contracts, matching with constraints, Mnaturalconcavity, strategyproofness, deferred acceptance 
Subjects:  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 D  Microeconomics > D6  Welfare Economics > D63  Equity, Justice, Inequality, and Other Normative Criteria and Measurement 
Item ID:  62226 
Depositing User:  Prof. Makoto Yokoo 
Date Deposited:  20 Feb 2015 16:47 
Last Modified:  28 Sep 2019 21:27 
References:  Abdulkadiro˘glu, A. (2005): "College Admissions with Affirmative Action," International Journal of Game Theory, 33(4), 535–549. Abdulkadiro˘glu, A., and T. Sönmez (2003): "School Choice: A Mechanism Design Approach," American Economic Review, 93(3), 729–747. Abdulkadiro˘glu, A., and T. Sönmez (2013): "Matching Markets: Theory and Practice," in Advances in Economics and Econometrics, ed. by D. Acemoglu, M. Arello, and E. Dekel, vol. 1, pp. 3–47. Cambridge. Abdulkadiro˘glu, A., P. A. Pathak, and A. E. Roth (2005): "The New York City High School Match," American Economic Review P&P, 95, 364–367. Abdulkadiro˘glu, A., P. A. Pathak, and A. E. Roth (2009): "Strategyproofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match," American Economic Review, 99, 1954–1978. Abdulkadiro˘glu, A., P. A. Pathak, A. E. Roth, and T. Sönmez (2005): "The Boston Public School Match," American Economic Review P&P, 95, 368–371. Abdulkadiro˘ glu, A., P. A. Pathak, A. E. Roth, and T. Sönmez (2006): "Changing the Boston School Choice Mechanism: Strategyproofness as Equal Access," Harvard University and Boston College, unpublished mimeo. Abraham, D. J., R. W. Irving, and D. F. Manlove (2007): "Two Algorithms for the StudentProject Allocation Problem," Journal of Discrete Algorithms, 5(1), 73–90. Aygün, O., and T. Sönmez (2013): "Matching with Contracts: Comment," American Economic Review, 103, 2050–2051. Biro, P., T. Fleiner, R. Irving, and D. Manlove (2010): "The College Admissions Problem with Lower and Common Quotas," Theoretical Computer Science, 411(3436), 3136–3153. Budish, E., Y.K. Che, F. Kojima, and P. R. Milgrom (2013): "Designing Random Allocation Mechanisms: Theory and Applications,"American Economic Review, 103(2), 585–623. Cormen, T. H., C. E. Leiserson, R. L. Rivest, and C. Stein (2009): Introduction to Algorithms, Third Edition. The MIT Press. Dubins, L. E., and D. A. Freedman (1981): "Machiavelli and the GaleShapley Algorithm," The American Mathematical Monthly, 88(7), 485–494. Echenique, F. (2012): "Contracts vs. Salaries in Matching," American Economic Review, 102(1), 594–601. Ehlers, L., I. E. Hafalir, M. B. Yenmez, and M. A. Yildirim (2014): "School Choice with Controlled Choice Constraints: Hard Bounds versus Soft Bounds," Journal of Economic Theory, 153, 648—683. Farooq, R., and A. Shioura (2005): "A Note on the Equivalence between Substitutability and M#convexity," Pacific Journal of Optimization, 1, 243–252. Farooq, R., and A. Tamura (2004): "A New Characterization of M#convex Set Functions by Substitutability," Journal of the Operations Research Society of Japan, 47, 18–24. Fleiner, T. (2001): "A Matroid Generalization of the Stable Matching Polytope," in Integer Programming and Combinatorial Optimization: 8th International IPCO Conference, LNCS 2081, ed. by B. Gerards, and K. Aardal, pp. 105–114. SpringerVerlag. Fleiner, T. (2003): "A FixedPoint Approach to Stable Matchings and Some Applications," Mathematics of Operations Research, 28, 103–126. Fragiadakis, D., A. Iwasaki, P. Troyan, S. Ueda, and M. Yokoo (2015): "Strategyproof Matching with Minimum Quotas," ACM Transactions on Economics and Computation, forthcoming (an extended abstract in AAMAS, pages 1327–1328, 2012). Fragiadakis, D., and P. Troyan (2014): "Market Design under Distributional Constraints: Diversity in School Choice and Other Applications," mimeo. Fujishige, S., and A. Tamura (2006): "A general twosided matching market with discrete concave utility functions," Discrete Applied Mathematics, 154(6), 950–970. Fujishige, S., and A. Tamura (2007): "A Twosided Discreteconcave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis," Mathematics of Operations Research, 32(1), 136–155. Fujishige, S., and Z. Yang (2003): "A note on Kelso and Crawford’s gross substitutes condition," Mathematics of Operations Research, 28, 463–469. Gale, D., and L. S. Shapley (1962): "College Admissions and the Stability of Marriage," The American Mathematical Monthly, 69(1), 9–15. Goto, M., N. Hashimoto, A. Iwasaki, Y. Kawasaki, S. Ueda, Y. Yasuda, and M. Yokoo (2014): "Strategyproof matching with regional minimum quotas," in Thirteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS2014), pp. 1225–1232. Goto, M., A. Iwasaki, Y. Kawasaki, Y. Yasuda, and M. Yokoo (2014): "Improving Fairness and Efficiency in Matching Markets with Regional Caps: Prioritylist based Deferred Acceptance Mechanism," mimeo (the latest version is available at http://mpra.ub.uni muenchen.de/53409/). Gul, F., and E. Stacchetti (1999): "Walrasian equilibrium with gross substitutes," Journal of Economic Theory, 87(1), 95–124. Hafalir, I. E., M. B. Yenmez, and M. A. Yildirim (2013): "Effective affirmative action in school choice," Theoretical Economics, 8(2), 325–363. Hatfield, J. W., and F. Kojima (2008): "Matching with Contracts: Comment," American Economic Review, 98, 1189–1194. Hatfield, J. W., and F. Kojima (2009): "Group Incentive Compatibility for Matching with Contracts," Games and Economic Behavior, 67, 745–749. Hatfield, J. W., and F. Kojima (2010): "Substitutes and Stability for Matching with Contracts," Journal of Economic Theory, 145, 1704–1723. Hatfield, J. W., and S. D. Kominers (2009): "Contract Design and Stability in Matching Markets," mimeo. Hatfield, J. W., and S. D. Kominers (2012): "Matching in Networks with Bilateral Contracts," American Economic Journal: Microeconomics, pp. 176–208. Hatfield, J. W., and S. D. Kominers (2014): "Hidden Substitutes," mimeo. Hatfield, J. W., S. D. Kominers, A. Nichifor, M. Ostrovsky, and A. Westkamp (2013): "Stability and competitive equilibrium in trading networks," Journal of Political Economy, 121(5), 966–1005. Hatfield, J. W., and P. R. Milgrom (2005): "Matching with Con tracts," American Economic Review, 95(4), 913–935. Huh, W. T., and G. Janakiraman (2010): "On the Optimal Policy Structure in Serial Inventory Systems with Lost Sales," Operational Research, 58, 486–491. Kamada, Y., and F. Kojima (2012): "Stability and StrategyProofness for Matching with Constraints: A Problem in the Japanese Medical Match and Its Solution," American Economic Review P&P, 102(3), 366–370. Kamada, Y., and F. Kojima (2014a): "General Theory of Matching under Distributional Con straints," mimeo. Kamada, Y., and F. Kojima (2014b): "Stability Concepts in Matching with Distributional Con straints," mimeo. Kamada, Y., and F. Kojima (2015): "Efficient Matching under Distributional Constraints: Theory and Applications," American Economic Review, 105(1), 67–99. Kelso, J. A. S., and V. P. Crawford (1982): "Job matching, coalition formation, and gross substitutes," Econometrica, 50(6), 1483–1504. Kojima, F. (2012): "School choice: Impossibilities for affirmative action," Games and Economic Behavior, 75(2), 685–693. Kominers, S. D., and T. Sönmez (2014): "Matching with SlotSpecific Priorities: Theory," mimeo. Korte, B., and J. Vygen (2012): Combinatorial Optimization, Theory and Algorithms, Fifth Edition. Springer. Milgrom, P. (2000): "Putting Auction Theory to Work: The Simulteneous Ascending Auction," Journal of Political Economy, 108(2), 245–272. Milgrom, P. (2004): Putting Auction Theory to Work. Cambridge University Press, Cambridge. Milgrom, P. (2009): "Assignment messages and exchanges," American Economic Journal: Microeconomics, 1(2), 95–113. Murota, K. (1991): Matrices and Matroids for Systems Analysis. Springer. Murota, K. (2003): Discrete convex analysis. Society for Industrial and Applied Mathematics. Murota, K., and A. Shioura (1999): "Mconvex function on generalized polymatroid," Mathematics of Operations Research, 24, 95–105. Murota, K., A. Shioura, and Z. Yang (2013): "Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items," in The 24th International Symposium on Algorithms and Computation, LNCS 8283, pp. 468–478. Murota, K., and A. Tamura (2003): "Application of Mconvex submodular flow problem to mathematical economics," Japan Journal of Industrial and Applied Mathematics, 20, 257–277. Murota, K., and Y. Yokoi (2013): "On the Lattice Structure of Stable Allocations in TwoSided DiscreteConcave Market," Mathematical Engineering Technical Reports, 201330, 1–27. Ostrovsky, M., and R. P. Leme (2014): "Gross Substitutes and Endowed Assignment Valuations," Theoretical Economics. Oxley, J. (2011): Matroid Theory. Oxford University Press. Roth, A. E. (1982): "The economics of matching: Stability and incentives," Mathematics of Operations Research, 7(4), 617–628. Roth, A. E. (1991): "A natural experiment in the organization of entrylevel labor markets: regional markets for new physicians and surgeons in the United Kingdom," American Economic Review, 81, 415–440. Roth, A. E. (2002): "The economist as engineer: Game theory, experimentation, and computation as tools for design economics," Econometrica, 70(4), 1341–1378. Roth, A. E. (2008): "Deferred Acceptance Algorithms: History, Theory, Practice and Open Questions," International Journal of Game Theory, 36, 537–569. Roth, A. E., T. Sönmez, and M. U. Unver (2005): "Pairwise kidney exchange," Journal of Economic Theory, 125(2), 151–188. Roth, A. E., and M. A. O. Sotomayor (1990): Twosided Matching: a Study in Gametheoretic Modeling and Analysis. Econometric Society Monographs, Cambridge. Schrijver, A. (2003): Combinatorial Optimization  Polyhedra and Efficiency. Springer. Sönmez, T. (2013): "Bidding for Army Career Specialties: Improving the ROTC Branching Mechanism," Journal of Political Economy, 121(1), 186–219. Sönmez, T., and T. B. Switzer (2013): "Matching With (BranchofChoice) Contracts at the United States Military Academy," Econometrica, 81(2), 451–488. Sönmez, T., and M. Unver (2011): "Matching, Allocation, and Exchange of Discrete Resources," in Handbook of Social Economics, ed. by A. Bisin, J. Benhabib, and M. Jackson, pp. 781–852. NorthHolland. Sun, N., and Z. Yang (2006): "Equilibria and Indivisibilities: Gross Substitutes and Complements," Econometrica, 74, 1385–1402. Zipkin, P. (2008): "On the Structure of LostSales INventory Models," Operational Research, 56, 937–944. 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/62226 
Available Versions of this Item

Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis. (deposited 30 May 2014 03:37)
 Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis. (deposited 20 Feb 2015 16:47) [Currently Displayed]