July 02, 2026
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.
Facility location , Mechanism design ,Strategyproof ,Distributed ,Distortion
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 [1] and has since led to a variety of models (see the survey by Chan et al. [2]).
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 nominates its own candidates, and the final winners are chosen from this pool. To analyze these complex dynamics, Filos-Ratsikas et al. [3] 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 ratio between the social objective value achieved by a mechanism and the theoretical optimum. In follow-up work, Filos-Ratsikas and Voudouris [4] investigated a distributed single-facility location problem aimed at minimizing the social cost, which represents the sum of all agents’ costs.
While classic models often assume that facilities can be placed anywhere in a metric space, many practical applications involve constrained facility location. Feasible regions or the capacity of specific sites may be limited due to land-use regulations, environmental protection, or human factors. This has motivated research into mechanism design for facility location within restricted sets of locations.
In this paper, we study a constrained distributed heterogeneous two-facility location problem. We assume each agent requires access to both facilities, and her individual cost is defined by the distance to the farther one, known as the max-variant cost. This cost model reflects scenarios such as an express delivery outlet that must dispatch regular packages to an ordinary distribution center and cold-chain packages to a specialized one. Assuming the outlet has multiple vehicles traveling at the same speed, its total waiting time depends on the distance to the more distant center. Our work provides lower and upper bounds on the distortion of strategyproof distributed mechanisms under four distinct social objectives.
We study a constrained, distributed, and heterogeneous two-facility location problem. In this model, facilities can only be deployed within a predetermined set of candidate locations, with a capacity of at most one facility per site. We consider a set of agents with private locations on the real line, partitioned into disjoint groups. Once the two facilities are located, each agent’s individual cost is determined by the distance to the farther facility (the max-variant cost). Our objective is to design strategyproof distributed mechanisms that take agents’ reported locations as input and output the final locations of the two facilities. Such mechanisms operate in two steps: first, for each group, the mechanism selects two candidate locations as representatives based solely on local reports; second, it chooses the final two facility locations from the aggregated pool of representatives. Our mechanisms are evaluated under four social objectives:
Average-of-Average cost: The arithmetic mean of the average individual costs across all groups.
Max-of-Max cost: The maximum individual cost among all agents.
Max-of-Average cost: The maximum of the average individual costs of all groups.
Average-of-Max cost: The average of the maximum individual costs within each group.
While the Average-of-Average cost and the Max-of-Max cost are adaptations of classic objectives from non-distributed settings, the Max-of-Average cost and the Average-of-Max cost are fairness-inspired metrics specifically meaningful in distributed environments. For each of these objectives, we establish lower and upper bounds on the distortion of strategyproof distributed mechanisms. A summary of our main results is provided in Table 1.
| Social objective | Lower bound | Upper bound |
|---|---|---|
| Average-of-Average cost | \(3\) [Theorem [AoAlower]] | \(9\) [Theorem [AoAupper]] |
| Max-of-Max cost | \(3\) [Theorem [MoMlower]] | \(3\) [Theorem [MoMupper]] |
| Max-of-Average cost | \(7/2\) [Theorem [MoAlower]] | \(2+\sqrt{5}\) [Theorem [MoAupper]] |
| Average-of-Max cost | \(3\) [Theorem [AoMlower]] | \(2+\sqrt{5}\) [Theorem [AoMupper]] |
The framework of approximate mechanism design without money was established by Procaccia and Tennenholtz [1], who developed strategyproof mechanisms with constant approximation ratios for facility location problems on the real line. Their foundational study covered both single-facility and homogeneous two-facility models under social cost and maximum cost objectives. Since then, the field has expanded significantly: Alon et al. [5] explored facility location on circles and graphs, while Tang et al. [6] considered constrained models where facilities are restricted to a discrete set of candidate locations. Other variations include obnoxious facility games, where agents seek to maximize their distance from the facility [7], and studies focused on envy-based objectives [8], [9]. Below, we highlight the two research threads most relevant to our work: heterogeneous and distributed facility location.
Heterogeneous facility location. This line of research considers models where facilities may provide different utilities to agents. Zou and Li [10] investigated dual preferences where a facility could be either desirable or obnoxious. Serafino and Ventre [11] introduced an optional preference model where each agent approves either one facility or both. In their setting, agents’ locations are public while their preferences remain private, and the individual cost is defined as the sum of distances to the facilities of interest (referred to as sum-variant cost). Later, Chen et al. [12] extended this optional preference model to include max-variant and min-variant costs, with the results for the latter subsequently refined by Li et al. [13]. Anastasiadis and Deligkas [14] analyzed heterogeneous \(k\)-facility location problems with min-variant. In scenarios where agents’ locations are private but preferences are public, Zhao et al. [15] explored the optional preference model with max-variant cost, while Kanellopoulos et al. [16] focused on the sum-variant cost. Additionally, Kanellopoulos and Voudouris [17] addressed obnoxious two-facility location with optional preferences, and Deligkas et al. [18] examined heterogeneous facility location under limited resources. Finally, Fong et al. [19] proposed a fractional preference model where an agent’s preference for a facility is represented by a value between 0 and 1, a setting further studied by Fang and Liu [20] in the context of limited resources.
Distributed facility location. Filos-Ratsikas et al. [3] initiated the study of distortion in distributed social choice, which was further extended by Anshelevich et al. [21] to a distributed metric social choice setting where voters and alternatives are represented as points in a metric space. Voudouris [22] investigated the metric distortion of obnoxious distributed voting. Closely related to our work, Filos-Ratsikas and Voudouris [4] analyzed a distributed single-facility location problem under the social cost objective, considering both the discrete setting (where facilities are restricted to a finite set of candidate locations) and the continuous setting (where facilities can be placed at any point on the real line). For the discrete case, they established a tight bound of 7 for strategyproof distributed mechanisms, while for the continuous case, they derived a tight bound of 3. Further, Filos-Ratsikas et al. [23] explored a continuous distributed single-facility location problem under four social objectives: the average cost, the max cost, the average-of-max cost, and the max-of-average cost. A summary of their results is provided in Table 2.
| Social objective | Tight bounds | |
|---|---|---|
| Average cost | \(3\) [23] | |
| Max cost | \(2\) [23] | |
| Max-of-Average cost | \(1+\sqrt{2}\) [23] | |
| Average-of-Max cost | \(1+\sqrt{2}\) [23] |
Let \(N=\left\{1,2,...,n\right\}\) be a set of agents. Each agent \(i\in N\) has a private location \(x_i\in \mathbb{R}\) and denote by \(\mathbf{x}=(x_1,...,x_n)\in \mathbb{R}^n\) the location profile of all agents. The agents are partitioned into \(k\) (\(\ge 1\)) disjoint groups, denoted by the set \(D=\left\{1,...,k\right\}\). For each group \(d\in D\), let \(N_d\subseteq N\) be the set of agents belonging to group \(d\), and let \(n_d=|N_d|\) represent the number of agents in that group.
Let \(\mathcal{F}=\{ F_1,F_2\}\) be the two heterogeneous facilities to be located. Define \(A=\left\{a_1,...,a_m\right\}\in \mathbb{R}^m\) as a multiset of candidate locations, with the constraint that at most one facility can be placed at each location in \(A\). Without loss of generality, assume \(a_1\le a_2\le\cdots\le a_m\). An instance of the problem is denoted by the tuple \(I=(N,\mathbf{x},D,A)\).
Distributed Mechanism. A distributed mechanism \(M\) is a function that maps an instance \(I\) to a facility location profile \(\mathbf{w}\) through two steps, i.e. \(M(I)=\mathbf{w}=(w_1,w_2)\), where \(w_1\in A\) is the location of \(F_1\) and \(w_2\in A\setminus\left\{w_1\right\}\) is the location of \(F_2\). Specifically, for a given instance \(I\), the mechanism \(M\) operates in two steps:
Step \(1\). For each group \(d\in D\), \(M\) selects two representative locations \(y_{d(1)}\in A\), \(y_{d(2)}\in A\setminus \left\{y_{d(1)}\right\}\) based solely on the locations reported by agents in \(N_d\).
Step \(2\). \(M\) outputs a final facility location profile \(\mathbf{w}=(w_1,w_2)\), where \(w_1, w_2\in \{y_{d{(1)}},y_{d{(2)}}\}_{d \in D}\) and \(w_1\neq w_2\), chosen from the set of all group representatives..
Remark 1. Following the distributed framework in Filos-Ratsikas et al. [23], Properties (P1) and (P2) represent the inherent structural characteristics of the mechanism, reflecting the fundamental information-restricted nature of the two-stage decision process:
P1 (Local Aggregation): The representative of each group is determined solely by the positions of agents within that group.
P2 (Information Restriction): The final facility location profile must be a function of the group representatives, as the mechanism only has access to this summarized information in the second stage.
These properties are also essential for deriving our distortion lower bounds.
For any two points \(x,y\in \mathbb{R}\), let \(\delta(x,y)=|x-y|\) be the distance between \(x\) and \(y\). In our model, we assume that all agents approve the two heterogeneous facilities. The individual cost of each agent \(i\) for a facility location profile \(\mathbf{w}\) is the distance to the farthest facility, which we refer to as the max-variant cost: \[c(x_i,\mathbf{w})=\max\left\{\delta(x_i,w_1),\delta(x_i,w_2)\right\}.\]
Social Objectives. We consider four standard cost-minimization social objectives, defined as follows:
(1) The Average-of-Average cost of a facility location profile \(\mathbf{w}\) is the arithmetic mean of the average individual costs across all groups: \[AoA(\mathbf{w}|I) = \frac{1}{k}\sum_{d \in D}\left\{\frac{1}{n_d} \sum_{i \in N_d} c(x_i, \mathbf{w}) \right\}.\]
(2) The Max-of-Max cost of a facility location profile \(\mathbf{w}\) is the maximum individual cost among all agents: \[MoM(\mathbf{w}|I) = \max_{d \in D} \max_{i \in N_d} c(x_i, \mathbf{w}).\]
(3) The Max-of-Average cost of a facility location profile \(\mathbf{w}\) is the maximum of the average individual costs of all groups: \[MoA(\mathbf{w}|I) = \max_{d \in D} \left\{\frac{1}{n_d}\sum_{i \in N_d} c(x_i, \mathbf{w})\right\}.\]
(4) The Average-of-Max cost of a facility location profile \(\mathbf{w}\) is the average of the maximum individual costs within each group: \[AoM(\mathbf{w}|I) = \frac{1}{k}\sum_{d \in D} \max_{i \in N_d} c(x_i, \mathbf{w}).\]
Strategyproofness. A mechanism \(M\) is strategyproof if each agent can never benefit by misreporting her location, regardless of the locations reported by the other agents, i.e., for every \(i\in N\), for every \(\mathbf{x}\in \mathbb{R}^n\), and for every \(x_i'\in \mathbb{R}\), it must hold that
\[c(x_i, M(N, (x_i, \mathbf{x}_{-i}), D, A) \leq c(x_i, M(N, (x_i', \mathbf{x}_{-i}), D, A)) ,\] where \(\mathbf{x}_{-i} = (x_1, \ldots, x_{i-1}, x_{i+1}, \ldots, x_n)\) is the location profile of \(N\setminus\{i\}\).
Distortion. In the distributed setting, due to lack of global information and the requirement for strategyproofness of a mechanism, the facility location profile chosen by a distributed mechanism may be suboptimal. Here, we adopt the notion of distortion to quantify the performance gap between a mechanism and the optimal mechanism. Formally, the distortion of a distributed mechanism \(M\) is the worst-case ratio between the social objective value obtained by \(M\) and the optimal social objective value, taken over all possible instances:
\[\text{dist}(M) = \sup_{I} \frac{\text{cost}(M(I) \mid I)}{\text{cost}(OPT(I) \mid I)},\] where \(OPT(I)\) denotes the optimal solution for instance \(I\) and cost \(\in\{AoA,\) \(MoM, MoA, AoM\}\) represents the social objective function. For notational simplicity, we abbreviate \(\text{cost}(M(I)|I)\) as \(\text{cost}(M|I)\).
For each agent \(i\in N\), let \(t({i})\) denote the closest candidate location to \(i\) in the set \(A\), and \(s(i)\) denote the closest candidate location to \(i\) in \(A\setminus \{t(i)\}\). We now introduce a class of distributed mechanisms, termed the \((\alpha,\beta)\)-Quantile Mechanism (with \(\alpha,\beta\in [0,1]\)).
\(\boldsymbol{(\alpha,\beta)}\)-Quantile Mechanism1
Step 1. For each group \(d\in D\), let \(\alpha_d\) be the \(\lceil\alpha\cdot n_d\rceil\)-th leftmost agent in \(N_d\). Define \(y_{d(1)}=t({\alpha_d})\) and \(y _{d(2)}=s({\alpha_d})\) as the two representative locations for group \(d\).
Step 2. Initialize \(z_d=y_{d(1)}\) for all \(d\in D\) and let \(w_1\) be the \(\lceil\beta\cdot k\rceil\)-th leftmost location in the set \(\{z_d\}_{d\in D}\). For each group \(d\in D\), update \(z_d\) to \(y_{d(2)}\) if \(y_{d(1)}=w_1\), then set \(w_2\) to be the \(\lceil\beta\cdot k\rceil\)-th leftmost location in the updated set \(\{z_d\}_{d\in D}\).
Remark 2. The \((\alpha,\beta)\)-Quantile Mechanism naturally satisfies the following key properties. For every group \(d\), \(y_{d(1)}\), \(y_{d(2)}\) are consecutive candidate locations, which implies that the pairs \((y_{d(1)},y_{d(2)})\) and \((y_{d'(1)},y_{d'(2)})\) are never "interlaced" 2 for any two distinct groups \(d\) and \(d'\). Consequently, the output locations \(w_1\), \(w_2\) of the mechanism must correspond to the two consecutive representative locations of a single group \(d\), i.e., \(w_1=y_{d(1)}\), \(w_2=y_{d(2)}\).
We will prove that the \((\alpha,\beta)\)-Quantile Mechanism is strategyproof.
Theorem 1. The \((\alpha,\beta)\)-Quantile Mechanism is strategyproof.
Proof. Consider any instance \(I\), and let \(\mathbf{w}=(w_1,w_2)\) be the facility location profile output by the mechanism. By the property of the mechanism established in Remark 2, \(w_1\) and \(w_2\) must be two consecutive candidate locations that are the closest and second-closest to some agent \(j\), i.e., \(w_1=t(x_j)\), \(w_2=s(x_j)\).
Let \(i\) be any agent in group \(d\), and assume without loss of generality (w.l.o.g.) that \(x_i \leq x_{\alpha_d}\) (the \(\lceil \alpha \cdot n_d \rceil\)-th leftmost agent in \(N_d\)). We analyze all possible orderings of \(x_i, x_j, x_{\alpha_d}\) to show that agent \(i\) has no incentive to misreport its location.
Case 1: \(x_i\le x_{\alpha_d}\le x_j\). To alter the mechanism’s output, agent \(i\) must first become the \(\lceil \alpha \cdot n_d \rceil\)-th leftmost agent in \(N_d\), which requires reporting \(x'_i > x_{\alpha_d}\). If \(x_j\ge x_i' > x_{\alpha_d}\), the mechanism’s output remains unchanged, so agent \(i\) has no incentive to misreport. If \(x_i' > x_j\), The output becomes the two consecutive locations closest to some agent \(k\) with \(x_k \geq x_j\). This cannot decrease agent \(i\)’s cost, so \(i\) still has no incentive to misreport.
Case 2: \(x_i<x_j< x_{\alpha_d}\). To alter the output, agent \(i\) would need to report \(x'_i > x_{\alpha_d}\) to become the \(\lceil \alpha \cdot n_d \rceil\)-th leftmost agent in \(N_d\). However, this manipulation leaves the mechanism’s output unchanged, so \(i\) has no incentive to misreport.
Case 3: \(x_j<x_i\le x_{\alpha_d}\). This case is symmetric to Case 1, and agent \(i\) has no incentive to misreport its location.
Thus, the \((\alpha,\beta)\)-Quantile Mechanism is strategyproof. ◻
In the subsequent sections, we analyze the upper bounds on the distortion of the \((\alpha, \beta)\)-Quantile Mechanism under four social objective functions, by tuning the parameters \(\alpha\) and \(\beta\).
Notations. Let \(l, r,\) and \(m\) denote the leftmost, rightmost, and median agent in \(N\), respectively. Similarly, let \(l_d, r_d,\) and \(m_d\) denote the leftmost, rightmost, and median agent in \(N_d\), respectively. For a facility location profile \(\mathbf{w} = (w_1, w_2)\) and any agent \(i \in N\), let \(w(x_i)\) denote the location in \(\{w_1, w_2\}\) that is farther from agent \(i\).
In this section, we study the Average-of-Average cost, defined as the arithmetic mean of the average individual costs across all groups. For the lower bound, we prove that the distortion of any strategyproof mechanism is at least \(3-\epsilon\) for any \(\epsilon>0\). For the upper bound, we analyze the \(\left(\frac{1}{2}, \frac{1}{2}\right)\)-Quantile Mechanism3, which achieves a distortion of at most \(9\).
Theorem 2. For the Average-of-Average cost, the distortion of any strategyproof mechanism is at least \(3-\epsilon\), for any \(\epsilon>0\).
Proof. We proceed by contradiction. Assume there exists a strategyproof mechanism \(M\) with distortion strictly smaller than \(3 - \epsilon\) for some \(\epsilon > 0\), and let \(\theta > 0\) be an infinitesimal. We derive a contradiction by analyzing the following instances, with the set of candidate locations \(A = \{0, 0, 1, 1\}\).
Instance \(I_1\). Consider an instance \(I_1\) with a single group containing one agent located at \(x^1_1 = 0\). By strategyproofness, \(M\) must output \((0,0)\) as the group’s representative, i.e., \(M(I_1) = (0,0)\); otherwise, the distortion of \(M\) would be unbounded.
Instance \(I_2\). Consider an instance \(I_2\) with a single group containing one agent located at \(x^2_1 = \frac{1}{2} - \theta\). If \(M(I_2) \neq (0,0)\), then \(c(x^2_1, M(I_2)) = \frac{1}{2} + \theta\). Since \(c(x^2_1, M(I_1)) = \frac{1}{2} - \theta\), the agent could strictly reduce her cost by misreporting her location as \(0\), violating strategyproofness. Thus, \(M(I_2) = (0,0)\).
Instance \(I_3\). Consider an instance \(I_3\) with a single group containing one agent located at \(x^3_1 = 1\). By the same argument as in \(I_1\), we obtain \(M(I_3) = (1,1)\).
Instance \(I_4\). Consider an instance \(I_4\) with a single group containing one agent located at \(x^4_1 = \frac{1}{2} + \theta\). By the same argument as in \(I_2\), we conclude that \(M(I_4) = (1,1)\).
Instance \(I_5\). Consider an instance \(I_5\) with two groups:
In group 1, there is a single agent located at \(\frac{1}{2} - \theta\).
In group 2, there is a single agent located at \(1\).
By \(M(I_2) = (0,0)\) and \(M(I_3) = (1,1)\), \((P1)\) implies that the representatives of group 1 and group 2 in \(I_5\) are \((0,0)\) and \((1,1)\), respectively. Since \(AoA(0,0)=\frac{3}{4}-\frac{\theta}{2}\), \(AoA(0,1)=AoA(1,0)=\frac{3}{4}+\frac{\theta}{2}\) and \(AoA(1,1)=\frac{1}{4}+\frac{\theta}{2}\), Thus, \(M\) must output \((1,1)\) as the global facility location profile, i.e., \(M(I_5) = (1,1)\). Otherwise, the distortion of \(M\) is at least \(\frac{\frac{3}{2}-\theta}{\frac{1}{2}+\theta}\ge3-\epsilon\), for \(\theta\le\frac{\epsilon}{8-2\epsilon}\).
Instance \(I_6\). We now derive a contradiction by considering the following instance \(I_6\) with two groups:
In group 1, there is a single agent located at \(\frac{1}{2} + \theta\).
In group 2, there is a single agent located at \(0\).
By \(M(I_4) = (1,1)\) and \(M(I_1) = (0,0)\), \((P1)\) implies that the representatives of group 1 and group 2 in \(I_6\) are \((1,1)\) and \((0,0)\), respectively. Since the group representatives in \(I_5\) and \(I_6\) are identical, \((P2)\) guarantees that \(M(I_6) = (1,1)\). Since \(AoA(0,0)=\frac{1}{4}+\frac{\theta}{2}\), \(AoA(0,1)=AoA(1,0)=\frac{3}{4}+\frac{\theta}{2}\) and \(AoA(1,1)=\frac{3}{4}-\frac{\theta}{2}\), the distortion of \(M\) is at least \(\frac{\frac{3}{2}-\theta}{\frac{1}{2}+\theta}\ge3-\epsilon\), for \(\theta\le\frac{\epsilon}{8-2\epsilon}\). This directly contradicts the assumption that \(M\) achieves a distortion strictly smaller than \(3 - \epsilon\). ◻
We next present the \(\left(\frac{1}{2}, \frac{1}{2}\right)\)-Quantile Mechanism and prove that its distortion is at most 9.
\(\boldsymbol{\left(\frac{1}{2}, \frac{1}{2}\right)}\)-Quantile Mechanism
Step 1. For each group \(d\in D\) , set \(y_{d(1)}=t({m_d})\), \(y _{d(2)}=s({m_d})\).
Step 2. Initialize \(z_d=y_{d(1)}\) for all \(d\in D\) and let \(w_1\) be the median location in the set \(\{z_d\}_{d\in D}\). For each group \(d\in D\), update \(z_d\) to \(y_{d(2)}\) if \(y_{d(1)}=w_1\), then set \(w_2\) to be the median location in the updated set \(\{z_d\}_{d\in D}\).
Theorem 3. For the Average-of-Average cost, the distortion of the \(\left(\frac{1}{2}, \frac{1}{2}\right)\)-Quantile Mechanism is at most \(9\).
Proof. Given any instance \(I\) , let \(\mathbf{w}=(w_1,w_2)\) be the location profile chosen by the mechanism and \(\mathbf{o}=(o_1,o_2)\) be an optimal solution. Without loss of generality, we assume that \(w_1\le w_2\) and \(o_1\le o_2\). By the property of the mechanism, there exists a group \(d^*\) such that \(w_1 = y_{d^*(1)} = t({m_{d^*}})\) and \(w_2 = y_{d^*(2)} =s(m_{d^*})\). For each group \(d\in D\), let \(N_{d(1)}=\{i\in N_{d}|w(x_i)=w_1\}\) and \(N_{d(2)}=\{i\in N_{d}|w(x_i)=w_2\}\). Using the triangle inequality, we have \[\begin{align} AoA(\mathbf{w}) &= \frac{1}{k}\sum_{d \in D} \left\{ \frac{1}{n_d}\sum_{i \in N_{d(1)}} \delta(x_i, w_1) +\frac{1}{n_d} \sum_{i \in N_{d(2)}} \delta(x_i, w_2) \right\}\\ & \leq\frac{1}{k} \sum_{d \in D} \left\{\frac{1}{n_d} \sum_{i \in N_{d(1)}} \left[ \delta(x_i, o_1) + \delta(o_1, w_1) \right] + \frac{1}{n_d}\sum_{i \in N_{d(2)}} \left[ \delta(x_i, o_2) + \delta(o_2, w_2) \right] \right\}\\ &= AoA(\mathbf{o})+\frac{1}{k}\sum_{d \in D} \left\{\frac{1}{n_d}\sum_{i \in N_{d(1)}} \delta(o_1, w_1) +\frac{1}{n_d}\sum_{i \in N_{d(2)}} \delta(o_2, w_2) \right\}. \end{align}\]
Case 1: \(o_1 \leq o_2 < w_1 \leq w_2\). Since \(\delta(o_1,w_1)\le \delta(o_1,w_2)\) and \(\delta(o_2,w_2)\le \delta(o_1,w_2)\), we have \[\begin{align} AoA(\mathbf{w}) &\le AoA(\mathbf{o})+\frac{1}{k}\sum_{d \in D} \left\{\frac{1}{n_d}\sum_{i \in N_{d(1)}} \delta(o_1, w_1) +\frac{1}{n_d}\sum_{i \in N_{d(1)}} \delta(o_2, w_2) \right\}\\ &\le AoA(\mathbf{o})+\delta(o_1,w_2). \label{2} \end{align}\tag{1}\]
Let \(S=\{ d\in D\mid y_{d(1)}\ge w_1, y_{d(2)}\ge w_1\}\). For each group \(d\in D\), since \(y_{d(1)}\), \(y_{d(2)}\) are consecutive, \(w_1\) is the median location in \(\{ z_{d} \}_{d \in D}=\{ y_{d(1)} \}_{d \in D}\), and \(w_2\) is the median location in the updated \(\{ z_{d} \}_{d \in D}\), we have \(|S| \geq \frac{1}{2} k\). For each group \(d\in S\), let \(T_d = \{ i \in N_d \mid x_i \geq x_{m_d} \}\). By the definition of \(m_d\), we have \(|T_d|\ge \frac{1}{2} n_d\). As \(w_1\) and \(w_2\) are the closest locations to \(m_{d^*}\), it holds that \(x_{m_{d^*}} \ge \frac{o_2 + w_2}{2}\). Thus, we have \(\delta(x_i, o_1) \geq \delta(o_1, o_2) + \frac{\delta(o_2, w_2)}{2}\ge \frac{\delta(o_1,w_2)}{2}\) for all \(d \in S\) and \(i\in T_d\). Hence, \[\begin{align} AoA(\mathbf{o}) &\ge \frac{1}{k}\sum_{d \in D} \left\{\frac{1}{n_d}\sum_{i \in N_{d}} \delta(x_i, o_1) \right\}\ge \frac{1}{k}\sum_{d \in S} \left\{\frac{1}{n_d}\sum_{i \in T_{d}} \delta(x_i, o_1) \right\}\\ &\ge \frac{1}{k}\sum_{d \in S} \left\{\frac{1}{n_d}\sum_{i \in T_{d}} \frac{\delta(o_1,w_2)}{2} \right\}\ge \frac{\delta(o_1,w_2)}{8}. \label{3} \end{align}\tag{2}\]
Combining 1 and 2 , we obtain \[\begin{align} AoA(\mathbf{w}) &\le AoA(\mathbf{o})+\delta(o_1,w_2)\le 9\cdot AoA(\mathbf{o}). \end{align}\]
Case 2: \(o_1 < o_2 = w_1< w_2\). Similar to Case 1, we obtain \(AoA(\mathbf{w}) \le 9\cdot AoA(\mathbf{o}).\)
Case 3: \(w_1 \le w_2 < o_1 \le o_2\). In this case, since \(\delta(o_1,w_1)\le \delta(o_2,w_1)\) and \(\delta(o_2,w_2)\le \delta(o_2,w_1)\), we have \[\label{5} \begin{align} AoA(\mathbf{w}) \le AoA(\mathbf{o})+\delta(o_2,w_1). \end{align}\tag{3}\]
Similar to Case 1, let \(S' = \{ d \in D \mid y_{d(1)} \le w_1\}\). As \(w_1\) is the median location in \(\{ y_{d(1)} \}_{d \in D}\), we have \(|S'| \geq \frac{1}{2} k\). For each group \(d\in S'\), let \(T'_d = \{ i \in N_d \mid x_i \le x_{m_d} \}\). By the definition of \(m_d\), \(|T'_d|\ge \frac{1}{2} n_d\). Since \(w_1\) and \(w_2\) are the closest locations to \(m_{d^*}\), it holds that \(x_{m_{d^*}}\le \frac{w_1+w_2}{2}\). Thus, we have \(\delta(x_i, o_2) \geq \delta(o_2, w_2) + \frac{\delta(w_1, w_2)}{2}\ge \frac{\delta(o_2,w_1)}{2}\) for all \(d \in S'\) and \(i\in T'_d\). Hence, \[\label{6} AoA(\mathbf{o}) \ge \frac{1}{k}\sum_{d \in S'} \left\{\frac{1}{n_d}\sum_{i \in T'_{d}} \delta(x_i, o_2) \right\}\ge \frac{1}{k}\sum_{d \in S'} \left\{\frac{1}{n_d}\sum_{i \in T'_{d}} \frac{\delta(o_2,w_1)}{2} \right\}\ge \frac{\delta(o_2,w_1)}{8}.\tag{4}\]
Therefore, combining (3 ) and (4 ), we obtain \[AoA(\mathbf{w})\le AoA(\mathbf{o})+\delta(o_2,w_1)\le 9\cdot AoA(\mathbf{o}).\]
Case 4: \(w_1 <w_2 = o_1\le o_2\). Similar to Case 3, we obtain \({AoA}(\mathbf{w})\le 9\cdot AoA(\mathbf{o}).\)
Case 5: \(o_1 < w_1 \le w_2 \le o_2\). In this case, \(AoA(\mathbf{w})\leq AoA(\mathbf{o}) + \delta(o_1, o_2).\) Clearly, \[\begin{align} AoA(\mathbf{o}) \ge \frac{1}{k}\sum_{d \in D} \left\{\frac{1}{n_d}\sum_{i \in N_{d}} \delta(x_i, o_1) \right\}, AoA(\mathbf{o}) \ge \frac{1}{k}\sum_{d \in D} \left\{\frac{1}{n_d}\sum_{i \in N_{d}} \delta(x_i, o_2) \right\} \end{align}\]
Using the triangle inequality, we have \[\begin{align} AoA(\mathbf{o}) &\ge \frac{1}{2k}\sum_{d \in D} \left\{\frac{1}{n_d}\sum_{i \in N_{d}} \left[\delta(x_i, o_1)+\delta(x_i,o_2)\right]\right\}\\ &\ge \frac{1}{2k}\sum_{d \in D} \left\{\frac{1}{n_d}\sum_{i \in N_{d}} \delta(o_1, o_2)\right\}\ge \frac{\delta(o_1,o_2)}{2}. \end{align}\]
Therefore, we obtain \(AoA(\mathbf{w})\le 3\cdot AoA(\mathbf{o}).\)
Case 6: \(o_1= w_1\le w_2<o_2\). Similar to Case 5, we obtain \(AoA(\mathbf{w})\le 3\cdot AoA(\mathbf{o}).\)
Thus, we conclude that \(AoA(\mathbf{w})\le 9\cdot AoA(\mathbf{o}).\) ◻
Remark 3. In the facility location problem, the most natural social objective is the social cost. In fact, our results under the average-of-average cost can be easily generalized to the social cost.
In this section, we study the Max-of-Max cost, defined as the maximum individual cost among all agents. For the lower bound, we prove that the distortion of any strategyproof mechanism is at least \(3-\epsilon\) for any \(\epsilon>0\). For the upper bound, we analyze the \((1,1)\)-Quantile mechanism4, which achieves a distortion of at most \(3\).
Theorem 4. For the Max-of-Max cost, the distortion of any strategyproof mechanism is at least \(3-\epsilon\), for any \(\epsilon>0\).
Proof. We proceed by contradiction. Assume that there exists a strategyproof mechanism \(M\) with distortion strictly smaller than \(3-\epsilon\) for some \(\epsilon>0\), and let \(\theta>0\) be sufficiently small. We derive a contradiction by constructing a sequence of instances with candidate location set \(A = \{0,0,2,2,4,4\}\).
Instance \(I_1\). Consider an instance \(I_1\) consisting of a single group with two agents located at \(-1\) and \(1-\theta\). By computing the MoM cost for all possible facility location pairs in \(A\), we have \(OPT(I_1)=(0,0)\). Thus, \(M(I_1)=(0,0)\); otherwise its distortion would be at least \(3\), contradicting the assumption.
Instance \(I_2\). Consider an instance \(I_2\) with a single group containing two agents both at \(1-\theta\). If \(M\) does not output \((0,0)\) on \(I_2\), then the agent’s cost would be at least \(1+\theta\). Since the agent can reduce her cost to \(1-\theta\) by misreporting her location as \(-1\), strategyproofness implies \(M(I_2)=(0,0)\).
Instance \(I_3\). Consider an instance \(I_3\) with a single group containing two agents at \(5\) and \(3+\theta\). By symmetry with \(I_1\), we have \(OPT(I_3)=(4,4)\), so \(M\) must output \((4,4)\) to avoid distortion at least \(3\).
Instance \(I_4\). Consider an instance \(I_4\) with a single group containing two agents both at \(3+\theta\). Using the same strategyproofness argument as in \(I_2\), we obtain \(M(I_4)=(4,4)\).
Instance \(I_5\). Consider an instance \(I_5\) with two groups: group 1 has two agents at \(1-\theta\), and group 2 has two agents at \(3+\theta\). By \(M(I_2)=(0,0)\) and \(M(I_4)=(4,4)\), (P1) implies that the group representatives in \(I_5\) are \((0,0)\) and \((4,4)\). Therefore, \(M\) can only output \((0,0)\), \((0,4)\), \((4,0)\), or \((4,4)\), all of which yield MoM cost \(3+\theta\). However, \(OPT(I_5)=(2,2)\) and \(MoM(OPT|I_5)=1+\theta\). As a result, the distortion of \(M\) is at least \[\frac{3+\theta}{1+\theta} \ge 3-\epsilon,\] for sufficiently small \(\theta\), which is a contradiction. ◻
We next present the \((1,1)\)-Quantile Mechanism and prove that its distortion is at most 3.
\(\boldsymbol{(1,1)}\)-Quantile Mechanism
Step 1. For each group \(d\in D\) , set \(y_{d(1)}=t({r_d})\), \(y _{d(2)}=s({r_d})\).
Step 2. Initialize \(z_d=y_{d(1)}\) for all \(d\in D\) and let \(w_1\) be the rightmost location in the set \(\{z_d\}_{d\in D}\). For each group \(d\in D\), update \(z_d\) to \(y_{d(2)}\) if \(y_{d(1)}=w_1\), then set \(w_2\) to be the rightmost location in the updated set \(\{z_d\}_{d\in D}\).
Theorem 5. For the Max-of-Max cost, the distortion of the \((1,1)\)-Quantile mechanism is at most 3.
Proof. Given any instance \(I\), let \(\mathbf{w} = (w_1,w_2)\) be the location profile chosen by the mechanism and \(\mathbf{o}= (o_1,o_2)\) be an optimal solution. By the property of the mechanism, we have \(w_1 = t(r)\) and \(w_2 = s(r)\). Let \(i^*\) denote the agent such that \(MoM(\mathbf{w}) = \max\{\delta(x_{i^*}, w_1), \delta(x_{i^*}, w_2)\} = \delta(x_{i^*}, w(x_{i^*}))\). As \(w_1=t(r)\) and \(w_2=s(r)\) are the closest candidate locations to \(r\) and using the triangle inequality, we have \[\begin{align} MoM(\mathbf{w}) &= \delta(x_{i^*}, w(x_{i^*})) \\ &\leq \delta(x_{i^*}, o_1) + \delta(o_1, x_r) + \delta(x_r, w(x_{i^*}))\\ &\le \delta(x_{i^*}, o(x_{i^*})) + \delta(x_r, o(x_r)) + \delta(x_r, w(x_r)) \\ &\le \delta(x_{i^*}, o(x_{i^*})) + 2 \cdot \delta(x_r, o(x_r)). \end{align}\]
For the optimal solution \(\mathbf{o}\), we have \(MoM(\mathbf{o}) \geq \delta(x_i, o(x_i))\) for all \(i\in N\). Thus, we obtain \[MoM(\mathbf{w})\leq \delta(x_{i^*},o(x_{i^*}))+2\cdot \delta(x_r,o(x_r))\leq3\cdot MoM(\mathbf{o}).\] ◻
In this section, we study the Max-of-Average cost, defined as the maximum of the average individual costs of all groups. For the lower bound, we prove that the distortion of any strategyproof mechanism is at least \(\frac{7}{2}-\epsilon\) for any \(\epsilon>0\). For the upper bound, we analyze the \((\frac{3-\sqrt{5}}{2},1)\)-Quantile Mechanism, which achieves a distortion of at most \(2+\sqrt{5}\).
Theorem 6. For the Max-of-Average cost, the distortion of any strategyproof mechanism is at least \(\frac{7}{2}-\epsilon\), for any \(\epsilon>0\).
Proof. We proceed by contradiction. Assume that there exists a strategyproof mechanism \(M\) with distortion strictly smaller than \(\frac{7}{2}-\epsilon\) for some \(\epsilon>0\), and let \(\theta>0\) be sufficiently small. We consider the following instances with candidate location set \(A = \{0,0,1,1,2,2\}\).
Instance \(I_1\). Consider an instance \(I_1\) with a single group containing five agents located at \(0,0,0,0,1\). We compute the MoA costs for all facility location pairs in \(A\), and obtain that \(OPT(I_1)=(0,0)\). Thus, \(M(I_1)=(0,0)\); otherwise the distortion would be at least \(4\), which contradicts the assumption.
Instance \(I_2\). Consider an instance \(I_2\) with a single group containing five agents located at \(\frac{1}{2}-\theta,0,0,0,1\). If \(M\) does not output \((0,0)\) on \(I_2\), then the cost of the agent at \(\frac{1}{2}-\theta\) would be at least \(\frac{1}{2}+\theta\). Since the agent can reduce her cost to \(\frac{1}{2}-\theta\) by misreporting her location as \(0\), strategyproofness implies \(M(I_2)=(0,0)\).
Instance \(I_3\). Consider an instance \(I_3\) with a single group containing five agents located at \(\frac{1}{2}-\theta,\frac{1}{2}-\theta,\frac{1}{2}-\theta,\frac{1}{2}-\theta,1\). By the same strategyproofness argument as in \(I_2\), we have \(M(I_3)=(0,0)\).
Instance \(I_4\). Consider an instance \(I_4\) with a single group containing five agents located at \(2,2,2,2,1\). By symmetry with \(I_1\), we have \(OPT(I_4)=(2,2)\), and thus \(M(I_4)=(2,2)\).
Instance \(I_5\). Consider an instance \(I_5\) with a single group containing five agents located at \(\frac{3}{2}+\theta,\frac{3}{2}+\theta,\frac{3}{2}+\theta,\frac{3}{2}+\theta,1\). By the same strategyproofness argument as in \(I_3\), we obtain \(M(I_5)=(2,2)\).
Instance \(I_6\). Consider an instance \(I_6\) with two groups: the first group contains four agents at \(\frac{1}{2}-\theta\) and one agent at \(1\), and the second group contains four agents at \(\frac{3}{2}+\theta\) and one agent at \(1\). By \(M(I_3)=(0,0)\) and \(M(I_5)=(2,2)\), (P1) implies that the group representatives in \(I_6\) are \((0,0)\) and \((2,2)\). Therefore, \(M\) can only output \((0,0)\), \((0,2)\), \((2,0)\), or \((2,2)\), and the corresponding MoA cost is \(\frac{7+4\theta}{5}\). However, \(OPT(I_6)=(1,1)\) and \(MoA(OPT|I_6)=\frac{2+4\theta}{5}\). As a result, the distortion of \(M\) is at least \[\frac{7+4\theta}{2+4\theta} \ge \frac{7}{2}-\epsilon,\] for sufficiently small \(\theta\), which is a contradiction. ◻
We first present the \((\alpha,1)\)-Quantile Mechanism and analyze its performance.
\(\boldsymbol{(\alpha,1)}\)-Quantile Mechanism
Step 1. For each group \(d\in D\) , let \(\alpha_d\) denote the \(\lceil\alpha\cdot n_d\rceil\)-th leftmost agent in \(N_d\). Set \(y_{d(1)}=t({\alpha_d})\), \(y _{d(2)}=s({\alpha_d})\).
Step 2. Initialize \(z_d=y_{d(1)}\) for all \(d\in D\) and let \(w_1\) be the rightmost location in \(\{z_d\}_{d\in D}\). For each group \(d\in D\), update \(z_d\) to \(y_{d(2)}\) if \(y_{d(1)}=w_1\), then set \(w_2\) to be the rightmost location in \(\{z_d\}_{d\in D}\).
Lemma 1. For the Max-of-Average cost, the distortion of the \((\alpha,1)\)-Quantile Mechanism is at most \(\max \left\{ 1+\frac{2(1-\alpha)}{\alpha}, 1 + \frac{2}{1 - \alpha}\right\}\).
Proof. Given any instance \(I\), let \(\mathbf{w}= (w_1, w_2)\) be the location profile chosen by the mechanism and \(\mathbf{o} = (o_1, o_2)\) be an optimal solution. Assume w.l.o.g. that \(w_1 \leq w_2\) and \(o_1 \leq o_2\). By the property of the mechanism, there exists a group \(d^*\) such that \(w_1 = y_{d^*(1)} = t({\alpha_{d^*}})\) and \(w_2 = y_{d^*(2)} =s(\alpha_{d^*})\). Let \(d'\) denote the group with the maximum average individual cost under \(\mathbf{w}\), so that \(MoA(\mathbf{w})=\frac{1}{n_{d'}}\sum_{i\in N_{d'}}\delta(x_i,w(x_i) )\). Let \(N_{d'(1)}=\{i\in N_{d'}|w(x_i)=w_1\}\) and \(N_{d'(2)}=\{i\in N_{d'}|w(x_i)=w_2\}\).
Case 1: \(o_1 \leq o_2 < w_1 \leq w_2\). By the definition of \(d'\) and the triangle inequality, we have \[\label{13} \begin{align} MoA(\mathbf{w}) &=\frac{1}{n_{d'}}\sum_{i \in N_{d'(1)} } \delta(x_i, w_1) + \frac{1}{n_{d'}}\sum_{i \in N_{d'(2)} } \delta(x_i, w_2)\\ &\leq\frac{1}{n_{d'}} \sum_{i \in N_{d'} } \delta(x_i, o(x_i)) + \frac{1}{n_{d'}}\sum_{i \in N_{d'(1)} } \delta(o_1, w_1) + \frac{1}{n_{d'}}\sum_{i \in N_{d'(2)} } \delta(o_2, w_2)\\ &\leq MoA(\mathbf{o}) + \delta(o_1, w_2). \end{align}\tag{5}\]
Let \(S=\left\{i\in N_{d^*}|x_i\ge x_{\alpha_{d^*}}\right\}\). By the definition of \(\alpha_{d^*}\), \(\left|S\right|\ge (1-\alpha)\cdot n_{d^*}\). Since \(o_1 \leq o_2 < w_1 \leq w_2\) and \(w_1\), \(w_2\) are the closest locations to \(\alpha_{d^*}\), all agents in \(S\) are closer to \(\mathbf{w}=(w_1,w_2)\) than \(\mathbf{o}=(o_1, o_2)\). So we have \(\delta(x_i,o_2)\ge \frac{\delta(o_2,w_2)}{2}\) and \(\delta(x_i,o_1)\ge \delta(o_1,o_2)+\frac{\delta(o_2,w_2)}{2}\) for all \(i\in S\). Using these properties, we have \[\begin{align} MoA(\mathbf{o})&\ge\frac{1}{n_{d^*}}\sum_{i \in N_{d^*} } \delta(x_i, o(x_i))\ge\frac{1}{n_{d^*}}\sum_{i \in S } \delta(x_i, o_1) \\ &\ge(1-\alpha)\cdot\left[\frac{\delta(o_2,w_2)}{2}+\delta(o_1,o_2)\right], \end{align}\]
and \[\begin{align} MoA(\mathbf{o})\ge\frac{1}{n_{d^*}}\sum_{i \in S } \delta(x_i, o_2) \ge(1-\alpha)\cdot\frac{\delta(o_2,w_2)}{2}. \end{align}\]
Then, it follows that \[\label{16} \begin{align} MoA(\mathbf{o})&\ge\frac{(1-\alpha)}{2}\cdot\delta(o_1,w_2). \end{align}\tag{6}\]
Comining (5 ) and (6 ), we obtain \[\begin{align} MoA(\mathbf{w})&\le MoA(\mathbf{o})+\delta(o_1,w_2)\le \left(1+\frac{2}{1-\alpha}\right)\cdot MoA(\mathbf{o}). \end{align}\]
Case 2: \(o_1 <o_2 = w_1 < w_2\). Similar to Case 1, we obtain \[\begin{align} MoA(\mathbf{w})\le \left(1+\frac{2}{1-\alpha}\right)\cdot MoA (\mathbf{o}). \end{align}\]
Case 3: \(w_1\le w_2 <o_1 \le o_2\). Let \(L\) be the set of agents in \(N_{d'}\) from the first leftmost agent to \(\alpha_{d'}\) and \(R\) be the set of remaining agents in \(N_{d'}\). By the definition of \(\alpha_{d'}\), we have \(\left|L\right|=\alpha\cdot n_{d'}\) and \(\left|R\right|=(1-\alpha)\cdot n_{d'}\). Since \(w_1=\max\left\{y_{d(1)}\right\}_{d\in D}\), it follows that \(y_{d'(1)}\le w_1\le w_2<o_1\le o_2\). As \(y_{d'(1)}\) is the closest location to \(\alpha_{d'}\), we have \(\delta(x_i,w(x_i))\le \delta(x_i,o(x_i))\) for all \(i\in L\). Using these properties, we obtain \[\label{19} \begin{align} MoA(\mathbf{w}) &= \frac{1}{n_{d'}}\sum_{i \in L} \delta(x_i, w(x_i)) + \frac{1}{n_{d'}}\sum_{i \in R} \delta(x_i, w(x_i))\\ &\leq \frac{1}{n_{d'}}\sum_{i \in L} \delta(x_i, o(x_i)) +\frac{1}{n_{d'}} \sum_{i \in R \cap N_{d'(1)}} \delta(x_i,w_1)+ \frac{1}{n_{d'}}\sum_{i \in R \cap N_{d'(2)}} \delta(x_i,w_2)\\ &\leq \frac{1}{n_{d'}}\sum_{i \in L} \delta(x_i, o(x_i)) + \frac{1}{n_{d'}}\sum_{i \in R \cap N_{d'(1)}} [\delta(x_i,o_1)+\delta(o_1,w_1)] \\ &+ \frac{1}{n_{d'}}\sum_{i \in R \cap N_{d'(2)}} [\delta(x_i, o_2) + \delta(o_2, w_2)] \\ &\leq MoA(\mathbf{o}) + (1 - \alpha) \cdot \delta(o_2, w_1). \end{align}\tag{7}\]
Since all agents in \(L\) are closer to \(\mathbf{w}=(w_1,w_2)\) than \(\mathbf{o}=(o_1,o_2)\), we have \(\delta(x_i,o_2)\ge \frac{\delta(w_1,w_2)}{2}+\delta(o_2,w_2)\) (when \(w_1\ne w_2\)) and \(\delta(x_i,o_2)\ge \frac{\delta(o_1,w_2)}{2}+\delta(o_1,o_2)\) (when \(w_1=w_2\)) for all \(i\in L\). Thus, \[\label{20} \begin{align} MoA(\mathbf{o})&\ge\frac{1}{n_{d'}}\sum_{i \in N_{d'} } \delta(x_i, o(x_i))\ge\frac{1}{n_{d'}}\sum_{i \in L } \delta(x_i, o_2) \\ &\ge\alpha\cdot\left[\frac{\delta(w_1,w_2)+\delta(o_2,w_2)}{2} \right]\ge \frac{\alpha}{2}\cdot\delta(o_2,w_1). \end{align}\tag{8}\]
Comining (7 ) and (8 ), we obtain \[\begin{align} MoA(\mathbf{w})\le MoA(\mathbf{o})+(1-\alpha)\cdot\delta(o_2,w_1)\le \left(1+\frac{2(1-\alpha)}{\alpha}\right)\cdot MoA(\mathbf{o}). \end{align}\]
Case 4: \(w_1 <w_2=o_1\le o_2\). Similar to Case 3, we obtain \[MoA(\mathbf{w})\le \left(1+\frac{2(1-\alpha)}{\alpha}\right)\cdot MoA(\mathbf{o}).\]
Case 5: \(o_1< w_1\le w_2\le o_2\). By the definition of \(d'\) and the triangle inequality, we have \[\label{MoA9} \begin{align} MoA(\mathbf{w})&=\frac{1}{n_{d'}}\sum_{i \in N_{d'(1)} } \delta(x_i, w_1) + \frac{1}{n_{d'}}\sum_{i \in N_{d'(2)} } \delta(x_i, w_2)\\ &\leq MoA(\mathbf{o}) + \delta(o_1, o_2). \end{align}\tag{9}\]
Clearly, \(MoA(\mathbf{o})\ge \frac{1}{n_{d'}}\sum_{i \in N_{d'} } \delta(x_i, o_1)\) and \(MoA(\mathbf{o})\ge\frac{1}{n_{d'}} \sum_{i \in N_{d'} } \delta(x_i, o_2)\). Adding these two inequalities and applying the triangle inequality again, we have \[\label{MoA10} \begin{align} MoA(\mathbf{o})&\ge\frac{1}{2n_{d'}}\cdot\sum_{i \in N_{d'} } [\delta(x_i, o_1)+\delta(x_i,o_2)]\ge\frac{1}{2}\cdot\delta(o_1,o_2) \end{align}\tag{10}\]
Combining (9 ) and (10 ), we obtain \(MoA(\mathbf{w})\le 3\cdot MoA(\mathbf{o}).\)
Case 6: \(o_1=w_1\le w_2<o_2\). Similar to Case 5, we obtain \(MoA(\mathbf{w})\le 3\cdot MoA(\mathbf{o}).\)
Combining all cases, an upper bound of the distortion is given by \[\max\left\{ 1 + \frac{2(1-\alpha)}{\alpha},\;1 + \frac{2}{1-\alpha},\;3 \right\} = \max\left\{ 1 + \frac{2(1-\alpha)}{\alpha},\;1 + \frac{2}{1-\alpha} \right\}.\] ◻
By solving the equation \(1 + \frac{2(1 - \alpha)}{\alpha} = 1 + \frac{2}{1 - \alpha}\), we establish the following theorem.
Theorem 7. For the Max-of-Average cost, the distortion of the \((\frac{3 - \sqrt{5}}{2},1)\)-Quantile Mechanism is at most \(2 + \sqrt{5}\).
In this section, we study the Average-of-Max cost, defined as the average of the maximum individual costs within each group. For the lower bound, we prove that the distortion of any strategyproof mechanism is at least \(3-\epsilon\) for any \(\epsilon>0\). For the upper bound, we analyze the \((1,\frac{3-\sqrt{5}}{2})\)-Quantile Mechanism, which achieves a distortion of at most \(2+\sqrt{5}\).
Theorem 8. For the Average-of-Max cost, the distortion of any strategyproof mechanism is at least \(3-\epsilon\), for any \(\epsilon>0\).
Proof. We proceed by contradiction. Assume there exists a strategyproof mechanism \(M\) with distortion strictly smaller than \(3 - \epsilon\) for some \(\epsilon > 0\), and let \(\theta > 0\) be an infinitesimal. We derive a contradiction by analyzing the following instances, with the set of candidate locations \(A = \{0, 0, 1, 1\}\).
Instance \(I_1\). Consider an instance \(I_1\) with a single group containing two agents located at \(\frac{1}{2}\) and \(\frac{3}{2}\). We compute the AoM costs for all candidate facility pairs and obtain that \(OPT(I_1) = (1,1)\), so \(M(I_1) = (1,1)\) must hold; otherwise, the distortion of \(M\) would be at least \(3\), contradicting our assumption.
Instance \(I_2\). Consider an instance \(I_2\) with a single group containing two agents, with \(x^2_1 = \frac{1}{2}\) and \(x^2_2 = \frac{1}{2} + \theta\). If \(M(I_2) \neq (1,1)\), then \(c(x^2_2, M(I_2)) = \frac{1}{2} + \theta\). Since \(c(x^2_2, M(I_1)) = \frac{1}{2} - \theta\), the agent at \(x^2_2\) could strictly reduce her cost by misreporting her location as \(\frac{3}{2}\), violating strategyproofness. Thus, \(M(I_2) = (1,1)\).
Instance \(I_3\). Consider an instance \(I_3\) with a single group containing one agent, with \(x^3_1 = 0\). By strategyproofness, the mechanism \(M\) must output \((0,0)\) as the group’s representative, i.e., \(M(I_3) = (0,0)\); otherwise, the distortion of \(M\) would be infinite.
Instance \(I_4\). Consider an instance \(I_4\) with a single group containing one agent, with \(x^4_1 = \frac{1}{2} - \theta\). If \(M(I_4) \neq (0,0)\), then \(c(x^4_1, M(I_4)) = \frac{1}{2} + \theta\). Since \(c(x^4_1, M(I_3)) = \frac{1}{2} - \theta\), the agent at \(x^4_1\) could strictly reduce her cost by misreporting her location as \(0\), violating strategyproofness. Thus, \(M(I_4) = (0,0)\).
Instance \(I_5\). Consider an instance \(I_5\) with two groups: group 1 contains one agent at \(\frac{1}{2} - \theta\), whose representative is \((0,0)\) by \(I_4\), and group 2 contains one agent at \(1\), whose representative is \((1,1)\) by the same argument as \(I_3\). We compute the AoM costs for all possible facility location pairs: \[AoM(0,0) = \frac{3}{4} - \frac{\theta}{2}, \quad AoM(0,1) = AoM(1,0) = \frac{3}{4} + \frac{\theta}{2}, \quad AoM(1,1) = \frac{1}{4} + \frac{\theta}{2}.\] Thus, \(M(I_5) = (1,1)\). Otherwise, the distortion of \(M\) would be at least \(\frac{\frac{3}{4} - \frac{\theta}{2}}{\frac{1}{2} + \theta} \geq 3 - \epsilon\) for \(\theta \leq \frac{\epsilon}{8 - 2\epsilon}\), which contradicts our assumption.
Instance \(I_6\). We now reach a contradiction by considering instance \(I_6\) with two groups: group 1 contains two agents at \(\frac{1}{2}\) and \(\frac{1}{2} + \theta\), whose representative is \((1,1)\) by \(I_2\), and group 2 contains one agent at \(0\), whose representative is \((0,0)\) by \(I_3\). By \(I_5\) and \((P2)\), we conclude that \(M(I_6) = (1,1)\). We compute the AoM costs for all facility location pairs: \[AoM(0,0) = \frac{1}{4} + \frac{\theta}{2}, \quad AoM(0,1) = AoM(1,0) = \frac{3}{4} + \frac{\theta}{2}, \quad AoM(1,1) = \frac{3}{4}.\] Thus, the distortion of \(M\) is at least \(\frac{\frac{3}{4}}{\frac{1}{2} + \theta} \geq 3 - \epsilon\) for \(\theta \leq \frac{\epsilon}{8 - 2\epsilon}\), which is a contradiction. ◻
We next present the \((1,\beta)\)-Quantile Mechanism and analyze its performance.
\(\boldsymbol{(1,\beta)}\)-Quantile Mechanism
Step 1. For each group \(d\in D\) , set \(y_{d(1)}=t({r_d})\), \(y _{d(2)}=s({r_d})\).
Step 2. Initialize \(z_d=y_{d(1)}\) for all \(d\in D\) and let \(w_1\) be the \(\lceil\beta\cdot k\rceil\)-th leftmost location in \(\{z_d\}_{d\in D}\). For each group \(d\in D\), update \(z_d\) to \(y_{d(2)}\) if \(y_{d(1)}=w_1\), then set \(w_2\) to be the \(\lceil\beta\cdot k\rceil\)-th leftmost location in \(\{z_d\}_{d\in D}\).
Lemma 2. For the Average-of-Max cost, the distortion of the \((1,\beta)\)-Quantile mechanism is at most \(\max \left\{ 1+\frac{2(1-\beta)}{\beta}, 1 + \frac{2}{1 - \beta}\right\}\).
Proof. Given any instance \(I\), let \(\mathbf{w}= (w_1, w_2)\) be the solution chosen by the mechanism and \(\mathbf{o} = (o_1, o_2)\) be an optimal solution. W.l.o.g., we assume that \(w_1 \leq w_2\) and \(o_1 \leq o_2\). By the property of the mechanism, there exists a group \(d^*\) such that \(w_1 = y_{d^*(1)} = t(r_{d^*})\) and \(w_2 = y_{d^*(2)} = s(r_{d^*})\). For each group \(d\), let \(i_d\) and \(i'_{d}\) denote the agents in \(N_d\) with the maximum individual cost under \(\mathbf{w}\) and \(\mathbf{o}\), respectively. Then we have \[\begin{align} &AoM(\mathbf{w}) =\frac{1}{k} \sum_{d \in D} \left\{\max_{i \in N_d} \delta(x_i, w(x_i))\right\} = \frac{1}{k}\sum_{d \in D} \delta(x_{i_{d}}, w(x_{i_{d}})),\\ & AoM(\mathbf{o}) = \frac{1}{k}\sum_{d \in D}\left\{ \max_{i \in N_d} \delta(x_i, o(x_i))\right\} = \frac{1}{k}\sum_{d \in D} \delta(x_{i_{d'}}, o(x_{i'_{d}})). \end{align}\]
Let \(D_1=\{d\in D|w(x_{i_d})=w_1\}\) and \(D_2=\{d\in D|w(x_{i_d})=w_2\}\).
Case 1: \(o_1 \leq o_2 < w_1 \leq w_2\). Using the triangle inequality, and since \(\delta(x_{i_d}, o(x_{i_{d}})) \leq \delta(x_{i'_{d}}, o(x_{i'_{d}}))\), we have \[\label{25} \begin{align} AoM(\mathbf{w})& = \frac{1}{k}\sum_{d \in D_1} \delta(x_{i_d}, w_1) +\frac{1}{k} \sum_{d \in D_2} \delta(x_{i_d}, w_2) \\ &\leq \frac{1}{k}\sum_{d \in D} \delta(x_{i_d}, o(x_{i_d})) + \frac{|D_1|}{k} \cdot \delta(o_1, w_1) +\frac{|D_2|}{k} \cdot \delta(o_2, w_2)\\ &\leq AoM(\mathbf{o}) + \delta(o_1, w_2). \end{align}\tag{11}\]
Let \(S=\{ d\in D\mid y_{d(1)}\ge w_1, y_{d(2)}\ge w_1\}\). For each group \(d\in D\), since \(y_{d(1)}\), \(y_{d(2)}\) are consecutive, \(w_1\) is the \(\lceil\beta\cdot k\rceil\)-th leftmost location in \(\{ y_{d(1)} \}_{d \in D}\) and \(w_2\) is the\(\lceil\beta\cdot k\rceil\)-th leftmost location in the updated \(\{ z_{d} \}_{d \in D}\), we have \(|S| \geq (1 - \beta) \cdot k\). Since \(w_1\) and \(w_2\) are the closest locations to \(x_{r_{d^*}}\), it holds that \(x_{r_{d^*}}\ge \frac{o_2 + w_2}{2}\). Then, we have \(\delta(x_{r_d}, o_1) \geq \delta(o_1, o_2) + \frac{\delta(o_2, w_2)}{2}\) for all \(d \in S\). Hence, \[\label{26} \begin{align} AoM(\mathbf{o})\ge \frac{1}{k}\sum_{d \in S} \delta(x_{r_d}, o_1) \ge \frac{(1-\beta)}{2}\cdot\delta(o_1,w_2). \end{align}\tag{12}\]
Comining (11 ) and (12 ), we have \[\begin{align} AoM(\mathbf{w})\leq AoM(\mathbf{o}) + \delta(o_1, w_2) \le \left(1+\frac{2}{1-\beta}\right) \cdot AoM(\mathbf{o}). \end{align}\]
Case 2: \(o_1 < o_2 = w_1 <w_2\). Similar to Case 1, we obtain \(AoM(\mathbf{w})\le \left(1+\frac{2}{1-\beta}\right)\cdot AoM(\mathbf{o})\).
Case 3: \(w_1 \le w_2 < o_1 \le o_2\). Let \(L\) denote the set of groups from the leftmost group in \(\{ y_{d(1)} \}_{d \in D}\) to the group at the \(\lceil\beta\cdot k\rceil\)-th position in \(\{ y_{d(1)} \}_{d \in D}\) and \(R\) the set of remaining groups. Then, for every \(d \in L\), \(i\in N_d\), since \(y_{d(1)}\) is the closest location to \(x_{r_d}\) and \(y_{d(1)} \leq w_1 \le w_2< o_1 \leq o_2\), we have \(\delta(x_i, w(x_i)) = \delta(x_i,w_2)\le \delta(x_i, o(x_i)) = \delta(x_i, o_2)\)
By the triangle inequality, we have \[\label{28} \begin{align} AoM(\mathbf{w})& =\frac{1}{k} \sum_{d \in L} \delta(x_{i_d}, w_2) +\frac{1}{k} \sum_{d \in R} \delta(x_{i_d}, w(x_{i_d})) \\ &\le\frac{1}{k}\sum_{d \in L} \delta(x_{i_d}, o(x_{i_d})) +\frac{1}{k} \sum_{d \in R\cap D_1} \delta(x_{i_d}, w_1) +\frac{1}{k} \sum_{d \in R\cap D_2} \delta(x_{i_d}, w_2) \\ &\le AoM(\mathbf{o})+(1-\beta) \cdot \delta(o_2, w_1). \end{align}\tag{13}\]
Since \(w_1\) and \(w_2\) are the closest locations to \(x_{r_{d^*}}\), it holds that \(x_{r_{d^*}} \leq \frac{w_1 + w_2}{2} \quad \text{(when \( w_1 \neq w_2 \))} \quad \text{or} \quad x_{r_{d^*}} \leq \frac{w_2 + o_1}{2} \quad \text{(when \( w_1 = w_2 \))}\).
Then, for every \(d \in L\), we have \(\delta(x_{r_d}, o_2) \geq \frac{\delta(w_2, o_2) +\delta(w_1, w_2)}{2}.\)
Hence, \[\label{29} \begin{align} {AoM}(\mathbf{o}) \geq\frac{1}{k} \sum_{d \in L} \delta(x_{r_d}, o_2) \geq \frac{\beta }{2} \cdot \delta(o_2, w_1). \end{align}\tag{14}\]
Combining (13 ) and (14 ), we obtain \[\begin{align} {AoM}(\mathbf{w})\le AoM(\mathbf{o})+(1-\beta)\cdot\delta(o_2,w_1)\le \left(1+\frac{2(1-\beta)}{\beta}\right)\cdot AoM(\mathbf{o}). \end{align}\]
Case 4: \(w_1 < w_2 = o_1 \le o_2\). Similar to Case 3, we obtain \({AoM}(\mathbf{w})\le \left(1+\frac{2(1-\beta)}{\beta}\right)\cdot AoM(\mathbf{o})\).
Case 5: \(o_1 < w_1 \le w_2 \le o_2\). Using the triangle inequality again, we have \[\begin{align} AoM(\mathbf{w})& =\frac{1}{k} \sum_{d \in D} \delta(x_{i_d}, w(x_{i_d}))\leq AoM(\mathbf{o}) + \delta(o_1, o_2). \end{align}\]
Clearly, \(AoM(\mathbf{o})\ge\frac{1}{k}\sum_{d \in D} \delta(x_{i'_{d}}, o_1)\) and \(AoM(\mathbf{o})\ge\frac{1}{k}\sum_{d \in D} \delta(x_{i'_{d}}, o_2)\). Using again the triangle inequality, we have \[\begin{align} AoM(\mathbf{o})&\ge\frac{1}{2k}\cdot\sum_{d \in D } [\delta(x_{i'_{d}}, o_1)+\delta(x_{i'_{d}},o_2)]\ge\frac{1}{2}\cdot\delta(o_1,o_2). \end{align}\]
Therefore, we conclude that \(AoM(\mathbf{w})\le 3\cdot AoM(\mathbf{o}).\)
Case 6: \(o_1=w_1\le w_2<o_2\). Similar to Case 5, we obtain \(AoM(\mathbf{w})\le 3\cdot AoM(\mathbf{o}).\)
Combining all cases, an upper bound of the distortion is given by \[\max \left\{ 1 + \frac{2(1 - \beta)}{\beta}, \, 1 + \frac{2}{1 - \beta},3 \right\}=\max \left\{ 1 + \frac{2(1 - \beta)}{\beta}, \, 1 + \frac{2}{1 - \beta} \right\}.\] ◻
By solving the equation \(1 + \frac{2(1 - \beta)}{\beta} = 1 + \frac{2}{1 - \beta}\), we establish the following theorem.
Theorem 9. For the Average-of-Max cost, the distortion of the \((1,\frac{3-\sqrt{5}}{2})\)-Quantile mechanism is at most \(2+\sqrt{5}\).
In this paper, we studied a constrained distributed heterogeneous two-facility location problem, and established lower and upper bounds on the distortion of strategyproof mechanisms under four social objectives.
There are several promising directions for future work. First, it would be of great interest to close the gaps between our derived lower and upper bounds for each objective. Second, it is meaningful to extend our analysis to settings with more than two facilities, as well as to more general metric spaces beyond the real line. Third, one could explore alternative social objectives in distributed environments (such as minimax envy), and consider scenarios where agents have more general preferences over facilities (e.g., fractional preferences).
Acknowledgments. This research was supported in part by the National Natural Science Foundation of China (12201590, 12171444) and Natural Science Foundation of Shandong Province (ZR2024MA031).
Disclosure of Interests.
The authors declare that they have no conflict of interest.
For the boundary cases: when \(\alpha=0\), the \(\lceil\alpha\cdot n_d\rceil\)-th leftmost agent in \(N_d\) is defined as the leftmost agent in \(N_d\); similarly, when \(\beta=0\), the \(\lceil\beta\cdot k\rceil\)-th leftmost location is defined as the leftmost location in the corresponding set.↩︎
Here, "interlaced" refers to the scenario where the representative pairs of two distinct groups overlap in order, i.e., \(y_{d(1)}<y_{d'(1)}<y_{d(2)}<y_{d'(2)}\) for \(d\neq d'\).↩︎
We use the method of undetermined coefficients to show that the \((1/2,1/2)\)-Quantile mechanism attains the minimum possible distortion upper bound among all \((\alpha,\beta)\)-Quantile mechanisms.↩︎
In fact, whatever values \(\alpha\) and \(\beta\) take, the \((\alpha,\beta)\)-Quantile Mechanism would achieve a distortion of at most \(3\) under the max-of-max cost.↩︎