Abstract
The standard approach to fair rent division assumes that agents have quasi-linear utilities and seeks allocations that are envy-free. While this framework underlies widely used algorithms, it fails to account for individual budget constraints, potentially assigning agents to rooms they cannot afford. This paper introduces a polynomial-time algorithm that incorporates budget constraints directly into the input. The algorithm determines the existence of budget-constrained envy-free allocations and computes a solution that optimizes the maximin utility—maximizing the minimum utility of any agent. We demonstrate that this solution is unique in terms of utilities and satisfies desirable properties such as equitability, providing a robust theoretical and practical foundation for real-world rent division.
Introduction
The classic rent division problem involves assigning $n$ roommates to $n$ rooms and partitioning the total rent such that the resulting allocation is envy-free: no agent prefers another's room at its assigned price. While mathematicians have established that envy-free solutions always exist under the assumption of quasi-linear utilities, these models typically assume agents have unlimited financial resources. In practice, as evidenced by user feedback on platforms like Spliddit.org, "fair" prices often exceed an individual's maximum budget, rendering the theoretical solution unusable.
This research addresses the gap between fair division theory and financial reality by introducing budget constraints into the envy-free framework. This addition introduces two primary challenges: first, an envy-free solution is no longer guaranteed to exist; and second, the computational complexity increases because the choice of room assignment (the matching) becomes coupled with the price feasibility in ways not seen in the standard model.
Methodology
The authors propose a new algorithmic framework centered on the maximin solution, which seeks to maximize the utility of the least-happy roommate. The framework consists of two primary stages:
1. The Component Solver (Algorithm 1)
Utilizing graph theory, the authors represent agent preferences through Weak Envy Graphs. They prove that the set of strongly connected components in this graph remains invariant across different fair allocations. Algorithm 1 handles these components by iteratively adjusting prices and "reshuffling" room assignments along cycles in the envy graph. This process determines the maximum possible rent that can be charged within a component while strictly adhering to individual budget limits.
2. The Global Optimizer (Algorithm 2)
This "master" algorithm decomposes the set of roommates into components, applies the Component Solver to each, and then employs Linear Programming (LP) to integrate these local solutions. The LP ensures that the final global allocation is envy-free, budget-respecting, and optimizes the overall maximin objective. Crucially, the authors prove that this entire process runs in polynomial time, ensuring its viability for large-scale applications.
Key Insights and Theoretical Results
The Shift from Efficiency to Feasibility
In standard rent division, any "efficient" assignment (one that maximizes the sum of values) can be paired with envy-free prices. The authors demonstrate that with budget constraints, this property fails. A globally optimal solution may require a "sub-optimal" room assignment to ensure that prices remain within everyone's financial reach.
Uniqueness and Equitability
Despite the added complexity of budgets, the research proves that the maximin solution results in a unique set of utilities for all agents. Furthermore, the authors uncover a link between maximin and equitability: the solution that maximizes the minimum utility also tends to minimize the gap between the most and least happy agents. This suggests that the algorithm naturally balances individual welfare with group fairness.
Robustness to Failure
In instances where no budget-constrained envy-free allocation exists (e.g., when the total rent exceeds the combined budgets of the roommates), the algorithm is designed to find an allocation that minimizes the maximum budget violation. This ensures that if a budget must be exceeded, the financial burden is distributed to minimize the impact on any single individual.
Practical Considerations and Limitations
While the algorithm provides a significant step forward, several areas for future work remain:
- Incentive Compatibility: Like many fair-division mechanisms, the algorithm is theoretically manipulable if agents misreport their budgets or room valuations. However, the authors suggest the complexity of successful manipulation serves as a practical deterrent.
- Preference Elicitation: The model requires users to provide values for every room and a strict budget. Future iterations could explore simplified reporting methods to reduce the cognitive load on users.
- Utility Modeling: The current model assumes utility is a linear function ($Value - Price$). Future research could incorporate non-linear utilities to better reflect the increasing "pain" of expenditures as an agent approaches their budget limit.
Conclusion
By integrating budget constraints into the envy-free rent division problem, this work provides a more realistic and compassionate approach to fair division. The polynomial-time algorithm offers a practical tool for platforms like Spliddit, ensuring that "fairness" is defined not just by the absence of envy, but by the reality of what participants can actually afford.
Summary updated