Course Allocation with Friendships as an Asymmetric Distributed Constraint Optimization Problem
Ilya Khakhiashvili, Tal Grinshpoun, Lihi Dery · IEEE/WIC/ACM International Conference on Web Intelligence · 2021
Course allocation, i.e., the problem of assigning students to courses, is a difficult problem. Students value being assigned to the same course as their friends. We propose a model that considers not only the students’ preferences over courses but also their preferences over classmates. We formulate the problem as an asymmetric distributed constraint optimization problem. This solution has an additional interesting feature: it is solved in a distributed manner, thus removing the need to directly share private preferences with anyone. An extensive evaluation of our proposed model on real-world student preferences over courses shows that it obtains high utility for the students, while keeping the solution fair and observing courses’ seat capacity limitations. Our model is general and can be adapted to solve a variety of multi-allocation problems where it is required to consider friendships.