Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2409.14600 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913513063055360 |
|---|---|
| author | Huang, Yanqing Kitch, Madeline Melas-Kyriazi, Natalie |
| author_facet | Huang, Yanqing Kitch, Madeline Melas-Kyriazi, Natalie |
| contents | How can one assign roommates and rooms when tenants have preferences for both where and with whom they live? In this setting, the usual notions of envy-freeness and maximizing social welfare may not hold; the roommate rent-division problem is assumed to be NP-hard, and even when welfare is maximized, an envy-free price vector may not exist. We first construct a novel greedy algorithm with bipartite matching before exploiting the connection between social welfare maximization and the maximum weighted independent set (MWIS) problem to construct a polynomial-time algorithm that gives a $\frac{3}{4}+\varepsilon$-approximation of maximum social welfare. Further, we present an integer program to find a room envy-free price vector that minimizes envy between any two tenants. We show empirically that a MWIS algorithm returns the optimal allocation in polynomial time and conjecture that this problem, at the forefront of computer science research, may have an exact polynomial algorithm solution. This study not only advances the theoretical framework for roommate rent division but also offers practical algorithmic solutions that can be implemented in real-world applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14600 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Rent Division with Picky Roommates Huang, Yanqing Kitch, Madeline Melas-Kyriazi, Natalie Computer Science and Game Theory How can one assign roommates and rooms when tenants have preferences for both where and with whom they live? In this setting, the usual notions of envy-freeness and maximizing social welfare may not hold; the roommate rent-division problem is assumed to be NP-hard, and even when welfare is maximized, an envy-free price vector may not exist. We first construct a novel greedy algorithm with bipartite matching before exploiting the connection between social welfare maximization and the maximum weighted independent set (MWIS) problem to construct a polynomial-time algorithm that gives a $\frac{3}{4}+\varepsilon$-approximation of maximum social welfare. Further, we present an integer program to find a room envy-free price vector that minimizes envy between any two tenants. We show empirically that a MWIS algorithm returns the optimal allocation in polynomial time and conjecture that this problem, at the forefront of computer science research, may have an exact polynomial algorithm solution. This study not only advances the theoretical framework for roommate rent division but also offers practical algorithmic solutions that can be implemented in real-world applications. |
| title | Rent Division with Picky Roommates |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2409.14600 |