736
C.-J. Haake et al.
dki - dk!+i a mki - mk,+ι :
By summing this over all 0 a i a l — 1, we have
dk0 - dkl a mk0 - mkl :
But dkl ¼ 0 because kl was the root, i.e., a player not compensated throughout
the entire procedure. And since the discount mkl is non-negative, we have
dko ¼ dko dkι a mko mkι a mko :
This contradicts the fact that mk0 < dk0 . r
Together Lemmas 5 and 6 allow us to establish the following practical re-
sult.
Theorem 3. For given bundles, the outcome of the compensation procedure yields
a unique minimal vector of player discounts which does not depend on the utili-
tarian assignment chosen.
Proof. Suppose there were two utilitarian assignments - the non-prime and
the prime assignment. The compensation procedure applied to each assign-
ment yields corresponding vectors of player discounts ðdi) and (di0).
Note that the discounts (di0) are also envy-free discounts for the non-prime
assignment (Lemma 5), and because the (di) are minimal for the non-prime
assignment (Lemma 6), we must have di a di0 for all i. Similarly, the (di) are
also envy-free discounts for the prime assignment, and minimality of the (di0)
for the prime assignment implies that di0 a di for all i. Therefore di ¼ di0 for
all i. r
The sum of discounts thus yields the minimal amount of money required
for envy-freeness. With n bundles to allocate among the individual players,
multiple utilitarian assignments do not cause a coordination problem, because
they all lead to the same discounts. Hence there is no problem of choosing an
appropriate starting point for the compensation procedure as long as the as-
signment maximizes the sum of players’ bids.
We have shown that this procedure will terminate with envy-free costs
without having used the individual qualification condition (Assumption 3).
The only need for this condition is to ensure that the surplus is never exceeded
at the end of the compensation rounds. (If the surplus were exceeded at the
end, one could still obtain envy-free prices by charging all players equally for
the overdraft, but then some players might end up paying more than what
they bid on their bundle.)
Theorem 4. If each person meets the qualification condition (Assumption 3),
then by the end of the procedure, the compensations will not have exceeded the
surplus.
Proof. Since the prices obtained at the end of the procedure are envy-free,
aii b aij for all i; j. Using (1) this implies
dj — di a bj(Bj) — bi(Bj); (4)