744
C.-J. Haake et al.
where the cycle may contain more than one single arrow. Due to the com-
pensations of (not necessarily all) ancestors of kl in the graph G,
dkι ¼ bkι (Bki ) bkι~ι (Bki~1 ) + dki-ɪ
l
a X X ½bkh ð Bkh ι) ⅛-1 (Bkh 1)] + dko :
h¼1
However, since k0 is now envious of kl ,
dko < bko ð Bkl) ⅛ (Bki) + dkι ;
and therefore,
X2bkh(Bkh) < bko(Bkι) + X^bkh(Bkh-1 );
h¼0 h¼1
which shows that a reassignment of bundles in the opposite direction of the
arrows strictly increases the sum of players’ utilities. r
Applying the compensation procedure to any assignment B A B, for which
the directed graph G contains no envy cycles, will either lead to envy-freeness
or to a cycle in G that allows a utility-increasing reassignment of bundles.
Repeated application of the compensation procedure (restarting with zero dis-
counts after each permutation of bundles), leads to an envy-free e‰cient out-
come with respect to the given bundles, since the number of assignments is
finite. Note that, unlike the permutation procedure of Klijn (2000), our pro-
cedure does not need to keep track of all envy relations. This is because the
single arrows in the directed graph identify only maximum envy, i.e., possible
cycles in non-maximum envy are simply ignored.
Since the computation of assessment matrices requires additional calcu-
lations when the assignment changes during the procedure, we use the com-
pensation procedure with ex-post equal payments, where initial assessments
are made directly on the basis of players’ bids. From the previous section, we
know that this procedure also satisfies Theorems 1-3. The modified compen-
sation procedure consists of the following steps.
The compensation procedure for an arbitrary assignment
1. Consider all players to be non-envious at the start. For n exogenously given
bundles, assign to each player an initial bundle. (For practical reasons, one
could let each player state her ‘‘best guess’’ of a utilitarian assignment and
then choose the assignment with the highest sum of bids as the initial start-
ing point.) Use the bid matrix as the initial assessment matrix.
2. Use the assessment matrix to identify each player’s maximum envy. If no
player is envious, skip to Step 5.
3. If a previously non-envious player has become envious, check for an envy
cycle. If a cycle exists, re-assign bundles by giving each player in the cycle
the bundle of the player she envies (single arrow) or previously envied