| paper | d4-conf-sagt-2019-0023 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The numbered theorems characterize when welfare-optimal mechanisms satisfy incentive constraints; none gives an algorithmic guarantee, hardness result, or computational formulation used to compute. The proponent also acknowledges that the proposed mass-coalition extension is not a computational anchor. The facility computation derived from the welfare formula is not a named result of the paper.
fails bit a — no named computational result to mirror
The proposed mass-distribution question follows Theorem 1’s unknown-preference setting; it leaves Theorems 2–5 and their unknown-location characterizations aside.
There is no qualifying computational anchor in this paper. Theorem 1, proved here, says that when preferences are private and locations are public, a social-welfare-optimal mechanism is group-strategyproof for every feasible region \(\Gamma\). Theorems 2–5, also proved here, characterize the opposite setting: when locations are private, strategyproofness of an optimum requires the optimum to be constant in the stated preference-count cases. These are incentive and geometric characterizations, not results that a problem is in P, hard, or parameterized-tractable. So under the anchor rule, the paper supplies no named computational result to mirror.
The strongest nearby positive case is a population version of Theorem 1, though it is an extension of an incentive result, not a valid computational anchor. Consider a school district with many residents in a modest number \(q\) of known location clusters \(X=\{x_1,\ldots,x_q\}\subseteq[0,\ell]\). A type is \((x_j,p)\), where \(p\in\{-1,1\}\) records whether a resident wants the facility nearby or far away. The rational mass \(\mu_{j,p}\) is the fraction of residents of that type. The regime is credible when the number of residents is large relative to the number \(2q\) of possible types.
Call the proposed problem Preference-Report Facility Location with Mass Coalitions. Given \(X\), the masses, \(\lambda\), and a compact feasible region \(\Gamma\), a mechanism receives preference reports while locations remain public, then selects \(f\in\Gamma\) maximizing
\[
\mathrm{SW}_{\mu}(f)=\sum_{j,p}\mu_{j,p}u((x_j,p),f).
\]
A solution is a deterministic optimal selection rule that is group-strategyproof against deviations by any positive-mass coalition: members’ true-type utilities must not decrease, and a positive mass must strictly gain, for the deviation to be profitable. This replaces the paper’s sums over agents with population-weighted sums while keeping its types, utilities, objective, private information, and facility decision. It covers the unknown-preferences result only.
The anchor it most closely follows is Theorem 1: for every feasible region where the optimum is well-defined, the social-welfare-optimal mechanism is GSP when agents can misreport preferences but not locations. That theorem is proved in this paper. The continuous question is whether the same claim holds for mass distributions and positive-mass coalition deviations. I expect the incentive claim to extend: the paper’s proof works through aggregate counts and location sums, which have direct mass-weighted counterparts. That expectation still needs proof.
There is also a tractable computational question attached to this model, once \(\Gamma\) is represented as a rational compact polygon: compute an optimal facility for a reported mass profile. The paper’s welfare expression reduces this to a two-dimensional geometric optimization using the aggregate preference mass and location sums. The zero, positive, and negative cases of \(m-n\) require, respectively, a linear \(x\)-coordinate extremum, a nearest-point problem, or a farthest-vertex search. That gives a plausible polynomial-time computational problem for this restricted input representation, but it is derived from the paper’s model; it is not a complexity result established by one of its theorems.
The weakest point is the gap between the paper’s question and the programme’s computational focus. Its main contribution is about incentive compatibility, not worst-case complexity, and a nonatomic model makes an individual’s deviation have zero effect. Defining positive-mass coalition deviations avoids that vacuity and fits high multiplicity, but changes the strategic quantifier and must be defended as the intended limit. The paper’s unknown-location results are promising further questions for mass populations, but I would not count them as anchors either.
The paper gives no named computational result to mirror. Theorem 1 characterizes incentives when preferences are private; Theorems 2–5 characterize feasible regions compatible with truthful optimal mechanisms when locations are private. They say nothing about the complexity of a computational problem. The proponent’s own account concedes this, so their proposed extension of Theorem 1 is an incentive question, not a complexity anchor.
The proposed mass model is plausible, but its computational task does not make a strong case for ChoCo. With types \((x_j,p)\), the welfare depends on the population only through aggregate preference masses and location-weighted masses. Writing \(\gamma\) for the difference in preference masses and \(\delta\) for the difference in their location-weighted sums, the paper’s formula makes the facility choice a linear \(x\)-coordinate extremum when \(\gamma=0\), or a nearest- or farthest-point problem relative to \((\delta/\gamma,0)\) otherwise. For a rational polygon, those are straightforward geometric operations after computing the aggregates. Even a distribution over a continuum of locations contributes only the corresponding masses and first moments. The added population continuum creates no pricing problem or other substantial computational bottleneck; most of the computation is over the facility’s already continuous outcome space.
Theorem 1’s GSP claim could still motivate a mass-coalition extension. Ordinary individual strategyproofness becomes vacuous for nonatomic agents, while the proposed positive-mass coalition definition is a defensible replacement. But whether the theorem extends under that definition is an incentive-theoretic question. Proving it would not classify the complexity of bribery, control, campaigning, or robustness. Theorem 1 remains the closest named anchor, and it does not carry the programme’s computational question.
The strongest alternative is to continuize Theorems 2–5: ask which facility regions permit a truthful, welfare-optimal mechanism for a distribution over locations. That could be a worthwhile extension of the paper’s mechanism-design programme. It still asks for an incentive and geometric characterization, rather than a computational result. Turning it into a decision problem about a polygon’s representation, or an optimization problem over feasible regions, would require an additional formal input model; any complexity could then come from that encoding rather than the population. The paper’s broader question about how large a feasible region can be has the same gap.
So I would reject these as anchors for ChoCo, while recognizing that the mass-population incentive questions could interest mechanism-design researchers. The limit of this negative case is the word “any”: one could add a new intervention problem, such as minimum-cost mass bribery, that the authors might recognize as nearby. But that would add a computational objective absent from the paper. The material given here does not support ruling out every such extension; it supports the narrower, stronger conclusion that none of the paper’s named results supplies a worthwhile computational mirror as stated.
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.