What “envy-free” actually means

It is a precise term that describes an algorithm. Keep your ideas about turning green with envy out of it. An allocation is envy-free when no person prefers anyone else’s room-and-price pair to their own, judged by the numbers that person submitted. That definition turns out to be far stronger than it sounds.

The word “envy” is not so much supposed to bring the color green to mind. It is not a claim that everybody will be happy. It is not a claim that everybody gets their first choice. In a house with one master bedroom and six people, that is arithmetically impossible. And it is not a claim about how people feel afterwards.

It is this, and only this:

For every person, and for every other room in the house: given the price attached to that room, you said you would rather keep what you have.

Why that reframes the whole argument

Take the case that generates all the bad feeling. In a plain auction, Dave outbids you for the master. You are in the bunk room, Dave is on the balcony, and the difference between you is that Dave had more money to spend or cared more about spending it.

Under an envy-free allocation, Dave still gets the master and still pays a premium for it. What changes is how large the premium is. It has to be large enough that you, looking at the master with that price on it, would rather have your room at your price. Not “told to accept.” Would rather.

So the sentence “he just bought the good room” has a complete answer for the first time: at the price the master ended up carrying, your own numbers said you would rather have your room and the difference in cash. If that is untrue, if you would actually have taken the master at Dave’s price, then the allocation was not envy-free and the allocator has a bug, which is a checkable claim rather than an argument.

Three facts from the theory

Rent division has been studied properly, and the results are unusually generous. Three of them do the heavy lifting here.

1. A solution always exists

For this setting, each person takes one room, prices can be any real numbers, and the prices have to add up to the total rent. An envy-free assignment of rooms and prices always exists. There are no conditions on what people want. No configuration of preferences, however contrarian or however identical, can make the problem unsolvable.

This is due to Svensson (1983), and to Alkan, Demange and Gale (1991). It is the reason the product can promise the property rather than attempt it: there is no input for which the answer is “sorry, no fair division exists here.”

2. Fairness does not cost efficiency

You would reasonably expect a trade-off: make it fairer, lose some total value; maximise total value, accept some unfairness. In this problem that trade-off does not exist.

Every envy-free assignment is automatically the one that maximises total value across the group. Not most of them. Every one. The fairness constraint does not compete with efficiency. It forces the efficient assignment. Any allocation that leaves value on the table (two people who would each rather have the other’s room) is, by definition, one where somebody envies somebody, so it was never envy-free to begin with.

3. Prices are not unique, so you get to choose

There is generally a whole range of price vectors that make a given assignment envy-free. Some of them are kinder to the people at the bottom than others. Since they are all equally “fair” by the envy test, you need a second rule to pick one.

The best-known second rule is maximin: choose the prices that make the worst-off person as well off as possible, where “well off” means the gap between what someone said their room was worth and what they are actually charged. That is the rule from Gal, Mash, Procaccia and Zick (EC 2017), and it is the one behind Spliddit’s rent-division tool.

We used to use it and no longer do. Maximin asks a single question: "how badly off is the worst-off person?" and answers it without reference to who wanted which room. That was fine while the ballot only collected money. Once it started collecting desire as well, there was a better question available: whose opinion about a room’s price should carry the most weight?

Our answer is the household sleeping in it, then whoever wanted it next most, and so on down, with the weights falling away over that order and scaled to the size of the group rather than fixed at some number we picked. The reasoning is that you cannot underbid your way to a cheaper room. Underbidding loses you the room, so the person who won it is the one with the least to gain from lying about it.

Changing the selector does not touch the guarantee, and that is the whole reason it was safe to change. Envy-freeness is the fence: the set of price vectors that satisfy the property. Maximin was only ever one way of choosing a point inside that fence. Swap it for another and every price is still inside. Where our rule wants a point outside, it gets pulled back to the nearest one that is not, and how far it had to move is recorded rather than hidden.

How it is computed

