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



746


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

P1

I—501

80

90

80

P2

40

|—601

85

90

P3

100

60

I—751

65

P4

50

65

90

70

Initial reward               50               60               75

70

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



More intriguing information

1. The name is absent
2. Notes on an Endogenous Growth Model with two Capital Stocks II: The Stochastic Case
3. Opciones de política económica en el Perú 2011-2015
4. Modelling Transport in an Interregional General Equilibrium Model with Externalities
5. From Communication to Presence: Cognition, Emotions and Culture towards the Ultimate Communicative Experience. Festschrift in honor of Luigi Anolli
6. Standards behaviours face to innovation of the entrepreneurships of Beira Interior
7. The name is absent
8. The name is absent
9. Mergers under endogenous minimum quality standard: a note
10. The Folklore of Sorting Algorithms