2026 Theses Doctoral

The Value of Advice: Predictions Across Mechanism Design and Online Algorithms

Zhu, Cherlin

Algorithms and mechanisms have traditionally been analyzed under worst-case guarantees that hold for all instances. However, these are often pessimistic in practice because they do not allow for the incorporation of instance-specific prior knowledge that is often available to practitioners. Recent work seeks to overcome this by augmenting algorithms and mechanisms with a prediction of the instance, giving rise to the field of "learning-augmented algorithms." The goal is to obtain improved guarantees when the prediction is correct (consistency) while simultaneously guaranteeing some worst-case bounds even if the prediction is arbitrarily wrong (robustness).

In this thesis, we expand the algorithms-with-predictions literature along three complementary fronts. First, we broaden the study of online speed scaling through a novel prediction model, introducing predictions of the output rather than the input. Second, we initiate the study of strategic learning with advice by providing results on strategic regression and classification. Finally, we bridge the two largely parallel lines of work on online algorithms and mechanism design by introducing online mechanism design with predictions through the study of online auctions with predictions. In all three settings, we provide consistency-robustness guarantees, complemented by impossibility results and extensions that handle approximately correct (not just exactly correct) predictions.