A ballot says two things, and they are separate on purpose. Where you drag a room says whether you want it. What you set its price to says what it should cost the group. Those are routinely opposite, and the form is built so they can be. A person on their own can hold that the master suite is genuinely the best room in the house and rank it last, because alone they would be paying for all of it. High value, no desire. Both halves of that sentence are real information, and an earlier version of this tool could only hear one of them.

1. Value. Build a table of what every room is worth to every household, from the money they put on it and from where they ranked it. A couple is one household with one bed, and their money is added together rather than averaged.
2. Assignment. Find the maximum-weight perfect matching of households to beds. Exactly, by dynamic programming over subsets, not greedily. This matters for a reason that is invisible until you look for it: a greedy assignment breaks ties by whatever order it happens to process people in, which means filling in the form early is worth money. The exact version is order-independent. Who submitted first is not an input.
3. Price bounds. Envy-freeness is a system of difference constraints. For each person, the price gap between two rooms must be at least the value gap they see between them. That system is solvable exactly when it contains no positive cycle, and it is solved with longest paths. It does not name one answer; it fences off every price set that satisfies the property.
4. Choosing inside the fence. Somebody still has to pick a point. The loudest voice on a room’s price is the household that ends up in it, then whoever wanted it next most, and so on, with the weights falling away down that order and scaled to the size of the group. Then every price shifts by the same amount so the adjustments sum to zero and the total still equals the rent.

That fourth step used to work differently. It maximised the worst-off person’s surplus, and before that it weighted the biggest bidder most. The second of those had a flaw worth naming, because it is the kind of thing only measurement finds: once ranking started counting, the biggest bidder on a room was no longer guaranteed to be the person sleeping in it. Someone could price a room they had ranked last, never receive it, and still hold the largest single share of what it cost the person who did. On our test scenarios that was 47% of the room’s price held by someone in a different bed. Listening to the occupant first is the repair.

How strictly we hold to it

Envy-freeness is the backbone of this site: the placement and the price bounds both come straight out of the literature above. It is not a slogan bolted onto something else. But a theorem and a rental house are different objects, so let's talk about where they part company.

The theory assumes each person holds one number per room. Real groups do not. They produce ballots the theorem never anticipated: a room nobody wants at any price, a bed for two with one person in it, a person who prices a room honestly and still will not sleep in it. Held to the letter in those cases, envy-freeness can require billing somebody more than they themselves said their room was worth. We think that is the worse outcome of the two.

So the honest statement is this: Every allocation this site produces is checked for envy before it is shown to anyone, in dollars, against the numbers the group actually submitted and the result is printed rather than asserted. When an organiser hand-edits an assignment, the page says so and reports what the edit cost. We do not ask you to take the property on faith, because a claim you cannot check is not worth much on a page about your own money.

The settings that decide the remaining trade-offs were not chosen by taste. They came from running 20,000 combinations across 25 group scenarios built on five real listings, and keeping the ones where nobody is billed above their own stated valuation and nobody envies anybody. Where a rule and the property genuinely conflict, the property is the constraint and the rule bends. How far it bends is recorded.

Couples take one bed, deliberately

Two people sharing a bed are modelled as a single participant who takes a single bed. That sounds like an implementation convenience. It is load-bearing.

The moment a couple can take a bundle — say, two separate singles — the problem stops being unit-demand and acquires complementarities: the pair is worth more together than the sum of the parts. Under complementarities, envy-free prices can fail to exist entirely (Gul and Stacchetti). The guarantee in fact 1 above quietly evaporates.

So the couples rule is not a simplification of the fair thing. It is the boundary of the region where the fair thing is provably available at all, and staying inside it is why the promise can be made without an asterisk.

What it does not do

Envy-freeness is a strong property and a narrow one. It is defined over the numbers people submit, which means it inherits whatever those numbers do and do not capture — including the fact that somebody with more money can afford to bid a wider spread. We wrote the limitations down separately, because a fairness claim without its boundary conditions is marketing rather than a specification.