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

Table 7. Players’ valuations of bundles after the first round of compensations

surplus is divided equally among all players, giving each an additional 2.5 (iii).
The discounts are (2.5; 12:5; 17:5; 12:5), and the procedure for Player 4 ends
(iv).

Eliminating envy-cycles with the compensation procedure

The following example shows how our modified compensation procedure
with ex-post equal payments works for a non-utilitarian assignment. Consider
the bid matrix shown in Table 6, which reproduces Table 1 with columns
exchanged. The framed bids indicate the non-utilitarian assignment. The cor-
responding envy graph, constructed on the basis of bids, is denoted by G^~.

Strictly following the compensation procedure, Players 1 and 4 are now
compensated by 30 and 15. (Player 3 is not yet compensated, because she
envies an envious player.) Accordingly, the bid matrix changes to Table 7.

Now Players 3 and 4 envy Player 1. In order to eliminate their envy, they
receive compensations of 40 and 10, respectively. The result is shown in Table
8. However, this second round of compensations involving the last envious
players (3 and 4) creates new envy: Player 4 feels tied with 1 and Player 1 feels
tied with 2, but Player 2 now envies 4, thus creating a cycle in the directed
graph G^~.

The modified procedure now calls for a trade in the opposite direction of
the arrows in G^~. Hence, Player 4 gives her bundle to Player 2, Player 2 gives
her bundle to Player 1, and Player 1 gives her bundle to Player 2. In addi-

<<   <   23   24   25   26   27