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

C.-J. Haake et al.

tions. Consequently, we do not preclude the possibility that an individual may
end up being paid by the others to take a bundle of goods. In the context of fair
division we do not find this problematic at all. Indeed, if a group does not wish
to exclude any of its members, then there is no reason why the group should
not subsidize a member for receiving an undesired bundle. Moreover, the qual-
ification constraint guarantees that subsidization is never a consequence of a
player’s insu‰cient valuation of the complete set of objects to be distributed.

As with all cooperative procedures, our compensation scheme is theoreti-
cally vulnerable to strategic manipulation. However, practically speaking, this
requires detailed information on the other players’ preferences. If players’ bids
are disclosed simultaneously, strategic bids under incomplete information can
easily backfire: an untruthful player may have to pay more than what she
thinks her bundle is worth or may envy some other players for their bundles.
By contrast, since a player’s compensation is based on her own subjective
assessments, truthful behavior will always guarantee her envy-freeness, regard-
less of the others’ behavior. In practice, this insurance creates a disincentive
for attempting to distort one’s preferences.

Implemented as a computer algorithm, our compensation procedure is
polynomially bounded, thus making it comparable to alternative algorithms.
But this is not our point: as a procedure, it is not meant to be run on a machine;
instead it is designed to be used live in a mediation process.

Appendix

Envy-free division of burdens

Consider the following example of four players that have to divide a number of
chores among each other. The total compensation for all chores is: —C ¼ 300.
The utilitarian assignment bundles the chores and thereby determines the min-
imum total requested payment — M > 0. Table 5 shows players (negative) bids
for the four bundles of burdens.17

Table 5. Players’ requested payments

Bi

B2

B3

B4

P4

—50

—65

—90

70

17 The entries in Table 5 are equal to the entries in Table 1 minus 100.

<<   21   22   23   24   25   26   27   >>

More intriguing information