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

Bidding for envy-freeness

the total cost for the group as a whole. This is not needed for an envy-free
solution, but it guarantees that a player will never have to pay more than her
bid.3

We consider two alternative methods for financing the necessary monetary
side-payments. In the method of ex-ante payments,players first pay the amount
they bid for the objects they receive. Everyone thus begins with the same ad-
vantage, viz. none, and there is an aggregate amount of money left to divide
among the players. Under the method of ex-post payments, players submit
payments only after the monetary compensations needed to establish envy-
freeness are determined via the procedure. A distinctive feature of both meth-
ods is that the resources for compensation are generated by the group itself.
Because we find ex-ante payments more intuitive for players, we focus mainly
on this method, but we do provide a comparison of the outcomes.

In Sect. 2, we formulate the first step of our procedure: an assignment of
objects to players that maximizes the sum of players’ utilities. We call this the
utilitarian assignment.4 When the bundling of objects is restricted, the utili-
tarian assignment will generally cause envy among the players.

In Sect. 3, we describe non-technically the individual steps of the compen-
sation procedure which will eliminate envy by using the surplus from players’
initial payments. We demonstrate its application with a numerical example
that we use throughout the paper.

The formal characterization of our compensation procedure and thus a
constructive existence proof for an envy-free allocation is given in Sect. 4.
Here we prove that there is always at least one player who is non-envious at
the start and then show how our procedure successively eliminates the envy
of players who are envious of non-envious players. In contrast to the algo-
rithms of Aragones (1995) and Klijn (2000), our procedure does not need to
keep track of all envy relations, since it uses only maximum envy.5 A further
feature distinguishing our compensation procedure from Klijn’s algorithm
is that it requires only minimal financial resources to establish envy-freeness.
The necessary amount is automatically determined through the compensa-
tions.

In Sect. 5, we study alternative methods of dividing the surplus that gen-
erally remains after envy-freeness is established.6 The simplest way to obtain

3 Brams and Kilgour (2001) use a similar, but stricter constraint, basically for the same
purpose.

4 The same starting point is chosen by Steinhaus (1948), Aragones (1995), or Brams
and Kilgour (2001). A notable exception is Klijn (2000).

5 Of course all envy relations are assessed by players within the procedure in order to
determine maximal envy; but the non-maximal assessments are not retained for the
procedure.

6 There will generally be an infinite number of envy-free outcomes to choose from.
And, as Tadenuma and Thomson (1991) verify, there exists no proper sub-solution
satisfying the notion of consistency. A sub-solution is consistent in their sense if it
allocates the objects and money received by a subset of players in the same way as the
solution assigns total resources to all players.

<<   1   2   3   4   5   6   >>

More intriguing information