| paper | Heterogeneous Facility Location with Limited Resources |
| authors | Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros A. Voudouris |
| venue | AAAI 2022 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper has named approximation and impossibility theorems, and their mass formulations are coherent. However, under the explicit bit-(a) rule, these are statements about strategyproof mechanisms rather than complexity or algorithms for an instance-level computational problem on a society. The proposed optimization is a global mechanism-design characterization, so the paper fails the computational requirement and is red.
fails bit a — no named computational result to mirror
The proposed optimization chooses a mechanism over all societies, making it a mechanism-design characterization rather than an instance-level computational problem; this defeats bit (a) for every anchor.
fatal: True
The proposed mass extension mirrors Theorems 1, 2, 4, and the restricted-class lower bound in Theorem 5; it does not establish computational mirrors for the remaining results or the \(k\)-out-of-\(m\) extensions.
The strongest honest case is a high-multiplicity mirror of the paper’s two-facility problem in the known-preferences setting. It is a legitimate population continuization, although it is not a flagship ChoCo complexity example: the paper proves approximation and incentive bounds, not NP-hardness or parameterized complexity.
The type must include both location and approval preference. Let \(\theta=(x,t)\), where \(x\in[0,1]\) and \(t\in\{0,1\}^2\). A society is a finite-support rational distribution \(\mu\) over such types. Thus \(\mu_{(x,t)}\) is the fraction of residents in a cohort at location \(x\) with approval vector \(t\). The action remains exactly the paper’s action: choose one facility \(j\in\{1,2\}\) and locate it at \(y\in[0,1]\). Welfare is
\(W_\mu(j,y)=\sum_{(x,t)}\mu_{(x,t)}t_j(1-|x-y|)\),
and \(\operatorname{OPT}(\mu)=\max_{j,y}W_\mu(j,y)\).
A plausible regime is a large municipality with tens or hundreds of thousands of residents, but only a few dozen relevant cohorts: residents of the same census block or housing development, with the same approval preference for a library or sports facility and approximately the same normalized location. Here \(N\gg\tau\), where \(\tau\) is the number of occupied \((x,t)\)-cohorts. The mass is genuinely population mass; neither the facility nor its location is fractionalized.
There is one necessary adjustment. Literal individual strategyproofness becomes vacuous in a nonatomic population, because one person has zero mass and cannot change \(\mu\). I would therefore define the mirror using positive-mass-coalition strategyproofness: a coalition may transfer mass from \((x,t)\) to reported locations \((\widehat{x},t)\), preserving the public approval vector, but no positive-mass coalition may make every member strictly better off. This is the natural continuous counterpart of group-strategyproofness, which the paper already treats as a central incentive requirement. A finite-\(N\) version can retain one-agent deviations by representing \(\mu\) as \(n/N\) and then taking the high-multiplicity limit.
My lead anchor is Theorem 2, proved in this paper. It states that in the known-preferences setting no deterministic strategyproof mechanism has approximation ratio better than \(2-\delta\), for any \(\delta>0\).
The corresponding continuous problem is:
Continuous Deterministic Known-Preference Facility Location. Given a finite-support rational society \(\mu\) over \((x,t)\)-types, determine the smallest \(\rho\) for which there exists a deterministic map \(M\) from reported societies to outcomes \((j,y)\) such that:
\(M\) is positive-mass-coalition strategyproof; and
\(W_\mu(M(\mu))\ge \operatorname{OPT}(\mu)/\rho\) for every society \(\mu\).
A solution is the mechanism \(M\), together with its truthfulness proof and worst-case approximation guarantee.
The paper’s lower-bound construction survives this mirror almost verbatim. Put mass \(1/4\) at each of the four cohorts obtained from the paper’s four agents: approval types \((0,1)\) and \((1,0)\), each appearing at \(\epsilon\) and \(1\). After moving the \((1,0)\)-cohort at \(\epsilon\) to report location \(1\), the same incentive argument forces the mechanism to continue selecting facility \(2\). The resulting welfare is at most \((1+\epsilon)/4\), while the optimum is \(1/2\), giving ratio at least \(2/(1+\epsilon)\), which tends to \(2\). The deviation is now by a coherent mass-\(1/4\) cohort rather than by one named individual, so it is meaningful in the continuum model.
The upper bound also survives. The paper’s Theorem 1, proved here, shows that the Middle mechanism is group-strategyproof and has ratio \(2\). In the mirror, let \(q_j=\sum_{(x,t)}\mu_{(x,t)}t_j\). Choose the facility with larger approval mass and place it at \(1/2\). Every approving unit receives utility at least \(1/2\), so the welfare is at least half the optimum. Hence the continuous problem should have exact optimum \(\rho=2\). Under the ChoCo trichotomy, this is a tractable problem with a transferred incentive impossibility, not a Class B hardness result and not a Class C phenomenon.
The main follow-up is whether this exact \(2\) boundary remains under a more literal family of finite-\(N\), one-agent-strategyproof mechanisms, rather than the positive-mass notion. That is also the mirror’s weakest technical point.
A second, independently worthwhile anchor is Theorem 4, also proved in this paper. It gives the randomized Mirror mechanism in the known-preferences setting: universal group-strategyproofness and approximation ratio \(4/3\).
The continuous problem is:
Continuous Randomized Known-Preference Facility Location. Given \(\mu\), find a universally positive-mass-coalition-strategyproof randomized mechanism \(R\) mapping reported societies to distributions over \((j,y)\), minimizing the worst-case ratio
\(\operatorname{OPT}(\mu)\big/\mathbb{E}_{(j,y)\sim R(\mu)}[W_\mu(j,y)]\).
A concrete candidate is the exact mass analogue of the paper’s Mirror mechanism. Assume \(q_1\ge q_2\), set \(\alpha=(3q_1-2q_2)/(4q_1-2q_2)\), choose facility \(1\) with probability \(\alpha\) and facility \(2\) otherwise, and locate the chosen facility at a weighted median of the approving population for that facility. The relevant weighted median is computable by sorting the finitely many support locations. The same inequalities \(q_j/2\le W_j\le q_j\) used in the paper give approximation ratio \(4/3\), and the mechanism is computable in polynomial time in \(\tau\) and the input bit length.
Thus this second mirror is clearly Class A in the programme’s sense: the continuous mechanism is explicit and efficiently computable. The natural further question is whether \(4/3\) remains optimal among all universally mass-group-strategyproof mechanisms, rather than only for the particular Mirror construction. The paper’s Theorem 5, also proved here, gives a \(4/3-\delta\) lower bound for the narrower Random-Median class; its weighted two-cluster witnesses are strong evidence that this lower bound should transfer to the mass formulation, though that transfer should be proved rather than assumed.
The mirror covers only the paper’s two-facility, one-built-facility, known-preferences results—especially Theorems 2 and 4, with Theorem 1 as supporting structure. I would not claim that it automatically covers the known-positions, fully general, or \(k\)-out-of-\(m\) settings.
The positive case is therefore real but bounded. The original authors should recognize the mirror: same agents’ information, same approval utilities, same facility-and-location decision, same welfare objective, same strategyproofness notion in its non-vacuous mass form, and the same approximation questions. The serious limitation is that the paper contains no named NP-hardness, \(\mathrm{P}\), W[1]-hardness, or FPT result. This mirror tests whether mechanism-design approximation bounds survive high multiplicity; it does not yet deliver the computational-complexity landscape that is ChoCo’s central prize.
The strongest negative case is not that the proposed population model is nonsensical. It is that none of the paper’s anchors is a computational result of the kind ChoCo is meant to continuize.
Theorem 2 is an approximation-impossibility theorem for strategyproof mechanisms, not a complexity theorem. Its mass analogue is perfectly definable: place mass \(1/4\) at each of the four locations and approval types, and let the whole \((\varepsilon,(1,0))\)-cohort misreport its position. The lower-bound argument transfers. But what transfers is a global mechanism-design axiom and its worst-case ratio, not an algorithmic problem on a continuous society. The corresponding optimization is
\[ \inf_M\sup_\mu \frac{\operatorname{OPT}(\mu)}{W_\mu(M(\mu))}, \]
where the variable is a mechanism over all societies. That is a continuum mechanism-design characterization, not an instance-level problem such as bribery, control, campaigning, or winner robustness.
The computational content of the proposed mirror is correspondingly negligible. For a finite-support society, approval masses are
\[ q_j=\sum_\ell w_\ell t_{\ell j}, \]
and the welfare-maximizing location for facility \(j\) is a weighted median of the approving locations. Middle is computed by counting masses and placing the facility at \(1/2\); the optimal welfare is obtained by sorting locations and taking weighted medians. These are ordinary weighted-statistics computations, not exponential-type LPs, pricing problems, or a new complexity landscape. Calling the resulting bound “Class A” would therefore stretch Class A beyond its stated purpose: the continuous object has not made a hard computational problem tractable; it has merely replaced finite sums by weighted sums.
Theorem 1 has exactly the same defect. Its continuous proof is a valid rescaling of the finite proof, but it asks only whether a simple rule is group-strategyproof and achieves ratio \(2\). That is an axiomatic approximation statement. The fact that the answer remains \(2\) is neither a computational discovery nor a reason to build a continuous mirror.
Theorem 4 is no stronger in this respect. The mass version of the Mirror mechanism is easy to write:
\[ \alpha=\frac{3q_1-2q_2}{4q_1-2q_2}, \]
followed by a weighted median for the selected facility. Its approximation proof uses exactly the paper’s inequalities \(q_j/2\le W_j\le q_j\). This is a legitimate continuous mechanism, but only in the sense that every finite-population mechanism based on counts and medians has an obvious weighted analogue. Theorem 5 does not rescue it: its lower bound concerns only the restricted Random-Median class, not all universally group-strategyproof mechanisms. Even if that lower bound is transferred exactly, the result remains a class-specific mechanism-design bound.
There is also a representation fork that the proposed mirror does not resolve. If the society is genuinely an arbitrary distribution over \(x\in[0,1]\), then polynomial-time computation requires an encoding or oracle model for that distribution. Without one, “compute the weighted median” is not a complexity question. If the society is instead restricted to rational finite support, as the proponent suggests, then the input is simply a high-multiplicity list of location-preference cohorts, and all of the paper’s mechanisms reduce to sorting, counting, and elementary arithmetic. Either the continuous input is under-specified, or the finite encoding contains no interesting computational obstruction.
Changing the scenario does not repair this. A municipality with repeated census-block cohorts is a sensible high-multiplicity interpretation, and the known-positions, fully private, and \(k\)-out-of-\(m\) variants can likewise be given mass formulations. But they remain questions about which strategyproof rule has which distortion guarantee. They do not become computational questions merely because agents are represented by a measure. Nor can one obtain a ChoCo-style result by asking for the “best” strategyproof mechanism: that is an infinite-dimensional rule-characterization problem, and is precisely the axiomatic mechanism-design direction that the programme places outside scope.
So the proposed mirror is not wrong. The proponent is right that Theorem 2, and probably Theorem 4, admit coherent mass formulations. The weakness is more fundamental: this paper supplies no named \(\mathrm{P}\), NP-hardness, approximation-algorithm, or parameterized-complexity result for the continuous population to investigate. Its theorems concern the design and impossibility of rules, while the continuous versions merely replace cardinalities by masses and medians by weighted medians. Under a broader programme on continuous mechanism design, this would be a modestly worthwhile case. Under ChoCo’s stated computational remit, all three anchors fall outside the target, and no worthwhile continuous mirror is established.
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.