Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
Randomized Strategic Facility Location with Predictions
ArXiv.org
11 Sep 2024
Abstract
We revisit the canonical problem of strategic facility location and study the
power and limitations of randomization in the design of truthful mechanisms
augmented with machine-learned predictions. In the strategic facility location
problem, a set of agents are asked to report their locations in some metric
space and the goal is to use these reported locations to determine where to
open a new facility, aiming to optimize some aggregate measure of distance of
the agents from that facility. However, the agents are strategic and can
misreport their locations if this may lead to a facility location choice that
they prefer. The goal is to design truthful mechanisms, which ensure the agents
cannot benefit by misreporting. A lot of prior work has studied this problem
from a worst-case perspective, but a recent line of work proposed a framework
to refine these results when the designer is provided with some, possible
incorrect, predictions regarding the agents' true locations. The goal is to
simultaneously provide strong consistency guarantees (i.e., guarantees when the
predictions provided to the mechanism are correct) and near-optimal robustness
guarantees (i.e., guarantees that hold irrespective of how inaccurate the
predictions may be). In this work we focus on the power of randomization in
this problem and analyze the best approximation guarantees achievable with
respect to the egalitarian social cost measure for one- and two-dimensional
Euclidean spaces.
Metrics
9 Record Views
Details
- Title
- Randomized Strategic Facility Location with Predictions
- Creators
- Eric BalkanskiVasilis GkatzelisGolnoosh Shahkarami
- Publication Details
- ArXiv.org
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Computer Science
- Other Identifier
- 991021903962304721