Search and Verification for Strategyproof Facility Location on Metric Graphs

Abstract

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.