The Roommate Problem

You and two friends rent an apartment. The rooms are not equal: one is big and sunny, one is tiny, one gets the morning noise from the street. The rent is one number — say $3000 — and somehow you have to split it three ways. Charge equally and whoever got the closet feels robbed. Charge "by the square meter" and tastes still differ: maybe someone would gladly pay more for the quiet room.

The real question is sharper than "what's fair in dollars." It is: can we assign rooms and prices so that no roommate would rather have someone else's room-and-price deal? When that holds, the split is called envy-free — nobody envies anybody.

It sounds like the kind of thing that might be impossible to arrange. Astonishingly, under very mild assumptions it is always possible — and the proof comes not from economics but from a piece of combinatorial topology about coloring triangles.

Find the Fair Split

Three roommates, three rooms, total rent $3000. Each roommate secretly values the rooms differently (sliders below set how much each person would pay for each room). The solver searches for a price on each room so that, at those prices, every roommate's favorite room is a different one — that is an envy-free assignment.

<p class="hint">Three roommates split <b>$3000</b> over three unequal rooms. Each slider
sets how much a person would <i>happily pay</i> for a room (their private value). The
solver searches room prices so that, at those prices, every roommate's best deal is a
<b>different</b> room — an <b>envy-free</b> split. By Sperner's lemma one always exists.</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">Set values, then find a split.</div>
<div id="result" class="result"></div>
<div class="btns">
  <button id="find" type="button">Find a fair split</button>
  <button id="rand" type="button" class="ghost">Randomize values</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.grid { display: grid; grid-template-columns: auto repeat(3, 1fr); gap: .4rem .7rem; align-items: center; }
