Constrained Distributed Heterogeneous Two-Facility Location Problems with Max-Variant Cost
2026-07-02 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study a problem where two facilities need to be placed on a line among specific allowed spots, with groups of agents wanting to be close to these facilities. Each agent's cost depends on their distance to the farthest facility, and the authors want mechanisms that encourage agents to truthfully share their locations. Their method picks candidate locations in two steps: first, each group picks two representative spots based on local info, then two final spots are chosen from those. They analyze these mechanisms to show how well they can approximate social objectives without agents lying.
facility location problemmax-variant cost modelstrategyproof mechanismsdistributed algorithmssocial objectivesdistortionprivate informationtwo-facility problemtruthfulnessapproximation
Authors
Xinru Xu, Wenjing Liu, Qizhi Fang
Abstract
This paper investigates a constrained distributed heterogeneous two-facility location problem under the max-variant cost model. In this setting, a set of agents with private locations on the real line is partitioned into disjoint groups. The constraint stipulates that facilities must be situated within a given multiset of candidate locations, with the restriction that each candidate location can host at most one facility. Under the max-variant model, an agent's individual cost is defined as the distance from their location to the farthest facility. Our objective is to design strategyproof distributed mechanisms that incentivize agents to report their locations truthfully while approximating social objectives. Such mechanisms operate in two stages: first, for each group, a pair of candidate locations is selected as representatives based solely on local reports; subsequently, the mechanism outputs two final facility locations from the set of all representatives. We focus on a class of deterministic strategyproof distributed mechanisms and establish constant lower and upper bounds on the distortion under four social objectives: Average-of-Average, Max-of-Max, Average-of-Max, and Max-of-Average costs.