The advice model of online computation captures the setting in which the online algorithm is
given some information concerning the request sequence. This paradigm allows to establish
tradeoffs between the amount of this additional information and the performance of the
online algorithm. However, unlike real life in which advice is a recommendation that we can
choose to follow or to ignore based on trustworthiness, in the current advice model, the
online algorithm treats it as infallible. This means that if the advice is corrupt or, worse, if it …

We study a generalization of the advice complexity model of online computation in which the
advice is provided by an untrusted source. Our objective is to quantify the impact of
untrusted advice so as to design and analyze online algorithms that are robust if the advice
is adversarial, and efficient is the advice is foolproof. We focus on four well-studied online
problems, namely ski rental, online bidding, bin packing and list update. For ski rental and
online bidding, we show how to obtain algorithms that are Pareto-optimal with respect to the …