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

Bidding for envy-freeness

for any permutation p. Hence B is an e‰cient assignment of the n bun-
dles.                                                                     r

So, what if the initial assignment B a B is not e‰cient? With exogenously
given bundles, the utilitarian assignment B can be obtained from B through
a permutation of bundles. This is equivalent to the setting studied by Klijn
(2000) who assumes that the number of objects equals the number of players,
with the additional restriction that each player must receive one object. If this
is the case, Lemma 7 implies that envy-freeness can only be established for a
utilitarian assignment.16

Consider an arbitrary assignment B A B.IfB results in an e‰cient alloca-
tion of bundles, the compensation procedure will lead to envy-free discounts.
If the assignment is not e‰cient, then Lemma 7 implies that the compensation
procedure cannot establish envy-freeness, so it must lead to an envy cycle, i.e.,
during the compensation procedure the envy graph exhibits a cycle with at
least one single arrow.

Theorem 6. Let B A B be an ine‰cient assignment of n given bundles. Applying
the compensation procedure will then create an envy cycle (in the directed graph
G) after at most n — 1 compensation rounds. Cycling bundles in the opposite
direction of the arrows (re-assigning to each player in the cycle the bundle of the
player she envies or previously envied) will increase the sum of players’ utilities.

Proof. We begin by proving the first claim. If the directed graph G of the inef-
ficient assignment B contains cycles in single arrows (i.e., before compensa-
tions are made), the claim trivially holds. Assume therefore that G contains
no envy cycles in single arrows. In that case there is at least one player who is
non-envious.

The compensation procedure eliminates envy by compensating envious
players. Throughout the procedure the directed graph G evolves, with single
arrows being converted into double arrows and new single arrows emerging
through the creation of new envy. In Lemmas 3 and 4 the notion of a level
only applies to a non-cyclical graph, but otherwise both lemmas are valid re-
gardless of whether or not the assignment is e‰cient. Assume by way of con-
tradiction that an envy cycle is never created. Then the procedure must ter-
minate in at most n — 1 rounds in an envy-free solution. This contradicts
Lemma 7. Thus after at most n — 1 rounds the procedure must create a cycle
(consisting of at least one single arrow and the rest double arrows) in the
directed graph G.

In order to establish the second claim, consider the situation where a cycle
is created, in which a non-envious player k0 becomes envious of a newly com-
pensated player kl. (Note that k0 does not have to be a root in G.) The cycle in
G has the following structure:

kl )■■■) kɪ ) ko —! kl ; 1 a l a n — 1;

16 This is equivalent to a result established by Svensson (1983).

<<   18   19   20   21   22   23   24   >>

More intriguing information