Cake-cutting protocols aim at dividing a cake'' (i.e., a divisible resource) and assigning the resulting portions to several players in a way that each of the players feels to have received a fair'' amount of the cake. An important notion of fairness is envy-freeness: No player wishes to switch the portion of the cake received with another player's portion. Despite intense efforts in the past, it is still an open question whether there is a envy-free cake-cutting protocol for an arbitrary number of players, and even for four players. We introduce the notion of degree of guaranteed envy-freeness (DGEF) as a measure of how good a cake-cutting protocol can approximate the ideal of envy-freeness while keeping the protocol finite bounded (trading being disregarded). We propose a new finite bounded proportional protocol for any number n 3 of players, and show that this protocol has a DGEF of 1 + (n^2) 2 . This is the currently best DGEF among known finite bounded cake-cutting protocols for an arbitrary number of players. We will make the case that improving the DGEF even further is a tough challenge, and determine, for comparison, the DGEF of selected known finite bounded cake-cutting protocols.
More recently, Brams, Jones, and Klamler @cite_6 proposed to minimize envy in terms of the maximum number of players that a player may envy. Their notion of measuring envy differs from our notion of DGEF in various ways, the most fundamental of which is that their notion takes an egalitarian'' approach to reducing the number of envy-relations (namely, via minimizing the most-envious player's envy, in terms of decreasing the number of this single player's envy-relations). In contrast, the DGEF aims at a utilitarian'' approach (namely, via minimizing overall envy, in terms of increasing the total number of guaranteed envy-free-relations among all players). That is to say that, although these notions may seem to be very similar at first glance, the approach presented in @cite_6 is not sensitive to a reduction in the number of envy-relations on the part of any other than the most-envious player, whereas the DGEF does take each single improvement into account and adapts accordingly. The DGEF, thus, is a more specific, more fine-tuned measure. Note also that Brams, Jones, and Klamler @cite_6 focus primarily on presenting a new protocol and less so on introducing a new notion for measuring envy.
@cite_6
2166670127
Properties of discrete cake-cutting procedures that use a minimal number of cuts (n A¢â‚¬â€œ 1 if there are n players) are analyzed. None is always envy-free or efficient, but divide-and-conquer (D&C) minimizes the maximum number of players that any single player may envy. It works by asking n ? 2 players successively to place marks on a cake that divide it into equal or approximately equal halves, then halves of these halves, and so on. Among other properties, D&C (i) ensures players of more than 1 n shares if their marks are different and (ii) is strategyproof for risk-averse players. However, D&C may not allow players to obtain proportional, connected pieces if they have unequal entitlements. Possible applications of D&C to land division are briefly discussed.