Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2508.14194 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911111470645248 |
|---|---|
| author | Leng, Jing Roy, Sanjukta |
| author_facet | Leng, Jing Roy, Sanjukta |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_14194 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithms for Stable Roommate with Externalities Leng, Jing Roy, Sanjukta Computer Science and Game Theory 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. |
| title | Algorithms for Stable Roommate with Externalities |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2508.14194 |