2014/03/04 by Augustine Kwanashie, Kwanashie, Augustine, Robert W. Irving +5
Decision Sciences · Economics, Econometrics and Finance · Computer Science · #Auction Theory and Applications #Game Theory and Voting Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1403.0751
In the Student / Project Allocation problem (SPA) we seek to assign students\nto individual or group projects offered by lecturers. Students provide a list\nof projects they find acceptable in order of preference. Each student can be\nassigned to at most one project and there are constraints on the maximum number\nof students that can be assigned to each project and lecturer. We seek\nmatchings of students to projects that are optimal with respect to profile,\nwhich is a vector whose rth component indicates how many students have their\nrth-choice project. We present an efficient algorithm for finding a greedy\nmaximum matching in the SPA context - this is a maximum matching whose profile\nis lexicographically maximum. We then show how to adapt this algorithm to find\na generous maximum matching - this is a matching whose reverse profile is\nlexicographically minimum. Our algorithms involve finding optimal flows in\nnetworks. We demonstrate how this approach can allow for additional\nconstraints, such as lecturer lower quotas, to be handled flexibly. Finally we\npresent results obtained from an empirical evaluation of the algorithms.\n