Weighted Matching Markets with Budget ConstraintsIsmaili, A., Hamada, N., Zhang, Y., Suzuki, T. & Yokoo, M., 24-Jul-2019, In : Journal of artificial intelligence research. 65, p. 393-421 29 p.
Research output: Contribution to journal › Article › Academic › peer-review
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.
|Number of pages||29|
|Journal||Journal of artificial intelligence research|
|Publication status||Published - 24-Jul-2019|
- SCHOOL CHOICE, COLLEGE ADMISSIONS, STABILITY, CONTRACTS, EFFICIENCY, BOUNDS