Data Science Deep Dive - Learning-Augmented Mechanism Design
Abstract: In this talk, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to complement the traditional approach in computer science, which analyzes the performance of algorithms based on worst-case instances, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions regarding the optimal solution. The algorithms can use the predictions as a guide to inform their decisions, and the goal is to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are very inaccurate (robustness). So far, these results have been limited to algorithms, but in this work we argue that another fertile ground for this framework is in mechanism design.
We initiate the design and analysis of strategyproof mechanisms that are augmented with predictions regarding the private information of the participating agents. To exhibit the important benefits of this approach, we revisit the canonical problem of facility location with strategic agents in the two-dimensional Euclidean space. We study both the egalitarian and utilitarian social cost functions, and we propose new strategyproof mechanisms that leverage predictions to guarantee an optimal trade-off between consistency and robustness guarantees. This provides the designer with a menu of mechanism options to choose from, depending on her confidence regarding the prediction accuracy. Furthermore, we also prove parameterized approximation results as a function of the prediction error, showing that our mechanisms perform well even when the predictions are not fully accurate. We will conclude by discussing other exciting recent results in this new area of learning-augmented mechanism design.
Joint work with Priyank Agrawal, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan.
Bio: Eric Balkanski is an Assistant Professor in the Department of Industrial Engineering and Operations Research at Columbia University. His research focuses on data-driven algorithm design, combinatorial optimization, and mechanism design. He is the recipient of an NSF Fairness in AI grant, a Columbia Center of AI Technology (CAIT) in collaboration with Amazon faculty research award, an NSF SMALL grant, and an ACM SIGecom Doctoral Dissertation Honorable Mention Award.
The Data Science Deep Dive is free and open to the public. If you are interested in giving a talk, please email Mohammad Hajiesmaili or Adam Lechowicz. Note that in addition to being a public lecture series, the Data Science Deep Dive is also a seminar (CompSci 692K, Algorithms with Predictions Seminar) that can be taken for credit.