Behavioral Potentials II. Apr 10 13:15:53 PDT 2002 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.