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

C.-J. Haake et al.

lets each party pay an equal share of the total costs. We call this the com-
pensation procedure with ex-post equal payments.

With this modification, Player i’s assessment of Player j^,s bundle becomes
a_ij ¼ b_i(Bj) + dj, where d~ denotes the compensation under the modified pro-
cedure. Thus, in this case the initial assessment matrix is the bid matrix, so it
follows that Theorems 1-3 also hold for the method of ex-post equal pay-
ments. And,similar to the proof of Theorem 4, it can be shown using the quali-
fication condition that¹ (Pj- d^j + C) a b_i (Bi) + d_i, Ei a I. Hence no player pays
more than what she thinks her share is worth.

Generally, the directed graphs for ex-ante and ex-post payments will fea-
ture different envy relations. Nevertheless, the seemingly different procedures
exhibit an interesting equivalence: if the final directed graphs turn out to be
the same and exactly one and the same player remains non-envious in both
procedures, then the ex-post equal payments procedure and the ex-ante pay-
ments procedure with an equal distribution of the remaining surplus will yield
the same outcome.12

Theorem 5. Consider the two procedures: (1) ex-post equal payments and (2)
ex-ante payments with equal distribution of the remaining surplus. Suppose that
the final envy graphs of both procedures coincide and have exactly one root.
Then the outcome of both procedures will be the same.

Proof. With ex-post payments, each player i a I begins with an initial value
b_i^B_i). Player i envies Player j if Player i thinks that Player j receives more
than Player i. In the (final) directed graph, which we denote by G^j, i ) j then
implies

~ , . , . ~ ___

^di ¼ ^bi ^(Bj j   ^bi ^(Bi^{)+ d}j ;                                                       ⁽7)

where d^j_i denotes the compensation under the modified procedure.

In contrast, the compensation procedure with ex-ante payments begins by
having each player i a I pay b_i (B_i) for her assigned bundle. Player i envies
Player j if Player j pays less for her bundle than what Player i thinks it is
worth. In the (final) directed graph G, i ) j implies

^di ¼ ^bi^(Bj^{) — b}j^(Bj^{)+ d}j:                                                   ⁽⁸⁾

Coincidence of the final graphs enables us to subtract (8) from (7) and to ob-
tain:

bi(Bi)+ di- di¼ bj (Bj )+ dj - dj :

Assume that Player r is a root of the directed graphs G and G^j. Since Player
r does not receive a compensation under either procedure, dr ¼ d^jr ¼ 0, hence

bi^(Bi^{)+ d}i ^{- d}i ¼ br^(Br^{)                                                    (9)}

12 This is the case for our example given in Table 1. The ex-post payments procedure
yields final discounts d^j ¼(0; 20; 35; 25). With C ¼ 100, there is a total of 180 units to
be shared equally by all four players. The final cost for each player is thus the same as
under the ex-ante method.

<<   <   13   14   15   16   17   18   19   >   >>