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



Soc Choice Welfare (2002) 19: 723-749


Social Choice

JndWelfare


© Springer-Verlag 2002

Bidding for envy-freeness: A procedural approach to
n-player fair-division problems

Claus-Jochen Haake1, Matthias G. Raith2, Francis Edward Su3

1 Institute of Mathematical Economics, University of Bielefeld, P.O. Box
100131, 33501 Bielefeld, Germany (e-mail:
[email protected],
[email protected])

2 Department of Economics, University of Magdeburg, P.O. Box 4120,

39016 Magdeburg, Germany (e-mail: [email protected])

3 Department of Mathematics, Harvey Mudd College, Claremont, CA 91711, USA
(e-mail:
[email protected])

Received: 6 March 2000/Accepted: 21 May 2001

Abstract. We develop a procedure for implementing an e‰cient and envy-free
allocation of m objects among n individuals with the possibility of monetary
side-payments, assuming that players have quasi-linear utility functions. The
procedure eliminates envy by compensating envious players. It is fully descrip-
tive and says explicitly which compensations should be made, and in what
order. Moreover, it is simple enough to be carried out without computer sup-
port. We formally characterize the properties of the procedure, show how it
establishes envy-freeness with minimal resources, and demonstrate its appli-
cation to a wide class of fair-division problems.

1 Introduction

In this paper we consider problems of fair division, in which a group of
individuals must decide how to allocate several objects (goods or burdens)
‘‘fairly’’ among the group’s members, given the possibility of (monetary) side-
payments. A variety of situations fit into this setting: heirs inheriting an estate,
employees splitting a list of duties, developers staking claims in a new frontier,
or students renting a house together. In many cases, such problems can also
involve additional costs or compensations for the group as a whole.

As a basic notion of fairness, we focus on envy-freeness, which means that

We would like to thank Steven Brams and Marc Kilgour for stimulating discussions,
and we are grateful to an anonymous referee for helpful comments. Financial support
by the 'Ministerium fur Wissenschaft und Forschung, NRW’ (Raith) and the ‘Gra-
duiertenkolleg’ Mathematical Economics, University of Bielefeld’ (Su) is gratefully
acknowledged.



More intriguing information

1. The name is absent
2. Integrating the Structural Auction Approach and Traditional Measures of Market Power
3. Endogenous Determination of FDI Growth and Economic Growth:The OECD Case
4. The name is absent
5. The name is absent
6. The name is absent
7. The name is absent
8. Sustainability of economic development and governance patterns in water management - an overview on the reorganisation of public utilities in Campania, Italy, under EU Framework Directive in the field of water policy (2000/60/CE)
9. AGRICULTURAL TRADE IN THE URUGUAY ROUND: INTO FINAL BATTLE
10. The name is absent
11. Can a Robot Hear Music? Can a Robot Dance? Can a Robot Tell What it Knows or Intends to Do? Can it Feel Pride or Shame in Company?
12. Are Japanese bureaucrats politically stronger than farmers?: The political economy of Japan's rice set-aside program
13. Economie de l’entrepreneur faits et théories (The economics of entrepreneur facts and theories)
14. Models of Cognition: Neurological possibility does not indicate neurological plausibility.
15. Une Classe de Concepts
16. PRIORITIES IN THE CHANGING WORLD OF AGRICULTURE
17. Altruism and fairness in a public pension system
18. The name is absent
19. Does South Africa Have the Potential and Capacity to Grow at 7 Per Cent?: A Labour Market Perspective
20. The name is absent