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

Bidding for envy-freeness

(double arrow). Have all players return any compensations they have re-
ceived, and repeat Step 2 to restart the compensation procedure.

4. If there are envious players, perform a round of compensations: identify
those players whose maximum envy is directed towards a non-envious
player. Compensate them by their maximum envy difference, thus making
them non-envious. Then recalculate the assessment matrix (but only after
all the compensations have been made in this round), and repeat Step 2.

5. Have each player pay an equal share of the total compensations and the
total cost C.

We provide an example of the modified compensation procedure in the Ap-
pendix.

It is important to note that the procedure as formulated above cycles to a
utilitarian assignment and establishes envy-freeness only for n exogenously
given bundles. In particular, when each bundle contains only a single object,
the final assignment will be utilitarian. In our more general framework,
though, an assignment does not require the same number of objects as players.
Consequently, an assignment is non-utilitarian not only when the n bundles of
the assignment are allocated ine‰ciently, but also if the m objects are bundled
ine‰ciently. Since cyclical trades under the compensation procedure involve
complete bundles of objects, players may thus still wish to trade individual
objects when the procedure is finished, even though they will not want to trade
complete bundles. However, this type of envy will be di‰cult to identify under
the compensation procedure, because the discounts that players receive apply
only to their complete bundles; they cannot be broken down into partial dis-
counts and associated with individual objects. The compensation procedure
thus establishes envy-freeness for the highest aggregate utility that any player
can identify. In order to obtain an e‰cient bundling of objects, players may
still have to resort to computational support in order to improve their best
initial guess.

7 Conclusions

Our objective in this paper was to formally develop a practical procedure for
multilateral problems of fair-division. Our procedural approach eliminates
envy in a ‘‘natural’’ way: it first identifies the players who are non-envious (we
showed that there will always be at least one if the assignment of bundles
is e‰cient), and then it compensates those players whose maximum envy is
directed towards non-envious players. By first beginning with an e‰cient as-
signment, we formulated the procedure for establishing envy-freeness using
intuitive, plausible, and manageably simple steps. We then showed that the
procedure is also capable of guiding parties to an e‰cient assignment when
the bundles are fixed. Moreover, the outcome of the compensation procedure
is the same no matter which e‰cient assignment is eventually reached.

In our analysis, we placed no bound on the level of individual compensa-

<<   20   21   22   23   24   25   26   >>

More intriguing information