| paper | d4-conf-atal-2015-0105 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Both properties hold in the stated mass-splitting model. The exact worst-case approximation ratio is \(1/3\). For \(m=1\), the specified exact algorithm uses \(O(\tau)\) arithmetic operations, \(O(L^2)\) bit operations, and \(O(L)\) working space under standard binary rational encoding. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given \(l>0\) and a finite-support rational society \(\mu\) over types \(t=(x,p)\in[0,l]\times\{0,1\}\), set \(z_t=x\) when \(p=0\), \(z_t=l-x\) when \(p=1\), and \(a=\sum_{t:z_t<l/2}\mu_t\). Let \(F(\mu)=0\) if \(a\le 1/2\), and \(F(\mu)=l\) otherwise, extending this rule to reported finite-support real-mass distributions so deviations are defined. Prove or refute that \(F\) is group-strategyproof against every positive-mass coalition whose members may reassign their reports and that \(U(F(\mu);\mu)\ge \frac13\max_{y\in[0,l]}U(y;\mu)\) for every rational input; give the exact algorithm and its bit complexity.
A finite-support distribution of residents by location and preference, with rational type masses; the facility location \(y\) is chosen by the transformed-location mass threshold, and the objective is per-capita social utility \(U(y;\mu)=\sum_t\mu_tu(t,y)\), compared with the optimum over \(y\in[0,l]\). Coalitions reassign the reports of positive mass.
For rational societies, denominator replication makes the \(1/3\) guarantee an immediate transfer from Theorem 6, leaving little new computational structure; this bounds novelty but does not invalidate the continuous question.
fatal: False
The mirror covers Mechanism 2's group-strategyproofness in Theorem 3 and its social-utility guarantee in Theorem 6. It leaves Theorem 2's preference-only setting and the two-facility results, including their parity-dependent guarantees, aside.
The strongest case is in the dual-character facility location game, where a single facility is placed on a line and agents may either want to be close to it or far from it. A plausible high-multiplicity setting is a city deciding where to put a noisy, busy market: many households live in a relatively small set of residential blocks, and households at the same block with the same attitude toward the market are one type. A type is \(t=(x,p)\), with block location \(x\) and preference \(p\in\{0,1\}\). The society is a rational distribution \(\mu\) over the finite type set \(T=X\times\{0,1\}\); \(\mu_t\) is the fraction of households of that type. The number of households can be very large while the support size \(\tau\) stays small.
The facility’s choice remains \(y\in[0,l]\), as in the paper. Utility is also unchanged: \(u((x,0),y)=|x-y|\) and \(u((x,1),y)=l-|x-y|\). The social utility is \(U(y;\mu)=\sum_t\mu_tu(t,y)\), with benchmark \(\operatorname{OPT}(\mu)=\max_{y\in[0,l]}U(y;\mu)\). The continuous object is the population: an ordinary \(n\)-agent profile becomes \(\mu_t=n_t/n\), while the mass model also allows arbitrary rational proportions and fractional deviations by a cohort.
My first anchor is Theorem 3, proved in this paper. It says that Mechanism 2 is group-strategyproof when agents can misreport both location and preference. For each report \((x,p)\), set \(z=x\) if \(p=0\), and \(z=l-x\) if \(p=1\). The mechanism counts reports with \(z\in[0,l/2)\) as \(n_l\), and the others as \(n_r\); it places the facility at \(0\) if \(n_l\le n_r\), and at \(l\) otherwise.
A continuous verification question is: Mass-Weighted Dual-Character GSP. Given \(l\) and \(X\), does that rule remain group-strategyproof for every rational society \(\mu\) on \(T\), when a coalition may be any positive-mass submeasure \(\lambda\le\mu\) and may reassign its members’ reports to arbitrary \((x',p')\in[0,l]\times\{0,1\}\)? Write \(\mu'\) for the resulting society. The rule is group-strategyproof if there is no such deviation for which almost every participating household strictly improves its *true-type* utility, \(u(t,F(\mu'))>u(t,F(\mu))\). A solution is a proof of this universal claim, or a counterexample consisting of a society and a profitable deviation. I expect the claim to hold: when the rule outputs \(0\), any household that strictly prefers switching to \(l\) has \(z<l/2\), and such a coalition cannot turn a non-majority into a strict majority merely by changing its reports. The other output has the symmetric argument.
The lead anchor is Theorem 6, also proved here. It says that Mechanism 2 has social-utility approximation ratio at least \(1/3\): for every finite profile \(c\), its output \(y\) satisfies \(\mathrm{SU}(f,c)/\mathrm{OPT}(c)\ge 1/3\). My continuous question is Mass-Weighted Dual-Character \(1/3\)-GSP Design. Given \(l\) and \(X\), find one deterministic rule \(F\), defined on every rational society supported on \(T\), such that it is group-strategyproof under the positive-mass deviation definition above and, for every input \(\mu\), satisfies
\[
U(F(\mu);\mu)\ge \tfrac13\operatorname{OPT}(\mu).
\]
The solution is the rule, a proof of both properties, and an exact algorithm for evaluating it. The direct mass analogue of Mechanism 2 is the natural candidate: compute \(a=\sum_{t:z_t<l/2}\mu_t\), output \(0\) if \(a\le 1/2\), and \(l\) otherwise. This takes polynomial time in \(\tau\) and the mass bit length \(L\). I expect a tractable, Class A result: the rule is explicit, and Theorem 6’s structural argument appears amenable to weighted masses and quantile pairing. The weighted approximation guarantee is the claim to prove, rather than something Theorem 6 automatically establishes.
That \(1/3\) is also a plausible sharp target. The paper relates the all-obnoxious special case to prior work that rules out a better deterministic strategyproof ratio. That known finite-profile bound is useful evidence about the mass question; under the programme’s novelty standard it does not make the continuous question a collision. A further question is whether \(1/3\) is exactly optimal among mass-group-strategyproof rules, including for nonuniform rational weights.
These are the paper’s named algorithmic-mechanism results, rather than classical P/NP or parameterized-complexity theorems. The mirror covers Theorems 3 and 6 only. I would not extend it to the two-opposite-facility results: their statements depend on the parity of the exact agent count and have ratios that shrink with \(k\). The single-facility mass rule has a cleaner population interpretation.
My weakest point is the incentive model. A zero-mass individual cannot change the output, so ordinary individual strategyproofness in a nonatomic model would be vacuous. The proposed question uses the paper’s group-strategyproofness and tests deviations by positive-mass cohorts; it is meaningful for households or organized residential groups, though it does not preserve every detail of incentives for one named person. That is a real qualification, but the paper’s group-strategyproof anchor gives a credible reason to study precisely this mass-level question.
The strongest case against is a scope argument: this paper gives no computational complexity result for an optimization problem. Theorems 3 and 6 establish properties of a particular mechanism—group strategyproofness and a welfare approximation guarantee. They do not ask how hard it is to compute an optimal intervention, and Mechanism 2 itself only requires a weighted threshold calculation. That makes these weaker anchors for ChoCo’s complexity programme than results whose central object is a hard computational problem.
For Theorem 3, though, the proposed mass version is coherent. A city’s residents can be grouped by block and preference, and a coalition of positive mass has a sensible interpretation. The best version would allow finite support over the full location interval and let a coalition reassign any submeasure. But the weighted rule is still just the paper’s rule with counts replaced by masses. Its incentive argument carries over directly: a type that strictly prefers switching endpoints is already on the corresponding side of the transformed-location threshold, so a coalition of such types cannot move the threshold in its favor. With rational masses, denominator clearing also realizes the society as a finite profile. This is a valid mirror, but it poses no new computational task.
Theorem 6 is the stronger anchor. The proposed weighted approximation question has a plausible setting and keeps the population as the continuous object. For rational masses, replicate each type according to a common denominator: the resulting finite profile has the same mechanism output and the same per-capita welfare ratio. Equivalently, the mass mechanism evaluates the transformed-location majority in \(O(\tau)\) arithmetic operations. Asking for the best mass-group-strategyproof ratio would be a legitimate mechanism-design question, but it would extend the paper’s design and distortion analysis rather than expose a complexity landscape of the sort this programme targets.
That case against has a real limit. The block-and-attitude model passes the high-multiplicity test, and neither identity dependence nor a degenerate limit rules it out. I cannot honestly claim that no worthwhile continuous mirror exists in any scenario. My narrower judgment is that these two anchors are poor fits for ChoCo’s computational-complexity gap: their most natural mass versions are direct weighted restatements of results about an explicit mechanism. That is a reason to prioritize other papers, not a decisive reason to reject the continuous-population question.
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.