Egalitarian roommate allocations: Complexity and stability

We study two roommate assignment problems, called Ordinal Roommate Allocation and Cardinal Roommate Allocation, where students have preferences over roommates, rooms have varying capacities, and the goal is to maximize the minimum payoff of the students (under two distinct notions of payoff). Both problems are NP-hard when room sizes are unrestricted. In contrast, the Ordinal Roommate Allocation problem becomes tractable when the maximum room capacity is fixed, while the Cardinal Roommate Allocation problem remains NP-hard even with bounded room capacity and number of preferences. We then analyze the problems through the lens of stability, considering envy-freeness and a weaker notion we call swap-resistance. Not all instances guarantee an envy-free outcome, and it is shown to be NP-hard to determine which ones do. However, swap-resistance is always achievable using an efficient algorithm. We discuss connections and distinctions between our work and existing research about utilitarian matchings and stable roommate problems.