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

C.-J. Haake et al.

Table 1. Players’ bids for bundles

Table 2. The initial assessment matrix

Table 3. The modified assessment matrix

the diagonal entry from each column. In Table 2, row i then shows Player
i ’s assessment of Player j’s bundle. We keep track of discounts in a separate
row.

The assessment matrix in Table 2 shows (by comparing entries in each
row) that Player 2 envies Player 1 (a22 < a21) and Player 3 envies Player 4
(a₃₃ < a₃₄). Therefore we must compensate Player 2 by giving her a discount
of 10, and Player 3 a discount of 5. To recalculate the assessment matrix, we
may add 10 to column 2 and add 5 to column 3. The new assessment matrix
is given in Table 3.

Now both Player 3 and Player 4 envy Player 2, and Player 2 feels tied with
Player 1 (who remains non-envious). We must compensate Player 3 and Player
4 by giving them both additional discounts of 5. Adding 5 to both columns 3
and 4, we obtain Table 4.

<<   <   5   6   7   8   9   10   11   >   >>