Research map / Learning theory and algorithms / Submodular and game algorithms
Multi-Apartment Rent Division
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Generalizes rent division to multiple apartments and proposes negotiated envy-freeness (always exists, optimizable in polynomial time) and universal envy-freeness (studied probabilistically).
Problem
Fair rent division when a group of roommates must jointly choose among multiple apartments and then assign rooms and rents within the chosen one; existing envy-free notions consider only a single apartment.
Approach
Defines negotiated envy-freeness: start from an individually envy-free price matrix in each apartment, then reallocate rent across apartments via zero-sum negotiations between players until a consensus apartment is reached; also defines universal envy-freeness and studies its existence under random i.i.d. valuations.
Key results
- Negotiated envy-free solutions always exist and can be computed in polynomial time (constructive proof).
- Maximin and equitability objectives can be optimized over negotiated envy-free solutions in polynomial time via linear programming.
- For discrete i.i.d. valuations, Pr(universal envy-free solution exists) approaches 1 as the number of apartments grows; for continuous distributions it is bounded away from 0 and 1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use negotiated envy-freeness instead of universal envy-freeness | Multi-apartment rent division · Every multi-apartment rent division instance | existence | Helped |
| Optimize a linear objective subject to negotiated envy-freeness | Multi-apartment rent division · Multi-apartment rent division instances | computation time | Helped |
| Increase the number of apartments | Universal envy-freeness with values drawn from a finite discrete distribution · Random instances with fixed n | probability of existence: \Pr\left(E_m\right) \xrightarrow[m \to \infty]{} 1 | Helped |
| Increase the number of apartments | Universal envy-freeness with values drawn from a continuous distribution · Random instances with fixed n | probability of existence: \Pr\left(E_m\right) \ge p_0(n); \Pr\left(E_m\right) \le p_1(n) | Mixed |
| Add apartments one at a time and check for universal envy-freeness before each addition | Universal envy-freeness with values drawn from a continuous distribution · Sequential apartment search | probability of eventually finding a solution: = 1 | Helped |
| Require universal envy-freeness rather than negotiated envy-freeness | Multi-apartment rent division · Some multi-apartment instances | existence | Hurt |
Surprising findings
- Universal envy-free solutions do not always exist, even when all players have equal total value for each apartment.
- For continuous distributions, the probability of universal envy-freeness does not converge to 0 or 1 as apartments grow, though sequentially adding apartments yields existence with probability 1.
Limitations
- Envy-freeness is not strategyproof and the quasi-linear utility assumption is strong.
- Negotiated envy-freeness is harder to explain as a fairness notion and envy may remain in the chosen apartment.
- Universal envy-free solutions may not exist.
Experimental setup
Builds on: envy-freeness rent division (Gal et al.) maximin envy-free rent division (Gal et al.) second welfare theorem
Closest papers by meaning
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.87)
- Envy-Free House Allocation under Uncertain Preferences (AAAI 2024 · similarity 0.87)
- Strategyproof Matching of Roommates and Rooms (AAAI 2025 · similarity 0.86)
- Towards Optimal Subsidy Bounds for Envy-Freeable Allocations (AAAI 2024 · similarity 0.86)
- Reachability of Fair Allocations via Sequential Exchanges (AAAI 2024 · similarity 0.86)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.