d4-conf-wine-2011-0028

Theorem 6.3 proves a stability statement about aggregation mechanisms on finite voter profiles; it gives no algorithm, complexity bound, or hardness result. The proposed population version could be a coherent extension, but it cannot supply the missing computational anchor.

The objection that survived

The proposed uniform measure on the simplex is not derived from the paper’s i.i.d. profile model; the proponent acknowledges this change but does not otherwise motivate that prior.

What the mirror covers

The proposed extension targets Theorem 6.3’s XOR-agenda stability claim; it leaves the conjunction, general truth-functional, and affine-agenda results unmodeled.

Open questions for a prover

The case FOR (proponent)

The strongest honest positive case is a candidate continuization of the paper’s robustness question. It is not a valid complexity anchor under your stated rule: the paper has no numbered theorem establishing that a problem is in P, NP-hard, FPT, or similar. Its closest named result is Theorem 6.3, proved here: for the agenda with \(m-1\) premises and one conclusion equal to their XOR, where \(m\ge3\), any aggregation mechanism \(F\) over \(n\) voters that is \(\varepsilon\)-independent and \(\varepsilon\)-consistent, for \(\varepsilon<1/6\), is within distance \(m(2m+3)\varepsilon\) of a mechanism that is exactly independent and consistent. This is a quantitative rigidity theorem, not a computational-complexity result.

Here is a precise continuous question suggested by that theorem. Let the agenda be
\[ \mathcal X_m=\{x\in\{0,1\}^m:x_m=x_1\oplus\cdots\oplus x_{m-1}\}. \]
A type is a complete consistent judgment vector \(x\in\mathcal X_m\). A society is a distribution \(\mu\in\Delta(\mathcal X_m)\), with \(\mu_x\) the fraction of the population holding type \(x\). Consider a rule \(F:\Delta(\mathcal X_m)\to\{0,1\}^m\). For issue \(j\), write \(p_j(\mu)=\sum_{x:x_j=1}\mu_x\).

Fix the symmetric uniform measure \(\lambda\) on this simplex, and define inconsistency as \(\Pr_{\mu\sim\lambda}[F(\mu)\notin\mathcal X_m]\). Define issue \(j\)’s dependency index by drawing \(\mu,\nu\) independently from the conditional distribution on the fiber with a given \(p_j\), then averaging \(\Pr[F_j(\mu)\ne F_j(\nu)]\) over \(p_j\). Let \(d_\lambda(F,G)=\Pr_{\mu\sim\lambda}[F(\mu)\ne G(\mu)]\).

The named problem is XOR Population Robust Aggregation: given \(m\), \(\eta<1/6\), and a measurable rule \(F\), if its inconsistency and every dependency index are at most \(\eta\), must there be a rule \(G\) that is consistent on every society and whose issue-\(j\) output depends only on \(p_j(\mu)\), with
\[ d_\lambda(F,G)<m(2m+3)\eta? \]
A solution would prove this bound for all such \(F\), or give a counterexample. This is a theorem-level question about the underlying aggregation rule, not about an encoding.

The regime would be large, repeated panels deciding the same linked set of propositions: many participants, but at most \(2^{m-1}\) distinct consistent judgment types. If the collective rule responds only to type proportions, then issue-wise independence naturally means that each decision uses only the fraction supporting that issue. The XOR agenda and the paper’s consistency-versus-independence tradeoff both survive in the mirror. I would expect a rigidity theorem to be plausible, though the paper does not establish this continuous claim.

The soft spot is substantial. Theorem 6.3 concerns arbitrary functions of individual voter profiles, including identity-sensitive rules; the proposed mirror restricts attention to rules determined by population shares. And the paper’s uniform i.i.d. profile assumption does not induce the uniform measure on the simplex used here. Those are genuine model changes. A referee might accept the question as a natural anonymous, high-multiplicity extension of the authors’ subject, but could reasonably reject it as a mirror of Theorem 6.3 itself. So this is the best positive research lead I see, but it does not clear the programme’s computational-anchor gate.

The case AGAINST (opponent, writing after the proponent)

I don’t see a computational-complexity result in this paper to mirror. Theorem 6.3 is the closest anchor, but it is a stability theorem: under the uniform distribution on finite voter profiles, small inconsistency and dependence indices imply closeness to an exactly consistent and independent mechanism. The paper’s property-testing discussion explains how to test those indices; it does not give a complexity classification or an algorithmic result for a problem whose input is a society. That misses the ChoCo programme’s computational gate.

The proposed XOR mirror makes the shift clear. It replaces a mechanism on labeled profiles, \(F:\mathcal X_m^n\to\{0,1\}^m\), with a rule on population distributions, \(F:\Delta(\mathcal X_m)\to\{0,1\}^m\). The latter is sensible for repeated panels, but a distribution over types forgets which voter held which type. The paper quantifies over mechanisms that can use those voter identities. Requiring the continuous rule to depend only on type masses is a legitimate high-multiplicity restriction, but then the question is a new stability theorem for anonymous rules, not a continuization of the theorem as stated.

There is also no canonical continuous probability model inherited from the paper. Under its impartial-culture assumption, the empirical type distribution of an increasingly large electorate concentrates at the uniform distribution on \(\mathcal X_m\). That limit cannot carry over the paper’s profile-wide error measure or its tests along fibers of fixed issue support. Choosing a uniform or Dirichlet distribution over the simplex avoids that collapse, but adds a population prior that the paper does not supply. One could study the resulting theorem; its validity would concern that newly chosen model.

The strongest repair would be to define an oracle-testing problem: query an anonymous aggregation rule at rational population distributions sampled from a specified nondegenerate prior, and test consistency and issue-wise dependence. That could be a coherent research question. But its computational content depends on added choices about the oracle, precision, and sampling access. It tests a rule over a space of societies; it does not classify the complexity of a computational task performed on a given society. The paper’s theorem supplies a motivation for that adjacent question, not a computational anchor for a continuous mirror.

So the negative case is strongest at the programme boundary, not at the modelling boundary. A continuous, anonymous version is plausible and could be worth studying as a separate property-testing result. I cannot honestly rule out every worthwhile formulation; I can say that neither Theorem 6.3 nor its property-testing connection currently yields the kind of population-input complexity question ChoCo is set up to chart.

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.