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.