Game Theoretic Analysis for Two-Sided Matching with Resource Allocation

K. Yahiro, M. Yokoo
AAMAS 2020
Abstract
In this work, we consider a student-project-resource matching-allocation problem, where students have preferences over projects and the projects have preferences over students. Although students are many-to-one matched to projects, indivisible resources are many-to-one allocated to projects whose capacities are endogenously determined by the resources allocated to them. Traditionally, this problem is decomposed into two separate problems: (1) resources are allocated to projects based on 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, if the expectations used in the first are incorrect, we obtain a suboptimal outcome. Thus, this problem must be solved as a whole without dividing it in two parts. We show that no strategyproof mechanism satisfies fairness (i.e., no student has justified envy) and weak efficiency requirements on students' welfare. Given this impossibility result, we develop a new strategyproof mechanism that strikes a good balance between fairness and efficiency and assess it by experiments.

Experiments:

Election type Culture Candidates Voters Instances Parameters
Ordinal Impartial Culture {10} {200} None None
Ordinal Impartial Culture {200} {10} None None
Ordinal Mallows {10} {200} None [0.1,0.7]
Ordinal Mallows {200} {10} None [0.1,0.7]