A rent nobody envies is not one rent

A rent nobody envies answered the existence question for the oldest practical problem in fair division. Three housemates rent a flat with three rooms that are not alike, and must agree who takes which room and how the rent is split. Francis Su showed in 1999, with Sperner’s lemma, that some split always lets each housemate take a different room while preferring its own room at its own rent to any other room at that room’s rent. Nobody envies anybody.

The housemates of that essay — A, who values the three rooms at 50, 25 and 15; B, at 35, 40 and 15; C, who values every room at 30 — had their envy-free split found by a grid search: rents of 28.5, 33 and 28.5. That essay noted, almost in passing, that for these housemates the envy-free splits fill a whole region. This essay looks at the region. It is large, it is not a detail, and the choice of a point in it turns out to be as consequential as anything about envy, and much more open to dispute.

Every envy-free split gives the same rooms to the same people #

Housemates who judge a room by its value to them minus its rent are said to have quasi-linear preferences, and the rent-splitting websites assume them because they make the problem exact. Two things follow, both short.

The first is that envy-freeness decides who gets which room. Suppose a split is envy-free, with each housemate in its own room. Each housemate’s room, at its rent, is worth at least as much to it as any other room at that room’s rent. Now take any other way of giving out the rooms, and add up these inequalities, each housemate comparing its own room with the room the other arrangement would give it. The rents on the two sides are the same three rents in a different order, so they cancel, and what is left says that the total value of the rooms to the people in them is at least as large in the envy-free arrangement as in the other. So an envy-free split always gives the rooms out in a way that maximises total value. Here that is A in room 1, B in room 2 and C in room 3, worth 50, 40 and 30, a total of 120 against at most 95 for any other arrangement.

The second is that, with the rooms fixed, envy-freeness is a list of straight-line conditions on the rents. A envies nobody if room 1’s rent exceeds room 2’s by no more than A’s value for room 1 exceeds its value for room 2, which is 25, and room 3’s by no more than 35. Six such conditions, one for each housemate and each room it did not get, together with rents of nought or more, cut a convex polygon out of the triangle of splits — here a hexagon with corners at (30, 30, 30), (46.7, 21.7, 21.7), (50, 25, 15), (45, 35, 10), (35, 40, 15) and (28.3, 33.3, 28.3).

These rents have a second meaning. The best way of giving out rooms is an assignment problem, and a price for every person and task showed that the cheapest assignment comes with numbers attached to each person and each task that certify it. Here the room numbers are the rents: a set of rents is envy-free exactly when, together with the housemates’ leftover values, it certifies that the assignment is the best. The hexagon is the set of all such certificates, and the simplex method’s walk from corner to corner is how such a set is explored.

Two housemates: a band and its middle #

With two housemates and two rooms everything can be done by hand, and the polygon becomes a band. Say A values room 1 at 60 and room 2 at 30, B values both at 45, and the rent is 90. Total value is largest with A in room 1. A envies nobody if room 1 costs no more than 30 above room 2 — its preference for room 1 — and B envies nobody if room 1 costs at least as much as room 2, since B is indifferent. So the envy-free splits are exactly those in which room 1 costs between 0 and 30 more than room 2: room 1’s rent anywhere from 45 to 60.

The width of the band, 30, is the difference between how strongly A prefers room 1 and how strongly B does. Housemates who want different rooms have a wide band; housemates who want the same room by the same margin have a band of width nought, and only one envy-free split. In the band, every unit of rent moved from room 1 to room 2 is a unit of surplus moved from B to A.

The maximin choice puts room 1 at 52.5 and room 2 at 37.5, where A keeps 60 − 52.5 = 7.5 and B keeps 45 − 37.5 = 7.5: the two surpluses equal, the middle of what each could have kept. With three housemates the band becomes the hexagon, and the middle is where three surpluses are equal, if that point lies inside the hexagon; if it does not, the maximin split sits on the hexagon’s edge, and one housemate keeps more than the others because envy-freeness will not let the rents equalise them.

What the corners leave each housemate #

