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

C.-J. Haake et al.

a unique outcome is to divide the surplus equally. However, this always leads
to an outcome on the boundary of the set of envy-free prices that favors a
particular player. We therefore propose an alternative method that implements
a unique outcome, generally in the interior of the envy-free set, thus treating
players more symmetrically.

In Sect. 6, we allow the initial assignment of exogenously given bundles
to be ine‰cient (i.e., non-utilitarian with respect to those bundles). We find
this aspect crucial, because an e‰cient assignment may be di‰cult to find
in practice if the fair-division problem involves many players and objects.
We show how our compensation procedure is easily adapted to non-
utilitarian initial assignments. We use the fact that envy-freeness requires an
e‰cient assignment of bundles (cf. Svensson 1983). If the assignment is in-
e‰cient, our envy-reducing procedure will create an envy cycle indicating a
cyclical trade of bundles that increases the sum of players’ utilities; this is
analogous to the permutation procedure of Klijn (2000). Strict application
of the compensation procedure thus produces cyclical trades of bundles lead-
ing to an e‰cient assignment, and then establishes envy-freeness as described
above.

Section 7 concludes with some practical considerations. The Appendix
contains numerical examples that illustrate the analysis.

2 Characterization of a utilitarian assignment

We consider a group of players I ¼f1; ...; ng who wish to assign a set of
objects K ¼f1; ...; mg among themselves in an envy-free fashion.

Assumption 1. Players value bundles of objects in a common divisible unit of
account, e.g., money.

Each player i A I can express her valuations of bundles Bi J K of objects
through (monetary) bids, which we characterize by functions bi : 2^K ! R.
Note that Assumption 1 does not say anything specific about the relationship
between a player’s valuation of a bundle and her valuations of the individual
objects contained within. In specific cases, however, players may have addi-
tively separable preferences over the objects in K, such that the value of a
bundle simply equals the sum of values of the individual objects, i.e., b_i∙(B_j∙) ¼
Pk A B biðk) ði; j A I), where bi : K ! R denotes a player’s bid for specific
objects. Moreover, as we will see below, when players have linear preferences
over sub-divisions of objects that are divisible,the outcome of our fair-division
procedure is the same whether or not K contains divisible objects.

We assume no specific relationship between the number of objects and the
number of players - this can be included through additional restrictions
(addl. restr.) on the objects. The group’s assignment determines the bundle
Bi J K of objects that each player i receives. Possible assignments are char-
acterized by

<<   1   2   3   4   5   6   7   >>

More intriguing information