Rental Harmony

The Roommate Problem

Imagine Mara, Dev, and Priya are moving into a three-bedroom apartment for $3,000 a month. The rooms are not identical. One has big windows and almost no closet space. One is smaller but has an en-suite bathroom. One is closest to the door and gets the least light.

The obvious first instinct is to split evenly: $1,000 each, everyone picks a room. This falls apart fast. Priya, who got the en-suite, knows she got a good deal. Mara, in the dark room, with less ability to pay, knows she didn’t. They’re paying the same amount for demonstrably different situations. The resentment is slow but it is coming. 6 months later, over what should have been a small infraction with Priya not taking the trash out in time for the garbage truck that week, Mara totally blows up at her, calls her spoiled and stuck-up and undeserving, and their friendship never recovers.

Rewind.

The better approach is to price the rooms differently — the total still has to be $3,000, but the split between rooms should account for their actual differences. The problem: how differently? Priya cares deeply about natural light. Dev would pay a premium for a private bathroom. Mara just wants to minimize her number. These preferences aren’t the same and they’re not written down anywhere.

What you actually want is a split where each person, looking at what the others are paying for the other rooms, thinks: yeah, I’d pick my room at my price. Where nobody is eating breakfast across from Dev’s bathroom door thinking I should have pushed harder for that one. This is the formal definition of “envy-free” - nobody would trade their situation with anyone else’s.

For two people, there’s a classic protocol: one cuts (in this case, assigns prices to the rooms), the other chooses¹. For three people with three different rooms and prices that have to add up to a fixed total, it’s not obvious that an envy-free solution even exists, let alone how to find one.

Sperner’s Lemma

In 1928, Emanuel Sperner (German, mathematician, not so far as we know having any housing disputes) published a result in combinatorics, the branch of math that deals with discrete structures: counting², graphs, tilings, things you can reason about without calculus.

The setup: take a triangle³. Subdivide it into a mosaic of smaller triangles. Color every corner of every small triangle using three colors, let’s call them red, blue, green, with these rules: each outer corner of the big triangle gets its own dedicated color, corners on an outer edge can only be one of the two colors at that edge’s endpoints, and interior corners can be anything. (Interior corners have more freedom. This is their one win.)

The claim: no matter how you color, as long as you follow those rules, there will always be at least one small triangle whose three corners are all different colors.

That’s Sperner’s Lemma. The proof is a counting argument — not especially hard, actually, for something that ends up doing this much work downstream. (I say “not especially hard” meaning: hard, but the kind of hard where once someone walks you through it, you can almost convince yourself you would have seen it. Almost.) Sperner published it as a stepping stone to something in topology. He was not thinking about roommates.

Seventy-one years later (Spongebob Narrator Voice)

In 1999, Francis Su published “Rental Harmony: Sperner’s Lemma in Fair Division” in the American Mathematical Monthly.

The connection he made: the space of all possible rent splits for three rooms- e.g. “room A costs $x, room B costs $y, room C costs $z, and x + y + z = $3,000” - has the shape of a triangle. Each outer corner represents an extreme case where one room pays all the money, every point on an edge is two rooms have a cost and the third is free, and every interior point is some specific all-non-zero split.

Triangulate that space. At each vertex, ask the question: given these prices, which room would each person want? Label the vertex with the answer⁴. Under assumptions about preferences that are both mild and very plausible (roughly, if a room is free, someone would want it) this labeling satisfies exactly the conditions of Sperner’s Lemma.

Which means there’s always a tiny triangle in the subdivision where Mara, Dev, and Priya would all name different rooms. As you subdivide to finer and finer triangulations, that rainbow triangle shrinks toward a specific point. Thus, a specific price split where each person would independently choose their own room over the others must exist.

Sperner guaranteed a solution to the envy free cake (or apartment) cutting problem in 1928, without knowing he was doing that.

The Tool

At this point you are probably wondering if I’m going to make you triangulate something.

The New York Times published a calculator that implements exactly this. You enter the total rent, the number of rooms, and each person answers a few questions about which room they’d want at which price. The algorithm runs Sperner-style triangulation on their preferences and outputs a suggested price for each room. If everyone answers honestly, the result is envy-free by construction.⁵

The next time you’re standing in an apartment arguing about whether the sunnier room is worth $200 more a month, know you don’t have to argue. There is a website. It has been quietly implementing the consequences of a 1928 combinatorics proof this whole time.

The algorithm doesn’t know or care what anyone earns. But it does take seriously the preference to pay less. If Mara is working with a tight budget, she can express that consistently, by every time she’s asked which room she’d want at a given price split, gravitating toward the cheapest option. The algorithm respects that and finds her a lower price point, even if the room isn’t the nicest.

This is meaningfully fairer than splitting evenly, or even by square footage. An envy-free split at least accommodates the reality that people are working with different budgets, without anyone having to disclose their income or make the conversation weird.

Why this should matter to people who fund things

In 1928, Sperner was not solving a widely applicable fair division problem. He was doing pure mathematics — mathematics motivated by questions inside mathematics, with no obvious application outside of it. He needed a combinatorial fact to prove something about topology. He proved it. He moved on.

Seventy-one years passed before it became “useful”.

This pattern is not rare. G.H. Hardy wrote an essay in 1940 essentially bragging that his work in number theory was so abstract it would never have practical uses. RSA encryption — the math behind HTTPS, banking, every secure message you’ve sent today — is built on the number theory Hardy was talking about. Non-Euclidean geometry was developed in the 1820s through 1860s to settle a purely logical question about whether Euclid fifth axiom was actually necessary. Einstein needed it for general relativity in 1915; the math was just sitting there, waiting. George Boole published “An Investigation of the Laws of Thought” in 1847. Every computer ever made runs on his algebra.

Somebody follows a question because the question is interesting. Decades pass. It turns out to be load-bearing for something we hadn’t invented yet.

I don’t think the lesson here is that pure math should be funded because it’s secretly practical. That framing still asks mathematics to justify itself on somebody else’s terms. The more honest version is: usefulness is genuinely hard to predict in advance, and curiosity has a better track record than directed application when you’re playing the long game.

So follow the weird thing. The interest that doesn’t obviously connect to anything, that you can’t quite justify on a spreadsheet. Not because it’ll secretly pay off someday — maybe it will, maybe in seventy years, maybe never — but because “will this be useful?” is genuinely a bad filter for what’s worth thinking about.

Embrace your whims. They have a better track record than they look.

1. This can have its own problems - if you can accurately model the other person’s preferences, then even though it’s envy free, the cutter can often manufacture a much better deal for themselves than for the other person

2. It’s tougher than it sounds

3. Technically it’s a simplex, which generalizes triangles to higher dimensions — which matters when you have four or more rooms. Triangle is the right intuition

4. TECHNICALLY we only ask one person at each vertex and then do a SUPER FINE triangulation so that the vertices next to each other are different peoples answers about rent splits that are within cents of each other, but, ya know, nerd alert.

5. Also check out Spliddit !