Strategyproof Mechanisms for Group-Fair Facility Location Problems

The paper has a sensible high-multiplicity facility-location interpretation, and its mechanism statements can be lifted to weighted medians and mass-based objectives. However, none of its numbered results asserts the complexity of a computational problem or provides an algorithmic complexity guarantee in ChoCo's required sense. The continuous lifts therefore remain strategic approximation and impossibility restatements, so bit (a) fails.

The objection that survived

The strongest objection is that the credible mass lift reduces to weighted-median computation and one-dimensional piecewise-linear optimization, while global optimization over truthful rules has no finite encoding or verification model.

What the mirror covers

The proposed mirror covers the \(\mathrm{mtgc}\), \(\mathrm{magc}\), IIF1, IIF2, and difference-objective mechanism statements, but none supplies a named computational theorem because the paper contains no such result.

Open questions for a prover

The case FOR (proponent)

This paper has a credible continuous mirror, although not a hardness-first one. It contains no named NP-hard, P, W[1]-hard, or FPT theorem. Its strongest anchors are approximation and impossibility results proved in the paper. I would use those rather than invent a complexity classification.

The mirror is high-multiplicity group-fair facility location. Let \(G=\{1,\ldots,m\}\) be protected groups and \(X=\{x_1,\ldots,x_q\}\subseteq\mathbb Q\) be a finite set of location types. A type is \(t=(x,g)\): location \(x\) and group \(g\). A society is a distribution \(\mu=(\mu_{x,g})\) over \(T=X\times G\), with \(p_g=\sum_x\mu_{x,g}>0\). The action is a facility location \(y\in\mathbb R\), and the mass-normalized cost of group \(g\) is \(H_g(\mu,y)=\sum_x\mu_{x,g}|x-y|\).

This is exactly the high-multiplicity version of the paper’s model: a discrete profile with \(N\) agents has \(\mu_{x,g}=n_{x,g}/N\), and the original total group cost is \(N H_g\), so approximation ratios are unchanged. For average group cost, \(H_g/p_g\) is exactly the paper’s average. The facility location is already real-valued in the paper; the new continuous object is the population distribution.

A sensible regime is a municipal facility or public-service corridor with hundreds of thousands of residents but only a few dozen location cells and protected-group categories. Agents in the same cell and group share one type, while their total prevalence is represented by mass. This is a genuine high-multiplicity regime: \(N\) is large and \(\tau=mq\) is comparatively small.

To preserve the paper’s incentive question, strategyproofness should not be interpreted as nonatomic price-taking, where one individual has zero influence and truthfulness becomes vacuous. A continuous mechanism is a scale-invariant rule \(f\) mapping \(\mu\) to \(y\), required to satisfy the paper’s one-agent incentive constraint on every finite realization: if \(N\mu\) is an integer profile and one type-\((x,g)\) agent reports \(x'\), then \( |x-f(\mu)|\le |x-f(\mu+(e_{x',g}-e_{x,g})/N)| \). This is the finite-agent-consistent high-multiplicity interpretation of strategyproofness.

My lead anchor is Theorem 3, proved in this paper: MGDM has approximation ratio \(3\) for minimizing the maximum total group cost. The corresponding problem is:

\(\mathrm{SP\text{-}MTGC}_\infty\): given \(X\), \(G\), and a rational threshold \(\alpha\), find a deterministic scale-invariant strategyproof rule \(f\) such that, for every society \(\mu\), \(M(\mu,f(\mu))\le \alpha M^*(\mu)\), where \(M(\mu,y)=\max_g H_g(\mu,y)\) and \(M^*(\mu)=\min_{z\in\mathbb R}M(\mu,z)\). For a particular query society \(\mu\), the solution is the facility \(y=f(\mu)\); globally, a solution is the finite description of the rule \(f\).

