Experiments with envy-prone cake cutting

Suppose that 3 people share a cake as follows. Player 1 cuts it into 3 pieces, then player 2 takes a piece, then player 3 takes one, then player 1 takes the remaining one. Player 1 can avoid envy by cutting into pieces that he values equally, player 2 can avoid envy since he gets first choice, but the worst case for player 3 is terrible - he may see player 2 walk off with a piece that he (player 3) deems to contain all the value in the entire cake. Consider the following "fix": after player 3 has taken a piece, he has the right to combine it with player 2's and challenge him to cut-and-choose. In this case, player 1 can end up envious: he can ensure his own piece is worth 1/3 of the total, but he may watch as one of the other players ends up with a share that he values as 2/3. Indeed, player 2 can also end up envious of player 1, under this scheme.

An obvious way to quantify the envy of a cake-cutting scheme is to say that each player values the cake at 1 unit, and look for the worst case envy of any player, i.e. the maximum amount that he may be forced to value another player's share more than his own. The first scheme above has an envy of 1 in the worst case, and the second version is 1/3.

We can analyze schemes in an ad-hoc manner to figure out their worst-case envy, but can we do it automatically? For an undergraduate programming project I got the student (Amir Niknafs-Kermani) to try doing this as follows. Model the cake as a unit line segment. Represent a player's value function by a set of N (typically about 1000) points on the line, each worth 1/N. Generate for each player, an initially random value function, and run the scheme on them, and measure the level of envy (which is typically zero or very low for a sensible scheme, since these value functions all more or less agree with each other). Then, try to tweak the value functions by adding and removing points that define those functions. The hope is that points get added in "sensitive" regions of the line, and when you re-run the scheme, the envy goes up. Repeat until you don't manage to raise it further, and you've got a lower bound for the worst-case envy.

And the results, briefly, are that it works pretty well, at least for simple schemes. The envy level that is found by the algorithm varies quite a lot (depending on the initial random choice of value functions) but is often close to the theoretical limit. But the performance gets worse with larger number of players.

Since it is unknown whether there is a 4-player envy-scheme with a finite number of cuts, perhaps it is interesting to study the above "level of envy" measure, and how fast it can go down towards zero, as a function of the number of cuts in specific types of schemes.