We define a red-black game G to be a labeled bipartite weighted graph with
non-negative weights, where each edge has a label drawn from a given alphabet.
We refer to the nodes on one side as "red" and the other nodes as "black."
The color of an edge is defined to be the color of its source node.

There are two players, Red and Black.  The state of the game is one node of
the graph.  At each step, the player whose color matches the color of the
state changes the state by using one edge of the graph, and pays a cost
equal to the weight of that edge.  We say that the game is C-competitive
if there exists a constant K and Red can play the game so that, starting from
any node, no matter what Black does, cost_red <= K + C*cost_black.

We say that "the competitiveness of G is C" if G is C-competitive, and
for any C' < C, G is not C'-competitive.

For a given C, we define a C-potential to be a function from the nodes of
the graph to the real numbers which satisfies the following conditions,
which we call the "pullback conditions."

1) If e = (x,y) is a black edge, then Phi(x) >= Phi(y) - C*cost(e)
2) For any red node y, there is a red edge f = (y,z) such that
Phi(y) >= Phi(z) + cost(f)

We define an edge to be "exact" with respect to Phi if the inequalities are
equalities.  That is, if e = (x,y) is a black edge, it is exact if
Phi(x) = Phi(y) - C*cost(e), while if f = (y,z) is a red edge, it is exact
if Phi(y) = Phi(z) + cost(f).  We say that Phi is an "exact C-potential" if
Phi is a C-potential and if every node has an exact out-edge.

Theorem 1.  For any fixed C, the game is C-competitive if and only if
there is a C-potential.

We define a subgraph Z of G which we call the "no-cost subgraph of G with
respect to Phi." If the state of the game is in Z, Red can force it to remain
in Z and pay nothing forever, unless Black makes a bad move.  Z is defined to
be the maximum subgraph of G such that:

1) If x is a black node in Z, then all exact out-edges of x are in Z.
2) If y is a red node in Z, then there is at least one exact out-edge of y
in Z.
3) All red edges in Z have zero cost.

Theorem 2.  The competitiveness of G is C if and only if the following two
conditions hold:

1) G has an exact C-potential Phi.
2) The no-cost subgraph of G with respect to Phi is empty.
