Fair Rent Division: New Budget and Rent Constraints
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909829061148672 |
|---|---|
| author | Gangam, Rohith Reddy Taherijam, Shayan Vazirani, Vijay V. |
| author_facet | Gangam, Rohith Reddy Taherijam, Shayan Vazirani, Vijay V. |
| contents | We study the classical rent division problem, where $n$ agents must allocate $n$ indivisible rooms and split a fixed total rent $R$. The goal is to compute an envy-free (EF) allocation, where no agent prefers another agent's room and rent to their own. This problem has been extensively studied under standard assumptions, where efficient algorithms for computing EF allocations are known.
We extend this framework by introducing two practically motivated constraints: (i) lower and upper bounds on room rents, and (ii) room-specific budget for agents. We develop efficient combinatorial algorithms that either compute a feasible EF allocation or certify infeasibility.
We further design algorithms to optimize over EF allocations using natural fairness objectives such as maximin utility, leximin utility, and minimum utility spread. Our approach unifies both constraint types within a single algorithmic framework, advancing the applicability of fair division methods in real-world platforms such as Spliddit. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05434 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fair Rent Division: New Budget and Rent Constraints Gangam, Rohith Reddy Taherijam, Shayan Vazirani, Vijay V. Computer Science and Game Theory Data Structures and Algorithms We study the classical rent division problem, where $n$ agents must allocate $n$ indivisible rooms and split a fixed total rent $R$. The goal is to compute an envy-free (EF) allocation, where no agent prefers another agent's room and rent to their own. This problem has been extensively studied under standard assumptions, where efficient algorithms for computing EF allocations are known. We extend this framework by introducing two practically motivated constraints: (i) lower and upper bounds on room rents, and (ii) room-specific budget for agents. We develop efficient combinatorial algorithms that either compute a feasible EF allocation or certify infeasibility. We further design algorithms to optimize over EF allocations using natural fairness objectives such as maximin utility, leximin utility, and minimum utility spread. Our approach unifies both constraint types within a single algorithmic framework, advancing the applicability of fair division methods in real-world platforms such as Spliddit. |
| title | Fair Rent Division: New Budget and Rent Constraints |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.05434 |