Bidding for envy-freeness
735
Proof. We have
aj :¼ bi(Bj)- bj(Bj)+ dj; i, j a I:
Let p : I ! I be the permutation that transforms the original utilitarian
assignment into the other one; i.e., in the second assignment Player i receives
the bundle that Player pði) would receive in the original assignment. Envy-
freeness of the discounts di in particular yields aii b aipði) .
Taking the sum over differences yields
Еда» - αip(i)) ¼ ∑(d - dp(i)) + ∑(bp(i)(Bp(i))- ЬдВрдо))
¼ 0 + M - M ¼ 0:
Since each addend on the left-hand side is non-negative, and their sum is zero,
aii ¼ aip(i) ; Ei A I: r
Said another way, Lemma 5 shows that the compact convex set of all pos-
sible envy-free discount vectors is independent of the utilitarian assignment.10
Note, however, that Lemma 5 says nothing specific about the discount vector
induced by the compensation procedure.
Lemma 6. The compensation procedure yields a unique minimal vector of non-
negative discounts that make a given utilitarian assignment envy-free.
Proof. Given a utilitarian assignment, the compensation procedure yields a
vector of player discounts (di) which makes every player envy-free. If there
were some other vector of (non-negative) envy-free player discounts (mi) which
was smaller for some player, then we obtain a contradiction.
Suppose mk0 < dk0 , for player k0. Thus dk0 is strictly positive (because
mk0 b 0), i.e., player k0 was compensated sometime during the compensa-
tion procedure. This implies that in the final envy graph at the conclusion of
the compensation procedure, Player k0 is not at the root of her tree. Let
k0 ; k1 ; k2 ; ... ; kl ¼ r be the path from k0 to the root r of her tree. Since each
of the arrows in the final envy-graph are double arrows, akiki ¼ akiki+1 for all
0 a i a l — 1. Using (1) to express this in terms of the bids and discounts, we
have
dki ¼ bki (Bk;+i) — bki+ι CBki+ι )+ dki+ι ;
for all 0 a i a l — 1. But the (mi ), being an envy-free vector of discounts, must
satisfy
mki b bki (Bki+1 )— bki+1 (Bki+1 )+ mki+1 ;
since the left side is what Player ki would receive under these discounts and the
right side is what Player ki believes Player ki+1 would receive. Subtracting
these two equations we obtain
10 Lemma 5 corresponds to Aragones’ (1995) Lemma 4.