Inside the hexagon room 1 can cost anything from 28.3 to 50, room 2 anything from 21.7 to 40, and room 3 anything from 10 to 30. That is not a small uncertainty about a fair answer. It is a range of 21.7 in one room’s rent, out of a total of 90, over which nobody envies anybody.

The corners are the extremes, and each is somebody’s best or somebody’s worst. At (28.3, 33.3, 28.3), close to the split the grid found, A keeps 21.7 of value and C only 1.7; at (50, 25, 15), A keeps nothing and B and C keep 15 each. At the equal split, (30, 30, 30), which is also a corner, C keeps nothing: it values every room at exactly 30, so at an equal split it is paying the full value of its room. Moving across the hexagon moves value from one housemate to another, unit for unit, since the rents always add up to 90 and the rooms do not change hands.

Envy-freeness is silent about all of this, and the silence matters to the people involved. A’s surplus can be anything from nought to 21.7 among envy-free splits. The split the grid procedure of the previous essay found is envy-free, and among the least favourable to C.

How much envy-freeness leaves open #

The housemates in the figures were chosen to illustrate. Random housemates show how typical the width is.

In the median house some room’s rent can range over 22, about a quarter of the rent, without anybody envying anybody. In a tenth of houses the range is under 6.7, and envy-freeness nearly fixes the split; in another tenth it is 45 or more, half the rent. The polygon is wide when the housemates want different rooms anyway, since then many rents keep each content with its own, and narrow when they compete for the same room, since then the difference in rents has to balance the competition almost exactly. The two-housemate case below makes that precise.

So a fair-division procedure that guarantees only envy-freeness has left something like a quarter of the money to be settled by a choice that is not about envy at all. The choice is made somewhere, by whoever wrote the procedure, and the procedure’s users are rarely told.

The maximin choice #

The choice made by Spliddit, the rent-division website built by Ariel Procaccia’s group, was argued for by Ya’akov Gal, Moshe Mash, Procaccia and Yair Zick in 2016 under the title Which is the fairest (rent division) of them all? Among the envy-free splits, choose the one that makes the worst-off housemate as well off as possible: maximise the smallest of the three surpluses. The rule is the rent version of an old principle from welfare economics, the one John Rawls built a theory of justice around, and in the house above it gives rents of 40, 30 and 20, leaving every housemate a surplus of exactly 10.

That is not one of the hexagon’s corners. The worst-off housemate’s surplus is the smaller of three straight-line functions of the rents, and the largest value of such a minimum lies where the lines cross — here at the point where all three surpluses are equal. No corner does as well: at every corner somebody keeps 10 or less, and at four corners somebody keeps 1.7 or less. The maximin split is in the middle of the polygon in the sense that matters, as far from every housemate’s worst case as it can be.

Gal and his coauthors compared the maximin rule with other choices one could make inside the polygon, and preferred it because of what it guarantees the least fortunate housemate. The product that makes a division fair made the case for a different criterion when goods are divided rather than rents: maximise the product of the people’s values. The two criteria agree in some cases and not in others, and there is no theorem that says either is the one right choice. What there is, is the observation that choosing something is unavoidable.

A lie the rule rewards #

A rule that sets rents from what the housemates say about the rooms can be told something false. The maximin rule tries to make the worst-off housemate as well off as possible, as measured by the reported values. A housemate that reports low values for every room looks badly off at any rent, and the rule compensates it.

Told the truth, the rule leaves B a surplus of 10. If B reports its values at three quarters of the truth, its true surplus rises to 16.7; if it claims to value every room at nothing, it still gets room 2, pays only 21.7 for it, and keeps a true surplus of 18.3 — nearly twice what honesty gave it. Overstating its values lowers what B keeps; understating raises it up to a point and then flattens, since the rule cannot compensate B for more than the envy-free polygon allows.

This is not a quirk of one house.

