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

Bidding for envy-freeness

for all i; j. Summing the above equation over all j, one obtains that for all i,

Xd_j - di) a M - Xb_i(Bj).                                 (5)

Choose any player i who was not compensated throughout the entire proce-
dure (there must be at least one, by Theorem 1). Since d_i ¼ 0, and since the
sum of the bids of any player is C or greater, we must have that

X d_j a M - C;

which shows that the sum of the compensations does not exceed the sur-
plus.                                                                     r

5 Dividing the remaining surplus

According to Theorem 4, after the compensation procedure has established
envy-freeness, the remaining surplus S is given by

S ¼ M - C - X d_j b 0.

jAI

With S > 0, there is surplus left to distribute among the players. The distri-
bution schemes that are of interest here are those that maintain envy-freeness.
There is a convex and compact set of envy-free discounts to choose from.11
We consider two alternative methods for implementing a unique solution.

Equal distribution of the surplus or ‘‘ex-post equal payments’’

With an envy-free assessment matrix at the end of the compensation proce-
dure, no envy will be created if all entries in the matrix are increased by the
same amount. This is easily achieved through an equal distribution of the
remaining surplus among all players. Denoting players’ final discounts under
this equal distribution scheme by d_i^e , this gives

die ¼ di +¹ S.                                                               (6)

in

The equal distribution of the remaining surplus was demonstrated in our exam-
ple in Sect. 3. Despite the simplicity of this distribution scheme, some parties
may dislike the procedural asymmetry because they pay different amounts for
their bundles but receive identical shares of the remaining surplus.

Therefore, consider the following modification of the compensation pro-
cedure: parties are assigned bundles, but they do not pay in advance. Instead,
a (hypothetical) mediator finances the compensation procedure and charges
the group afterwards for total compensations and the cost C. The mediator

11 The set of envy-free prices is given by a convex polyhedron characterized by n²
inequalities that can be derived from the envy-free assessment matrix.

<<   12   13   14   15   16   17   18   >>

More intriguing information