Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location

Priyank Agrawal (), Eric Balkanski (), Vasilis Gkatzelis (), Tingting Ou () and Xizhi Tan ()
Additional contact information
Priyank Agrawal: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Eric Balkanski: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Vasilis Gkatzelis: Department of Computer Science, Drexel University, Philadelphia, Pennsylvania 19104
Tingting Ou: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Xizhi Tan: Department of Computer Science, Drexel University, Philadelphia, Pennsylvania 19104

Mathematics of Operations Research, 2024, vol. 49, issue 4, 2626-2651

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.

Keywords: Primary: 91B03; facility location; mechanisms design with predictions (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0225 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:4:p:2626-2651

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().