Weighted matching markets with budget constraints

Anisse Ismaili, Naoto Hamada, Yuzhe Zhang, Takamasa Suzuki, Makoto Yokoo

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


We investigate markets with a set of students on one side and a set of colleges on the other. A student and college can be linked by a weighted contract that defines the student’s wage, while a college’s budget for hiring students is limited. Stability is a crucial requirement for matching mechanisms to be applied in the real world. A standard stability requirement is coalitional stability, i.e., no pair of a college and group of students has any incentive to deviate. We find that a coalitionally stable matching is not guaranteed to exist, verifying the coalitional stability for a given matching is coNP-complete, and the problem of finding whether a coalitionally stable matching exists in a given market, is ΣP2 -complete: NPNP-complete. Other negative results also hold when blocking coalitions contain at most two students and one college. Given these computational hardness results, we pursue a weaker stability requirement called pairwise stability, where no pair of a college and single student has an incentive to deviate. Unfortunately, a pairwise stable matching is not guaranteed to exist either. Thus, we consider a restricted market called a typed weighted market, in which students are partitioned into types that induce their possible wages. We then design a strategy-proof and Pareto efficient mechanism that works in polynomial-time for computing a pairwise stable matching in typed weighted markets.

Original languageEnglish
Pages (from-to)393-421
Number of pages29
JournalJournal of Artificial Intelligence Research
Publication statusPublished - 2019

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence


Dive into the research topics of 'Weighted matching markets with budget constraints'. Together they form a unique fingerprint.

Cite this