Constrained Distributed Heterogeneous Two-Facility Location Problems with Max-Variant Cost

Jul 16, 2026

This paper studies a constrained distributed heterogeneous two-facility location problem under the max-variant cost model. Agents have private positions on the real line and are partitioned into disjoint groups. Facility sites must be chosen from a given multiset of candidate locations, with at most one facility per candidate. Each agent’s cost equals the distance to the farthest facility. The work designs deterministic strategyproof distributed mechanisms using two stages of local representative selection, then derives constant distortion bounds for four social objectives.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages31

Reading Time1 h 18 min

Introduction

Our Results

arXiv :2607 .023 14v2 [ cs .GT] 6 Jul 2026 Constrained Distributed Heterogeneous Two-Facility Location Problems with Max-Variant Cost Xinru Xua , Wenjing Liua,b,∗, Qizhi Fanga , Alexandros A. Voudourisc a School of Mathematical Sciences, Ocean University of China, Qingdao, 266100, China b Laboratory of Marine Mathematics, Ocean University of China, Qingdao, 266100, China c School of Computer Science and Electronic Engineering, University of Essex, Colchester, CO4 3SQ, United Kingdom 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-ofAverage costs. Keywords: Facility location, Mechanism design, Strategyproof, ∗ Corresponding author. Email addresses: [xuxinru1207@stu.ouc.edu.cn](xuxinru1207@stu.ouc.edu.cn) (Xinru Xu), [liuwj@ouc.edu.cn](liuwj@ouc.edu.cn) (Wenjing Liu), [qfang@ouc.edu.cn](qfang@ouc.edu.cn) (Qizhi Fang), [alexandros.voudouris@essex.ac.uk](alexandros.voudouris@essex.ac.uk)[ ](alexandros.voudouris@essex.ac.uk)(Alexandros A. Voudouris) Distributed, Distortion 1. Introduction As a fundamental problem in combinatorial optimization, the facility location problem seeks to determine optimal facility placements under specific constraints to optimize a given social objective. In many practical settings, however, the social planner does not have direct access to agents’ private information, such as their exact residential addresses. Instead, the planner must rely on information reported by the agents themselves. This creates a conflict of interest: while the planner aims for social optimality, individual agents may misreport their locations to reduce their own costs. The goal, therefore, is to design strategyproof mechanisms that ensure truthful reporting while (approximately) optimizing the social objective. This line of research on approximate mechanism design without money was initiated by Procaccia and Tennenholtz [18] and has since led to a variety of models (seethe survey by Chan et al. [5]) . In real-world scenarios, collective decision-making is often distributed. In such processes, agents are divided into groups where each group first reaches a local decision independently of others; these local outcomes are then aggregated into a final collective decision. A typical example is the selection of national scholarship recipients at a university: each faculty first nominatesits own candidates, and the final winners are chosen from this pool. To analyze these complex dynamics, Filos-Ratsikas et al. [12] introduced the study of distributed social choice from a voting perspective, employing two-step mechanisms: each group elects a representative based on local preferences, and the mechanism then selects an overall winner from these representatives. To quantify the resulting efficiency loss, they extended the notion of distortion, defined as the worst-case

FAQs

What is the max-variant cost model used in this paper?

Each agent’s individual cost is the distance from the agent’s location to the farthest of the two facility locations.

How are facilities selected in the proposed distributed mechanisms?

The mechanism works in two stages: each group selects two representative candidate locations based only on local reports, and the final two facility locations are chosen from the set of all representatives.

Which social objectives are analyzed for distortion bounds?

The paper establishes constant lower and upper distortion bounds under four social objectives: Average-of-Average, Max-of-Max, Average-of-Max, and Max-of-Average costs.

Jul 16, 2026

Upload by Ava Thompson