2025/07/09 by Yangguang Shi, Shi, Yangguang, Zhenyu Xue +1 · 1 citation
Engineering · #Advanced Manufacturing and Logistics Optimization
paper · pdf · doi:10.48550/arxiv.2507.06509
Facility location is fundamental in operations research, mechanism design, and algorithmic game theory, with applications ranging from urban infrastructure planning to distributed systems. Recent research in this area has focused on augmenting classic strategyproof mechanisms with predictions to achieve an improved performance guarantee against the uncertainty under the strategic environment. Previous work has been devoted to address the trade-off obstacle of balancing the consistency (near-optimality under accurate predictions) and robustness (bounded inefficiency under poor predictions) primarily in the unweighted setting, assuming that all agents have the same importance. However, this assumption may not be true in some practical scenarios, leading to research of weighted facility location problems. The major contribution of the current work is to provide a prediction augmented algorithmic framework for balancing the consistency and robustness over strategic agents with non-uniform weights. In particular, through a reduction technique that identifies a subset of representative instances and maps the other given locations to the representative ones, we prove that there exists a strategyproof mechanism achieving a bounded consistency guarantee of \frac√(1+c)2W2min+(1-c)2W2max(1+c)Wmin and a bounded robustness guarantee of \frac√(1-c)2W2min+(1+c)2W2max(1-c)Wmin in weighted settings, where c can be viewed as a parameter to make a trade-off between the consistency and robustness and Wmin and Wmax denote the minimum and maximum agents' weight. We also prove that there is no strategyproof deterministic mechanism that reach 1-consistency and O( n ⋅ \fracWmaxWmin )-robustness in weighted FLP, even with fully predictions of all agents.