
CO Seminar – Artem Tsikiridis
February 28 @ 12:30 - 13:30
Location: MF 12
Speaker: Artem Tsikiridis (CWI)
Title: To Trust or Not to Trust: Assignment Mechanisms with Predictions in the Private Graph Model
Abstract:
Recently, an emerging line of research has focused on leveraging predictions in the design of truthful mechanisms. Here, the challenge is to achieve optimal approximation guarantees as the prediction quality varies from perfect (consistency) to imperfect (robustness).
In this environment, we focus on variants of the Generalized Assignment Problem (GAP) in the private graph model (Dughmi \& Ghosh, 2010), where agent-resource compatibilities are private information. For the Bipartite Matching Problem (BMP), our deterministic weakly group-strategyproof (WGSP) mechanism, which achieves the optimal consistency-robustness trade-off, draws inspiration from the Gale-Shapley algorithm, crucially incorporating the predicted assignment. Additionally, we give a randomized mechanism that is universally WGSP with an improved approximation guarantee. For more general variants of GAP, our universally WGSP mechanism randomizes over a greedy mechanism, our mechanism for BMP and the predicted assignment. All our mechanisms provide approximation guarantees that smoothly interpolate between consistency and robustness, depending on an appropriate error measure.
Joint work with Riccardo Colini-Baldeschi (Meta), Sophie Klumper (CWI and University of Amsterdam) and Guido Schäfer (CWI and University of Amsterdam).
The paper is available on ArXiv: https://arxiv.org/abs/2403.03725.