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.