{"ID":2880835,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.14194","arxiv_id":"2508.14194","title":"Algorithms for Stable Roommate with Externalities","abstract":"In the roommate matching model, given a set of 2n agents and n rooms, we find an assignment of a pair of agents to a room. Although the roommate matching problem is well studied, the study of the model when agents have preference over both rooms and roommates was recently initiated by Chan et al. [11]. We study two types of stable roommate assignments, namely, 4-person stable (4PS) and 2-person stable (2PS) in conjunction with efficiency and strategy-proofness. We design a simple serial dictatorship based algorithm for finding a 4PS assignment that is Pareto optimal and strategy-proof. However, the serial dictatorship algorithm is far from being 2PS. Next, we study top trading cycle (TTC) based algorithms. We show that variations of TTC cannot be strategy-proof or PO. Finally, as Chan et al. (2016) showed that deciding the existence of 2PS assignment is NP-complete, we identify preference structures where a 2PS assignment can be found in polynomial time.","short_abstract":"In the roommate matching model, given a set of 2n agents and n rooms, we find an assignment of a pair of agents to a room. Although the roommate matching problem is well studied, the study of the model when agents have preference over both rooms and roommates was recently initiated by Chan et al. [11]. We study two typ...","url_abs":"https://arxiv.org/abs/2508.14194","url_pdf":"https://arxiv.org/pdf/2508.14194v1","authors":"[\"Jing Leng\",\"Sanjukta Roy\"]","published":"2025-08-19T18:39:07Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}