![]() ![]() A many-to-one matching from to is a function such that for any distinct and in, we have. The solution is a matching between colleges and students, which is formalized as follows:ĭefinition 2.1 (Many-to-One Matching). Additionally, each college has a capacity of students it can admit. Each college also has a strict, transitive preference relation over. ![]() By convention, if an agent prefers to another agent, then prefers being unmatched than to being matched with. Each student has a strict, transitive preference relation over the set. The College Admissions problem starts with two disjoint sets: a set of students and a set of colleges. I assume familiarity with the Stable Marriage Problem. This is also more realistic of how firms hire workers. The College Admissions problem provides a model allowing for a college to be matched with multiple students, but students may only be matched with one college. ![]() To this end, we extend the notion of a one-to-one matching to allow for a many-to-one matching. More realistically, a firm hires many desirable employees, and a college admits many students. The Stable-Marriage problem is a one-to-one matching problem in which each proposer may be matched with at most single acceptor, and vice-versa: e.g., one man and one woman, one firm and one employee, or one student and one school. The College Admissions problem extends the Stable Marriage problem by allowing for a many-to-one matching. This blog entry introduces the College Admissions problem, as well as several algorithmic solutions.
0 Comments
Leave a Reply. |