A rent nobody envies

Three friends rent a house with three bedrooms. One room is large and bright, one has a view, one is small and next to the kitchen. The total rent is fixed; the question is how to split it so that each friend is happy with a room — so that nobody, looking at the rooms and the prices, would rather pay somebody else’s rent for somebody else’s room.

That is an envy-free division, like a cake shared three ways, but with a twist that makes it hard in a different way: the rooms are indivisible, like the items of the previous essay, and what is divided is money. Money can be split as finely as wanted, and it is that continuity that saves the problem. In 1999 Francis Su showed that a split always exists, under two mild assumptions about the housemates, and the proof is the colouring argument of Sperner’s lemma.

Two housemates on a line #

With two housemates and two rooms the whole idea fits on a line.

Every split of the rent between the two rooms is a point on a segment: at the left end room 1 costs nothing, at the right end it costs everything. At a grid of points along the segment, ask A and B alternately which room they would take at those prices. At the left end the answer is room 1, since it is free, and at the right end it is room 2. So somewhere along the way the answer changes between two neighbouring points — and since the points alternate between A and B, one of those two points was A’s and the other B’s. At prices between them, one of them wants room 1 and the other room 2. Refine the grid and the two points close in on a single split at which both are content.

It is the intermediate value theorem in its discrete form: a quantity that starts on one side and ends on the other must cross somewhere, and the alternation of owners is what turns “somewhere the choice changes” into “somewhere two different people want two different rooms”. Without the alternation the argument would find a point where one person changes its mind, which is useless; with it, the crossing is always a disagreement between the two housemates, and a disagreement is exactly what a fair division needs.

That is an intermediate-value argument, and it needs nothing but the endpoints. The three-person version needs the same thing one dimension up, and that is where Sperner’s lemma comes in.

Every split is a point of a triangle #

With three rooms, a split of the rent $R$ is three non-negative numbers $p_1 + p_2 + p_3 = R$ — a point of a triangle whose corners are the three splits in which one room costs everything and the other two are free.

The corners of the triangle are the extreme splits, where one person would be paying the whole rent for one room; the middle is the even split, thirty each. Neither extreme nor middle is likely to be fair, since the rooms are not alike, and the fair split is somewhere the housemates’ different tastes pull it. The argument never computes where; it only shows that it exists and how to close in on it.

Triangulate the triangle with a grid, and assign each grid point to one housemate in such a way that every small triangle has one corner belonging to each. A regular pattern does it: going along any line of the grid, the owners cycle A, B, C, A, B, C. At every grid point ask its owner which room it would take at the prices that point represents, and colour the point by the answer.

A small triangle whose three corners got three different answers is fully labelled. Its three corners belong to three different housemates, who, at three nearby splits of the rent, want three different rooms. That is almost an envy-free division: at any price inside the small triangle each housemate is close to a split where the room it named is its favourite.

The owner pattern is the one ingredient that has no counterpart in the fixed-point use of the lemma, and it is the clever part. Colouring by a single person’s preferences would find a small triangle where that person is torn between three rooms — interesting, but no help in dividing the house. Assigning corners to people in rotation means that whatever small triangle the lemma finds, its three answers come from three different people, and three different answers from three different people is a proposed assignment.

Why the miser’s rule makes it work #

Su’s two assumptions are what turn the colouring into one Sperner’s lemma applies to.

Nobody is homeless: at every split, every housemate prefers some room. That just says the question can always be answered.

The miser’s rule: a housemate always prefers a free room to one that costs money. That fixes the colours on the edges of the big triangle. At the corner where room 1 costs everything, rooms 2 and 3 are free, so whoever owns that corner picks one of them — never room 1. On the edge between the corners where room 1 and room 2 cost everything, room 3 is free throughout, so every grid point on that edge is coloured room 3.

That is a Sperner labelling, in the arrangement where each corner avoids its own colour and each edge avoids the colours of its two ends. Sperner’s lemma — proved by walking through the triangulation from door to door, where a door is an edge with two particular colours — says that such a colouring always has a fully labelled small triangle, and in fact an odd number of them. The figure checks both: on every edge the colours respect the miser’s rule, and the count of fully labelled triangles is odd.

Coarse grids and fine ones #

The fully labelled triangle is only approximately envy-free, because its three corners are three different price splits. How good the approximation is depends on the grid.

On a grid of four steps, each step is 22.5 of the 90 rent, and the three corners of a small triangle differ by that much. The housemates’ answers at those corners are honest, but the prices they answered about are not the same prices, and at the centre of the triangle one of them would rather have a different room — by 25, a large fraction of the rent.

The coarse grid is still useful as the first round of a procedure. Having found the one fully labelled triangle, the procedure can triangulate that small triangle more finely and ask the housemates again, zooming in on the region where the answer lies instead of refining the whole big triangle. That is how Su’s argument becomes a practical protocol: a sequence of questions that homes in on a fair split, each round a finer grid on a smaller region.

On the fine grid the fully labelled triangles are small, and at the centre of the best of them the envy is zero: at rents of 32, 32 and 26 each housemate is content with a different room. The corners of a small triangle now differ by only 6 in any room’s price, and for these housemates that is close enough.

How fast the envy disappears #

The envy at the best fully labelled triangle is never more than twice the grid step, because a housemate’s preference for a room changes by at most the change in that room’s price, and within a small triangle no price moves by more than a step. So as the grid is refined the envy goes to zero, and a limiting argument — the fully labelled triangles on finer and finer grids have a convergent subsequence, and at the limit point every housemate’s choice is available to it — gives a split with no envy at all. Su’s theorem is exactly that: under the two assumptions, an envy-free division of the rent exists.

