Searching for facility-location rules that make honesty worthwhile

A location rule can minimize total travel distance yet give someone an incentive to lie about where they live. Requiring honest reporting to be individually worthwhile changes the optimization problem: the best manipulation-resistant rule may incur more travel than an unconstrained optimum.

In a preprint posted on November 3, 2026, University of Warsaw researchers Krzysztof Rogowski and Marcin Dziubiński present a framework for searching for such rules and checking their guarantees. Their study combines mathematical reductions, exact-arithmetic verification and computational experiments. It does not establish the optimal rule for every network.

A network with locations between junctions

The model places participants and a single facility on a continuous metric graph: locations can lie at junctions or anywhere along edges, and distance means shortest-path distance through the network. A rule, called a mechanism, takes reported locations and returns a lottery over finitely many possible facility locations.

Each participant wants to minimize their expected distance to the facility. A mechanism is strategyproof if no individual can reduce that expectation by misreporting, whatever everyone else reports. This is an expected-cost guarantee, not a claim that every possible outcome of the lottery is individually preferable under truthful reporting.

The collective objective is to minimize the sum of expected distances. Performance is measured by an approximation ratio: the worst-case factor by which the mechanism's total expected distance exceeds the minimum achievable without incentive restrictions. Smaller factors are better; a factor of one would match the unconstrained optimum everywhere.

Turning continuous guarantees into finite checks

The authors represent candidate mechanisms using what they call piecewise-linear attributions. These divide the space of reported-location combinations into finitely many regions. Within each region, the mechanism mixes deterministic component rules, with probabilities that vary affinely with the reports.

This structure makes expected costs piecewise quadratic. The paper shows that checking strategyproofness or a proposed approximation guarantee then reduces to finitely many quadratic nonnegativity problems over bounded polyhedral regions. Under the stated assumptions of exact arithmetic and comparisons, verification either certifies the property throughout the continuous domain or returns locations where it fails.

Finding candidates remains a separate task. To simplify optimization, the authors introduce strong strategyproofness: with the true location and other reports fixed, expected cost cannot decrease as a report moves along a shortest path away from the truth. For fixed component rules and regions, this stronger requirement has finitely many linear constraints.

That enables linear-programming searches, but the approximation objective is checked initially only on sampled profiles. A sampled result can underestimate a candidate's actual worst-case ratio, making subsequent global verification essential.

The lower-bound method answers a different question: how well could any strategyproof mechanism possibly perform? A cost-preserving reduction transfers the continuous problem to suitable finite report and output sets. Feasible certificates from the resulting linear-programming dual establish lower bounds for all strategyproof mechanisms in the paper's model, not merely those searched by the authors.

Certified bounds and numerical promise

For three participants on a continuous cycle, the authors report a certified upper factor of 1.10747 and an unrestricted lower bound of 1.0591173691. The unknown optimal strategyproof ratio therefore lies between these values. The upper result improves on the 1.25 guarantee of the proportional circle distance mechanism used as a benchmark.

For three participants on an equal-path theta graph—two hubs connected by three equal-length paths—the certified bounds are 1.078216584909 and 1.2028. The upper factor improves on random dictatorship's 4/3 guarantee in this setting.

Large language models developed search procedures for these experiments. The paper attributes the guarantees to separate exact-arithmetic verifier programs and the underlying mathematics, rather than to the models' reasoning. Their correctness still depends on the reductions and verifier implementations.

A separate numerical cycle study produced a more promising candidate on a mesh of 128 equally spaced points. Its estimated approximation interval was 1.072278 to 1.072288. These floating-point results are not exact certificates. Rationally reconstructed candidates on four smaller meshes passed exact checks, but those checks do not certify the finest-mesh candidate.

What remains unresolved

The paper also proves that every deterministic strategyproof mechanism that can output every graph location satisfies strong strategyproofness and admits the proposed representation. That result does not establish equivalent expressiveness for randomized mechanisms.

Whether the search restrictions exclude the best randomized rules remains open. The work also supplies neither a polynomial-time complexity guarantee for its general verification procedure nor a convergence guarantee for sampled search. Its contribution is a framework for proposing mechanisms, testing their continuous guarantees and bounding how much improvement may remain—not a complete solution to strategic facility location.