Bidding for Envy-Freeness: A Procedural Approach to n-Player Fair Division Problems

Bidding for envy-freeness

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 d_i in particular yields a_ii b a_ipð_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 (d_i) 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 mk₀ < dk₀ , for player k0. Thus dk₀ is strictly positive (because
mk₀ 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, ak_ik_i ¼ ak_ik_i+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+ι ^{)+ d}k_i+ι ;

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.

<<   10   11   12   13   14   15   16   >>

More intriguing information