| paper | Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems |
| authors | — |
| venue | AAAI 2024 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
Given a finite rational type support of group-location types and rational masses, compute the PBPM endpoint distribution using each group's left/right mass and determine whether the resulting single rule is mass-group-strategyproof and achieves expected maximum total group cost at most twice the optimum location cost.
A finite-support distribution over group-location types, with mass variables μ, endpoint probability α as the decision output, and maximum total group cost as the objective; the rule must be mass-GSP and 2-approximate.
The paper proves group strategyproofness only for finite agents, so extension to arbitrary real masses and partial positive-mass coalitions remains to be established.
fatal: False
The proposed mirrors cover Theorems 4, 9, and 11 together with the associated strategyproofness propositions; they leave the two-candidate characterization, most lower bounds, and the open multi-candidate directions untreated.
The paper admits a credible, though deliberately narrow, continuous mirror. Its named results are approximation and strategyproofness theorems rather than P/NP-hardness classifications, so the positive case is for a Class-A population implementation and a continuous approximation frontier—not for a new complexity dichotomy.
The natural regime is large infrastructure-siting consultations. Suppose millions of households are represented by neighbourhood or census-tract locations, and belong to a small number of public stakeholder groups. A type is \(t=(g,x)\): group \(g\) and private undesirable facility location \(x\in[0,1]\). Two agents of the same type have identical costs and reporting possibilities. A society is a rational distribution \(\mu_{g,x}\) over finitely many such types. For example, 20 million households, 30 groups, and 500 representative locations give at most 15,000 types, with hundreds or thousands of agents per type. This is exactly the high-multiplicity regime, not an outcome-space continuization: the facility remains on \([0,1]\), and the continuous object is the population mass.
For incentive compatibility, the correct continuum notion cannot be ordinary individual strategyproofness, since one atomless individual has zero influence. I would use mass group-strategyproofness. A deviation replaces a submass of agents by reports at other locations, preserving each agent’s public group. The mechanism is mass-GSP if every positive-mass deviation leaves a positive submass no better off. For rational masses, multiplying by a common denominator recovers the paper’s finite-agent setting exactly.
My lead anchor is Theorem 4, proved in this paper: PBPM is a 2-approximation for maximum total group cost. Proposition 2, also proved here, supplies the corresponding group-strategyproofness.
Call the continuous problem \(\mathrm{PBPM\text{-}MTGC}_\infty\). An instance consists of a finite rational type set \(T\subseteq G\times([0,1]\cap\mathbb Q)\), a reported rational mass vector \(\mu\), and positive group masses. Define
\[ C_g(y;\mu)=\sum_x\mu_{g,x}(1-|y-x|), \qquad \mathrm{mtgc}_\mu(y)=\max_g C_g(y;\mu). \]
For a randomized facility \(Y\), the objective is exactly the paper’s
\[ \mathbb E[\mathrm{mtgc}_\mu(Y)]. \]
The mechanism must output a distribution over the two candidates \(\{0,1\}\), remain mass-GSP over the whole type domain, and achieve at most twice
\[ \min_{y\in[0,1]}\mathrm{mtgc}_\mu(y). \]
The PBPM∞ candidate is explicit. Let
\[ a_g=\sum_{x\le 1/2}\mu_{g,x}, \qquad b_g=\sum_{x>1/2}\mu_{g,x}, \]
and define
\[ R_L=\frac{\max_g(a_g/2+b_g)}{\max_g(a_g/2)}, \qquad R_R=\frac{\max_g(b_g/2+a_g)}{\max_g(b_g/2)}. \]
Choose \(\alpha\) satisfying
\[ \alpha+(1-\alpha)R_L=(1-\alpha)+\alpha R_R, \]
with the paper’s endpoint conventions when a denominator is zero, and output \(Y=0\) with probability \(\alpha\) and \(Y=1\) otherwise. A solution is this explicit rule together with the returned endpoint distribution. Computing it requires only aggregating type masses and rational arithmetic, hence is polynomial in \(|T|\) and the encoding length.
This is recognisably the authors’ problem: same obnoxious facility, same private location reports, same public groups, same endpoint mechanism, same cost, same maximum-total-group objective, and the same strategic requirement. Nothing has been made easier by replacing the objective or removing group structure. The expected classification is Class A. The approximation proof should lift from counts to masses by homogeneity and continuity, while the GSP proof needs to be rewritten as monotonicity on the mass simplex rather than silently assumed from the finite theorem.
The second anchor is Theorem 9, proved here: NPBPM is a 2-approximation for maximum average group cost. Proposition 4 proves its group strategyproofness, and Lemma 2 is unusually favourable evidence for continuization: duplicating a group does not change the objective, optimum, mechanism output, or approximation ratio.
Call this problem \(\mathrm{NPBPM\text{-}MAGC}_\infty\). The instance is the same finite rational population distribution, but now
\[ \mathrm{magc}_\mu(y) = \max_g \frac{C_g(y;\mu)}{M_g}, \qquad M_g=\sum_x\mu_{g,x}. \]
The randomized objective is \(\mathbb E[\mathrm{magc}_\mu(Y)]\). The solution must be a mass-GSP rule over \(\{0,1\}\) with approximation ratio at most 2.
NPBPM∞ uses the conditional within-group masses
\[ p_{g,L}=a_g/M_g,\qquad p_{g,R}=b_g/M_g, \]
and applies the same balancing equation as PBPM, replacing \(a_g,b_g\) by \(p_{g,L},p_{g,R}\). This is arguably the cleaner continuous mirror: average group cost is inherently scale-free, and Lemma 2 says that replication—the defining high-multiplicity operation—does not alter the problem.
Again I expect Class A for explicitly supported rational distributions. The implementation is linear in the number of types. The interesting follow-up is not whether NPBPM can be evaluated, but whether 2 is optimal among mass-GSP mechanisms, whether allowing more than two facility candidates improves the ratio, and whether a genuinely implicit population density creates a nontrivial separation problem.
The third, weaker but still defensible anchor is Theorem 11, proved here: BGMV is a 4-approximation for both intergroup/intragroup objectives IIF1 and IIF2. Proposition 3 proves its group strategyproofness. Theorem 12 gives a matching deterministic lower bound in the finite model, which should transfer under replication.
Call the problem \(\mathrm{BGMV\text{-}IIF}_\infty\). For each group define
\[ \bar c_g(y)= \frac{1}{M_g} \sum_x\mu_{g,x}(1-|y-x|) \]
and
\[ d_g(y)= \max_{x:\mu_{g,x}>0}(1-|y-x|) - \min_{x:\mu_{g,x}>0}(1-|y-x|). \]
The two objectives are
\[ \mathrm{IIF1}_\mu(y)= \max_g\bar c_g(y)+\max_g d_g(y), \]
and
\[ \mathrm{IIF2}_\mu(y)= \max_g\{\bar c_g(y)+d_g(y)\}. \]
The task is to output a deterministic mass-GSP facility location, with BGMV∞ selecting the group with largest within-group half-interval bias and placing the facility at the corresponding endpoint. A valid solution should guarantee a factor 4 for both objectives. This remains a faithful mirror because averaging over a type mass and taking the extrema of the type support are exactly what repetition of identical agents does in the finite model. It is also Class A for explicit finite support.
The scope is intentionally limited. These mirrors cover the paper’s group-fair approximation mechanisms: Theorem 4, Theorem 9, and Theorem 11, together with their strategyproofness propositions and the replication-relevant lemmas. They do not cover the full characterization in Theorem 3, the open multi-candidate mechanism question, or every lower-bound and future-work statement.
The weakest point is that the computational content may be too routine. PBPM, NPBPM, and BGMV depend only on half-interval aggregates, so their continuous implementations are essentially weighted versions of finite counting algorithms; they do not yet produce the kind of exponential-variable LP or new population-specific complexity boundary that motivates the broader ChoCo programme. There is also a genuine incentive-theoretic issue: individual strategyproofness becomes vacuous in an atomless population unless positive-mass deviations are admitted.
That weakness does not destroy the mirror. The paper’s own objects are homogeneous under replication, and its mechanisms are explicitly driven by group-level counts. The proposed problems preserve the authors’ model almost verbatim while making population mass the primitive quantity. The right claim is therefore modest but solid: this paper supplies a good Class-A test case for continuous group-fair facility mechanisms, and a natural platform for studying mass-strategyproofness, finite-population rounding, optimal approximation ratios, and whether richer population representations create any genuinely continuum-specific difficulty.
The strongest negative case begins with scope. This paper has named algorithmic approximation theorems, but it has no theorem about the complexity of solving an input-dependent computational problem. Theorems 4, 9, and 11 certify distortion guarantees for explicitly prescribed mechanisms; PBPM, NPBPM, and BGMV are already closed-form rules. Continuizing their inputs therefore does not expose a new optimization or complexity question.
Theorem 4 is the most defensible anchor, but only as a high-multiplicity restatement. Replacing the counts \(n_{g,L},n_{g,R}\) by masses \(a_g,b_g\) gives exactly the same equation for \(\alpha\). For rational masses, multiplying by a common denominator recovers the finite profile, and the proof transfers by homogeneity. That establishes that the regime is sensible, but it also shows the limitation: the proposed “algorithm” only aggregates two masses per group and solves one linear equation. The full location distribution disappears. With an atomless population, ordinary individual strategyproofness becomes vacuous, since one report has zero effect; mass-GSP repairs this only by replacing the paper’s individual/finite-coalition notion with a new positive-measure coalition notion. Thus the mirror is either a compressed finite instance or a different incentive problem. It is not a substantive continuous computational question.
Theorem 9 is weaker still as a population mirror. MAGC deliberately divides each group’s cost by its group size, and NPBPM depends only on the conditional left/right proportions \(p_{g,L},p_{g,R}\). Total population mass and multiplicity cancel. This is not a defect in the paper, but it means the proposed continuous society contributes no relevant mass information: populations with radically different sizes induce the same anchored problem whenever their within-group proportions agree. One could study optimal mass-strategyproof mechanisms over richer distributions, but that would be a new mechanism-design programme, not a continuous version of Theorem 9. The named result itself yields only the same weighted two-bin calculation.
Theorem 11 presents a more fundamental obstruction. IIF1 and IIF2 contain the within-group term \(\max_i c_i-\min_i c_i\). In a genuine nonatomic population, literal maxima and minima are not functions of the distribution: changing a null set can change them without changing the measure. Replacing them by essential suprema and infima is the natural repair, but it changes the finite objective’s treatment of outliers. A type with mass \(1/n\) controls the finite IIF objective just as much as a type with mass \(1/2\), yet it disappears in the limiting distribution. Consequently the objective is unstable under the very high-multiplicity limit the programme wants to study. A finite-support version avoids this by retaining positive-mass atoms, but then it is again simply a weighted finite profile. Quantile- or mass-threshold versions could be well behaved, but they are new fairness objectives rather than mirrors of IIF.
The proponent is right that census tracts or neighbourhoods can supply a plausible repeated-type story; lack of multiplicity is not the objection. The problem is that, for this paper, multiplicity does no computational work. The paper’s substantive contribution is the strategyproofness/approximation analysis of a few endpoint rules, not an algorithmic bottleneck involving the population representation. The first two mirrors are therefore admissible but routine high-multiplicity encodings; the third is either measure-theoretically ill-behaved or no longer the same fairness objective.
This negative case is not airtight: if ChoCo is willing to count any weighted lift of a mechanism theorem as worthwhile, PBPM and NPBPM survive. But under the programme’s stated computational ambition, none of the three anchors supplies a compelling continuous mirror, and I would not green this paper as a priority target.
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.