Strategyproof Mechanism for Two-Sided Matching with Resource Allocation

Kwei guu Liu, Kentaro Yahiro, Makoto Yokoo

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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. In this problem, students and indivisible resources are many-to-one matched 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 (a resource allocation problem), and (2) students are matched to projects based on the capacities determined in the previous problem (a matching problem). Although both problems are well-understood, if the expectations used in the first are incorrect, we obtain a sub-optimal outcome. Thus, this problem should be solved as a whole without dividing it into two parts. We show that no strategyproof mechanism satisfies fairness and weak efficiency requirements. Given this impossibility result, we develop a new class of strategyproof mechanisms called Sample and Deferred Acceptance (SDA), which satisfies several properties on fairness and efficiency. We experimentally compare several SDA instances as well as existing mechanisms, and show that an SDA instance strikes a good balance of fairness and efficiency when students are divided into different types according to their preferences.

Original languageEnglish
Article number103855
JournalArtificial Intelligence
Volume316
DOIs
Publication statusPublished - Mar 2023

All Science Journal Classification (ASJC) codes

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Strategyproof Mechanism for Two-Sided Matching with Resource Allocation'. Together they form a unique fingerprint.

Cite this