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



Bidding for envy-freeness

743


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 n1 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).



More intriguing information

1. Expectations, money, and the forecasting of inflation
2. The name is absent
3. The name is absent
4. Stillbirth in a Tertiary Care Referral Hospital in North Bengal - A Review of Causes, Risk Factors and Prevention Strategies
5. QUEST II. A Multi-Country Business Cycle and Growth Model
6. REVITALIZING FAMILY FARM AGRICULTURE
7. The name is absent
8. The name is absent
9. Modelling the Effects of Public Support to Small Firms in the UK - Paradise Gained?
10. The name is absent
11. The name is absent
12. Moffett and rhetoric
13. The name is absent
14. Olfactory Neuroblastoma: Diagnostic Difficulty
15. The name is absent
16. An Incentive System for Salmonella Control in the Pork Supply Chain
17. Poverty transition through targeted programme: the case of Bangladesh Poultry Model
18. The Context of Sense and Sensibility
19. Quelles politiques de développement durable au Mali et à Madagascar ?
20. The name is absent