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



Bidding for envy-freeness

725


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.



More intriguing information

1. Deprivation Analysis in Declining Inner City Residential Areas: A Case Study From Izmir, Turkey.
2. The name is absent
3. Mortality study of 18 000 patients treated with omeprazole
4. Social Irresponsibility in Management
5. ENERGY-RELATED INPUT DEMAND BY CROP PRODUCERS
6. Regional dynamics in mountain areas and the need for integrated policies
7. An Attempt to 2
8. How Low Business Tax Rates Attract Multinational Headquarters: Municipality-Level Evidence from Germany
9. SAEA EDITOR'S REPORT, FEBRUARY 1988
10. Ultrametric Distance in Syntax
11. The name is absent
12. The name is absent
13. AN ECONOMIC EVALUATION OF THE COLORADO RIVER BASIN SALINITY CONTROL PROGRAM
14. Place of Work and Place of Residence: Informal Hiring Networks and Labor Market Outcomes
15. Three Strikes and You.re Out: Reply to Cooper and Willis
16. The name is absent
17. Regulation of the Electricity Industry in Bolivia: Its Impact on Access to the Poor, Prices and Quality
18. The name is absent
19. The name is absent
20. Happiness in Eastern Europe