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

Екатерина Валерьевна Глазунова; Иван Алексеевич Зелин

Екатерина Валерьевна Глазунова Санкт-Петербургский государственный экономический университет https://orcid.org/0000-0001-9936-8961
Иван Алексеевич Зелин Санкт-Петербургский государственный экономический университет https://orcid.org/0009-0009-2150-0219

Ключевые слова: двусторонние рынки, динамическое программирование, жадные алгоритмы

Аннотация

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

Биографии авторов

Екатерина Валерьевна Глазунова, Санкт-Петербургский государственный экономический университет

ассистент

Иван Алексеевич Зелин, Санкт-Петербургский государственный экономический университет

студент

Литература

1. Васильев, Ю. М., Глазунова, Е. В., & Фридман, Г. М. (2024). Умный университет: справедливое распределение студентов по учебным профилям. Вестник ВГУ. Серия: Экономика и управление, (1), 16-24. [Vasiliev, Yu. M., Glazunova, E. V., & Friedman, G. M. (2024). “Smart University” Project: fair matching of students to academic trajectories. Proceedings of Voronezh State University. Series: Economics and Management, (1), 16–24. (In Russian).] DOI: 10.17308/econ.2024.1/11838
2. Дроздов, С. Н. (2000). Комбинаторные задачи и элементы теории вычислительной сложности. Таганрог: Изд-во ТРТУ. [Drozdov, S. N. (2000). Combinatorial Problems and Elements of Computational Complexity Theory. Taganrog: TRTU Publishing House. (In Russian).]
3. Окулов, С. М. (2017). Динамическое программирование. Москва: БИНОМ. Лаборатория знаний. [Okulov, S. M. (2017). Dynamic Programming. Moscow: BINOM. Laboratory of Knowledge Publishing House. (In Russian).]
4. Ágoston, K. C., Biró, P., & McBride, I. (2016). Integer programming methods for special college admissions problems. Journal of Combinatorial Optimization, (32), 1371–1399. DOI: 10.1007/s10878-016-0085-x
5. Biró, P., Fleiner, T., Irving, R. W., & Manlove, D. F. (2010). The College Admissions problem with lower and common quotas. Theoretical Computer Science, 411(34–36), 3136–3153. DOI: 10.1016/j.tcs.2010.05.005
6. Boehmer, N., & Heeger, K. (2022). A Fine-Grained View on Stable Many-To-One Matching Problems with Lower and Upper Quotas. ACM Transactions on Economics and Computation, 10(2), 1-53. DOI: 10.1145/354660
7. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. Cambridge: The MIT Press.
8. Fragiadakis, D., Iwasaki, A., Troyan, P., Ueda, S., & Yokoo, M. (2015). Strategyproof matching with minimum quotas. ACM Transactions on Economics and Computation, 4(1), 1-40. DOI: 10.1145/2841226
9. Gabow, H. N. (1983). An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems. Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 448-456. DOI: 10.1145/800061.808776
10. Gale, D., & Shapley, L. S. (2013). College admissions and the stability of marriage. American Mathematical Monthly, 120(5), 386–391. DOI: 10.4169/amer.math.monthly.120.05.386
11. Hamada, K., Iwama, K., & Miyazaki, S. (2016). The hospitals/residents problem with lower quotas. Algorithmica, 74, 440-465. DOI: 10.1007/s00453-014-9951-z
12. Hamada, K., Iwama, K., & Miyazaki, S. (2011). The Hospitals/Residents Problem with Quota Lower Bounds. In: Demetrescu, C., & Halldórsson, M.M. (eds.). Lecture Notes in Computer Science, 6942. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-23719-5_16
13. Hamada, N., Hsu, C. L., Kurata, R., Suzuki, T., Ueda, S., & Yokoo, M. (2017). Strategy-proof school choice mechanisms with minimum quotas and initial endowments. Artificial Intelligence, (249), 47–71. DOI:10.1016/j.artint.2017.04.006
14. Manlove, D. (2013). Algorithmics of Matching Under Preferences. World Scientific. DOI:10.1142/8591
15. Powell, W. B. (1955). Approximate dynamic programming: solving the curses of dimensionality. Princeton University. The Department of Operations Research and Financial Engineering Princeton.
16. Rossum, G. V. (1995). Python tutorial, Technical Report CS-R9526. Amsterdam: Centrum voor Wiskunde en Informatica (CWI).
17. Roth, A. E., & Sotomayor, M. A. O. (1990). Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press.
18. Satterthwaite, M. A., & Sonnenschein, H. (1981). Strategy-Proof Allocation Mechanisms at Differentiable Points. The Review of Economic Studies, 48(4), 587–597. DOI:10.2307/2297198540
19. Shimada, N., Yamazaki, N., & Takano, Y. (2020). Multi-objective Optimization Models for Many-to-one Matching Problems. Journal of Information Processing, (28), 406-412. DOI: 10.2197/ipsjjip.28.406