Controlling Risk in the Online Bidding and Cow-Path Problems

Abstract

In the classical analysis of online algorithms, evaluation is done by their worst-case competitive ratio, and if they are randomized algorithms, by their worst-case expected competitive ratio. In the case of randomized algorithms, any risk in the tails of the distribution is ignored. In this thesis, risk-sensitive variants of two online problems are studied: the online bidding problem and the $w$-lane cow-path problem. Both are studied via tail constraints and the Conditional Value at Risk (CVaR). We specifically focus on periodic randomized algorithms that are parameterized by a base $q>1$ and a random uniform offset. For online bidding, we show that there exists a base $q_\gamma$, such that $P_{q_\gamma}$ minimizes the tail probability over all randomized bidding strategies. For a single tail constraint, this yields a $q^*/ln{q^*}$-competitive algorithm where $q^*$ minimizes the competitive ratio over feasible bases. We further introduce a strong CVaR-based risk measure and show that the periodic bidding strategy $P_{q_\delta}$ is optimal for it. For the $w$-lane cow-path problem, we extend this framework to periodic algorithms, and express closed-form formulas for the optimal base when tail constraints are included, or when we optimize for the strong CVaR-based risk measure.