734
C.-J. Haake et al.
Proof. We prove this by induction on k. For k ¼ 0 (before any compensa-
tions) the statement trivially holds, since there are by definition no envious
roots.
Now assume that the lemma holds for k. We show that it also holds for
k + 1. By the inductive hypothesis, after k compensation rounds all envious
players must be on levels ðk + 1) or higher. A subset of these will be com-
pensated during the ðk + 1)-st round; in particular this must include all the
envious players on level ðk + 1),since their maximum envy is for non-envious
players on level k.
So consider a player P anywhere in G. If P’s ancestral path did not change
as a result of the ðk + 1)-st compensation round,then she remains on the same
level. Moreover, if she is on level ðk + 1), then she must also now not be en-
vious (because she was either compensated or was not envious to begin with).
If P’s ancestral path did change as a result of the ðk + 1)-st compensation
round, then we show her new level number must be ðk + 2) or greater. Con-
sider the new path that flows from P; by Lemma 3, it contains some newly
compensated player. Thus it makes sense to speak of the newly compensated
player on P’s path who is closest to the root; call this player Q. Q’s ancestral
path cannot have been changed by the last compensation round (otherwise
Lemma 3 would have produced some other newly compensated player closer
to the root than Q). So Q’s level was unchanged, and being a newly compen-
sated player, Q must have had level number ðk + 1) or greater. Since P has a
higher level number than Q, P must have a level number of ðk + 2) or greater
in the new graph.
Thus if any player changed levels as a result of the ðk + 1)-st compensation
round,they must now be at level number ðk + 2) or greater. The players who
remain on levels 0 through k were non-envious before the round and must still
be non-envious,while the ones remaining on level ðk + 1) have been compen-
sated and are also non-envious. r
Theorem 2. The procedure requires no more than n — 1 compensation rounds to
eliminate envy.
Proof. Because G has only n vertices, and every tree in G must have a root, no
vertex can be on level n or greater. Hence, by Lemma 4, all players will be
non-envious after at most ðn — 1) compensation rounds. Г
It is not yet clear what effect the initial assignment has on the resulting
envy-free discounts. Moreover, when the utilitarian assignment for n given
bundles is not unique, players have multiple choices for the starting point
of the compensation procedure. Remarkably, the outcome is not affected by
the choice of assignment. We first prove two lemmas needed to establish this
result.
Lemma 5. If there are two utilitarian assignments involving the same bundles,
then a vector of discounts which yields envy-free assessments under one assign-
ment will also be envy-free under the other assignment.