| paper | d4-conf-ecai-2024-0114 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given \(d>0\) and a rational finite-support probability measure \(\mu=\sum_{j=1}^{\tau}\mu_j\delta_{x_j}\) over ideal locations on \(\mathbb R\), a deterministic mechanism \(F\) chooses a range \((a,b)\) with \(b-a\le d\). Let \(SC_\mu(a,b)=\int c_d(x;a,b)\,d\mu(x)\), and let \(OPT_\mu\) be its minimum over feasible ranges. Call \(F\) mass-SGSP if there are no submeasure \(\eta\le\mu\) and replacement measure \(\nu\) with \(\nu(\mathbb R)=\eta(\mathbb R)\) such that, under \(F(\mu-\eta+\nu)\), the coalition is weakly better off \(\eta\)-almost everywhere and strictly better off on positive \(\eta\)-mass. Prove or refute that every deterministic mass-SGSP \(F\) has unbounded worst-case ratio \(SC_\mu(F(\mu))/OPT_\mu\) over rational finite-support societies.
A rational finite-support distribution over residents’ ideal pickup locations; each unit of mass has the paper’s location-dependent cost, and the planner chooses an interval of length at most \(d\). A coalition removes a submeasure of residents and replaces it with reports of equal mass. The mechanism must be mass-SGSP, and the objective is per-capita social cost.
Theorem 3 establishes an incentive-constrained approximation frontier, not a runtime bound; the ChoCo connection therefore depends on treating the explicit mechanism and its approximation guarantee as computational results.
fatal: False
The anchors cover Theorem 3’s deterministic social-cost lower bound and Theorem 1’s optimal GSP mechanism. They leave Theorem 2’s SGSP approximation guarantee, the maximum-cost results, and the randomized lower bounds unaddressed.
This paper has no named NP-hardness, polynomial-time complexity, or parameterized-complexity theorem. Its closest anchors are named mechanism-design results about optimality and approximation. I would still make a positive mirror case for those, while being clear that it is a mirror of mechanism design and approximation—not a new complexity-class result.
The regime I find plausible is a large school district or municipality choosing a shuttle pickup corridor for a fixed facility. Many households live in the same apartment complexes or pickup zones, so \(n\) residents can be represented by \(\tau\) location types, with \(n\gg\tau\). A type is an ideal pickup location \(x\); its mass is the fraction of residents at that location. The planner chooses an interval of length at most \(d\), and each resident incurs the paper’s cost \(c_d(x;a,b)\). The continuous society is a finite-support rational distribution \(\mu=\sum_{j=1}^{\tau}\mu_j\delta_{x_j}\). Replacing the paper’s total social cost by the per-capita cost \(SC_\mu(a,b)=\sum_j\mu_jc_d(x_j;a,b)\) does not change approximation ratios.
My lead anchor is Theorem 3, proved in this paper: no deterministic strong group strategyproof mechanism has social-cost approximation ratio below \((n+2)/4\). Its continuous mirror is the Mass-SGSP Social-Cost Approximation Frontier. A mechanism \(F\) maps each rational finite-support society \(\mu\) to an interval of length at most \(d\). For a coalition, let \(\eta\le\mu\) be the mass of its members and let \(\nu\) be their replacement reports, with \(\nu(\mathbb R)=\eta(\mathbb R)\); the reported society becomes \(\mu'=\mu-\eta+\nu\). Require that no such deviation makes coalition members weakly better off almost everywhere and strictly better off on a positive mass. The question is whether every such deterministic \(F\) has unbounded worst-case ratio \(SC_\mu(F(\mu))/OPT_\mu\), where \(OPT_\mu\) is the minimum per-capita social cost.
The expected answer is yes, by transfer. For each even \(n\), restrict \(F\) to empirical societies \(\mu=\frac1n\sum_{i=1}^n\delta_{x_i}\). Mass-SGSP implies SGSP on these finite profiles, so Theorem 3 gives a ratio of at least \((n+2)/4\) on that subdomain. Since this holds for every even \(n\), no uniform finite approximation ratio is possible over all rational societies. This is a Class B-style transfer of an approximation impossibility, though it is not an NP-hardness result.
A second, constructive anchor is Theorem 1, proved in this paper: Mechanism 1 is group strategyproof and optimal for social cost. Its continuous question is the Mass-GSP Optimal Accessibility Mechanism: given \(d\) and \(\mu\), return an optimal interval using one deterministic mechanism that is group strategyproof against mass coalitions. The natural candidate replaces the paper’s counts by masses: set \(D_\mu=\{y:\mu((-\infty,y])\ge\mu([y+d,\infty))\}\); return \((0,d)\) if \(\inf D_\mu\ge0\), \((-d,0)\) if \(\inf D_\mu\le-d\), and \((\inf D_\mu,\inf D_\mu+d)\) otherwise. I expect this weighted version to be tractable: with rational support locations and masses, sort the \(\tau\) locations and find the threshold by scanning the support breakpoints. The substantive question is whether the paper’s optimality and GSP arguments extend when masses, and coalitions, can be fractional.
These mirrors cover the paper’s deterministic social-cost results. They do not claim to cover its maximum-cost or randomized results. The Theorem 3 mirror is the lead because it gives the strongest lower-bound question; Theorem 1 is the clearest constructive analogue.
My weakest point is the strategic interpretation. The paper has individual residents reporting locations, while the mirror permits a coalition to control a divisible mass of residents. That is a meaningful high-multiplicity version of the same incentives, but it needs authors and referees to accept mass coalitions as the right co-modification. Also, the paper’s “location” reports may be verifiable in a real shuttle-planning setting; the mirror is more convincing where residents report private ideal pickup locations than where they simply report their addresses.
The strongest case against spending ChoCo effort on this paper is that its named results answer a different kind of question. Theorem 3 is an incentive and welfare approximation lower bound; Theorem 1 is an optimality and group strategyproofness result. Neither studies runtime, computational hardness, or an algorithmic approximation guarantee. A continuous-population version would develop mechanism design for weighted societies, a legitimate neighboring topic, but it would not fill the programme’s stated gap in computational complexity.
That scope objection does not defeat the Theorem 3 mirror itself. On rational finite-support societies, a mass mechanism can be restricted to empirical distributions and pulled back to finite profiles. With a precise definition of coalition deviations, mass-SGSP implies SGSP on those profiles, so the paper’s lower bound supplies a meaningful continuous question. The fact that this restriction may settle part of the question is not a reason to dismiss it.
Theorem 1 also has a credible mirror: ask whether the optimal group-strategyproof rule extends to weighted societies. Its mechanism and proof are built around locations and counts, which have natural mass counterparts. One modeling change is needed: unilateral deviations by measure-zero individuals do not affect the society, so preserving the paper’s strategic content calls for mass coalitions or another explicit coalition model. The paper’s group-strategyproofness gives a plausible basis for that change; it is not a decisive objection.
So the negative case is weak against the broad claim that neither anchor has a worthwhile continuous mirror. Both proposed questions are well-posed, and I cannot honestly rule out a scenario their authors would recognize. The case is stronger only under a strict reading of ChoCo’s remit: these are continuous mechanism-design questions, not computational-complexity questions.
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.