Altruism in Facility Location Problems

The strongest positive case is a narrow one. This paper contains no numbered theorem saying that a problem is NP-hard, in P, FPT, or W[1]-hard. Its named results are approximation and mechanism-design results. So the case below is for a genuine Class-A computational mirror of those results, not for a complexity classification already proved by the paper.

My lead anchor is Theorem 5, proved in this paper: “Majority-Med has an approximation ratio of 3 for both” maximum total group cost and maximum average group cost. The duplicated notation in the theorem statement is evidently a typo; those are the two objectives defined in the preliminaries and table. Theorem 6, also proved here, is the matching lower bound: every deterministic Pareto-strategyproof mechanism has approximation ratio at least 3 for both objectives.

The natural mirror is a large regional authority choosing the location of one shared facility. There may be millions of residents, but only finitely many relevant population types: a type is a complete pair \(t=(x_t,g_t)\), where \(x_t\) is the resident’s ideal location and \(g_t\subseteq[m]\) is the set of overlapping groups to which the resident belongs. Groups could be neighbourhoods, school clubs, family associations, or regional communities. The society is a rational distribution \(\mu\) over these types, with \(\tau\ll N\): millions of residents represented by perhaps a few hundred location–membership types.

For group \(j\), let

\[ q_j=\sum_{t:j\in g_t}\mu_t \]

be its population mass and

\[ A_j(\mu,y)=\sum_{t:j\in g_t}\mu_t|x_t-y| \]

its normalized total cost at facility location \(y\). The two objectives are

\[ \operatorname{MTGC}(\mu,y)=\max_j A_j(\mu,y) \]

and

\[ \operatorname{MAGC}(\mu,y)=\max_j \frac{A_j(\mu,y)}{q_j}. \]

These are exactly the paper’s objectives after dividing all discrete costs by \(N\); average group costs are preserved exactly, since \((\sum_{i\in G_j}|x_i-y|)/|G_j|=A_j/q_j\).

The corresponding continuous problem is:

Continuous Altruistic Group-Fair Facility Location. Given \(m\), a finite rational type set \(T\), rational masses \(\mu\), and \(\Phi\in\{\operatorname{MTGC},\operatorname{MAGC}\}\), construct a deterministic population mechanism \(F\) and output \(F(\mu)\). The mechanism must satisfy population Pareto-strategyproofness: if a positive mass \(\varepsilon\) of one homogeneous type reports another location while retaining its group memberships, the deviation may not weakly improve every group cost and strictly improve one. The mechanism should minimize the worst-case ratio
\[ > \sup_\nu \frac{\Phi(\nu,F(\nu))}{\min_y\Phi(\nu,y)} > \]
over all rational societies \(\nu\) on the same type universe.

The natural candidate is Mass-Majority-Med. Replace every group median in the paper by a weighted median under population mass, apply the same profile-preprocessing map using weighted left and right medians, select the group of largest mass, and locate the facility at that group’s left weighted median after preprocessing.

The evaluation problem for this mechanism is plainly tractable in the compressed representation. Weighted medians can be found by sorting the \(\tau\) type locations and accumulating rational masses. The optimum itself is a small linear program: introduce \(d_t\ge |y-x_t|\) and minimize \(z\), subject to \(z\ge A_j(\mu,y)\) for MTGC, or \(q_jz\ge A_j(\mu,y)\) for MAGC. Thus exact evaluation and optimization are polynomial in \(m,\tau\), and the encoding length, rather than in the expanded population size \(N\). This is a real high-multiplicity gain: the population, not merely the facility location, is the continuous object.

I would expect the approximation part of Theorem 5 to extend to this setting, because its proof uses cumulative group-size inequalities that have direct cumulative-mass analogues. The expected answer is therefore Class A: exact weighted-quantile computation plus a constant-factor guarantee. Theorem 5 supplies the upper-bound target \(3\); Theorem 6 supplies the natural boundary question—whether any deterministic population-PSP mechanism can beat \(3\). The lower-bound construction should transfer particularly cleanly: a rational society can be replicated into a finite electorate, all total costs scale by \(N\), average group costs remain unchanged, and a positive-mass-PSP rule includes the \(1/N\)-mass deviations used by the discrete argument.

This would be recognisable to the authors as their problem rather than a softened variant. It preserves the line metric, overlapping memberships, altruistic group cost vectors, Pareto strategyproofness, Majority-Med, and the same group-fair objectives. It is not claiming that the paper’s real-valued facility location already constitutes continuization: the outcome was continuous in the original paper; the new continuous object is the population distribution.

The weakest point is strategic semantics. In an atomless population, an individual has zero mass and cannot change a distribution-based facility rule, making literal individual strategyproofness vacuous. The proposed positive-mass deviation is therefore a deliberate high-multiplicity interpretation: a homogeneous cohort can coordinate its report. It is stronger than the paper’s individual PSP notion, and Theorem 5 does not automatically prove that Mass-Majority-Med satisfies it. A new mass-PSP proof is required. If that strengthening is rejected, the mirror still gives a clean compressed optimization problem, but it no longer captures the paper’s central incentive contribution.

I would not extend this claim to the paper’s \(n/2\) or \(|G_{\max}|/2+1\) bounds: those depend on raw population cardinalities and are poor scale-free continuum quantities. The strongest honest mirror is therefore the scale-invariant Theorem 5/Theorem 6 pair, covering the group-fair altruistic facility-location results and leaving the rest outside scope.