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.cite journal |last=Brams |first=Steven J. |coauthors=Alan D. Taylor |title=An Envy-Free Cake Division Protocol |journal=The American Mathematical Monthly |volume=102 |issue=1 |date=January 1995 |pages=9–18]

A scheme is envy-free if each recipient believes that (according to their measure) no other recipient has received more than they have.

There is a finite procedure for three player envy free division and a moving knife procedure for four players. A procedure for envy-free division for any number of players was first published by Steven Brams and Alan D. Taylor in 1995, 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 her share is "smaller" than the other players'. The crucial issue is that no player would wish to swap her 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.

Many players

The Selfridge-Conway discrete procedure gives a envy free division for three players.

*The first player divides the cake into three pieces he considers of equal size.
*If the second player thinks there is a largest piece he should cut off a bit to make it the same size as the second largest. The bit cut off is the "trimmings".
*The third player chooses a piece.
*The second player chooses a piece, if the third player didn't choose the trimmed piece he has to.
*The first player chooses a piece.The cake minus the trimmings has now been divided in an envy free manner.Call the second or third player who received the trimmed piece A and the other one B.
*B cuts the trimmings into three equal pieces.
*A, the player with the trimmed piece, chooses a piece of the trimmings.
*The first player chooses a piece of the trimmings
*B chooses a piece of the trimmings

The reasoning behind the algorithm is tricky and a good exercise for the reader! The important point to note in a proof is that the first player will not be envious of A even if A gets all the trimmings.

There are a number of moving knife procedures for three or four players. These are quite complex.

For five or more players the only known algorithms have no fixed bound on the number of cuts required.

These methods do break down. If even divisions are not possible, there will be a result with envy; and if preferences are different it is possible that the utility received may not be even, making the division "unfair" even though no one would want to trade for another's share. The study and debate over which methods are most fair with which situations continue.

See also

* Allocative efficiency

References