| paper | d4-conf-ecai-2016-0327 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: Computing an optimal consensus is \(\mathrm{NP}\)-hard, even for \(\tau=2\), equal masses, and clauses of length at most two. The threshold decision problem is \(\mathrm{NP}\)-complete. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
Given a finite set of consistent clause sets \(\Phi_t\), each with positive binary-rational mass \(\mu_t\) and \(\sum_t \mu_t=1\), compute a set of clauses \(\Gamma\subseteq\bigcup_t\Phi_t\) maximizing \(\sum_{\delta\in\Gamma}\sum_{t:\delta\in\Phi_t}\mu_t\), subject to \(\Gamma\cup\Phi_t\) being satisfiable for every type \(t\).
The society is a distribution over types \(t\), where each type is a complete, consistent clause set \(\Phi_t\) and carries mass \(\mu_t\). The decision variable is an integral set of clauses \(\Gamma\); its objective is the total population mass supporting the selected clause claims, and every positive-mass type must remain compatible with it.
The population weights are not part of Proposition 2's max# objective: the mirror rewards source-weighted clause claims instead of distinct clauses, so its connection depends on treating the weighted variant as the authors' problem.
fatal: False
It extends the Boolean max# extraction anchored by Proposition 2 by weighting clause claims with population mass; it leaves the unweighted objective, the S5 results, and the reported experiments without population weights.
The strongest mirror I see is a population-weighted Boolean max# consensus. It is a credible extension of the paper’s problem, though not an exact restatement of its objective.
The population would be a large consultation or standards process in which agents submit consistent sets of logical constraints over a shared set of policy choices. For example, many agencies might use one of a modest number of standardized constraint templates. A type \(t\) is the agent’s complete constraint set \(\Phi_t\); \(\mu_t\) is the fraction of the population with that exact set. The regime is \(N\) agents with \(\tau\) distinct profiles, where \(N\) is very large and \(\tau\) is much smaller.
My lead question is: given finitely many consistent clause sets \(\Phi_t\) and positive binary-rational masses \(\mu_t\) summing to \(1\), find a set of clauses \(\Gamma\) that maximizes
\[
\sum_{\delta\in\Gamma}\sum_{t:\delta\in\Phi_t}\mu_t
\]
subject to \(\Gamma\subseteq\bigcup_t\Phi_t\) and \(\Gamma\cup\Phi_t\) being satisfiable for every type \(t\). In words, choose a fragment of the submitted information that conflicts with no represented type, maximizing the population share whose clause claims it includes. Any maximizing \(\Gamma\) is a solution. Each positive-mass type still matters to feasibility, just as each source does in the paper; mass determines how much its claims count in the objective.
The anchor is Proposition 2, proved in this paper using Algorithm 1, building on a transformation method cited from earlier work. It says that for a profile \(S=[\Phi_1,\ldots,\Phi_n]\) with \(m\) clauses in total, the transformational approach computes one max# consensus with a single call to Partial Max-SAT: the resulting instance has \(mn\) hard clauses and \(m\) soft clauses. The consensus being computed is a largest-cardinality subset of the pooled clauses that is satisfiable together with every source. This is a named computational result, though it is not a numbered P or hardness classification. The paper discusses complexity elsewhere in prose, but I would not present that discussion as a numbered hardness anchor.
The population objective is a co-modification: the paper counts distinct clauses, whereas this mirror counts the mass of agents asserting each selected clause. That choice gives mass a clear role and fits the paper’s stated interest in weighted preferences and weighted Partial Max-SAT. For a finite population with type \(t\) occurring \(n_t\) times out of \(N\), the objective is the average number of retained clause claims per agent. A weighted version of the paper’s selector construction appears to give a natural route to solving the problem; the mirror’s question is the consensus optimization itself, not that encoding.
I expect hardness to transfer, rather than the continuous formulation alone making the problem tractable: finite rational populations are included, and the clause-selection and satisfiability constraints remain. The paper’s max# result supplies an algorithmic starting point, not a lower-bound proof for this weighted variant, so establishing the precise complexity is a further question. Other natural questions are whether the problem admits useful parameterized algorithms in the support size \(\tau\), and whether the paper’s S5 translation can be adapted while preserving the population weights.
The weakest point is that the paper’s authors might accept this as a weighted consensus extension, but not as the continuous form of their exact max# objective. Also, the decision variable remains a set of whole clauses: making the population continuous does not make consensus selection fractional, and the formulation does not by itself expose an LP or convex-optimization gain. The case rests on the authors’ recognizable consensus problem and their interest in weighted variants, rather than on a claim that this mirror inherits a new continuous-optimization tractability result.
Proposition 2 is a real computational anchor, so I would not argue that the paper has no result to mirror. The strongest case against it is narrower: the proposition gives a transformation to Partial Max-SAT, not a complexity classification or a continuous-optimization method.
For the paper’s exact max# objective, changing the number of agents of each type to masses does not make the objective population-dependent. The candidate consensus is still a set of clauses, and every positive-mass type must remain compatible with it. If the objective remains cardinality, the masses do no work; only the support matters. That makes a literal continuous version of max# consensus a poor population mirror.
The proponent’s weighted objective repairs this: reward a clause according to the mass of agents asserting it. But this is a co-modification of the objective, producing weighted consensus rather than max# consensus. The paper itself identifies weighted Partial Max-SAT as a natural way to handle weighted preferences. Replacing selector weights by rational population masses appears to reuse the same transformation and SAT bottleneck. The same is true for an S5 version after the paper’s translation. Normalizing each agent’s contribution to account for different numbers of clauses would still amount to choosing weights for the soft selectors.
That is a substantial novelty objection, but it does not establish that the question is unworthy. A large consultation with repeated, standardized logical profiles is a credible high-multiplicity setting, and its distribution gives a sensible interpretation to clause weights. The paper’s weighted-variant discussion is not an existing continuous treatment, and a compact algorithm or complexity analysis in support size and mass bit length could still be useful. So the honest anti-case is weak at its central point: it can show that the proposed mirror is close to weighted Max-SAT, but it cannot rule out a worthwhile population-based computational question.
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.