| paper | d4-conf-aaai-2018-0910 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: Finding the required feasible rational selection is \(\mathrm{NP}\)-hard for every fixed \(\epsilon\in(0,1)\), already with uniform dyadic masses and symmetric positive payments. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational type masses \(\mu_t>0\) summing to \(1\), symmetric peer eligibility, rational expected payments \(\pi_{tu}\) for eligible pairs, and a rational per-capita budget \(B\), choose rational selected masses \(x_t\in[0,\mu_t]\). Every type with \(x_t>0\) must have an eligible peer type \(u\) with \(x_u>0\); a type may peer with itself when positive mass represents distinct agents of that type. The cost is \(C(x)=\sum_{t\in T}x_t\max_{u\text{ eligible for }t,\;x_u>0}\pi_{tu}\). Maximize \(F(x)=\sum_{t\in T}x_t\) subject to \(C(x)\le B\). What are the exact and approximation complexities of this problem in \(|T|\) and the input bit length?
Types are complete provider profiles, including their reporting and effort characteristics and peer-payment relationships. The population has mass \(\mu_t\) of type \(t\); the decision is how much mass \(x_t\) to select. The objective is selected population mass, and each selected type pays its mass times the greatest expected payment among its selected eligible peer types, within a per-capita budget.
Repeated sensor profiles may preserve pairwise payment patterns only by losing location-sensitive information value; this limits application fidelity, though the formal question uses the cardinality objective in Theorem 1 itself.
fatal: False
Covers Theorem 1's inapproximability result for cardinality utility; leaves Lemmas 1–3, Theorem 2, Corollary 1, PPCGreedyIter, and the experiments unmirrored.
The strongest mirror is the paper’s core peer-constrained information gathering problem, anchored on Theorem 1. Theorem 1 is proved in the paper’s Appendix A.2 by reducing from maximum clique and invoking Håstad’s cited inapproximability result. In full, it says that for every \(\epsilon>0\), it is NP-hard to find a feasible set \(S\) for the paper’s optimization problem with \(f(S)/f(\mathrm{OPT})\ge |V|^{-1+\epsilon}\); this applies to both the expanded-cost formulation and the original problem. The reduction uses \(f(S)=|S|\), makes peer payments low on the target graph’s edges and high on its non-edges, and sets the budget so that feasible selected sets correspond to cliques.
A plausible high-multiplicity setting is a large network of crowd sensors in repeated, standardized environments: many providers share a sensor and reporting profile, measurement distribution, effort cost, and correlation pattern with every other profile. A type is that complete profile, and \(\mu_t\) is its fraction of the provider population. The population might contain millions of providers but only dozens or hundreds of such profiles. Selecting \(x_t\) mass from type \(t\) can be implemented by choosing that fraction of an exchangeable cohort.
Here is the continuous question I would hand to a prover. The input is a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), symmetric peer eligibility and rational expected payments \(\pi_{tu}\) for eligible type pairs, and a rational per-capita budget \(B\). Choose a rational mass vector \(x\) with \(0\le x_t\le\mu_t\). Every type with \(x_t>0\) must have an eligible peer type with positive selected mass; if two distinct agents of the same type can peer, that type may peer with itself. The cost is
\[
C(x)=\sum_{t\in T}x_t\max_{\substack{u\text{ eligible for }t\\x_u>0}}\pi_{tu},
\]
and the objective is to maximize \(F(x)=\sum_{t\in T}x_t\), subject to \(C(x)\le B\). Call this Continuous Peer-Constrained Information Gathering. The objective is the cardinality utility used in Theorem 1’s hardness reduction, expressed as a fraction of the population. More general continuous diminishing-returns information utilities are a natural extension, but are not needed to state this anchor precisely.
I expect this problem to remain hard, probably for continuum-specific reasons (Class C): the selected support among types still determines who can peer with whom and which payment each selected type incurs. But Theorem 1 does not establish that. Its clique reduction relies on indivisible selected nodes and their minimum payments. In the mass model, a type can be selected in an arbitrarily small positive amount, so that budget argument may fail. A new reduction—or an algorithm exploiting fractional selection—is needed. That is the mirror’s weakest point and the central complexity question it raises.
The mirror covers Theorem 1’s hardness claim, not the paper’s PPCGreedy approximation guarantees: those analyze selecting discrete nodes, and their guarantees do not follow simply by replacing node counts with masses. The authors should nevertheless recognize this as their problem: the type graph, peer-selection rule, payment budget, and information objective are all retained, while the action becomes selection of a population fraction. The main follow-up is whether the mass formulation admits a polynomial-time approximation in \(|T|\) and the input bit length, and how its answer changes under restrictions such as bounded peer degree or nearly uniform payments.
The anchor is real: Theorem 1 is a named computational inapproximability result, so the “nothing computational to mirror” objection does not apply. My strongest case against is instead about fit. The paper studies submodular selection of data providers under bilateral incentive constraints. It has no collective preference aggregation, social choice rule, or social outcome. A continuous version could be worthwhile in high-multiplicity optimization or peer-prediction, but it does not fill ChoCo’s stated gap in computational social choice unless the programme deliberately expands that remit.
There is also a fidelity problem in the paper’s motivating sensing application. A provider’s location affects both the coverage utility and its correlations with other providers. If those details are part of the complete type, providers will usually have distinct types and \(\tau\) grows with the network; if they are omitted to create large groups, the type model can lose the geometry that defines the problem. Theorem 1’s reduction sharpens this issue: its hardness is encoded in an arbitrary graph of pairwise payment relationships, with cardinality as the objective. It gives no evidence that the application has large interchangeable cohorts with those same relationships.
The proponent’s stronger version—a population of repeated, standardized sensor profiles with type-level payments and utility \(F(x)=\sum_t x_t\)—is coherent, and it repairs the granularity problem in the original clique reduction. But it changes the application substantially. If providers of one type are genuinely interchangeable at the same sensing locations, additional providers can be redundant under coverage or information utility; if utility remains linear, the model no longer captures that information value. If instead one preserves rich location-specific utility and peer structure, one tends to restore many distinct types. The proposed cost also changes discontinuously at zero mass: an arbitrarily small selected mass can activate a peer and change the maximum payment charged to an entire type. Conditional on the support, choosing masses is linear; the central decision remains which types to activate. That makes the promised connection to continuous optimization technology less evident.
I can’t honestly rule out a useful mirror in every scenario. Repeated, standardized data-collection cohorts could make a high-multiplicity model sensible, and studying its fractional selection problem might yield new results. The negative case is strongest as a claim about programme relevance and fidelity to the paper’s central sensing problem; it is weak as a claim that the mathematical question is not worth asking at all. If ChoCo includes adjacent peer-prediction optimization, the proponent’s anchor survives this case.
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.