.h { font-weight: 700; color: #1d3557; font-size: .85rem; text-align: center; }
.name { font-weight: 700; color: #1d3557; font-size: .9rem; }
.vcell { display: flex; flex-direction: column; gap: 2px; }
.vcell input { width: 100%; }
.vcell span { font: 600 12px ui-monospace, monospace; color: #555; text-align: center; }
.status { font-size: 1rem; font-weight: 600; margin: .8rem 0 .3rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.result { display: grid; grid-template-columns: repeat(3, 1fr); gap: .5rem; margin: .3rem 0 .6rem; }
.card { border: 1px solid #cdd9e3; background: #e8eef3; border-radius: 8px; padding: .5rem; text-align: center; }
.card .who { font-weight: 700; color: #1d3557; }
.card .room { font-size: .85rem; color: #333; }
.card .price { font: 700 16px ui-monospace, monospace; color: #0a7d33; margin-top: 2px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Rent division: total rent T over 3 rooms, split among 3 roommates.
// value[i][j] = how much roommate i would pay for room j (their private worth).
// A price vector p (p0+p1+p2 = T) is ENVY-FREE if we can assign rooms so that each
// roommate's assigned room maximizes (value - price) for them — i.e. nobody prefers
// someone else's room-and-price. Sperner's lemma (Su, 1999) guarantees one exists.
const T = 3000;
const ROOMS = ['Sunny room', 'Tiny room', 'Street room'];
const NAMES = ['Alice', 'Bob', 'Carol'];
// Each person's value for each room (must roughly sum near T so prices stay sane).
let value = [
  [1500, 800, 900],
  [1100, 1200, 800],
  [1000, 900, 1300],
];

function buildGrid() {
  const g = document.getElementById('grid'); g.innerHTML = '';
  g.appendChild(cell('', 'h'));
  ROOMS.forEach(r => g.appendChild(cell(r, 'h')));
  for (let i = 0; i < 3; i++) {
    g.appendChild(cell(NAMES[i], 'name'));
    for (let j = 0; j < 3; j++) {
      const c = document.createElement('div'); c.className = 'vcell';
      const inp = document.createElement('input');
      inp.type = 'range'; inp.min = '200'; inp.max = '2000'; inp.step = '50';
      inp.value = value[i][j];
      const lab = document.createElement('span'); lab.textContent = '


Notice the asymmetry. Checking a proposed split is instant: at the given prices, ask each person which room they'd pick, and see whether the three choices are all different. Finding the split is the work — but unlike many puzzles on this site, a solution is guaranteed to exist. Move the sliders however you like and press Find a fair split: it never comes back empty-handed.

 + value[i][j];
      inp.addEventListener('input', () => { value[i][j] = +inp.value; lab.textContent = '


Notice the asymmetry. Checking a proposed split is instant: at the given prices, ask each person which room they'd pick, and see whether the three choices are all different. Finding the split is the work — but unlike many puzzles on this site, a solution is guaranteed to exist. Move the sliders however you like and press Find a fair split: it never comes back empty-handed.

 + inp.value;
        setStatus('Values changed — find a split.', ''); document.getElementById('result').innerHTML = ''; });
      c.appendChild(inp); c.appendChild(lab); g.appendChild(c);
    }
  }
}
function cell(t, cls) { const d = document.createElement('div'); d.className = cls; d.textContent = t; return d; }
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

// All 6 permutations of room assignment (perm[i] = room given to roommate i).
const PERMS = [[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]];

// Is assignment `perm` envy-free at prices p (using value matrix `val`)? Each roommate
// must (weakly) prefer their own room: val[i][perm[i]]-p[perm[i]] >= val[i][k]-p[k].
function envyFree(perm, p, val, tol) {
  tol = tol || 1e-9;
  for (let i = 0; i < 3; i++) {
    const mine = val[i][perm[i]] - p[perm[i]];
    for (let k = 0; k < 3; k++)
      if (val[i][k] - p[k] > mine + tol) return false;
  }
  return true;
}

// Normalize each person's values so their three numbers sum to the rent T. This is
// Su's "miserly tenant" hypothesis (a tenant's budget equals the rent), under which
// an envy-free split with non-negative prices is guaranteed to exist.
function normalized() {
  return value.map(row => { const s = row[0]+row[1]+row[2];
    return row.map(x => x / s * T); });
}

// Exact solver (no grid luck). Step 1: pick the welfare-MAXIMIZING assignment. Step 2:
// its envy-free prices satisfy difference constraints p[b]-p[a] >= val[i][b]-val[i][a]
// for the holder i of room a. LP duality guarantees no positive cycle, so a longest-path
// relaxation finds prices; shift them so they sum to T. This always succeeds.
function find() {
  const val = normalized();
  let perm = PERMS[0], bw = -Infinity;
  for (const pm of PERMS) { let w = 0; for (let i = 0; i < 3; i++) w += val[i][pm[i]];
    if (w > bw) { bw = w; perm = pm; } }
  const edges = [];
  for (let i = 0; i < 3; i++) { const a = perm[i];
    for (let b = 0; b < 3; b++) edges.push([a, b, val[i][b] - val[i][a]]); }
  let p = [0, 0, 0];
  for (let it = 0; it < 3; it++) for (const [a, b, w] of edges)
    if (p[a] + w > p[b]) p[b] = p[a] + w;
  const shift = (T - (p[0] + p[1] + p[2])) / 3;
  p = p.map(x => x + shift);
  // Round to whole dollars while keeping the sum exactly T (last room absorbs rounding).
  p = [Math.round(p[0]), Math.round(p[1]), 0];
  p[2] = T - p[0] - p[1];
  const best = { perm, p };
  // Whole-dollar rounding can leave a couple of dollars of slack; a $2 tolerance on a
  // $3000 rent is negligible and the float prices are exactly envy-free.
  if (!envyFree(perm, p, val, 2)) { setStatus('Rounding edge case — adjust a slider.', 'bad'); return; }
  render(best);
  setStatus('Found an envy-free split — everyone prefers their own room.', 'ok');
  console.log('Assignment', best.perm.map((r,i)=>fmt('%v%→%v2%', { v: NAMES[i], v2: ROOMS[r] })).join(', '),
              '| prices', best.p.map(x=>'


Notice the asymmetry. Checking a proposed split is instant: at the given prices, ask each person which room they'd pick, and see whether the three choices are all different. Finding the split is the work — but unlike many puzzles on this site, a solution is guaranteed to exist. Move the sliders however you like and press Find a fair split: it never comes back empty-handed.

+x).join(' '), '| sum', best.p.reduce((s,x)=>s+x,0));
}
function render(best) {
  const res = document.getElementById('result'); res.innerHTML = '';
  for (let i = 0; i < 3; i++) {
    const room = best.perm[i];
    const d = document.createElement('div'); d.className = 'card';
    d.innerHTML = '<div class="who">' + NAMES[i] + '</div><div class="room">' + ROOMS[room] +
      '</div><div class="price">


Notice the asymmetry. Checking a proposed split is instant: at the given prices, ask each person which room they'd pick, and see whether the three choices are all different. Finding the split is the work — but unlike many puzzles on this site, a solution is guaranteed to exist. Move the sliders however you like and press Find a fair split: it never comes back empty-handed.

 + best.p[room] + '</div>';
    res.appendChild(d);
  }
}
function randomize() {
  for (let i = 0; i < 3; i++) for (let j = 0; j < 3; j++)
    value[i][j] = 200 + Math.round((Math.random() * 36)) * 50; // 200..2000 step 50
  buildGrid(); document.getElementById('result').innerHTML = '';
  setStatus('New random values — find a split.', '');
}
document.getElementById('find').addEventListener('click', find);
document.getElementById('rand').addEventListener('click', randomize);
buildGrid();
Result
Console

Notice the asymmetry. Checking a proposed split is instant: at the given prices, ask each person which room they'd pick, and see whether the three choices are all different. Finding the split is the work — but unlike many puzzles on this site, a solution is guaranteed to exist. Move the sliders however you like and press Find a fair split: it never comes back empty-handed.

The Real Complexity

What makes rent division remarkable is not that it is hard — it is that it is provably solvable, every single time.

  • The status is settled. In 1999 the mathematician Francis Su published "Rental Harmony: Sperner's Lemma in Fair Division," proving that under mild conditions an envy-free rent split always exists. This is a solved problem with a constructive guarantee, not an open question.
  • The engine is Sperner's lemma (Emanuel Sperner, 1928). Picture all the ways to split $3000 among three rooms as points of a triangle. Triangulate it finely, and label each corner by which room that roommate would choose at those prices. Sperner's lemma guarantees at least one tiny sub-triangle whose three corners carry all three different labels.
  • A fully-labeled triangle is an (almost) envy-free split. Its three corners are three nearly-identical price vectors at which the three roommates each prefer a different room — so you can hand each person their favorite. Shrink the triangulation and the approximation becomes exact in the limit.
  • Mild assumptions only. Each person must always be willing to take some room if it is free (no infinitely-fussy tenants), and preferences must vary continuously with price. That's it.

So rent division sits in the friendly company of problems with existence theorems — like the stable matching that always pairs up couples, or the Nash equilibrium every finite game must have. The math doesn't just hope a fair split exists; it hands you the recipe to find it.

Where It Matters

"Divide this fairly among people who want different things" is everywhere, and the rent problem is its clearest case:

  • Real apartments. The New York Times built a public rent-division calculator on exactly this theorem; the academic site Spliddit offers it to anyone with squabbling roommates.
  • Inheritances and divorce. Splitting a house, a car, and a record collection between heirs is the same shape: indivisible items plus a money side-payment, made envy-free.
  • Chores and shared duties. Replace "rent" with "hours of unpleasant work" and the math flips into dividing burdens so nobody feels overloaded.
  • Computing resources. Cloud schedulers and shared clusters borrow fair-division ideas to split CPU, memory and bandwidth so no tenant envies another's allocation.

Understand the rent split and you've met fair division — the field that turns "that's not fair!" from a complaint into something you can actually compute and prove.

Conclusion

Rent division hides a quietly beautiful fact: the loudest household argument — who pays what for which room — has a mathematically guaranteed peaceful answer. Color the corners of a triangle by everyone's preferences, invoke a lemma from 1928, and out falls a price split that leaves no one envious.

So the next time roommates square off over the big bedroom, you can promise more than a compromise. You can promise a split that is provably envy-free — and, unlike P vs NP and the genuinely hard problems on this site, this one comes with both the existence guarantee and the algorithm to find it.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/rent-division/Content licensed under CC BY-NC 4.0.