An arXiv preprint reports a sharp split in a randomized rule for placing facilities on a line: Product-Gap keeps expected social cost to no more than 2k times the optimal k-facility cost for every k ≥ 2, and constructed profiles make that factor tight. The result is a worst-case theorem over formal agent-location profiles, not an empirical measurement.
That promise has a hard incentive limit. Product-Gap is strategyproof in expectation for two and three facilities, meaning no agent can lower expected cost by submitting a different report; but it is not strategyproof for any facility count from four upward. The result is an exact mathematical classification, not a statistical estimate.
A guarantee that scales with the number of facilities
The paper asks whether a randomized strategyproof mechanism can achieve a constant approximation ratio when more than two facilities are placed on the real line. Its formal model has n agents and k facilities, with n ≥ k ≥ 2, and compares expected social cost with the optimal k-facility social cost.
Product-Gap weights possible selections by spacing in the reports. It selects k reported locations with probability proportional to the product of the k − 1 consecutive gaps between those selected reports, then opens facilities at the selected reports.
To prove the cost result, the authors use a random-cut representation: they first select a cut vector, then independently choose one agent uniformly in each resulting block. They combine that representation with contiguous optimal clustering and charging inequalities to derive the 2k bound.
That bound scales with k, so it is not a k-independent constant across all facility counts. But the paper says the dependence is exact in the worst case: constructed profiles approach the 2k factor, so Product-Gap cannot be given a smaller general guarantee.
The incentive boundary
Cost and incentives require separate proofs. For three facilities, the incentive analysis uses closest-point deletion; for two, it uses a far-anchor limit. For four facilities, it gives an exact manipulation and then lifts that construction to larger facility counts.
Within the four-facility example, an agent whose true location is 0 has an alternative report that produces a strictly smaller expected cost than reporting 0. This is a mathematical counterexample to strategyproofness, and the paper uses it to establish failure for every k ≥ 4.
That distinction matters. A 2k approximation guarantee says how far the rule's expected social cost can be from the optimum; it does not say that truthful reporting minimizes each agent's expected cost for every facility count. In this analysis, Product-Gap has the cost guarantee for every k ≥ 2, while the strategyproofness guarantee covers only k = 2 and k = 3.
A narrower improvement for two facilities
For k = 2, Product-Gap's specialization is called Global Pair. It selects an unordered pair of reports with probability proportional to the distance between them and opens the two facilities at those reports.
Global Pair is then paired with Proportional in a fixed, report-independent mixture. For λ ∈ [0, 1], the two components run with probabilities λ and 1 − λ; because both components are strategyproof on the line, every fixed mixture is strategyproof.
The theorem gives the mixture's worst-case approximation ratio as max{3 + λ, 4 − κλ}. Optimizing that expression within the fixed mixture class yields a reported ratio of (74 + 4√3)/23 ≈ 3.519, improving on a previous factor of 4.
That result is deliberately narrow. Its tightness applies only to fixed, report-independent mixtures of Proportional and Global Pair; it does not establish the same ratio for mechanisms outside that class. Nor does the two-facility result answer the question of strategyproofness for four or more facilities.
A result about proofs, not deployments
This is a formal modeling study rather than an empirical trial. It quantifies over finite agent profiles, including constructed worst-case and manipulation profiles, and evaluates expected social cost and strategyproofness in expectation. The supplied analysis reports no empirical participants or facility-location dataset.
The manuscript also discloses generative-AI assistance with writing and formalizing parts of its proofs. It says AI-generated material was treated as draft rather than mathematical evidence, while the research questions, mechanisms and proof ideas are attributed to the authors.
That scope sets clear limits. The 2k welfare result does not make Product-Gap strategyproof when k ≥ 4, and the analysis does not establish corresponding mechanisms in higher-dimensional spaces. The mixture's tightness likewise says nothing beyond the fixed, report-independent class it studies.
Open questions remain about whether another randomized strategyproof mechanism can achieve a constant-factor guarantee for each fixed k ≥ 4 on the line, and whether analogous strategyproof mechanisms exist in higher-dimensional Euclidean spaces.
Taken together, the paper maps a trade-off rather than offering a universal solution. Product-Gap has a tight 2k welfare guarantee for all k ≥ 2 and remains strategyproof in expectation at k = 2 and k = 3, but a constructed manipulation blocks that property from k = 4 onward. For two facilities, the optimized fixed mixture offers a separate improvement inside its stated class.
Paper data and sources
Original title: Product Gap Mechanisms for Multi-Facility Location
Authors: Jianhao Jia
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text