Journal article
Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location
Mathematics of operations research, v 49(4), pp 2626-2651
01 Nov 2024
Abstract
In this work, 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 worst-case analysis approach in computer science, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions. The algorithms can use the predictions as a guide to inform their decisions, aiming 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 inaccurate (robustness). 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. 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.
Metrics
Details
- Title
- Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location
- Creators
- Priyank Agrawal - Columbia UniversityEric Balkanski - Columbia UniversityVasilis Gkatzelis - Drexel University, Computer ScienceTingting Ou - Columbia UniversityXizhi Tan - Drexel Univ, Dept Comp Sci, Philadelphia, PA 19104 USA
- Publication Details
- Mathematics of operations research, v 49(4), pp 2626-2651
- Publisher
- Informs
- Number of pages
- 26
- Grant note
- CCF-2210502; CCF-2047907 / National Science Foundation; National Science Foundation (NSF)
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:001134592300001
- Scopus ID
- 2-s2.0-85210322960
- Other Identifier
- 991021861201604721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Mathematics, Applied
- Operations Research & Management Science