Goto, Masahiro and Kojima, Fuhito and Kurata, Ryoji and Tamura, Akihisa and Yokoo, Makoto (2015): Designing Matching Mechanisms under General Distributional Constraints.
There is a more recent version of this item available. 

PDF
MPRA_paper_64000.pdf Download (213kB)  Preview 
Abstract
In this paper, we consider twosided, manytoone matching problems where agents in one side of the market (schools) impose some distributional constraints (e.g., a maximum quota for a set of schools), and develop a strategyproof mechanism that can handle a very general class of distributional constraints. We assume distributional constraints are imposed on a vector, where each element is the number of contracts accepted for each school. The only requirement we impose on distributional constraints is that the family of vectors that satisfy distributional constraints must be hereditary, which means if a vector satisfies the constraints, any vector that is smaller than it also satisfies them. When distributional constraints are imposed, a stable matching may not exist. We develop a strategyproof mechanism called Adaptive Deferred Acceptance mechanism (ADA), which is nonwasteful and ``more fair'' than a simple nonwasteful mechanism called the Serial Dictatorship mechanism (SD) and ``less wasteful'' than another simple fair mechanism called the Artificial Cap Deferred Acceptance mechanism (ACDA). We show that we can apply this mechanism even if the distributional constraints do not satisfy the hereditary condition by applying a simple trick, assuming we can find a vector that satisfy the distributional constraints efficiently. Furthermore, we demonstrate the applicability of our model in actual application domains.
Item Type:  MPRA Paper 

Original Title:  Designing Matching Mechanisms under General Distributional Constraints 
Language:  English 
Keywords:  twosided matching, manytoone matching, market design, matching with contracts, matching with constraints, 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:  64000 
Depositing User:  Prof. Makoto Yokoo 
Date Deposited:  02 May 2015 07:03 
Last Modified:  27 Sep 2019 07:08 
References:  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. 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. 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. 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. 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 (2013): “Market Design under Distributional Constraints: Diversity in School Choice and Other Applications,” mimeo. 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.unimuenchen.de/53409/). Hatfield, J. W., and P. R. Milgrom (2005): “Matching with Contracts,” American Economic Review, 95(4), 913–935. Kamada, Y., and F. Kojima (2014): “Stability Concepts in Matching with Distributional Constraints,” mimeo. Kamada, Y., and F. Kojima (2015): “Efficient Matching under Distributional Constraints: Theory and Applications,” American Economic Review, 105(1), 67–99. Kojima, F., A. Tamura, and M. Yokoo (2014): “Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis,” in Proceedings of the Seventh International Symposium on Algorithmic Game Theory (SAGT2014). the full version is available at http://mpra.ub.unimuenchen.de/62226). McVitie, D. G., and L. B. Wilson (1971): “The Stable Marriage Problem,” Commun. ACM, 14(7), 486–490. Milgrom, P. (2009): “Assignment messages and exchanges,” American Economic Journal: Microeconomics, 1(2), 95–113. Murota, K. (2003): Discrete Convex Analysis. Society for Industrial and Applied Mathematics. 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., and M. A. O. Sotomayor (1990): TwoSided Matching: A Study in GameTheoretic Modeling and Analysis (Econometric Society Monographs). Cambridge University Press. Sönmez, T., and T. B. Switzer (2013): “Matching With (BranchofChoice) Contracts at the United States Military Academy,” Econometrica, 81(2), 451–488. 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/64000 
Available Versions of this Item
 Designing Matching Mechanisms under General Distributional Constraints. (deposited 02 May 2015 07:03) [Currently Displayed]