为加权设施选址设计可预测的抗策略机制,平衡准确与鲁棒性。
Prediction-Augmented Mechanism Design for Weighted Facility Location
- 通过代表性实例映射法构造加权场景下的策略抗性机制。
- 一致性与鲁棒性均有理论上限:分别依赖权重极值与参数c。
- 适用于需兼顾个体权重差异的资源分配与决策系统。
设施选址是运筹学、机制设计与算法博弈论中的基础问题,应用涵盖城市规划到分布式系统。近期研究尝试通过引入预测来改进经典策略抗性机制在不确定环境下的性能。现有工作主要关注无权重情形下的一致性和鲁棒性权衡,假设所有参与者重要性相同。然而实际中权重差异显著,推动了加权设施选址问题的研究。本文提出一个预测增强的算法框架,可在非均匀权重下平衡一致性和鲁棒性。通过将给定位置映射到代表性实例,证明存在策略抗性机制,其一致性保证为 $\frac{\sqrt{(1+c)^2W^2_{\min}+(1-c)^2W^2_{\max}}}{(1+c)W_{\min}}$,鲁棒性保证为 $\frac{\sqrt{(1-c)^2W^2_{\min}+(1+c)^2W^2_{\max}}}{(1-c)W_{\min}}$,其中 $c$ 控制权衡,$W_{\min}$ 与 $W_{\max}$ 分别为最小与最大权重。此外,我们证明在加权设施选址中,不存在能同时实现1致性与 $O\left( n \cdot \frac{W_{\max}}{W_{\min}} \right)$ 鲁棒性的确定性策略抗性机制,即使拥有全部代理的完整预测。
原文摘要 · Abstract (English)
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{\sqrt{(1+c)^2W^2_{\min}+(1-c)^2W^2_{\max}}}{(1+c)W_{\min}}$ and a bounded robustness guarantee of $\frac{\sqrt{(1-c)^2W^2_{\min}+(1+c)^2W^2_{\max}}}{(1-c)W_{\min}}$ in weighted settings, where $c$ can be viewed as a parameter to make a trade-off between the consistency and robustness and $W_{\min}$ and $W_{\max}$ denote the minimum and maximum agents' weight. We also prove that there is no strategyproof deterministic mechanism that reach $1$-consistency and $O\left( n \cdot \frac{W_{\max}}{W_{\min}} \right)$-robustness in weighted FLP, even with fully predictions of all agents.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。