Behavioral Potentials. Apr 6 08:45 2002 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 0. There is a special pair (w^0,x^0), where x^0 is the start state. 1. For any special pair (w,x) and any state z, Phi(w,x) + Cw(z) >= 0. 2. 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 2(a). For any state z, Sum_i lambda_i w_i(z) + K <= w'(z). 2(b). Phi(w,x) >= Sum_i lambda_i*{||x,x_i||+r(x_i)+Phi(w_i,x_i)} - K*C. We remark that, without loss of generality, condition 1. may be replaced by its "strong" version, namely: 1.' For any special pair (w,x) and any state z, w(z) >= 0 and Phi(w,x) >= 0. Theorem: If there is a behavioral C-potential for a metrical task system M, such that for every state x there is at least one work function w for which (w,x) is a special pair, then there is a randomized online algorithm for M which is C-competitive against the adaptive online adversary. Proof: (incomplete) 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. 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. Without loss of generality, calR is deterministic. For each step t, let Phi^t = Phi(w^t,x^t). Let z^t be calR's state after t steps. 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. We prove the following claims. Claim 1: E(cost^t_calA) <= C*E(min_z{w^t(z)}+Sum_{i<=t}K^i) + Phi^0 - E(Phi^t). Claim 2: E(cost^t_calR) >= E(w^t(z^t)+Sum_{i<=t}K^i) - w^0(x^0). C-competitiveness follows from the two claims. We prove both claims by induction on t. For t = 0, they are trivial. Now suppose both claims hold for t-1. The adversary calR must choose z^t without knowing which i will be selected at random. [Continued on page 6.]