In 299 of 300 houses, some housemate can gain by misreporting. The median gain among the misreports searched is 15.3, about a sixth of the rent; a tenth of houses offer 27.3 or more. These are lower bounds, since the search tried only simple families of misreports. Nor is it a defect of the maximin rule in particular: it is classical that no rule which always produces an envy-free split can be immune to misreporting, for the reason the first section gave — envy-freeness fixes the rooms by the reported values and leaves a polygon of rents that the reports also shape, and any rule that picks a point in the polygon can be steered by moving the polygon. The same tension between a fair outcome and an honest report runs through voting, where a single voter can find a ballot that pays under every reasonable rule.

What the maximin rule’s users can be told is what happens when everyone reports truthfully, and that a housemate who games the rule is gaining at the expense of the others, since the rents still add up to the whole. In practice the gains depend on knowing the other housemates’ values, which a housemate rarely does precisely; how much can be gained under uncertainty about the others is a different and less alarming number.

When nobody can pay more than a little #

There is one more thing envy-freeness does not consider: whether anybody can afford it. The polygon can lie entirely at rents some housemate cannot pay, even when an affordable split exists that someone would envy.

With every rent capped at 30 — an equal split forced on the house — envy-freeness survives in only 1% of houses, those where the equal split happens to be envy-free. With a cap of 36 it survives in 74%; with 45, in 94%; above 60, always. In a quarter of houses, then, if nobody can pay more than 36 of a rent of 90, no envy-free split exists, however the rooms are given out. Ariel Procaccia, Rodrigo Velez and Dingli Yu showed in 2018 how to find an envy-free split respecting everyone’s budget whenever one exists, quickly; what to do when none exists — which kind of envy to allow, and for whom — is a judgement rather than a theorem.

The cap figure also shows what envy-freeness asks of the housemate who values a room most. At a cap of 30 the room A values at 50 must rent for 30, and someone who values it less must take a room they like less at the same price. Envy-freeness needs the rents to differ by as much as the housemates’ preferences do, and money that some cannot pay is the mechanism by which it does that.

The second decision is not about envy #

Fair division has a long habit of proving that something fair exists and moving on. One cuts and the other chooses guarantees each of two people half by its own measure; envy-free up to one item weakens envy-freeness until whole objects can meet it; Su’s theorem guarantees an envy-free rent. Each of those guarantees leaves room, and the room is where the remaining fairness questions live. For rent, the room is a polygon a quarter of the rent wide, and how to choose inside it — maximin, product, or something else — is a decision about which housemate to favour, made by a rule that is open to the housemates’ strategies and blind to their budgets.

Seen from the Sperner side, this is the familiar point that the lemma finds a fully labelled triangle, not a best one. The grid procedure found the split (28.5, 33, 28.5) because that is where its corridor happened to end, and the split favours A and leaves C almost nothing. A different grid, or a different order of questions, would have ended elsewhere in the hexagon. A procedure that asks only which room each housemate would choose at given prices cannot know how far inside the polygon it is, because the answers are the same everywhere inside it. Choosing a fair point in the polygon needs the values, and asking for the values is what invites the misreport.

Still open: rules that are fair inside the polygon and hard to game #

Whether there is a rule for choosing an envy-free split that is both attractive and hard to manipulate is not settled. Rules that ask only for choices at given prices, as the Sperner procedure does, cannot be gamed by misreporting values, since they never ask for values, but they land at an arbitrary point of the polygon. Rules that ask for values can choose well but can be gamed. Whether some rule limits how much a misreport can gain — to a bounded share of the rent, say — while still choosing well among envy-free splits, is an open question with practical stakes, since the websites that divide rents are used by people who talk to each other.

The budgeted problem has its own open side. When no envy-free split respects everyone’s budget, some envy must be allowed, and how to allow the least of it — the least total envy, the least envy for the worst-off, the fewest envious housemates — gives different answers, and which is right depends on whose budget is binding and why. And all of this assumes quasi-linear housemates, for whom a unit of rent is worth the same to everyone. For housemates to whom money matters differently, Su’s theorem still guarantees an envy-free split, but the polygon is no longer a polygon, and much less is known about choosing inside it.