Constrained distributed heterogeneous two-facility location problems with max-variant cost

This paper studies the design of strategyproof distributed mechanisms for a constrained location problem involving two heterogeneous facilities under the max-variant cost model. A set of agents with private locations on the real line is partitioned into disjoint groups, and the two facilities must be placed at locations drawn from a given multiset of candidate locations, with each candidate location hosting at most one facility. Each agent requires access to both facilities, and her individual cost is defined as the distance from her location to the farther facility. Each such mechanism operates in two stages. First, it selects a pair of candidate locations as representatives for each group based solely on the reports of that group's members. It then selects the final locations of the two facilities from the aggregated multiset of group representatives. We investigate deterministic strategyproof mechanisms within this distributed framework and derive constant lower and upper bounds on their distortion with respect to four social objectives: the Average-of-Average, Max-of-Max, Max-of-Average, and Average-of-Max costs.