Bidding for envy-freeness
739
for every player i in the directed graph leading (with double arrows) to Player
r. Summing up both sides in (9) we obtain in particular
1τ-^r,
-]T½bj(Bj)+ dj - dj] = ¼(⅛): (10)
nj
Note that the final value that Player i receives under the compensation
procedure with ex-ante payments and an equal distribution of the remaining sur-
plus is
bi(Bi) — bi (Bi)+ di + _
n
У? bj (Bj) — C - '>∖dj
¼ bi(Bi)-½bi(Bi)- di]+ 1 X½bj (Bj )— dj ]— 1 C:
nj n
This is the value of Player i’s bundle, minus its (discounted) cost, plus an equal
share of the total payments, minus an equal share of the total costs.
Consider now the final value that Player i receives under the compensation
procedure with ex-post payments and an equal distribution of total compensa-
tions and total costs C:
. , — 1 1 X--' 1 1
bi (Bi)+ di--d ʌ dj--C:
nj n
The final value is the value of the bundle, plus additional compensation, minus
an equal share of all costs.
By comparing their final values, one can see that both procedures lead to
the same outcome if and only if
1 1 1 1
bi(Bi)+ di - di ¼ -ɪɔbj(Bj) + dj — dj]:
nj
Equations (9) and (10) show that this condition is satisfied if the final envy-
graphs of both procedures are the same and possess a single root. r
But even when there is a difference in the outcomes (due to different envy
relations), the compensation procedure with ex-post equal payments estab-
lishes envy-freeness with minimal resources and thus minimal side-payments
between players. Afterwards each player is charged an equal amount, just
enough to cover the cost of envy-freeness plus the cost of the joint venture, so
that there is no remaining surplus to be distributed. Hence, if the sole objec-
tive is to implement a unique envy-free outcome, the method with ex-post
payments has a practical advantage. We demonstrate the application of this
procedure in Sect. 6.
The average discount method or ‘‘The average biased mediator’’
An equal distribution of the remaining surplus may not be the most plau-
sible approach if the set of envy-free discounts is asymmetric in the sense that