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



726


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 b
i : 2K ! 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., bi
(Bj) ¼
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
B
i J K of objects that each player i receives. Possible assignments are char-
acterized by



More intriguing information

1. A dynamic approach to the tendency of industries to cluster
2. The name is absent
3. Examining the Regional Aspect of Foreign Direct Investment to Developing Countries
4. The name is absent
5. WP 92 - An overview of women's work and employment in Azerbaijan
6. Moi individuel et moi cosmique Dans la pensee de Romain Rolland
7. The name is absent
8. The name is absent
9. Effects of a Sport Education Intervention on Students’ Motivational Responses in Physical Education
10. The name is absent