The counts of fully labelled triangles grow with the grid — 25 on the finest — but stay odd, which is the parity that the door-to-door walk in Sperner’s proof guarantees. The walk enters the big triangle through a door on its boundary and can only stop in a fully labelled triangle; the doors pair up the others, and one is left over.

The counts are not monotone — 3 at eight steps, then 1 at ten — because a fully labelled triangle is a local event, and a slightly different grid can split one region of mixed answers into several fully labelled triangles or none. Only the parity is forced; the number itself depends on where the grid lines fall.

An exact split, checked #

For housemates who judge rooms by value for money — a room is worth some amount to each of them, and they prefer the room with the largest value minus rent — an envy-free split can be found directly.

The table reads row by row. Person A values the rooms at 50, 25 and 15; at rents of 28.5, 33 and 28.5 its value for money is 21.5, −8 and −13.5, so room 1 is best by far. Person B values them at 35, 40 and 15, and gets 7 from room 2 against 6.5 from room 1 — close, but room 2 wins. Person C values every room at 30 and so prefers the cheapest; rooms 1 and 3 tie at 28.5, and room 3 is C’s without envy.

For valuations of this kind — quasi-linear, value minus price — envy-free splits are the solutions of a small linear program, and can be computed exactly and quickly for any number of rooms. That is how rent-division websites do it: they solve for the envy-free splits and then, among all of them, choose the one that makes the least happy housemate as happy as possible. Su’s Sperner argument is more general — it needs no model of how the housemates value rooms, only their answers to the question of which room each would take at given prices — and it can be run as a procedure that asks those questions one at a time, moving through the triangulation along the door-to-door path.

The same lemma, three uses #

Sperner’s lemma has appeared before in this collection, proving a fixed-point theorem by colouring the triangle according to which way a map moves each point. Here it divides a rent. The two uses are the same argument: in both, the colours on the boundary are constrained by the corners, the parity argument finds a small triangle of all three colours, and a limit turns the small triangle into a single point with a property that no single colour could guarantee. The fixed point is where the map moves nowhere; the rent split is where everybody’s preferred room is different.

And the same lemma gives the cake-cutting version: Su’s paper also divides a cake among $n$ people envy-freely using a triangulation of the space of cuts, and there the miser’s rule becomes the assumption that nobody wants an empty piece. The rent problem is the cake problem turned inside out — dividing a cost rather than a good — and that inversion is why the natural assumption is miserly rather than greedy.

The third use is the one that ties the collection’s subjects together. A fixed point of a map, a fair split of a rent and an envy-free cutting of a cake are three questions in three fields, and one combinatorial lemma about colouring a triangulated triangle answers all of them. What they share is a continuous space of possibilities whose boundary is controlled — by the map, by the miser, by the rule that nobody wants an empty piece — and a need for a single point where several conditions hold at once.

What the pictures show and what they assume #

The housemates’ answers are generated by a model. Each housemate’s choice at each grid point is computed from fixed values for the three rooms, with the miser’s rule applied on the boundary. Real housemates answer however they answer; the theorem needs only the two assumptions, and the figures show the argument on one well-behaved example.

Zero envy from K = 6 is a property of these housemates. Their envy-free splits form a whole region, so a fine enough grid lands a triangle’s centre inside it. For housemates whose envy-free split is a single point, the envy at every finite grid is positive and only shrinks, bounded by the dashed curve.

The grid points on the boundary are special. The miser’s rule is applied only where a room’s price is exactly zero, which on the grid means only at points on the edges of the big triangle. Nearby interior points use the housemates’ ordinary preferences, and the figure checks that the boundary colours obey the rule; it does not check what the housemates would do at prices very close to zero but not equal to it.

The exact split was found by search. The last figure scans rents in quarter-units and reports the first envy-free split it finds. The set of envy-free splits is larger; the search shows one exists and checks it, and the linear-programming method finds all of them.

Still open: fairness beyond envy #

For three rooms, or any number, Su’s theorem settles existence, and for quasi-linear housemates the linear program settles computation. What remains open is which envy-free split to choose, and what can be guaranteed when budgets matter. If a housemate cannot afford the rent of the room it would prefer — if utilities are not quasi-linear, because money matters more to some people than others — envy-free splits may require rents some housemates cannot pay, and the right way to trade envy-freeness against affordability is argued over. Whether an envy-free split can always be found that also respects every housemate’s budget, when one exists at all, is known only for special cases.

There is also a question about honesty. A housemate who knows how the split is computed can sometimes pay less by misreporting how much it values the rooms. No rule that always produces an envy-free split can be immune to that for every set of housemates, and how much a single misreport can gain under the rules actually used is an active question. The same tension runs through all of fair division: cut and choose is safe for the chooser but lets a cutter who knows the chooser’s taste shade the cut, and the procedures that divide among many trade the number of questions asked against how much any one answer can be gamed.

The parity that pays the rent #

The rent problem looks like a negotiation and turns out to be topology. Every split of the rent is a point of a triangle; the housemates’ preferences colour the triangle; a counting argument about doors forces a small triangle where the three colours meet; and refining the grid pins down a split where three people, wanting three different things, each get what they want. Nothing in the argument depends on how much anyone values anything, only on the fact that a free room is always welcome — which is the whole of what a lemma about coloured triangles needs.

The procedure also has the virtue that nobody has to explain their preferences. The housemates never report how much they value a room; they only answer, at particular prices, which room they would take. The argument turns those answers — the least a person could be asked for — into a guarantee that a split exists which all three would accept, and a way to find it. It is the rare fairness procedure whose inputs are as easy to give as its outputs are to check.