In the classic College Admissions problem, there are $m$ colleges and $n$ students. The colleges have a preference over the students and the students have preferences over the colleges. The students do not care who are the other students admitted to the college. The Gale-Shapley algorithm guarantees a stable matching in this case.

Now suppose I introduce a form of externality where a student's utility depends not only on the college he/she is admitted to, but also on who are the other students who are admitted to that college. What is the definition of stability in this case? Does a stable allocation always exist here? How to find one if it does?

  • $\begingroup$ It is not even clear how you get stable bids. Suppose there is a good college with 2 places and a bad one with 1 place, and the allocation $(A,B | C)$ is rated 2 by A, 1 by B and 0 by C, while $(A,C | B)$ is rated 1 by A, 0 by B and 2 by C, and $(B,C | A)$ is rated 0 by A, 2 by B and 1 by C. Then no bid is stable: for example if A suggests the first then C will suggest to B that the third would make them both better off and then A will suggest the to C than the second ... $\endgroup$ – Henry Dec 8 '20 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.