Kojima, Fuhito and Tamura, Akihisa and Yokoo, Makoto (2014): Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis.
This is the latest version of this item.
Preview 
PDF
MPRA_paper_86614.pdf Download (379kB)  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 (DA) 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 under which the generalized DA mechanism satisfies these desirable properties. 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:  86614 
Depositing User:  Prof. Makoto Yokoo 
Date Deposited:  11 May 2018 13:30 
Last Modified:  27 Sep 2019 15:21 
References:  Abdulkadiroglu, A. (2005): “College Admissions with Affirmative Action,” International Journal of Game Theory, 33(4), 535–549. Abdulkadiroglu, A., and T. Sonmez (2003): “School Choice: A Mechanism Design Approach,” American Economic Review, 93(3), 729–747. Abdulkadiroglu, A., and T. Sonmez (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. Abdulkadiroglu, A., P. A. Pathak, and A. E. Roth (2005): “The New York City High School Match,” American Economic Review P&P, 95(2), 364–367. Abdulkadiroglu, 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(5), 1954–1978. Abdulkadiroglu, A., P. A. Pathak, A. E. Roth, and T. Sonmez (2005): “The Boston Public School Match,” American Economic Review P&P, 95, 368–371. Abdulkadiroglu, A., P. A. Pathak, A. E. Roth, and T. Sonmez (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. Aygun, O., and T. Sonmez (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. Echenique, F., and M. B. Yenmez (2015): “How to Control Controlled School Choice,” American Economic Review, 105(8), 2679–2694. Edmonds, J. (1971): “Matroids and the greedy algorithm,” Mathematical Programming, 1(1), 127–136. 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. Erdil, A., and T. Kumano (2012): “Prioritizing Diversity in School Choice,” mimeo. Farooq, R., and A. Shioura (2005): “A Note on the Equivalence between Substitutability and Mconvexity,” 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. Fleiner, T., and N. Kamiyama (2016): “A Matroid Approach to Stable Matchings with Lower Quotas,” Mathematics of Operations Research, 41(2), 734–744. Fragiadakis, D., A. Iwasaki, P. Troyan, S. Ueda, and M. Yokoo (2016): “Strategyproof Matching with Minimum Quotas,” ACM Transactions on Economics and Computation, 4(1), 6:1–6:40. Fragiadakis, D., and P. Troyan (2017): “Improving Matching under Hard Distributional Constraints,” Theoretical Economics., 12(2), 863–908. 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., A. Iwasaki, Y. Kawasaki, R. Kurata, Y. Yasuda, and M. Yokoo (2016): “Strategyproof matching with regional minimum and maximum quotas,” Artificial Intelligence, 235, 40–57. Goto, M., A. Iwasaki, Y. Kawasaki, Y. Yasuda, and M. Yokoo (2014): “Improving Fairness and Efficiency in Matching with Distributional Constraints: An Alternative Solution for the Japanese Medical Residency Match,” mimeo (the latest version is available at http://mpra.ub.unimuenchen.de/53409/). Goto, M., F. Kojima, R. Kurata, A. Tamura, and M. Yokoo (2017): “Designing Matching Mechanisms under General Distributional Constraints,” American Economic Journal: Microeconomics, 9(2), 226–62. 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 Contracts,” 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 (2014): “General Theory of Matching under Distributional Constraints,” mimeo. Kamada, Y., and F. Kojima (2015): “Efficient Matching under Distributional Constraints: Theory and Applications,” American Economic Review, 105(1), 67–99. Kamada, Y., and F. Kojima (2017a): “Stability and StrategyProofness for Matching with Constraints: a Necessary and Sufficient Condition,” Theoretical Economics, forthcoming. Kamada, Y., and F. Kojima (2017b): “Stability Concepts in Matching with Distributional Constraints,” Journal of Economic Theory, 168, 107–142. 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. Kojima, F. (2016): “Recent Developments in Mathing Theory and Their Practical Applications,” in Advances in Economics and Econometrics, 11th World Congress of the Econometric Society, ed. by L. Samuelson. Cambridge. Kominers, S. D., and T. Sonmez (2016): “Matching with slotspecific priorities: Theory,” Theoretical Economics, 11(2), 683–710. 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. Murota, K.(2009): “Assignment Messages and Exchanges,” American Economic Journal: Microeconomics, 1(2), 95–113. Murota, K. (2000): Matrices and Matroids for Systems Analysis. Springer. Murota, K.(2003): Discrete Convex Analysis. Society for Industrial and Applied Mathematics. Murota, K. (2016): “Discrete Convex Analysis: A Tool for Economics and Game Theory,” Journal of Mechanism and Institution Design, 1, 151–273. Murota, K., and A. Shioura (1999): “Mconvex Function on Generalized Polymatroid,” Mathematics of Operations Research, 24(1), 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 (2015): “On the Lattice Structure of Stable Allocations in TwoSided DiscreteConcave Market,” Mathematics of Operations Research, 40, 460–473. Ostrovsky, M., and R. Paes Leme (2015): “Gross substitutes and endowed assignment valuations,” Theoretical Economics, 10(3), 853–865. Oxley, J. (2011): Matroid Theory. Oxford University Press. Pathak, P. A. (2016): “What Really Matters in Designing School Choice Mechanisms,” in Advances in Economics and Econometrics, 11th World Congress of the Econometric Society, ed. by L. Samuelson. Cambridge. 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(3), 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(3), 537–569. Roth, A. E., T. Sonmez, 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. Sonmez, T. (2013): “Bidding for Army Career Specialties: Improving the ROTC Branching Mechanism,” Journal of Political Economy, 121(1), 186–219. Sonmez, T., and T. B. Switzer (2013): “Matching with (BranchofChoice) Contracts at the United States Military Academy,” Econometrica, 81(2), 451–488. Sonmez, T., and M. U.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/86614 
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)

Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis. (deposited 21 Apr 2017 07:58)
 Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis. (deposited 11 May 2018 13:30) [Currently Displayed]

Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis. (deposited 21 Apr 2017 07:58)

Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis. (deposited 20 Feb 2015 16:47)