| paper | Facility Location Games with Optional Preferences: A Revisit |
| authors | Xingchen Sha, Shuyu Bao, Hau Chan, Vincent Chau, Ken C. K. Fong, Minming Li |
| venue | AAAI 2025 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Given \(k\), finitely many rational locations \(x\), and rational masses \(\mu_{x,A}\) over complete types \((x,A)\) with \(\varnothing\ne A\subseteq[k]\) and \(\sum_{x,A}\mu_{x,A}=1\), compute a deterministic rule returning facility locations \(y\in\mathbb{R}^k\) that is strategyproof under denominator-cleared clone deviations in the reported sets \(A\), places each facility \(j\) at a fixed weighted median of \(\nu_j(x)=\sum_{A\ni j}\mu_{x,A}\), and satisfies \(\operatorname{SC}^{\max}_\mu(y)\le k\min_{z\in\mathbb{R}^k}\operatorname{SC}^{\max}_\mu(z)\), where \(\operatorname{SC}^{\max}_\mu(y)=\sum_{x,A}\mu_{x,A}\max_{j\in A}|y_j-x|\).
High-multiplicity optional-preference facility location on \(\mathbb{R}\): types are \(\theta=(x,A)\), masses are \(\mu_\theta\), decision variables are facility positions \(y_1,\ldots,y_k\), and the objective is the mass-weighted Max-variant social cost \(\sum_\theta\mu_\theta\max_{j\in A_\theta}|y_j-x_\theta|\). Mechanism 6 uses weighted medians, while Theorem 4 uses accepted-support midpoints.
The mirror covers the Max variant, including Theorems 4 and 5, Mechanisms 5 and 6, and Theorem 5's tightness example. It leaves the Min variant, including Theorems 1–3, Lemmas 1–4, and their mechanisms and lower bounds, unmirrored.
The paper does admit a credible, though deliberately narrow, continuous mirror. The right regime is not an atomless population of arbitrary points on the line. It is a high-multiplicity society of recurring cohorts: many residents occupy the same public location \(x\) and have the same optional-preference set \(A\subseteq[k]\). A complete type is therefore \(\theta=(x,A)\), with mass \(\mu_{x,A}\in\mathbb Q_{\ge0}\) and \(\sum_{x,A}\mu_{x,A}=1\). Think of census cells, apartment complexes, or large commuting cohorts, where \(N\gg\tau\), the number of nonzero location/preference types.
The facilities remain \(k\) labelled facilities placed at positions \(y_1,\ldots,y_k\in\mathbb R\). For a type \((x,A)\), the paper’s Max cost is \(d_{x,A}(y)=\max_{j\in A}|y_j-x|\). The continuous population is the mass vector \(\mu\), not the already-continuous line. Clearing denominators gives exactly \(q\mu_{x,A}\) finite clone agents, and discrete social cost is \(q\) times continuous social cost. Thus this is a genuine high-multiplicity extension rather than a fractional-outcome reinterpretation.
My lead anchor is Theorem 5, proved in this paper. It states that Mechanism 6 is strategyproof and has approximation ratio \(k\) for the social cost in the Max variant. The corresponding problem is:
Continuous Max-Social Optional-Facility Location, \(\mathsf{MaxSC}_\infty\). Given \(k\), a finite rational type table \(\mu_{x,A}\), and nonempty accepted mass for every facility, compute a deterministic facility-location rule \(M^\infty\). On a truthful profile, it must output locations satisfying \(\operatorname{SC}^{\max}_\mu(M^\infty(\mu))\le k\,\operatorname{OPT}^{\max}_\mu\), where \(\operatorname{SC}^{\max}_\mu(y)=\sum_{x,A}\mu_{x,A}\max_{j\in A}|y_j-x|\) and \(\operatorname{OPT}^{\max}_\mu=\min_{y\in\mathbb R^k}\operatorname{SC}^{\max}_\mu(y)\). It must also be strategyproof under the paper’s information structure: \(x\) and its mass are public, while each agent reports \(A\).
The continuous Mechanism 6 places \(F_j\) at a weighted median of the location distribution \(\nu_j(x)=\sum_{A\ni j}\mu_{x,A}\). A fixed lower- or upper-median convention makes the rule deterministic. This is exactly the finite mechanism after denominator clearing: a weighted median is simply the ordinary median of the corresponding clone population. Therefore Theorem 5’s strategyproofness and its \(k\)-approximation guarantee transfer verbatim to every rational high-multiplicity instance.
This mirror is computationally meaningful. Each weighted median is computable in polynomial time in \(k\), \(\tau\), and the encoding length \(L\), independently of the number \(N\) of named agents. Even the optimum benchmark has a compact LP: introduce \(z_{x,A}\) and impose \(z_{x,A}\ge y_j-x\) and \(z_{x,A}\ge x-y_j\) for every \(j\in A\), then minimize \(\sum_{x,A}\mu_{x,A}z_{x,A}\). I therefore expect \(\mathsf{MaxSC}_\infty\) to be Class A.
The paper’s tightness example also survives. Put mass \(1/(k+1)\) at \(0\) with acceptable set \([k]\), and mass \(1/(k+1)\) at \(1\) for each singleton type \(\{j\}\). With the same tie-breaking convention as the paper, Mechanism 6 places all facilities at \(0\), while placing them all at \(1\) is optimal. The ratio is \(k\). Thus the continuous version does not trivialize the paper’s guarantee.
My second anchor is Theorem 4, also proved in this paper. It states that Mechanism 5 is strategyproof and optimal for maximum cost in the Max variant. The corresponding problem is:
Continuous Max-Robust Optional-Facility Location, \(\mathsf{MaxMC}_\infty\). Given the same type-mass instance, compute a deterministic rule \(M^\infty\) minimizing \(\operatorname{MC}^{\max}_\mu(y)=\max_{x,A:\mu_{x,A}>0}\max_{j\in A}|y_j-x|\), subject to strategyproofness. For each facility \(j\), define \(\ell_j\) and \(r_j\) as the leftmost and rightmost locations having positive mass of agents whose acceptable set contains \(j\). The rule outputs \(y_j=(\ell_j+r_j)/2\).
This is exactly Mechanism 5 with counts replaced by masses. It is optimal because every facility \(j\) must serve some agents in its accepted population, giving the lower bound \((r_j-\ell_j)/2\), and the midpoint attains that bound simultaneously for every \(j\). The resulting output is computable in polynomial time, and the optimum maximum-cost value is also an LP value. Hence this is another Class A mirror, in fact an exact one.
Theorem 4 is somewhat weaker as evidence for the population programme because maximum cost depends only on extreme support points; much of the mass can disappear from the objective. Theorem 5 is the stronger anchor because masses affect both the weighted medians and the social objective. Still, the two results are independently recognizable: one mirrors exact robust placement, the other approximate aggregate welfare.
I would not stretch the case to Theorems 1–3 or Lemmas 1–4. Their Min-variant mechanisms rely on well-separated individual configurations, deletion histories, and delicate pivotal-agent arguments. A mass formulation is possible, but the preservation of those conditions is not immediate and would require a separate paper-specific analysis. The present mirror covers only the Max-variant results, namely Theorems 4 and 5 and their associated mechanisms and guarantees.
The weakest point is strategyproofness in a literal atomless interpretation. A single individual has zero mass, so ordinary unilateral strategyproofness becomes vacuous. I would therefore define the continuous rule with clone-consistent strategyproofness: for every rational \(\mu\), every denominator-clearing clone population, and every single clone’s alternative report \(A'\), that clone cannot reduce its true cost. This preserves exactly the paper’s individual-deviation semantics and is inherited from Theorems 4 and 5. If a referee instead demands strategyproofness against positive-mass coalitions, these theorems do not establish it and may not remain true. That makes the proposal an author-recognizable high-multiplicity extension, not a complete atomless mechanism-design theory.
Natural follow-up questions are whether the \(k\) bound in Theorem 5 can be improved for restricted type supports, how finite-\(N\) rounding behaves for irrational distributions, whether positive-mass coalition strategyproofness is possible, and what happens when locations are given by a continuous density rather than a finite rational type table.
The strongest negative case is against Theorem 4. Its maximum-cost objective discards multiplicity entirely. If \(S_j\) is the support of locations of agents accepting facility \(j\), then
\[ \operatorname{MC}^{\max}_\mu(y) = \max_j\sup_{x\in S_j}|y_j-x| = \max_j\max\{y_j-\ell_j,r_j-y_j\}. \]
Thus only the extreme accepted locations \(\ell_j,r_j\) matter. The midpoint is optimal independently for every facility, and the masses of all types—including almost the entire population—disappear. Replacing the finite society by a density changes nothing except the meaning of “support.” A mass-sensitive objective would be a different problem, not a stronger mirror of Theorem 4. This is a genuine continuum degeneration: the proposed “continuous” problem is support geometry, not population computation.
Theorem 5 is harder to defeat. The proposed type \((x,A)\) is complete, repeated cohorts at a common location are plausible, and
\[ \operatorname{SC}^{\max}_\mu(y) = \sum_{x,A}\mu_{x,A}\max_{j\in A}|y_j-x| \]
is genuinely mass-sensitive. Weighted medians and the stated LP are legitimate high-multiplicity formulations. Denominator clearing transfers the theorem exactly, and high multiplicity is expressly within ChoCo’s scope. So this is not defeated by saying that it is merely a weighted restatement, nor by objecting that the answer may remain easy.
There is, however, a serious semantic weakness in the proposed strategyproofness claim. Under a literal atomless interpretation, one individual has zero mass and cannot change the weighted medians; strategyproofness is vacuous. The proposed “clone-consistent strategyproofness” repairs this only by referring back to every finite denominator-clearing clone election. That is a valid high-multiplicity lift, but it is not a nonvacuous strategyproofness notion on the continuous society itself.
If one instead gives a positive-mass type or coalition the ability to misreport, the paper’s theorem no longer transfers. For example, take \(k=2\): one agent at \(0\) with true set \(\{F_1\}\), two agents at \(10\) with true set \(\{F_1\}\), and two agents at \(0\) with true set \(\{F_2\}\). Mechanism 6 places \(F_1\) at \(10\) and \(F_2\) at \(0\). The latter two agents can jointly report \(\{F_1,F_2\}\). Their true costs remain \(0\), while the \(F_1\)-median moves to \(0\), strictly benefiting the first agent. Hence the weighted rule is not coalition-strategyproof. A genuinely population-level strategic formulation would therefore require a new theorem and possibly a different mechanism.
The preliminary scope objection is also worth recording: the paper contains no numbered result about complexity, hardness, parameterized algorithms, or a nontrivial optimization problem over a population. Theorems 4 and 5 are mechanism-design guarantees whose algorithms are coordinatewise midpoint and median rules. That makes them weaker ChoCo anchors than the paper’s proponents suggest, though it is not by itself decisive because approximation mechanisms can count as computational results.
The honest negative conclusion is therefore limited. Theorem 4 can be rejected as a degenerate support-only mirror, and Theorem 5 can be downgraded as either vacuous under atomless strategyproofness or purely a finite high-multiplicity lift under clone consistency. But Theorem 5 remains a credible continuous mirror under ChoCo’s explicitly permitted interpretation. A universal claim that no worthwhile mirror exists would not survive it honestly.
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.