d4-conf-atal-2010-0302

Theorem 17(iv) is a genuine \(\Pi_2^p\)-completeness result, but the proposed problem quantifies over every rational \(\mu\), so the decision input remains only \(\Phi\). Fixing \(\mu\) while retaining the proposed rule class leaves safety mass-insensitive; asking about a supplied society under weighted majority is a plausible adjacent question, but changes the theorem’s all-profiles, all-rules agenda-safety question. No population-input analogue of a computational result raised by the proponent survives.

The objection that survived

Universal quantification over \(\mu\) leaves the society out of the computational input, and the proposed class remains mass-insensitive even if \(\mu\) is fixed.

What the mirror covers

The proponent targets Theorem 17(iv) and uses Theorem 9 as its structural basis; the case does not mirror the majority-rule result or the other aggregator classes.

Open questions for a prover

The case FOR (proponent)

The strongest anchor is Theorem 17(iv), proved in this paper: given an agenda \(\Phi\), deciding whether it is safe for the class \(F_\Phi[\mathrm{WR},\mathrm{A},\mathrm{I}]\) is \(\Pi_2^p\)-complete. These are aggregation procedures satisfying weak rationality—complete, complement-free, and non-null outputs—anonymity, and independence. The paper’s Theorem 9, also proved here, gives the structural criterion behind that complexity result: an agenda is safe for this class exactly when it has the syntactic simplified median property (SSMP).

Here is the continuous-population problem I would put forward. In a large public consultation or multiagent system, participants judge the same finite set of linked propositions. A type is a complete, logically consistent judgment set \(J\in\mathcal J(\Phi)\). If only judgments matter to aggregation, participants with the same \(J\) are indistinguishable. A society is a finitely supported distribution \(\mu\) over these types, with rational masses \(\mu_J\) summing to \(1\). For each proposition \(\varphi\), its support is
\[ p_\mu(\varphi)=\sum_{J:\,\varphi\in J}\mu_J. \]
When the population is very large but has relatively few distinct response patterns, these shares are the natural input: they express, for example, “\(23\%\) accept \(\varphi\)” directly.

Call a population aggregation rule \(F\) weakly rational, anonymous, and independent if its collective judgment set \(F(\mu)\subseteq\Phi\) is complete and complement-free, the rule does not always output a contradiction, and each proposition’s collective acceptance depends only on its population share: \(\varphi\in F(\mu)\) exactly when \(h_\varphi(p_\mu(\varphi))=1\), for some decision function \(h_\varphi\). The functions must give complementary outcomes for \(\varphi\) and its complement so the collective set is complete and complement-free. Since this class does not require neutrality, it can resolve an exact half-and-half split differently for \(\varphi\) and \(\neg\varphi\).

The resulting problem, Continuous Independent Agenda Safety, is: given \(\Phi\), is \(F(\mu)\) logically consistent for every rational population distribution \(\mu\) over \(\mathcal J(\Phi)\) and every such rule \(F\)? A solution is a yes/no answer; a no-instance has an inconsistent collective judgment set. There is no optimization objective: the rule chooses an acceptance bit for each proposition, and the computational question is whether inconsistency can ever result.

I expect the paper’s SSMP characterization to carry over, and with it the \(\Pi_2^p\)-completeness, in the agenda’s formula encoding. The reason is visible in Theorem 9’s proof: if SSMP holds, weak rationality and independence rule out an inconsistent outcome; if it fails, the agenda contains an entailment conflict that a constant, independent rule can select regardless of the population masses. Thus the hardness rests on the agenda’s logical structure, not on the number of agents. This is a Class B-style case: the relevant combinatorics survive the population relaxation. Rational masses also map back to finite multiplicities by clearing denominators.

I think the authors would recognize this as a continuous version of their safety question: their definition asks for a guarantee across profiles, and this version replaces profiles by distributions over judgment types while preserving the rule axioms and the consistency predicate. It covers only Theorem 17(iv), not the paper’s other aggregator classes or its broader future questions.

The weakest point is that the society distribution is universally quantified rather than supplied as a fixed input. The problem therefore remains an agenda-safety problem; its running time is not an algorithmic bound in the support size \(\tau\) of a particular realized society. That makes this a faithful but computationally narrow mirror. Requiring a fixed-\(\mu\) problem would change the paper’s quantifier structure, and this theorem does not establish the complexity of that changed problem.

The case AGAINST (opponent, writing after the proponent)

The proposed mirror fails at the point where it should make the population continuous. Theorem 17(iv) asks a question about the agenda \(\Phi\): is every procedure in \(F_\Phi[\mathrm{WR},\mathrm{A},\mathrm{I}]\) safe on every profile? In the proposal, the population distribution is also universally quantified. It is never a fixed input, so the decision problem still takes only \(\Phi\) as input. And a rational distribution over complete judgment sets can be written as a finite profile by clearing denominators. The proposal changes the language for ranging over profiles, but does not make the society an object the algorithm receives or analyzes.

Fixing a distribution \(\mu\) does not rescue the proposed class of procedures. It still includes population-independent constant rules. Where the SSMP failure gives an inconsistent weakly rational outcome, such a rule produces it for every \(\mu\); where the agenda is safe by Theorem 9, fixing \(\mu\) does not create a new safety question for that class. Thus the actual anchor is insensitive to the society’s masses.

The strongest repair would fix \(\mu\) and ask whether weighted majority produces a consistent collective judgment. That is a natural population question, and the paper itself points toward checking whether a particular profile generates an inconsistent outcome. But it is no longer Theorem 17(iv)’s agenda-safety problem: it selects one aggregator and asks about one society. I cannot dismiss it as out of scope or as already solved; rational masses give a genuine high-multiplicity formulation, and the paper’s future-work discussion makes the connection especially direct. Theorem 17(i) and Theorem 6 offer a better anchor for this repair, but their results concern safety across profiles, not consistency for a supplied society.

So the negative case defeats the proponent’s stated mirror: its population is quantified away, and even fixing that population leaves their broad rule class insensitive to it. But the universal claim that no worthwhile continuous mirror exists is not persuasive. The fixed-distribution, specified-aggregator question survives as a plausible high-multiplicity version of the paper’s own suggested future work.

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.