Behavioral Potentials I. Apr 10 13:57:36 PDT 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 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. Remark: To verify Condition 3(a), it suffices to consider only z which are in the support of w'. Proof of Remark: Suppose that z is not in the support of w'. Then w'(z) = w'(z') + ||z,z'|| for some z' which is in the support of w'. By the Lipschitz condition for work functions, w_i(z) <= w_i(z') + ||z,z'|| for each i. Since, by hypothesis, the inequality holds for z', we have: Sum_i lambda_i w_i(z) + K <= Sum_i lambda_i(w_i(z)+||z,z'||) = Sum_i lambda_i w_i(z) + ||z,z'|| <= w'(z') + ||z,z'|| = w'(z), as required. 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).