Search and Verification for Strategyproof Facility Location on Metric Graphs

概要

We study automated design of strategyproof (SP) mechanisms for randomized facility location on continuous metric graphs, with the objective of minimizing total distance. We develop methods for computing upper and lower bounds on the optimal approximation ratio achievable by SP mechanisms for a given graph and number of agents. For the lower bound, we propose a cost-preserving reduction to a finite domain that yields lower bounds for unrestricted SP mechanisms through linear programming dual certificates. For the upper bound, we introduce finite representations of mechanisms, called piecewise-linear attributions (PL attributions), that mix piecewise-linear deterministic mechanisms using affine weights on a triangulation of the report space. We show that for mechanisms represented by PL attributions, checking SP and an approximation guarantee reduces to finitely many quadratic nonnegativity tests over compact polytopes. With exact arithmetic and comparisons, each verification certifies the proposed property or returns locations where it fails. In addition, we introduce a strengthening of the incentive notion called strong strategyproofness. We show that for fixed component mechanisms and regions of a PL attribution, the strong strategyproofness requirement can be expressed by a finite number of linear constraints on the attribution coefficients. Using these theoretical results, we propose a heuristic procedure for computing an upper bound on the approximation ratio. We compute certified upper and lower bounds on several metric graphs and numerically evaluate the proposed search procedure. Lastly, we show that deterministic SP onto mechanisms on graphs are strongly strategyproof and admit PL attributions. Thus restricting attention to strongly strategyproof mechanisms admitting PL attributions loses no deterministic SP onto mechanisms.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Search and Verification for Strategyproof Facility Location on Metric Graphs

# 概要
We study automated design of strategyproof (SP) mechanisms for randomized facility location on continuous metric graphs, with the objective of minimizing total distance. We develop methods for…

# 原典
https://arxiv.org/abs/2611.05092

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。