Student-Project-Resource Matching-Allocation Problems: Game Theoretic Analysis

Yamaguchi, Tomoaki and Yahiro, Kentaro and Yokoo, Makoto (2019): Student-Project-Resource Matching-Allocation Problems: Game Theoretic Analysis.

Abstract

In this work, we consider a three sided student-project-resource matching-allocation problem, in which students have preferences on projects, and projects on students. While students are many-to-one matched to projects, indivisible resources are many-to-one allocated to projects whose capacities are thus endogenously determined by the sum of resources allocated to them. Traditionally, this problem is divided into two separate problems: (1) resources are allocated to projects based on some expectations (resource allocation problem), and (2) students are matched to projects based on the capacities determined in the previous problem (matching problem). Although both problems are well-understood, unless the expectations used in the first problem are correct, we obtain a suboptimal outcome. Thus, it is desirable to solve this problem as a whole without dividing it in two.

In this paper, we first show that a stable (i.e., fair and nonwasteful) matching does not exist in general (nonwastefulness is a criterion related to efficiency). Then, we show that no strategyproof mechanism satisfies fairness and very weak efficiency requirements. Given this impossibility result, we develop a new strategyproof mechanism that strikes a good balance between fairness and efficiency, which is assessed by experiments.

• Item Type: MPRA Paper
• Language: English
• Keywords: two-sided matching, mechanism design, resource allocation, strategyproof
• 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

David J. Abraham, Robert W. Irving, and David F. Manlove. 2007. Two Algorithms for the Student-Project Allocation Problem. Journal of Discrete Algorithms 5, 1 (2007), 73–90.

Ahmet Alkan. 1988. Nonexistence of Stable Threesome Matchings. Mathematical Social Sciences 16, 2 (1988), 207–209.

Haris Aziz, Peter Biro, Tamas Fleiner, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari. 2017. Stable Matching with Uncertain Pairwise Preferences. In Proceedings of the 16th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS-2017). 344–352.

Christian Borgs, Jennifer Chayes, Nicole Immorlica, Mohammad Mahdian, and Amin Saberi. 2005. Multi-unit Auctions with Budget-constrained Bidders. In Proceedings of the 6th ACM Conference on Electronic Commerce (EC-2005). 44–51.

Frances Cooper and David Manlove. 2018. A 3/2-Approximation Algorithm for the Student-Project Allocation Problem. In Proceedings of the 17th International Symposium on Experimental Algorithms (SEA-2018). 8:1–8:13.

Joanna Drummond and Craig Boutilier. 2013. Elicitation and Approximately Stable Matching with Partial Preferences. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI-2013). 97–105.

Lars Ehlers, Isa E. Hafalir, M. Bumin Yenmez, and Muhammed A. Yildirim. 2014. School Choice with Controlled Choice Constraints: Hard Bounds versus Soft Bounds. Journal of Economic Theory 153 (2014), 648–683.

Daniel Fragiadakis, Atsushi Iwasaki, Peter Troyan, Suguru Ueda, and Makoto Yokoo. 2016. Strategyproof Matching with Minimum Quotas. ACM Transactions on Economics and Computation 4, 1 (2016), 6:1–6:40.

David Gale and Lloyd Stowell Shapley. 1962. College Admissions and the Stability of Marriage. The American Mathematical Monthly 69, 1 (1962), 9–15.

Andrew V. Goldberg, Jason D. Hartline, and Andrew Wright. 2001. Competitive auctions and digital goods. In Proceedings of the 12th Annual Symposium on Discrete Algorithms (SODA-2001). 735–744.

Masahiro Goto, Atsushi Iwasaki, Yujiro Kawasaki, Ryoji Kurata, Yosuke Yasuda, and Makoto Yokoo. 2016. Strategyproof Matching with Regional Minimum and Maximum Quotas. Artificial Intelligence 235 (2016), 40–57.

