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

We consider two-sided 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 M-natural-concave function, (i) the generalized Deferred Acceptance (DA) mechanism is strategyproof for doctors, (ii) it produces the doctor-optimal 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
• Language: English
• Keywords: two-sided matching, many-to-one matching, market design, matching with contracts, matching with constraints, M-natural-concavity, 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 ; Cost-Benefit Analysis; D - Microeconomics > D6 - Welfare Economics > D63 - Equity, Justice, Inequality, and Other Normative Criteria and Measurement

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): "Strategy-proofness 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 Student-Project 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(34-36), 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 Gale-Shapley 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. Springer-Verlag.

Fleiner, T. (2003): "A Fixed-Point 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 two-sided matching market with discrete concave utility functions," Discrete Applied Mathematics, 154(6), 950–970.

Fujishige, S., and A. Tamura (2007): "A Two-sided Discrete-concave 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): "Strategy-proof matching with regional minimum quotas," in Thirteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2014), 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: Priority-list 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 Strategy-Proofness 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 Slot-Specific 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): "M-convex 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 M-convex 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 Two-Sided Discrete-Concave Market," Mathematical Engineering Technical Reports, 2013-30, 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 entry-level 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): Two-sided Matching: a Study in Game-theoretic 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 (Branch-of-Choice) 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. North-Holland.

Sun, N., and Z. Yang (2006): "Equilibria and Indivisibilities: Gross Substitutes and Complements," Econometrica, 74, 1385–1402.

Zipkin, P. (2008): "On the Structure of Lost-Sales INventory Models," Operational Research, 56, 937–944.