| paper | d4-conf-aaai-2018-0613 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: A deterministic strategy-proof \(2\)-approximation exists, has strictly positive social utility on every society, and is computable in time polynomial in \(m,\tau,L\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite-support society of types \(t=(x_t,p_t)\), where \(x_t\in[0,L]\), \(p_t\in\{(p_1,p_2)\in[0,1]^2:p_1+p_2=1\}\), and positive rational masses \(\mu_t\) summing to \(1\), with locations public and preferences reported, construct a deterministic mechanism returning \(y_1,y_2\in[0,L]\). For each type, allow its whole mass to replace its reported preference by \(q_t\), while evaluating its utility using its true \(p_t\); require that no such deviation improves utility and that \(\mathrm{OPT}(\mu)/\mathrm{SU}_{\mu}(y)\le 2\), with computation polynomial in \(\tau\) and the input bit length.
Use types \((x_t,p_t)\) with rational masses \(\mu_t\); choose facility locations \(y_1,y_2\) to maximize \(\mathrm{SU}_{\mu}(y)=\sum_t\mu_t\bigl(L-p_{t1}|x_t-y_1|-p_{t2}|x_t-y_2|\bigr)\). A positive-mass type reports its preference as a cohort, with utility assessed under its true preference. The midpoint mechanism places each facility halfway between the extreme locations of types reporting positive preference for it.
Theorem 4 proves individual strategyproofness, while the continuous model needs cohort-level deviations; the proponent gives a proof sketch for that stronger condition, but the paper does not establish it or show that its authors would adopt that incentive unit.
fatal: False
The mirror extends Theorem 4's preference-only social-utility \(2\)-approximation. Theorem 3's \(1.06\) lower bound has a proposed cohort analogue but is not needed for the verdict; the other reporting regimes, minimum-utility results, and cost-minimization bound are outside this mirror.
The strongest positive case is narrow: the paper’s social-utility objective when locations are public and preferences are private. The paper does not give an NP-hardness or standard complexity-class result. Its useful anchors are instead a named approximation lower bound and a named mechanism guarantee.
A plausible regime is a large city planning a hospital and a clinic. A resident’s type is \(t=(x_t,p_t)\): their public location \(x_t\) on the line and their private preference vector \(p_t=(p_{t1},p_{t2})\), with \(p_{t1}+p_{t2}=1\). Residents at the same location with the same preference are indistinguishable for this problem. A society is a finite list of such types with positive binary-rational masses \(\mu_t\) summing to one. This fits a setting where many residents share building or neighborhood locations and a small number of recurring usage profiles, so the population size \(n\) can greatly exceed the support size \(\tau\).
For facilities at \(y=(y_1,y_2)\in[0,L]^2\), define
\[
u_t(y)=L-p_{t1}|x_t-y_1|-p_{t2}|x_t-y_2|,
\qquad
\mathrm{SU}_\mu(y)=\sum_t\mu_tu_t(y),
\]
and let \(\mathrm{OPT}(\mu)=\max_y\mathrm{SU}_\mu(y)\). A mechanism receives the locations, masses, and reported preferences, and returns facility locations. For strategyproofness, treat each positive-mass type as a cohort: it may report a different preference vector while its location and mass remain fixed, and its utility is evaluated using its true preference. This makes the population continuous while keeping the paper’s reporting question recognizable. The facilities’ locations are already continuous in the paper; the mirror’s continuization is the population.
My lead is Continuous Fractional-Preference Social Utility, 2-Approximation. Its anchor is Theorem 4, proved in this paper: when agents can misreport preferences only, Mechanism 2 places each facility at the midpoint of the leftmost and rightmost agents with positive preference for it; the mechanism is deterministic and strategyproof, and its social-utility approximation ratio is at most \(2\).
The continuous problem is: for every rational finite-support society just defined, construct one deterministic cohort-strategyproof mechanism that returns \(y_1,y_2\) and guarantees \(\mathrm{OPT}(\mu)/\mathrm{SU}_\mu(y)\le 2\) on every input. A solution is a mechanism and a proof of its incentive and approximation guarantees, with computation polynomial in \(\tau\) and the input bit length. The midpoint rule is a concrete candidate: each supported type that values facility \(j\) lies between that facility’s two support endpoints, so its distance to their midpoint is at most \(L/2\); its utility is therefore at least \(L/2\). For a normalized population, \(\mathrm{SU}_\mu\ge L/2\), while \(\mathrm{OPT}(\mu)\le L\). For a whole cohort’s preference deviation, keeping positive preference for \(j\) leaves its location among the supporters; dropping that preference can only remove an endpoint, moving the midpoint inward and away from the cohort. That gives a direct route to the cohort incentive proof. The expected classification is tractable.
A second, supporting question is Continuous Fractional-Preference Social Utility, 1.06 Barrier. Theorem 3, also proved here, says that in the preference-only reporting case no deterministic strategyproof mechanism has approximation ratio less than \(1.06\). Ask whether that same lower bound holds for the rational-mass cohort model. The paper’s witness compresses directly: its four agents become masses \(1/4\) at \((0,(1,0))\), \(1/2\) at \((0,(0,1))\), and \(1/4\) at \((L,(0,1))\). The proof’s joint misreport by the two identical agents is exactly a misreport by the mass-\(1/2\) cohort. The expected direction is that the impossibility transfers. This is a strategyproof approximation barrier, not an NP-hardness result.
These are meaningful mirrors because they preserve the same facilities, utility, preference reports, and objective, while making mass the population quantity. They cover only Theorems 3 and 4’s preference-only social-utility results; I would leave the other reporting regimes, minimum utility, and cost minimization out of scope. The approximation gap between \(1.06\) and \(2\), and whether randomization improves it for cohorts, are natural follow-up questions.
The weak point is the strategic unit: the paper proves ordinary individual strategyproofness, while the mirror treats an identical-type cohort as one reporting bloc. That is a stronger and explicit modeling choice. The lower-bound witness already uses such a bloc, and the midpoint mechanism appears to withstand a whole-cohort deviation by its endpoint structure, but that extension needs proof. If the authors reject cohort-level reporting as their problem, this case loses force; if they accept it as the high-multiplicity version, the same model yields a concrete tractable guarantee and a transferred lower bound.
The strongest objection is that both anchors are incentive theorems, and a society \(\mu\) by itself has no nontrivial notion of an individual agent’s deviation. In a nonatomic model, one person has zero mass: changing that person’s report leaves \(\mu\), the mechanism’s input, and its outcome unchanged. Strategyproofness then holds vacuously. This affects Theorem 4’s \(2\)-approximation and Theorem 3’s \(1.06\) lower bound alike.
The proposed fix—make each positive-mass type a strategic cohort—changes the incentive concept. Theorem 4 proves individual strategyproofness; asking a whole cohort to change its preference is a coalition-proofness requirement. Its midpoint rule may well satisfy that stronger condition in the preference-only case, since removing a cohort from a facility’s supporters can only move that facility’s midpoint away from them. But that is a new claim about group deviations, not a direct continuous version of the theorem. Conversely, Theorem 3’s proof already uses a joint deviation by two identical agents. Its lower bound therefore has a particularly natural cohort formulation, but it establishes an impossibility for that coalition model; it does not resolve the mismatch between individual incentives and nonatomic mass.
One could preserve individual deviations by specifying a finite population scale \(N\), so one report changes mass by \(1/N\). Then \(\mu\) alone is insufficient: the same distribution can represent populations with different unilateral deviation sizes. Adding \(N\) or a mass quantum yields a high-multiplicity discrete mechanism problem. That may be worthwhile, but the mirror now depends on a population-granularity parameter absent from the proposed continuous problem.
There is also a narrower scope concern: these are approximation and incentive guarantees for mechanisms, not worst-case complexity classifications. A continuous version would need to establish that mechanism design on distributional inputs is a target of this programme, rather than assume that every approximation theorem is already a computational-complexity question.
This is a real modeling objection, but it does not establish the universal negative. The paper’s lower-bound proof itself uses identical-agent groups, and a cohort interpretation is plausible for some institutions. If the authors accept cohort-level incentives—or explicitly study finite-granularity high-multiplicity mechanisms—Theorem 3 and possibly Theorem 4 remain credible mirrors. I cannot honestly defeat those better formulations on the material given; the negative case is strongest as a demand to justify the strategic unit, not as evidence that no worthwhile mirror exists.
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.