At \(\alpha=3\), the paper’s MGDM has an immediate continuous form: choose a largest-mass group \(g\), breaking ties by index, and place the facility at a weighted median of that group’s location distribution. The proof of Theorem 3 lifts directly: at least half of the largest group’s mass lies on one side of its weighted median, and every group-cost difference is bounded by its mass times the displacement of the facility. Proposition 1, also proved here, supplies strategyproofness.

The unrestricted optimum is computationally tractable as well. Since \(M(\mu,y)\) is the maximum of finitely many piecewise-linear convex functions, \(M^*(\mu)\) is obtained by a polynomial-size linear program. Thus this mirror is Class A: a polynomial-time continuous algorithm exists, and the theorem’s approximation guarantee survives exactly. The interesting follow-up is whether the best deterministic ratio is \(2\), \(3\), or something in between; Theorem 4 gives the lower bound \(2\).

My second anchor is Theorem 9, proved here: every deterministic strategyproof mechanism has approximation ratio at least \(4\) for both IIF objectives. The continuous problem is:

\(\mathrm{SP\text{-}IIF}_\infty\): given \(X\), \(G\), an objective \(i\in\{1,2\}\), and \(\alpha\), decide whether there exists a deterministic scale-invariant strategyproof rule \(f\) with worst-case ratio at most \(\alpha\) for the corresponding continuous IIF objective.

For \(p_g>0\), define \(A_g(\mu,y)=H_g(\mu,y)/p_g\), \(U_g(\mu,y)=\max_{\mu_{x,g}>0}|x-y|\), and \(L_g(\mu,y)=\min_{\mu_{x,g}>0}|x-y|\). Then \(F_1(\mu,y)=\max_g A_g+\max_g(U_g-L_g)\), while \(F_2(\mu,y)=\max_g(A_g+U_g-L_g)\). A solution is a truthful rule \(f\) and, on query \(\mu\), the facility \(f(\mu)\).

The expected answer is exactly \(4\). Theorem 8 gives the matching upper bound: the paper’s \(k\)-LDM becomes a fixed population quantile \(Q_\theta(\mu)\), which is strategyproof and achieves ratio \(4\). Theorem 9 gives the lower bound. The mass formulation is especially faithful here: averages become integrals against \(\mu\), while maximum and minimum costs become extrema over the positive-mass support. Duplicating every agent leaves all these quantities unchanged.

This is again Class A for finite support. The quantile can be computed by sorting the location types, and the unrestricted IIF optimum is a finite piecewise-linear minimization problem. Further questions include randomized continuous mechanisms, multiple facilities, and whether group-dependent quantiles can improve the deterministic bound.

As a useful boundary anchor, Theorem 1, proved here, says that no deterministic strategyproof mechanism has a finite approximation ratio for the difference objective \(\max_g h_g-\min_g h_g\), for each of the paper’s three choices of \(h_g\). Taking \(h_g=H_g\), the continuous question is:

\(\mathrm{SP\text{-}DIFF}_\infty\): does there exist a deterministic scale-invariant strategyproof rule \(f\) with \(D(\mu,f(\mu))\le \alpha D^*(\mu)\) for every \(\mu\), where \(D(\mu,y)=\max_g H_g(\mu,y)-\min_g H_g(\mu,y)\)?

The expected answer is no for every finite \(\alpha\). The paper’s bad finite profiles can be represented by rational masses and duplicated arbitrarily, so the obstruction should survive continuization. This is not Class C continuum-specific hardness; it is a strategic impossibility already present in the discrete problem. It is nevertheless valuable because it identifies where the mirror stops helping.

The mirror therefore covers the paper’s core group-fair objectives, not merely its already-continuous facility outcome. It gives a tractable mass version of Theorem 3, a tight continuous mechanism-design problem from Theorems 8 and 9, and a meaningful impossibility boundary from Theorem 1. I would not claim that it mirrors every result, especially the randomized mechanisms or every objective inherited from Marsh and Schilling.

