Serial dictatorship algorithms for assigning students to academic tracks

Abstract

Object. Serial dictatorship algorithms are allocation mechanisms where agents sequentially, in a predetermined order, select their most preferred available. These algorithms are studied within the problem of allocating students to academic tracks.
Purpose. This article investigates serial dictatorship algorithms for assigning students to academic tracks in universities, where students sequentially choose their most preferred available slots in academic tracks based on their academic performance (GPA) ranking.
Methodology. We proposed two algorithms that use dynamic programming methods, along with a greedy algorithm that offers greater efficiency in terms of time complexity.
Results. The algorithms were tested using real data from Saint Petersburg State University of Economics (UNECON) for student allocation to academic tracks in the "Economics" program, alongside large-scale computations on synthetic data. We analyzed the relationship between correlation patterns in student preferences for academic tracks and the number of envy conflicts for the described algorithms.
Conclusions. The developed algorithms expand the toolkit available to academic administrators, enabling the use of not only integer programming methods (currently employed at UNECON) but also serial dictatorship algorithms. The proposed algorithms are efficient (pseudopolynomial or polynomial) in terms of computational complexity. With strongly "decorrelated" preferences (90%), the proportion of envy conflicts does not exceed 30%.