Bidding for envy-freeness
733
(as compensations are made to envious players). Thus if there were a cycle of
double arrows, by stepping backwards through the procedure one would find
a prior round in which that cycle contained a single arrow - a possibility that
was ruled out above. r
The outdegree of a vertex represents the number of arrows that originate
at a vertex. Because of the way we defined arrows, every vertex in G has an
outdegree of at most 1. Hence there is a uniquely defined path that ‘‘flows’’
from any given vertex. Since G cannot have any cycles at any step in the
procedure, we deduce that G must always be a disjoint set of directed trees,
each of which has a unique root, a vertex of outdegree 0 to which all other
vertices flow. Roots of trees correspond to non-envious players who have not
yet experienced envy.
Theorem 1. At the start there is at least one player who will remain non-envious
throughout the entire procedure.
Proof. A vertex with no arrow is a root, and a vertex with a single or double
arrow corresponds to a player who experiences or has experienced envy. It
follows that the outdegree of a vertex can never decrease - once a root earns
an arrow it can never become a root again.
If by the end of the procedure there were no roots, then any path following
the arrows in G would eventually cycle, contradicting Lemma 2. Thus there is
a root which must have been a root throughout the entire procedure, corre-
sponding to a person who remains non-envious. r
Because every vertex in a tree has a unique path to its root, we may classify
vertices in G by ‘‘levels’’ - a level 0 vertex is a root, and a level k vertex is one
that is k arrows away from the root of its tree. A vertex i is said to be an an-
cestor of vertex j in the tree if there is a chain of arrows flowing from j to i.
Thus the root of a tree is an ancestor of every other vertex in the tree. The
ancestral path of vertex i is the set of all vertices on the path from i to its root
- including the root, but not including i. (Note that the ancestral path does
not depend on the type of arrows along the path.) Vertices may change levels
as G evolves throughout the procedure.
Lemma 3. During a compensation round, if a player P changes her ancestral
path, the new path must contain a newly compensated player Q between P and
the root. Thus in the new graph, P will have a higher level number than Q.
Proof. During a compensation round, the only new envy that can be intro-
duced is directed at players receiving compensations during that round. Thus
if player P or any of her ancestors changes her maximum envy (hence the direc-
tion of her arrow) to a newly compensated player Q, then after the compen-
sation round, the path flowing from P must pass through Q. From the defini-
tion of level this means that P will have a higher level number than Q. r
Lemma 4. After k compensation rounds, there are no envious players on levels
0 through k.