Abstract
We study markets with a set of students on one side and a set of colleges on the other side. A student and a college can be linked by a weighted contract which 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 a group of students has an incentive to deviate. We find that a coalitionally stable matching is not guaranteed to exist, checking the coalitional stability for a given matching is coNP-complete, and the decision problem to find whether a coalitionally stable matching exists in a given market, is NP^NP-complete (that is Sigma_2^P-complete).Time
2016-12-21 13:00 ~ 13:45Speaker
Anisse Ismaili, Kyushu UniversityRoom
Room 102, No.100 Wudong Road, School of Information Management & Engineering, Shanghai University of Finance & Economics
