Publication

Weighted Matching Markets with Budget Constraints

Ismaili, A., Hamada, N., Zhang, Y., Suzuki, T. & Yokoo, M., 2019, In : Journal of artificial intelligence research. 65, p. 393-421 29 p.

Research output: Contribution to journalArticleAcademicpeer-review

Copy link to clipboard

Documents

  • Weighted Matching Markets with Budget Constraints

    Final publisher's version, 431 KB, PDF document

    Request copy

DOI

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

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 Sigma(P)(2)-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
Volume65
Publication statusPublished - 2019

    Keywords

  • SCHOOL CHOICE, COLLEGE ADMISSIONS, STABILITY, CONTRACTS, EFFICIENCY, BOUNDS

View graph of relations

ID: 102600703