Behavioral Potentials. Let M be a metrical task system. We define a "behavioral C-potential" as to be a partial function Phi, whose domain is a set of pairs of the form (w,x) which we call "special pairs," where w is a work function and x is a state such that 1. There is a special pair (w^0,x^0), where x^0 is the start state. 2. For any special pair (w,x) and any state z, Phi(w,x)> = 0 and w(z) >= 0. 3. If (w,x) is any special pair and r is a request and if w' = w update r, then there exist special pairs (w_1,x_1), ... (w_n,x_n) and probabilities lambda_1 , ... lambda_n, where Sum_i lambda_i = 1, and a constant K such that 3(a). For any state z, Sum_i lambda_i w_i(z) + K <= w'(z). 3(b). Phi(w,x) >= Sum_i lambda_i*{||x,x_i||+r(x_i)+Phi(w_i,x_i)} - K*C. Theorem: If there is a behavioral C-potential for a metrical task system M, then there is a randomized online algorithm for M which is C-competitive against the adaptive online adversary. Proof: Suppose that Phi is a behavioral C-potential for M. We will define the current state x^t of the algorithm after t steps, as well as a work function w^t which we call the "Las Vegas work function at step t," in such a way that (w^t,x^t) is always a special pair. Initially, the calA's state is x^0, and the Las Vegas work function is w^0. Suppose that x^{t-1} and w^{t-1} are the state and the Las Vegas work function at step t-1. Let r^t be the request at step t. We describe how to pick the next state x^t and the next Las Vegas work function w^t. Let w' = w^{t-1} update r^t. Then choose special pairs (w_1,x_1), ... (w_n,x_n) and probabilities lambda_1 , ... lambda_n, where Sum_i lambda_i = 1, and a constant K^t, such that for any state z, Sum_i lambda_i w_i(z) + K^t <= w'(z), and such that Phi(w^{t-1},x^{t-1}) >= Sum_i lambda_i*{||x^{t-1},x_i||+r(x_i)+Phi(w_i,x_i)} - K^t*C. Then randomly choose some i, where each i is chosen with probability lambda_i. Let x^t = x_i, and let w^t = w_i. We now need to verify C-competitiveness. Let calR be any adaptive online adversary. Let z^t be calR's state after t steps. For each step t, let Phi^t = Phi(w^t,x^t). Let cost^t_calA be the cost incurred by calA during all steps from 1 to t. Let cost^t_calR be the cost incurred by calR during all steps from 1 to t. Since calA is randomized, Phi^t, cost^t_calA and cost^t_calR are random variables. Let "E" denote expected value. We now prove the following claims. Claim 1: E(cost^t_calA) <= C*E(Sum_{j<=t}K^j) + Phi^0 - E(Phi^t). Claim 2: E(cost^t_calR) >= E(w^t(z^t)+Sum_{j<=t}K^j) - w^0(x^0). We prove both claims by induction on t. For t = 0, they are trivial. For t = 0, Claim 1 simply states that 0 <= 0. For t = 0, Claim 2 is trivial since z^0 = x^0. Now suppose both claims hold for t-1. Let w' = w^{t-1} update r^t, and let {lambda_i}, {w_i}, and K be as given in the description of calA. The adversary calR must choose z^t without knowing which w_i will be selected to be w^t. We have (a) E(cost^t_calA) = E(cost^{t-1}_calA) + E(||x^{t-1},x^t||) + E(r^t(x^t). By the inductive hypothesis, we have: (b) E(cost^{t-1}_calA) <= C*E(Sum_{j= E(w'(z^t)). By the inductive hypothesis, we have: (f) E(cost^{t-1}_calR) >= E(w^{t-1}(z^{t-1}) + E(Sum_{j= E(w^t(z^t)) + E(K^t). Simply adding (d), (e), (f), and (g) and cancelling terms, we obtain the statement of Claim 2. We now complete the proof of the theorem. Let n be the number of requests. By Claim 1: (h) E(cost_calA) <= C*E(Sum_{j<=n}K^j) + Phi^0 - E(Phi^t). By Claim 2: (i) E(cost_calR) >= E(w^n(z^n)) + E(Sum_{j<=n}K^j) - w^0(x^0). By property 2 of Phi: (j) E(w^n(z^n)) >= 0, and (k) E(Phi^n) >= 0. Combining the inequalities (h), (i), (j), and (k) and cancelling terms, we obtain: E(cost_calA) <= C*E(cost_calR) + C*w^0(x^0). Since w^0(x^0) is constant, we have verified C-competitiveness.