Bidding for envy-freeness
741
After the algorithm has been applied for each player i A I , determine the
average extreme discount of Player i:
dia ¼ n X ⅛: (1D
njAI
We demonstrate the calculation of average discounts by using our example
of Sect. 3. The final outcome of the compensation procedure with ex-ante
payments is shown in Table 4, with a remaining surplus of S ¼ 20 to be dis-
tributed among the four players. Beginning with Player 1, the final discounts
are (5; 15; 15; 10); beginning with Player 2, the final discounts are (1:25; 16:25;
16:25; 11:25); beginning with Player 3, the final discounts are (3:75; 13:75;
18:75; 8:75); and beginning with Player 4, the final discounts are (2:5; 12:5;
17:5; 12:5). A detailed derivation of these discounts is given in the Appendix.
Taking all four extreme discount distributions into account, the average dis-
counts, given by Eq. (11), are d a ¼ (3:125; 14:375; 16:875; 10:625), yielding
final costs of c ¼ (46:875; 25:625; 8:125; 19:375).
In all four cases of individual discount maximization, as soon as Player 1 is
added to D, all other players are included as well, and the remaining surplus is
divided equally among the whole group. This is because Player 1 is the root of
a unique tree of double arrows at the end of the compensation procedure. So
if her discount is increased, all other players must benefit equally in order to
avoid new envy.
More generally, when there are several roots, as soon as the last uncom-
pensated player i with di ¼ 0 joins D, the whole group must belong to D,
i.e., D ¼ I. At this point, however, the aggregate discounts cannot yet have
exceeded the surplus if all players met the qualification constraint (Assump-
tion 3) - this follows from the proof of Theorem 4.
The maximization ofa specific player i’s discount according to the method
above could also be interpreted as the outcome of a modified compensa-
tion procedure implemented by a biased mediator who favors Player i. This
only requires modifying Step 3 of the compensation procedure: whenever the
favored player is compensated for her maximum envy and then, if noone
envies her, increase her discount as much as possible without raising the envy
of any other player.15 Compensate each other player the same as before.
Distribute the remaining surplus according to the average discount method,
favoring the same player. This biased procedure can be applied for each player.
The average over all biased compensations thus yields the outcome of the av-
erage biased mediator.
Recall that under an equal distribution of the remaining surplus, given by
Eq. (6), each player received an increment of 5 to her discount. In the pre-
15 In the directed graphs used in the proofs of Lemmas 2-4, a double arrow i ) j
then means that i envies no one, but feels a (weak) advantage over j, and this lead was
the result of an earlier compensation. Thus aii b aij , and these are the largest entries in
row i. As before, double arrows only keep track of created leads. Note that the biased
compensations during the compensation procedure do not change the envy graph.