2019/11/21 by Sofiat Olaosebikan, Olaosebikan, Sofiat, David F. Manlove +1
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1911.10262
openalex publication_date 2019/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a variant of the Student-Project Allocation problem with lecturer\npreferences over Students where ties are allowed in the preference lists of\nstudents and lecturers (SPA-ST). We investigate the concept of strong stability\nin this context. Informally, a matching is strongly stable if there is no\nstudent and lecturer l such that if they decide to form a private arrangement\noutside of the matching via one of l's proposed projects, then neither party\nwould be worse off and at least one of them would strictly improve. We describe\nthe first polynomial-time algorithm to find a strongly stable matching or to\nreport that no such matching exists, given an instance of SPA-ST. Our algorithm\nruns in O(m2) time, where m is the total length of the students'\npreference lists.\n