Masahiro Goto, Fuhiko Kojima, Ryoji Kurata, Akihisa Tamura, and Makoto Yokoo. 2017. Designing Matching Mechanisms under General Distributional Constraints. American Economic Journal: Microeconomics 9, 2 (2017), 226–262.

Gurobi. 2018. Gurobi Optimizer Reference Manual. http://www.gurobi.com/documentation/8.0/refman.pdf.

Isa E. Hafalir, M. Bumin Yenmez, and Muhammed A. Yildirim. 2013. Effective Affirmative Action in School Choice. Theoretical Economics 8, 2 (2013), 325–363.

Naoto Hamada, Chia-Ling Hsu, Ryoji Kurata, Takamasa Suzuki, Suguru Ueda, and Makoto Yokoo. 2017. Strategy-proof School Choice Mechanisms with Minimum Quotas and Initial Endowments. Artificial Intelligence 249 (2017), 47–71.

Naoto Hamada, Anisse Ismaili, Takamasa Suzuki, and Makoto Yokoo. 2017. Weighted Matching Markets with Budget Constraints. In Proceedings of the 16th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS-2017). 317–325.

Hadi Hosseini, Kate Larson, and Robin Cohen. 2015. On Manipulablity of Random Serial Dictatorship in Sequential Matching with Dynamic Preferences. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-2015). 4168–4169.

Chien-Chung Huang. 2007. Two's Company, Three's a Crowd: Stable Family and Threesome Roommates Problems. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA-2007). 558–569.

Yuichiro Kamada and Fuhito Kojima. 2015. Efficient Matching under Distributional Constraints: Theory and Applications. American Economic Review 105, 1 (2015), 67–99.

Yasushi Kawase and Atsushi Iwasaki. 2017. Near-Feasible Stable Matchings with Budget Constraints. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-2017). 242–248.

Fuhito Kojima. 2012. School Choice: Impossibilities for Affirmative Action. Games and Economic Behavior 75, 2 (2012), 685–693.

Fuhito Kojima, Akihisa Tamura, and Makoto Yokoo. 2018. Designing Matching Mechanisms Under Constraints: An Approach from Discrete Convex Analysis. Journal of Economic Theory 176 (2018), 803–833.

Bernhard Korte and Jens Vygen. 2018. Combinatorial Optimization: Theory and Algorithms. Springer.

Ryoji Kurata, Naoto Hamada, Atsushi Iwasaki, and Makoto Yokoo. 2017. Controlled School Choice with Soft Bounds and Overlapping Types. Journal of Artificial Intelligence Research 58 (2017), 153–184.

Tyler Lu and Craig Boutilier. 2014. Effective Sampling and Learning for Mallows Models with Pairwise-Preference Data. Journal of Machine Learning Research 15 (2014), 3963–4009.

Cheng Ng and Daniel S. Hirschberg. 1991. Three-Dimensional Stable Matching Problems. SIAM Journal on Discrete Mathematics 4, 2 (1991), 245–252.

Yasunori Okumura. 2018. School Choice with General Constraints: A Market Design Approach for the Nursery School Waiting List Problem in Japan. The Japanese Economic Review (2018).

Sofiat Olaosebikan and David Manlove. 2018. Super-Stability in the Student-Project Allocation Problem with Ties. In Proceedings of the 12th Annual International Conference on Combinatorial Optimization and Applications (COCOA-18). 357–371.

Alvin E. Roth and Marilda A. Oliveira Sotomayor. 1990. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis (Econometric Society Monographs). Cambridge University Press.

Tayfun Sonmez. 2013. Bidding for Army Career Specialties: Improving the ROTC Branching Mechanism. Journal of Political Economy 121, 1 (2013), 186–219.

Tayfun Sonmez and Tobias B. Switzer. 2013. Matching with (Branch-of-Choice) Contracts at the United States Military Academy. Econometrica 81, 2 (2013), 451–488.

Jack D. Tubbs. 1992. Distance Based Binary Matching. In Computing Science and Statistics. Springer, 548–550.