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.

## No comments:

Post a Comment