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

C.-J. Haake et al.

no individual will wish to trade shares with anyone else.1 In proving existence
of envy-free solutions, particular attention has been given to the development
of constructive proofs that yield implementable algorithms to find the desired
allocation. This aspect is emphasized by Alkan et al. (1991) and Su (1999).2
Because both these approaches assume non-linear utility in money, the algo-
rithms are not finite; instead they converge on an envy-free solution. Exact
solutions can be obtained using the algorithms of Aragones (1995) and Klijn
(2000) who assume that players’ preferences for money are characterized by
linear utility functions. This is a strong restriction, but one that seems appro-
priate for the present context, nevertheless.

Our approach in this paper is not only constructive, but we consider it to
be procedural as well. In the context of fair division, we view a procedure as
featuring the following characteristics: it is intuitive, meaning that each step
must be easy to understand; it is plausible, meaning that each step must be
simple to argue; and it is manageable, meaning that each step must be straight-
forward to compute. We see these subjective criteria as relevant for the prac-
tical implementation of a fair-division outcome, in particular when parties in
real life prefer to establish fairness by themselves, rather than trust the ‘‘magic’’
of a computer algorithm.

Knaster and Steinhaus (1948) proposed a fair-division method that is pro-
cedural in this sense, as it is simple to apply and largely intuitive. However, as
Brams and Taylor argue as they revisit this approach, the procedure does not
ensure envy-freeness for more than two players. In a more recent approach,
Brams and Kilgour (2001) characterize a procedure that assigns a given num-
ber of objects to the same number of players e‰ciently, establishing fairness
through internal ‘‘market prices’’. The procedure is intuitive, plausible, and
simple to manage. But for more than three players it also does not guarantee
envy-freeness.

In the following sections we develop a compensation procedure that estab-
lishes envy-freeness for any number of players and a possibly different number
of objects. We thus extend the Knaster-Steinhaus procedure, while preserving
envy-freeness for any number of players. The procedure eliminates envy in
rounds by compensating envious players. It is fully descriptive and says explic-
itly which compensations should be made, and in what order. The procedure
mimics and thus supports a natural mediation process with the objective of
implementing an envy-free outcome. We formally characterize the properties
of the procedure and illustrate how it works in practice.

We assume that players can articulate their preferences over bundles of
objects through monetary bids and that their utility of money is linear. In
addition we impose a qualification condition for each person taking part in
the fair division, requiring that her valuations of all bundles sum to at least

1 The concept of envy-freeness was first used in an economic context by Foley (1967),
although under a different label.

2 The algorithm of Su (1999) is even interactive in the sense that it sequentially gives
each player the opportunity to choose her favorite alternative at evolving prices.

<<   1   2   3   4   5   >>

More intriguing information