742
C.-J. Haake et al.
ceding analysis of extreme envy-free prices, we found that 5 is the maximum
discount that Player 1 (the root player) can receive. In contrast, for Player 3,
an increase of 5 is the minimum increment that preserves envy-freeness. The
equal distribution of the remaining surplus thus implements the most favor-
able outcome for the initially non-envious (and therefore uncompensated)
player on the boundary of the set of envy-free prices. This may be di‰cult to
justify in practice.
By contrast, the average discount method acknowledges an additional no-
tion of fairness: Player 1, who did not experience envy throughout the entire
compensation procedure and who is always at the verge of being envied by
Player 2, receives only a small share of the remaining surplus. Player 3, on the
other hand, who quickly becomes envious when other players are compen-
sated, but who is relatively far from being envied by anyone else, receives
a larger share. From a practical viewpoint, the average discounts enhance
the stability of the outcome: by choosing discounts in the interior of the set
of envy-free prices, each player strictly prefers her own bundle to any other
(unless, of course, some players have identical preferences).
6 Cycling to e‰ciency
In problems of fair division that involve only a few parties and a few objects, a
utilitarian assignment will usually be easy to identify in practice. When many
players are involved, the complexity of this initial step quickly rises. Clearly, if
players must rely on computational assistance to perform the necessary cal-
culations before compensations can be made, this will diminish the attractive-
ness of a procedure that is supposed to work without computer support.
In our previous analysis, we used a utilitarian assignment as the starting
point for our procedure, thus ensuring that the envy-free allocation is also ef-
ficient. However, e‰ciency is not just a further desirable property of the out-
come. Indeed, envy-freeness can only be achieved if the assignment of n given
bundles is e‰cient.
Lemma 7. Let d be a vector of envy-free discounts for a given assignment B A B.
Then B must be an e‰cient assignment of the n associated bundles.
Proof. Consider some assignment B A B and an assignment Bp A B, which is
obtained through a permutation p of the n bundles of B. Let d be the vector
of envy-free discounts associated with the assignment B. Envy-freeness then
implies aii b aip(i), or, using definition (1),
dib b^Bp^- ЬрдодВрдо)+ dpðŋ : (12)
Since Pidi ¼ Pi∙dp(i) and P bp(i)(Bp(i)) ¼ ∑ibi(Bi), we can sum over both
sides of (12) to obtain
X bi (Bi) b X bi(Bp(i));