Bidding for envy-freeness
747
Players’ demands under the utilitarian assignment (along the diagonal) are
satisfied through initial payments, which sum to 255. The total compensation
of 300 thus leaves an extra 45 to be granted to the players in the form of
bonuses. The assessment matrix can be computed by subtracting the diagonal
entry from each column.
The resulting initial assessment matrix is identical to the one in Table 2
where row i now shows Player i’s assessment of Player j’s bundle of chores.
Consequently, the remaining surplus is also the same as in the example of
Sect. 3. Hence, the compensation procedure together with the distribution
of the remaining surplus yields the same outcome, whether for the distribution
of goods with a total contribution, or for the distribution of chores with a
total compensation, or for a combination of goods and chores with a total
cost or compensation.
Numerical calculations for the average discount method
In what follows, (i)-(iv) denote the steps of the average discount method
algorithm.
Beginning with Player 1, the procedure places this player in set D (i). Since
Player 2 sees her bundle tied with that of Player 1 (see Row 2 of Table 4),
Player 2 is added to set D (ii). In further comparisons, one now finds that
Players 3 and 4 see their bundles tied with that of Player 2, so they must be
added to D as well (ii). With all players included in D, the remaining surplus is
divided equally among them (iii). The updated discounts are (5; 15; 15; 10),
and the procedure for Player 1 ends because the surplus is used up (iv).
Beginning with Player 2 (i), Players 3 and 4 must be added to set D (ii).
With only these players included in D, each one’s discount can be raised by 5
before Player 1 experiences envy (see Row 1 of Table 4). This leaves a remain-
ing surplus of 20 — 15 ¼ 5 (iii), so the procedure continues (iv). Player 1 now
sees her bundle tied with those of Players 3 and 4, so she must be added to D
(ii). The remaining surplus is divided equally among all players giving each an
additional 1.25 (iii). The discounts are (1.25,16:25; 16:25; 11:25), and the pro-
cedure for Player 2 ends (iv).
Beginning with Player 3 in set D (i), there is no player who feels tied with
this player (ii). Player 3’s discount can thus be raised by 5 without making any
other player envious (iii). With a remaining surplus of 20 — 5 ¼ 15, the pro-
cedure continues (iv). Now Player 1 is tied with Player 3, Player 2 is tied with
Player 1 and Player 4 is tied with Player 2, so they all must be added to D (ii).
The remaining surplus is divided equally, giving each player an additional 3.75
(iii). The discounts are now (3:75; 13:75; 18:75; 8:75), and the procedure for
Player 3 ends (iv).
Beginning with Player 4 in set D (i), Player 3 must be added because of
the tie with Player 4 (ii). The discounts of these two players can be raised
by 5 before Player 1 becomes envious (iii). With a remaining surplus of
20 — 10 ¼ 10, the procedure continues (iv). Now Player 1 is added to D and,
therefore, also Player 2, because of the tie with Player 1 (ii). The remaining