| paper | d4-conf-atal-2015-0217 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\Pi_2^{\mathrm P}\)-complete already at \(w=1\); in particular, \(\mathrm{NP}\)-hard even with \(m=3\) and \(w=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 9
statement extracted from the paper’s text layer
Given an agenda \(\Phi\) whose formula-incidence graph has treewidth \(w\), decide whether, for every distribution \(\mu\) over complete consistent judgment types \(J\in\mathcal{J}(\Phi)\), the set \(\{\varphi\in\Phi: \sum_{J\ni\varphi}\mu_J>1/2\}\) is consistent.
Types are complete consistent judgment sets \(J\in\mathcal{J}(\Phi)\), and the society is a distribution \(\mu\) over those types. Majority support for \(\varphi\) is \(\sum_{J\ni\varphi}\mu_J\); the decision question universally quantifies over societies and asks whether each resulting majority judgment is consistent.
The mirror covers universal majority-agenda safety under the restrictions in Propositions 3, 6, and 9. It leaves the paper’s other parameterized results unanchored, including the agenda-size SAT-call bounds and the counterexample-size result.
The strongest mirror is continuous majority-agenda safety. Consider a fixed agenda \(\Phi\), and let \(\mathcal J(\Phi)\) be its complete, consistent judgment sets. A type is one such judgment set: agents of that type agree on every issue in the agenda. A society is a distribution \(\mu\) over these types, with \(\mu_J\) the fraction of the population of type \(J\). For each proposition \(\varphi\), its majority support is \(p_\mu(\varphi)=\sum_{J\ni\varphi}\mu_J\); the collective judgment is \(M_\mu=\{\varphi:p_\mu(\varphi)>1/2\}\). The continuous problem is: given \(\Phi\), does every distribution \(\mu\) over \(\mathcal J(\Phi)\) make \(M_\mu\) consistent? A “no” solution is a population distribution whose majority judgment is inconsistent; a “yes” solution means no such distribution exists.
This is a natural high-multiplicity regime for a large public consultation or electorate deciding a fixed set of logically related policy propositions. With many participants, a type is a complete coherent ballot, and many people may share one. The population can have \(n\) in the millions and support size \(\tau\) far below \(n\), even though the full set of possible types may be large. The question ranges over every possible population mix because the paper’s agenda-safety problem ranges over every profile. The agenda and its structural parameter are the input; the population distribution is universally quantified, rather than fixed to one observed society.
That choice preserves the problem the authors study. Fixing one \(\mu\) would ask whether that particular society’s outcome is consistent, a different question. Here the continuum changes the population representation: individuals become type masses, while each person’s judgment remains a discrete, integral set of propositions.
The bridge to the paper’s results is exact. A finite profile induces a rational distribution by assigning each type its fraction of voters, so any finite counterexample remains a continuous one. Conversely, if a real-valued distribution produces an inconsistent majority judgment, the inconsistent subset has only finitely many strict majority inequalities. Approximate its masses by rationals closely enough to preserve all those inequalities. A common denominator then turns that rational distribution into a finite profile with the same inconsistency. Thus continuous majority-agenda safety holds exactly when the paper’s discrete agenda is safe. That equivalence is a result of the mirror model, not a claim that the paper already studies continuous populations.
My lead anchor is Proposition 9. It states that Maj-AS(f-tw*), parameterized by the formula-incidence treewidth of the agenda, is para-\(\Pi_2^P\)-complete. In particular, the paper observes that the problem remains \(\Pi_2^P\)-hard when that treewidth is \(1\). The proposition is proved in this paper; its hardness half uses the reduction of Endriss, Grandi, and Porello cited as reference [20], while membership follows from the \(\Pi_2^P\) upper bound. The continuous question to hand a prover is the same universal safety question above, restricted to agendas whose formula-incidence graph has parameter \(w\). The predicted outcome is hardness transfers: the equivalence between rational population mixtures and finite profiles carries the lower bound over. This is my strongest anchor because it says that even extremely tree-like incidence between agenda formulas and variables need not make continuous-population safety tractable.
A second anchor is Proposition 3, proved in this paper. It establishes that Maj-AS(degree + formula size) is para-\(\Pi_2^P\)-hard even when every formula in the pre-agenda is in Horn \(\cap\) 2CNF. Here the parameter is the sum of maximum formula size and agenda degree, where degree counts variable occurrences across pre-agenda formulas. Its continuous mirror is again universal majority safety, now restricted to agendas satisfying those syntactic bounds and restrictions. I expect hardness to transfer here too. The result is useful evidence that the mirror’s hard cases are not an artifact of complicated individual formulas: interacting issues can preserve the higher-level complexity even under these restrictions.
A useful positive boundary comes from Proposition 6, also proved here. It states that Maj-AS(f-tw) is fixed-parameter tractable when parameterized by the formula primal treewidth—the graph connects variables that occur together in an agenda formula. The continuous version asks universal majority safety on agendas parameterized by that treewidth; its expected outcome is tractable. The paper obtains this through a monadic second-order encoding and Courcelle’s theorem. Together, Propositions 9 and 6 give a concrete boundary: one natural form of tree structure permits an FPT algorithm, while another remains hard even at treewidth \(1\).
These anchors cover agenda safety for the majority rule under selected structural and syntactic restrictions. They do not continuize the propositions, the outcomes, or the axioms: only the population becomes a distribution over discrete judgment types. Further questions include whether safety for a *given* rational distribution with support \(\tau\) is tractable under parameters such as \(\tau\) or agenda treewidth, and how much mass must be transferred between judgment types to make a currently consistent majority outcome inconsistent. Those are new, society-specific questions rather than results established by these anchors.
The weakest point is also the model’s clearest limitation: agenda safety is already a worst-case question over profiles, so the continuous mirror is extensionally identical to the discrete one. The mirror therefore does not, by itself, reveal a new complexity landscape or exploit continuous-optimization machinery; its complexity results carry over because finite profiles sit inside the continuum and rational mixtures are dense. I still regard the mirror as credible: the authors’ central question is whether majority aggregation is safe under every admissible composition of coherent judgments, and a population distribution is a direct, natural way to express those compositions when agents occur in large repeated types. The continuous version gives that question a genuine population-level formulation, while being candid that the principal result here is an exact correspondence, not a tractability gain.
The strongest case against is that the three anchors keep the agenda as the input and quantify over every possible society. For Proposition 9 and Proposition 3, the continuous model supplies no population distribution: it asks whether *any* distribution over complete, consistent judgment types can produce an inconsistent majority. If one does, the inconsistency is witnessed by finitely many strict inequalities \(p_\mu(\varphi)>1/2\). Those inequalities survive a sufficiently close rational approximation, and a common denominator turns that approximation into a finite profile. Conversely, each finite profile gives a rational distribution. So these propositions’ complexity results carry over exactly; the mirror adds no population parameter or mass-optimization problem.
Proposition 6 carries over by the same bridge. Its fixed-parameter algorithm decides continuous safety because it decides the identical agenda predicate. That is a legitimate result, but it does not use continuous-optimization machinery or analyze a supplied high-multiplicity society.
The better versions of the mirrors change the question. Given a particular distribution with support \(\tau\), one can tally the weighted judgments and check whether their majority set is consistent. That is a population-input problem, but it drops the universal safety question, so Propositions 9, 3, and 6 no longer anchor it. A question about the least mass needed to make the majority inconsistent would also need a baseline society and a cost model absent from the paper. Restricting safety to distributions with support at most \(\tau\) is another possible problem, but it asks safety only over a restricted set of profiles and needs its own justification and results.
This is a real argument against spending ChoCo effort on these mirrors: they may produce no new complexity landscape beyond a correspondence theorem and the unchanged transfer of the paper’s classifications. It does not, however, defeat the proponent’s anchors under the programme’s stated rules. The population regime is sensible, and the exact discrete–continuous identity is expressly allowed to count as a result. I cannot honestly make the universal negative case that no worthwhile mirror exists; Proposition 6 in particular survives as a well-posed continuous mirror with an FPT answer.
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.