| paper | Positive Intra-Group Externalities in Facility Location |
| authors | — |
| venue | AAMAS 2024 |
| filed under | voting · structured |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
Given \(N\in\mathbb{N}\), rational public coefficients \(\alpha_g\), and rational finite-support masses \(\mu_{g,x}\) with \(N\mu_{g,x}\in\mathbb{Z}_{\ge 0}\) and \(\sum_{g,x}\mu_{g,x}=1\), compute the RGA-M facility \(F_N(\mu)\) using weighted group medians, weights \(c_g=\mu_g(1+\alpha_g(N\mu_g-1))\), and \(\lambda=2\sqrt{3}-3\), together with \(\max_{z\in[0,1]}SU_N(z;\mu)\) and the achieved ratio, where \(SU_N(y;\mu)=\sum_g[1+\alpha_g(N\mu_g-1)]\sum_x\mu_{g,x}(1-|y-x|)\). Prove uniformly that \(F_N\) is unanimous, no one-clone location report \(\mu\mapsto\mu+N^{-1}(e_{g,x'}-e_{g,x})\) improves the true type's utility, and the ratio is at most \(\sqrt{3}\); the design variant asks for the smallest achievable \(\rho\).
A rational high-multiplicity clone model: types are group/location pairs \((g,x)\), masses represent \(N\) cloned agents, \(\alpha_g\) is public, the facility remains an indivisible point \(y\in[0,1]\), and location-only deviations are one-clone mass transfers. The objective is the social-utility approximation ratio under the paper's unnormalized group externality.
The proposed optimization over all \(F_N\) lacks a formal finite encoding and uniform runtime model; the proponent only specifies a finite description informally. This is a repairable specification gap, not a fatal objection to the rational high-multiplicity mirror.
fatal: False
The mirror covers Theorem 1's public-group, location-only social-utility mechanism and its \(\sqrt{3}\) guarantee, and it can transfer Theorem 2's \(3/2\) lower bound. It leaves the group-membership-only results, both-report impossibility, minimum-utility results, and the other mechanisms largely untouched.
The strongest positive case is a qualified one. The paper contains no NP-hardness, \(P\), or parameterized-complexity theorem, but it does contain named constructive approximation results. My lead anchor is Theorem 1, proved in this paper; Theorem 2, also proved here, supplies a matching lower-bound anchor.
The natural regime is a large facility-planning population divided into a small number of public neighbourhoods or sections. A type is \(t=(g,x)\): group \(g\), location \(x\in[0,1]\), and the group’s publicly known externality parameter \(\alpha_g\). Agents with the same \(g\) and \(x\) are interchangeable. A society is a rational finite-support mass distribution \(\mu=(\mu_{g,x})\), with \(\sum_{g,x}\mu_{g,x}=1\), and total population scale \(N\). Thus \(N\mu_{g,x}\) is the number of cloned agents of type \((g,x)\). The intended regime has \(N\gg\tau\), where \(\tau=|\operatorname{supp}\mu|\): for example, millions of residents distributed over a few dozen group-location types.
The parameter \(N\) is essential here. The paper’s externality is not normalized by population: an agent’s utility contains a sum over all other members of the group. If \(M_g=N\sum_x\mu_{g,x}\), define \(v_y(x)=1-|y-x|\) and the group aggregate \(V_g(y)=\sum_x\mu_{g,x}v_y(x)\). The utility of a true type \((g,x)\) is
\[ u_{g,x}(y;\mu)=v_y(x)+\alpha_g\bigl(NV_g(y)-v_y(x)\bigr). \]
For clone profiles this is exactly the paper’s utility. The normalized social utility is
\[ SU_N(y;\mu)=\sum_{g,x}\mu_{g,x}u_{g,x}(y;\mu) =\sum_g\bigl(1+\alpha_g(M_g-1)\bigr)V_g(y). \]
The facility remains a single indivisible location \(y\in[0,1]\); only the population has been continuized. The egalitarian objective would analogously be \(\min_{\mu_{g,x}>0}u_{g,x}(y;\mu)\), or an essential infimum for a genuinely nonatomic density.
The strategic interpretation is the rational-clone one. A location-only deviation by one clone of type \((g,x)\) to \(x'\) changes the reported mass vector to \(\mu+\frac1N(e_{g,x'}-e_{g,x})\), while the deviator’s utility is evaluated using its true type and the original true profile. Group membership remains public. This is exactly the paper’s individual deviation after denominator clearing.
My lead continuous problem is:
\[ \textsc{Public-Group-Facility-Design}_{\infty}. \]
Given \(N\), the public group parameters \(\alpha_1,\ldots,\alpha_m\), and the location domain \([0,1]\), produce a deterministic facility rule \(F_N\) on rational mass profiles such that:
\[ \frac{\max_{z\in[0,1]}SU_N(z;\mu)} {SU_N(F_N(\mu);\mu)} \le \rho \]
for every admissible \(\mu\).
A solution consists of a finite description of \(F_N\), together with its facility output on any queried mass profile. The optimization version asks for the smallest achievable \(\rho\).
The paper’s RGA-M gives a direct candidate for \(F_N\). For each group \(g\), let \(z_g\) be its leftmost weighted median and let
\[ c_g=\mu_g\bigl(1+\alpha_g(N\mu_g-1)\bigr), \qquad \mu_g=\sum_x\mu_{g,x}. \]
Order groups by their medians, define prefix sums \(K_j\), and set \(\lambda=2\sqrt{3}-3\). RGA-M outputs the first group median whose prefix weight reaches \(\frac{1+\lambda}{2}K_m\) when the left side is sufficiently heavy, outputs \(1/2\) when the prefix weight at \(1/2\) lies between \(\frac{1-\lambda}{2}K_m\) and \(\frac{1+\lambda}{2}K_m\), and otherwise uses the first median reaching \(\frac{1-\lambda}{2}K_m\). This is exactly the paper’s RGA-M after replacing group counts by masses; the common factor \(N\) cancels from the threshold comparisons.
Theorem 1, proved here, therefore gives the anchor: this rule is unanimous, strategyproof for public group memberships, and has approximation ratio \(\sqrt{3}\) for social utility. Its computation requires only group medians, sorting, and a prefix scan, hence is polynomial in \(\tau\) and the input bit length. The proof is built from weighted sums and median inequalities, so it is structurally well suited to a mass formulation. I would expect this problem to be Class A for evaluating the named rule, and plausibly Class A for the broader fixed-type mechanism-design problem.
The authors should recognise this as their problem. The facility, the one-dimensional location space, the positive intra-group externality, the public group memberships, the location-only deviations, the social-utility objective, and the exact RGA construction all remain. What changes is only the representation of a large repeated population: \(N\) cloned agents become masses \(\mu_{g,x}\). This is particularly plausible in the paper’s own neighbourhood and musical-section examples, where many residents or performers share a group, a location category, and an externality coefficient.
The important open question generated by this mirror is whether the \(\sqrt{3}\) guarantee can be improved to the lower bound \(\frac32\), whether the optimal rule can be computed from type summaries alone, and whether the guarantee extends from rational atomic profiles to piecewise-constant or arbitrary spatial densities.
The secondary anchor is Theorem 2, also proved in this paper. It states that every deterministic unanimous strategyproof mechanism has approximation ratio at least \(1.5\) for social utility when group memberships are public. Its continuous counterpart is the threshold problem
\[ \textsc{Public-Group-Facility-Threshold}_{\infty}. \]
Given a rational target \(\rho\), ask whether there exists a deterministic rule satisfying unanimity and clone-strategyproofness on every rational mass profile while achieving ratio at most \(\rho\). A solution is such a rule; a negative answer means that no rule can satisfy the three requirements simultaneously.
For every \(\rho<\frac32\), the answer should remain negative. Every finite profile used in the paper’s lower-bound argument is represented exactly by rational masses, and clearing denominators recovers the original cloned electorate with the same utilities, facility locations, deviations, and approximation ratio. This is a transferred impossibility—closest to Class B in the programme’s trichotomy—rather than a new complexity classification. It is nevertheless useful: the continuous mirror has both a constructive upper bound, Theorem 1, and a nontrivial inherited lower bound, Theorem 2. The resulting interval \([\frac32,\sqrt3]\) is a meaningful continuous mechanism-design question rather than an unconstrained welfare optimization problem.
I would not use Theorem 5 as a main anchor. Its incompatibility between unanimity and strategyproofness when both location and group membership may be misreported is interesting, but literal atomless strategyproofness becomes vacuous: one individual has zero mass and cannot move the distribution. Recovering the theorem would require positive-mass coalition deviations or type-block reports, which changes the strategic problem. The group-membership-only results, Theorems 3 and 4, face the same issue in a different form.
That is also the weakest point of the positive case. A genuinely nonatomic version with unilateral individual reports does not preserve the paper’s strategic content. Moreover, the raw externality model requires the population scale \(N\); a normalized distribution \(\mu\) alone is insufficient. If a referee demands a theorem about atomless individual strategyproofness with no clone interpretation, this mirror should be rejected. The honest claim is narrower: this is a faithful rational high-multiplicity continuous extension, with a genuine mass-based algorithm and an inherited lower bound. The central welfare computation survives cleanly, the authors’ mechanism remains recognisable, and the strategic caveat is explicit rather than concealed.
The strongest negative case is that the proposed mirror exists only in a narrow high-multiplicity reading, and becomes either vacuous or ill-specified when made genuinely continuous.
For finite \(N\), the proponent’s construction is mathematically faithful. If \(M_g=N\mu_g\) and \(V_g(y)=\sum_x\mu_{g,x}(1-|y-x|)\), then
\[ \frac{1}{N}\sum_i u_i(y) = \sum_g \bigl(1+\alpha_g(M_g-1)\bigr)V_g(y), \]
and the paper’s RGA weights are exactly recovered after multiplying the proposed \(c_g\) by \(N\). Clearing denominators therefore reconstructs the cloned finite electorate. This is not a defect in the algebra; it is the central limitation of the anchor. Theorem 1 has not produced a continuous strategic model. It has produced a weighted transcription of the finite theorem, evaluated by weighted medians and prefix sums. There is no new separation problem, configuration LP, or complexity question. The proposed “smallest achievable \(\rho\)” is also not formally specified: a “finite description” of a mechanism over all rational mass profiles has no encoding, uniformity condition, or runtime model.
The alternatives fare worse. If locations are genuinely continuous, then the type space is \(\{1,\ldots,m\}\times[0,1]\), not a fixed finite type set. An arbitrary atomless distribution has no finite input representation without committing to a density, histogram, oracle, or other additional model. If one restricts to finite-support distributions, the number of types is simply the number of distinct locations; when locations are individuated, \(\tau\) can be \(n\). If one restricts to a small catalogue of locations, the result becomes a coarse repeated-location model rather than the paper’s facility-location problem.
More seriously, the strategic interpretation does not survive the atomless limit. In the finite clone model, a deviation changes the profile by
\[ \frac{1}{N}\bigl(e_{(g,x')}-e_{(g,x)}\bigr). \]
For an atomless individual, that perturbation has mass zero, so the reported society does not change. Every distributional facility rule is then individually strategyproof, and the paper’s incentive content disappears. Replacing unilateral deviations by positive-mass block deviations or coalition deviations would be a legitimate new model, but it is not Theorem 1’s strategyproofness.
The raw externality creates a further fork. Retaining the paper’s sum over group members requires the extra population-scale parameter \(N\); the society is really \((N,\mu)\), not \(\mu\). Letting \(N\) grow changes the agents’ utilities and makes the externality term dominate. Normalizing the externality by group size would yield a more stable continuum model, but then the \(|G_g|^2\) weights that drive RGA-M, its proof, and its bound disappear. That would be a new facility-location model, not a continuous mirror of Theorem 1.
Theorem 2 does not repair this. Its lower-bound profiles do transfer exactly to rational clone populations, but that merely reproduces the finite impossibility argument. In the atomless model, the pivotal deviations again have zero mass; in a block-deviation model, the strategic predicate has changed. Thus the claimed interval \([\frac32,\sqrt{3}]\) is a finite mechanism-design gap carried into a different notation, not a continuous computational boundary.
I would not use “high multiplicity is already known” as an objection; here it is evidence that the cloning regime is sensible. But sensibility is not enough. Theorem 1 survives as a recognizable high-multiplicity extension, while the genuinely atomless version loses its incentive semantics. Consequently, the negative case can reject the proponent’s stronger claim that this is already a substantive Class A continuous-computational result. It cannot honestly establish the universal claim that no worthwhile mirror exists: under ChoCo’s permissive high-multiplicity standard, the exact RGA clone model is a legitimate, if modest, mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.