Bidding for envy-freeness
729
Let aij denote Player i’s assessment of the value of Player j’s bundle minus
its cost:
aij ¼ bi(Bj )- Cj ¼ bi (Bj )~ bj (Bj ) + dj ; i; j A I ; (1)
where dj is the discount that Player j has received during the procedure (at the
start dj ¼ 0). We call A ¼(aij) the assessment matrix. Note that if aii < aij
then Player i will experience envy for Player j. Without additional restrictions
on bundles, the utilitarian assignment simply assigns each object to the player
who values it most. The assessment matrix will thus be envy-free from the
start, since aii b aij . With additional restrictions, however, this will generally
not be the case, and envious players will need to be compensated. The com-
plete compensation procedure is described as follows.
The compensation procedure for a utilitarian assignment
1. Assign bundles to players using the utilitarian assignment. Each player ini-
tially contributes her bid on her assigned bundle, yielding a pool of size M
from which the cost C is paid.
2. Calculate the assessment matrix. Note that there will always be at least
one player who experiences no envy (see Theorem 1). If all players are non-
envious, skip to Step 5.
3. Now perform a round of compensations: use the assessment matrix to iden-
tify all players whose maximum envy is directed towards a non-envious
player, and compensate these individuals from the surplus by their maxi-
mum envy difference. 8 Then recalculate the assessment matrix (but only
after all the compensations have been made in this round).
4. Perform additional compensation rounds until all envy is eliminated. (Theo-
rem 2 shows that at most (n — 1) compensation rounds will be needed.)
5. The sum of the compensations made in Steps 3 and 4 is minimal (see The-
orem 3), and it will never exceed the surplus M — C (see Theorem 4).
Therefore distribute any remaining surplus in a way that maintains envy-
freeness; e.g., one could simply divide it equally among all players. (Sect. 5
discusses an alternative method for post-envy allocation of the remaining
surplus.)
To illustrate we give an example. Suppose there are four players (denoted
Pi) who submit bids for a joint venture that has a total cost of C ¼ 100. The
utilitarian assignment determines four bundles (denoted Bi) for which players
have the valuations given in Table 1.
The bids in the utilitarian assignment (the framed entries along the diago-
nal of Table 1) are collected as initial payments. Since they sum to 145, after
paying the cost of 100, there is a surplus of 45 left to return to the players in
the form of discounts. The assessment matrix can be computed by subtracting
8 Alternatively, one could compensate all envious players. However, this would require
more compensations in each round, but not fewer rounds.