Xizhi Tan, Drexel University

Abstract

This talk will introduce the model of "learning-augmented mechanism design" (or "mechanism design with predictions"), which is an alternative model for designing and analyzing mechanisms in strategic settings. It aims to complement the traditional approach in computer science, which analyzes the performance of algorithms based on worst-case instances. Recent work on "algorithms with predictions" investigates how algorithms can be augmented with predictions to overcome these worst-case negative results. The algorithms can use this information to guide their decisions, and the goal is to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining good worst-case guarantees, even if these predictions are very inaccurate (robustness).

So far, most of these results have been limited to online algorithms, but some very recent work has shown that this model may be even more useful in mechanism design. This talk will cover the foundations of learning-augmented mechanism design and recent results in this model. In particular, we will showcase the power of predictions on one of the most important, and very recently resolved, problem, the strategic scheduling make span minimization problem.

See: https://theory.cs.rutgers.edu/theory_seminar