Envy-free

In mathematical sociology and especially game theory, envy-free is a property of certain fair division algorithms for a divisible heterogeneous good over which different players may have different preferences.^[1]

A division is envy-free if each recipient believes that according to his measure no other recipient has received more than he has. This requirement is stronger than proportional division.

There is a discrete procedure for three players and a moving-knife procedure for four players. Both have a bounded number of cuts. There is also a discrete procedure for any number of players, but this procedure has no fixed bound on the number of cuts required.

The concept generalizes naturally to chore division: in this case, a division is envy-free if each player believes their share is smaller than the other players'. The crucial issue is that no player would wish to swap their share with any other player.

Two players

Two siblings dividing the last piece of cake using divide and choose is a simple and practical example. The first sibling divides the cake into two pieces, and the second sibling chooses which piece to take. Since both siblings wish to maximize their share of the cake, the first sibling will divide the cake evenly in his estimation and the second sibling will take the one perceived as more desirable. Even if there is icing unevenly on the cake that the siblings want, the first sibling can divide the cake to compensate for the perceived benefit of the icing in his view making them even, and then the second sibling chooses the piece he prefers.

Note that for two players envy-free division is the same as proportional division.

Three players

Discrete procedure

Discrete procedures involve only discrete queries to the players. The Selfridge–Conway discrete procedure is a solution to the envy-free problem for three players.

Moving knife procedure

The drawback of moving-knife procedures is that they cannot be translated into discrete queries to the players involved in the procedure. The Stromquist moving-knife procedure is a solution to the envy-free problem for three players.

Four players

The Brams, Taylor and Zwicker moving knife algorithm devised in 1997 can ensure an envy free division amongst four people.^[2]

Five players and more

In 1995 Brams and Taylor devised an envy free procedure for any number of people. This is discrete but the number of cuts is unbounded, it is not determined in advance.^[3]

For five or more players, the only known exact algorithms have no fixed bound on the number of cuts required.^[4]

However, there are approximate algorithms that use the minimal number of cuts, i.e. n-1 cuts for n players.^[5]

See also

• Allocative efficiency
• Fair Division Calculator - an applet for calculating envy-free division for cakes, chores, rooms and rents.

References