The weakest point is the incentive semantics. A literally nonatomic model makes individual strategyproofness vacuous, so the finite-agent-consistent interpretation is essential. The second weakness is that the strongest regime requires many agents to share a location-and-group type; if every resident has an idiosyncratic location, \(\tau\) approaches \(N\) and the computational benefit disappears. Those are genuine qualifications, but they do not defeat the mirror for the municipal high-multiplicity scenario.

The case AGAINST (opponent, writing after the proponent)

The strongest case against a worthwhile mirror is that this paper has no computational anchor in ChoCo’s sense. Its numbered results concern strategyproofness, approximation ratios, and impossibility of mechanisms—not the complexity of a computational problem, nor an exact, approximation, or parameterized algorithm. The proposed mirrors therefore preserve theorem statements, but do not expose a new complexity landscape.

Theorem 3 is the most credible candidate. The high-multiplicity model with types \((x,g)\) and masses \(\mu_{x,g}\) is sensible for residents aggregated into location cells and protected groups. I would not object to that regime. But the resulting computation is elementary. The continuous MGDM is simply the weighted median of the largest-mass group, computable by sorting. The unrestricted \(M^*\) is a one-dimensional piecewise-linear convex minimization, equivalently a small LP. Nothing in the theorem involves exponentially many types, a separation problem, or a nontrivial computational barrier.

The proponent’s \(\mathrm{SP\text{-}MTGC}_\infty\) does not repair this. If it means evaluating a specified rule on \(\mu\), it is just weighted-median computation. If it means finding the best truthful rule, then the input is not merely \((X,G,\mu)\): the “solution” is a function on an uncountable domain, and no finite encoding or verification model is supplied. That is a new meta-level mechanism-design problem, not a continuous version of Theorem 3. Allowing arbitrary distributions over \(\mathbb R\) only shifts the issue to an unspecified oracle or representation model; restricting to finitely supported rational distributions returns to the elementary weighted problem.

Theorem 9 has the same defect. A natural repair does exist: replace order statistics by fixed population quantiles, and replace finite maxima and minima by extrema or essential extrema of the group support. That gives a coherent high-multiplicity formulation, and the bound \(4\) plausibly lifts. But on finite support every relevant function—average distance, maximum distance, minimum distance, and their combinations—is piecewise linear in the facility location. The query optimum can therefore be found by a finite one-dimensional breakpoint search. The \(k\)-LDM analogue itself is just sorting and selecting a quantile. Again, the paper supplies no computational theorem to continue.

There is also a semantic cost. In a genuinely nonatomic model, one individual has zero mass, so strategyproofness is vacuous: changing one report does not change \(\mu\). The proposed finite-agent-consistent constraint restores substance only by quantifying over every finite realization and every perturbation of size \(1/N\). That is a defensible high-multiplicity bridge, but it means the incentive theory is still being imposed from the finite model rather than arising from the continuum. Even granting that bridge, the resulting quantile mechanism remains explicit and computationally trivial.

Theorem 1 is the one anchor I cannot honestly defeat mathematically. Its bad finite profiles can be duplicated, so the impossibility for the difference objectives survives normalization into masses. A continuous high-multiplicity version is therefore well-defined. But it is not a computational result: the unbounded ratio comes from profiles with \(D^*=0\), where any positive error makes the multiplicative ratio infinite. The continuous statement merely preserves that degeneracy. It gives a strategic impossibility boundary, not a Class A/B/C computational boundary. Replacing the ratio by an additive guarantee or a regularized denominator might create a better research question, but that would no longer mirror the paper’s theorem.

Thus the negative case should not claim that high multiplicity is nonsensical here; it is not. The municipal location-cell scenario is perfectly admissible. The point is narrower: every credible mirror either duplicates the paper’s finite proof over weighted masses or invents a new global mechanism-design problem whose computational model is unspecified. Under ChoCo’s stated computational scope, this paper offers no worthwhile continuous mirror. The negative case is weakest at Theorem 1, which is a genuine continuous high-multiplicity lift—but only as an impossibility restatement, not as the computational theory ChoCo is designed to develop.

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.