E " max

Here we provide a proof for Theorem 1. Eq. (18) indicates that if the price charged by an algorithm in periodt is greater than Noting the expression of the optimal price in Eq.(18), we have the following lower bound on Combining (32) with (33), we obtain|gw(x) gw(y)| ||x y||β. Eq. (35) follows from the definition ofD(y, Mj) andProj(x, Mj) Mj. Eq. (41) holds due to the same reason as(37). T +O N T, (46) where the second identityholds since from the union bound,P(Ac) Nϵ = NT2. For convenience, we label(x,p,d) in D as {(xi,pi,di)}ti=1 in chronological order.