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

Bidding for envy-freeness

731

Table 4. The envy-free assessment matrix

Now all envy has been eliminated, since each diagonal element is the largest
entry in its row. The discounts used 25 units of the surplus, and the remain-
ing surplus of 20 can be equally divided among the four players, yielding
total discounts given by d ¼ (5, 15; 15; 10). This gives final envy-free costs of
c ¼ д45; 25; 10; 20).

It is important to note that, in formulating the compensation procedure,
we do not make any assumptions concerning the signs of players’ bids bi or
their contributions ci . Therefore, our procedure can also be applied to sit-
uations where the objects are burdens for which the group as a whole receives
a compensation (C < 0). Players’ negative bids are then requested payments
that express their disutility of accepting these burdens, and Assumption 3 states
that a player is qualified if her demands for bearing all burdens do not exceed
the total compensation, i.e., —bi∙(K) a —C. We provide an example for the
division of burdens in the Appendix.

More generally, our procedure can be applied to fair-division problems that
involve both goods and burdens. For example, a group of individuals that
decides to share a house cannot only derive a fair allocation of rooms and
rents, but they can also include all the (group’s) chores that come with the
house (e.g., lawn mowing, cleaning, cooking, etc.). Of course, if there is no
extra compensation, the qualification constraint (Assumption 3) becomes more
binding as chores are added. But this is only plausible - in order to qualify, a
housemate must not only be willing to pay the necessary rent, she must also
be willing to perform the necessary chores.

4 Properties of the compensation procedure

We now show that our procedure works as indicated. One property of the as-
sessment matrix A is crucial in all that follows. We define a permutation sum
of an n x n matrix A to be any sum of the form Pi ɑi-p(iɔ, where p : I ! I is a
permutation ofn elements. Thus a permutation sum picks one element of each
column and row and forms their sum.

Lemma 1. At any step of the procedure, the largest permutation sum of A occurs
along the diagonal.

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