Алгоритмы серийной диктатуры распределения студентов по учебным профилям в университете

Аннотация

Предмет. Алгоритмы серийной диктатуры – механизмы распределения, в котором агенты последовательно, в заранее определённом порядке, выбирают наиболее предпочтительные для себя варианты. Данные алгоритмы исследуются в рамках задачи распределения студентов по учебным профилям.
Цель. Статья посвящена алгоритмам серийной диктатуры поиска распределения студентов по учебным профилям в университете, где студенты в порядке своей успеваемости выбирают наиболее предпочтительные для себя места в учебных профилях среди оставшихся.
Метод. Предлагаются два точных алгоритма, использующие методы динамического программирования, а также жадный алгоритм, являющийся более эффективным в терминах временной сложности.
Результаты. Проведена апробация на реальных данных СПбГЭУ в рамках распределения студентов по учебным профилям направления «Экономика», а также выполнены массовые расчеты на синтетических данных. Проведен анализ связи скоррелированности предпочтений учебных профилей по студентам с количеством конфликтов зависти для описанных алгоритмов.
Выводы. Разработанные алгоритмы расширяют инструментарий для организаторов учебного процесса, позволяя использовать не только методы целочисленного программирования (которые на данный момент используются в СПбГЭУ), но и алгоритмы серийной диктатуры. Предложенные алгоритмы являются эффективными (псевдополиномиальными или полиномиальными) в терминах вычислительной сложности. При наличии сильно «расскоррелированных» предпочтений (90%) профилей, доля конфликтов зависти не превышает 30%.