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.

Bonifaci, V., Rivera Dallorto, H. (2025). Egalitarian roommate allocations: Complexity and stability. THEORETICAL COMPUTER SCIENCE, 1026(115009) [10.1016/j.tcs.2024.115009].

Egalitarian roommate allocations: Complexity and stability

Bonifaci, Vincenzo
;
Rivera Dallorto, Helena
2025-01-01

Abstract

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.
2025
Bonifaci, V., Rivera Dallorto, H. (2025). Egalitarian roommate allocations: Complexity and stability. THEORETICAL COMPUTER SCIENCE, 1026(115009) [10.1016/j.tcs.2024.115009].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/493836
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact