Conference proceeding
Randomized Strategic Facility Location with Predictions
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 37 (NEURIPS 2024), v 37, pp 35639-35664
01 Jan 2024
Abstract
In the strategic facility location problem, a set of agents report their locations in a metric space and the goal is to use these reports to open a new facility, minimizing an aggregate distance measure from the agents to the facility. However, agents are strategic and may misreport their locations to influence the facility's placement in their favor. The aim is to design truthful mechanisms, ensuring agents cannot gain by misreporting. This problem was recently revisited through the learning-augmented framework, aiming to move beyond worst-case analysis and design truthful mechanisms that are augmented with (machine-learned) predictions. The focus of this prior work was on mechanisms that are deterministic and augmented with a prediction regarding the optimal facility location. In this paper, we provide a deeper understanding of this problem by exploring the power of randomization as well as the impact of different types of predictions on the performance of truthful learning-augmented mechanisms. We study both the single-dimensional and the Euclidean case and provide upper and lower bounds regarding the achievable approximation of the optimal egalitarian social cost.
Metrics
2 Record Views
Details
- Title
- Randomized Strategic Facility Location with Predictions
- Creators
- Eric Balkanski - Columbia UniversityVasilis Gkatzelis - Drexel UniversityGolnoosh Shahkarami - Univ Saarland, Max Planck Inst Informat, Saarbrucken, Germany
- Contributors
- A Globerson (Editor)L Mackey (Editor)D Belgrave (Editor)A Fan (Editor)U Paquet (Editor)J Tomczak (Editor)C Zhang (Editor)
- Publication Details
- ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 37 (NEURIPS 2024), v 37, pp 35639-35664
- Conference
- Advances in Neural Information Processing Systems 37, 37 (Vancouver, Canada, 10 Dec 2024–15 Dec 2024)
- Series
- Advances in Neural Information Processing Systems
- Publisher
- Neural Information Processing Systems (Nips)
- Number of pages
- 26
- Grant note
- IIS-2147361; CCF-2210502 / NSF; National Science Foundation (NSF) CCF-2047907 / NSF CAREER award; National Science Foundation (NSF); NSF - Office of the Director (OD)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:001633236100159
- Scopus ID
- 2-s2.0-105000531548
- Other Identifier
- 991022202519204721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Artificial Intelligence
- Computer Science, Information Systems
- Computer Science, Theory & Methods