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

C.-J. Haake et al.

Proof. We check:

∑⅜_t(i) = ]Γ(bi(B_π(₀)- b_π(i)(B_π(₀)₊ d_π(₀)

¼ ∑>‰)-M + £ dia ∑di;

which follows from the definition of M, the maximum sum of bids. The in-
equality is clearly an equality when p is the diagonal assignment.          r

We keep track of ‘‘chains’’ of envy with the following notation. We write
i ! j if j is the player that i envies the most (if there are several,pick one ar-
bitrarily). In this case aii <aij and aij is the largest entry in row i. The single
arrows thus only indicate maximum envy relations. We use a double arrow
i ) j if i envies no one but feels tied with jand this tie was the result of an
earlier compensation. Thus aii =aij, and these are the largest entries in row i.
Note that double arrows only keep track of created ties, and are not used for
ties occurring ‘‘by coincidence’’ (e.g., where a_ii =a_ij but this was not the result
of a previous compensation). In the sequel when we refer to ‘‘arrow’’ we shall
mean either a single or double arrow unless explicitly specified.

We form a directed graph G in which the vertices represent players and the
edges are given by the arrow relations between players.9 (We shall speak of
‘‘players’’ and ‘‘vertices’’ interchangeably in all that follows.) Throughout the
procedure, the directed graph G will change. Keeping track of how G evolves
is the key to showing that the procedure terminates.

Lemma 2. At any step in the procedure, the directed graph G contains no cycles.

Proof. If there were a cycle of single arrows, say i₁ ! i₂ ! ■ ■ ■ ! i_k ! i₁, then
ai1i1 < ai1i2

^ai2i2 < ^ai2i3                                                                                         (2)

.
.

aikik <aik i1 ;

and by adding these relations one would find that

^ai₁i₁ ^{+ a}i₂i₂ ⁺ ■■■ ^{+ a}i_ki_k < ^ai₁i₂ ^{+ a}i₂i₃ ⁺ ■■■ ^{+ a}i_ki₁ ;                               ⁽3)

which augmented by the other diagonal terms would contradict Lemma 1.

A nearly identical argument can be used for cycles in which some (but
not all) of the arrows are double; some of the envy inequalities in (2) would
become equalities, but the inequality (3) would remain strict as long as there
were a single arrow in the cycle.

The only other possibility is a cycle consisting entirely of double arrows.
But this cannot arise, because double arrows only originate from single arrows

9 It is important to note that our directed graph G is simpler than the graphs con-
structed by Aragones (1995) and Klijn (2000), since our procedure only keeps track of
maximum envy.

<<   7   8   9   10   11   12   13   >>

More intriguing information