DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2025.32

Fair Rent Division: New Budget and Rent Constraints

Authors: Rohith Reddy Gangam, Shayan Taherijam, and Vijay V. Vazirani

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract

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.

Cite as

Rohith Reddy Gangam, Shayan Taherijam, and Vijay V. Vazirani. Fair Rent Division: New Budget and Rent Constraints. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gangam_et_al:LIPIcs.FSTTCS.2025.32,
  author =	{Gangam, Rohith Reddy and Taherijam, Shayan and Vazirani, Vijay V.},
  title =	{{Fair Rent Division: New Budget and Rent Constraints}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{32:1--32:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.32},
  URN =		{urn:nbn:de:0030-drops-251136},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.32},
  annote =	{Keywords: Rent Division, Envy‑Free, Fair Division}
}

Search Results

Documents authored by Taherijam, Shayan

Fair Rent Division: New Budget and Rent Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message