Bidding for envy-freeness
737
for all i; j. Summing the above equation over all j, one obtains that for all i,
Xdj - di) a M - Xbi(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 di ¼ 0, and since the
sum of the bids of any player is C or greater, we must have that
X dj 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 dj 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 die , this gives
die ¼ di +1 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 n2
inequalities that can be derived from the envy-free assessment matrix.