| paper | d4-conf-ecai-2024-0426 |
| 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: \(\Delta_2^p\)-complete under polynomial-time many-one reductions; in particular, \(\mathrm{NP}\)-hard. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 6
statement extracted from the paper’s text layer
Given a shared proposition set \(V\), a finite support of types \(\{(F_t,\mu_t):t\in[\tau]\}\) with \(\mu_t>0\), binary-rational masses summing to \(1\), and a classical query \(Q\), consider policies \(I:V\to\{0,1\}\) satisfying every supported formula \(F_t\) to a finite degree. For each degree \(k\), let \(w_k(I)=\sum_{t:\deg(I,F_t)=k}\mu_t\). Does every policy that lexicographically maximizes \((w_1(I),\ldots,w_K(I))\), where \(K=\max_t\operatorname{opt}(F_t)\), satisfy \(Q\)? If no admissible policy exists, use the paper’s vacuous-entailment convention.
A weighted population version of lexicographic preferred-model entailment: each type carries a complete QCCL preference formula \(F_t\) and mass \(\mu_t\); policies remain Boolean interpretations, and the objective lexicographically maximizes population mass at each finite satisfaction degree.
Any type with positive mass can exclude policies that fail its formula, so a tiny group retains veto power and the feasible set can change discontinuously as its mass approaches zero.
fatal: False
The mirror covers lexicographic preferred-model entailment from Proposition 6, including its vacuous-entailment convention. It leaves the paper’s other semantics, preferred-model computation results, and empirical comparisons outside its scope.
The best positive mirror is Continuous Lex-Choice Entailment: a population version of the paper’s lexicographic preferred-model entailment problem.
My numbered anchor is Proposition 6 (proved in this paper): for a QCCL theory \(T\) and a classical formula \(Q\), Algorithm 1 returns YES exactly when every lexicographically preferred model of \(T\) satisfies \(Q\). The algorithm uses iterative MaxSAT optimization to preserve the lexicographic satisfaction levels, then checks with SAT whether an optimal model can falsify \(Q\). The paper does not give a numbered result asserting a complexity classification; it reports that lexicographic entailment is \(\Delta_2^p\)-complete, citing [9]. That classification is useful context, but it is not my anchor.
Here is the mirror. The instance consists of a common set \(V\) of policy propositions; a finite support \(\{(F_t,\mu_t):t\in[\tau]\}\), where each \(F_t\) is a QCCL formula over \(V\), each \(\mu_t>0\) is a binary rational, and \(\sum_t\mu_t=1\); and a classical query \(Q\). A type is a complete QCCL preference statement about the shared policy choices. Its mass \(\mu_t\) is the fraction of stakeholders with that type. The regime is a large municipality or organization with many stakeholders but a much smaller number of distinct preference types: for instance, thousands or millions of people represented by hundreds or thousands of formulas.
A policy is an interpretation \(I:V\to\{0,1\}\). Require \(I\) to satisfy every supported formula to a finite degree. Let \(K=\max_t\operatorname{opt}(F_t)\), and for each degree \(k\), set
\[
w_k(I)=\sum_{t:\deg(I,F_t)=k}\mu_t.
\]
Among admissible policies, lexicographically maximize \((w_1(I),\ldots,w_K(I))\): first maximize the population share whose preference is met at degree \(1\), then the share met at degree \(2\), and so on. The question is whether every maximizing policy satisfies \(Q\). The solution is YES or NO, with a falsifying maximizing policy as a witness for NO. If no policy satisfies every supported formula to a finite degree, use the paper’s vacuous-entailment convention.
This preserves the paper’s central object: preferred interpretations of a shared choice-logic theory. It replaces the number of formulas satisfied at each degree with the mass of the population represented by those formulas. With equal masses \(\mu_t=1/\tau\), each \(w_k(I)\) is the paper’s count at level \(k\), divided by \(\tau\), so the original problem embeds exactly. Unequal masses make this a genuine population-weighted extension, while policy assignments remain integral for every interpretation.
I expect hardness to transfer. The paper’s cited \(\Delta_2^p\)-completeness result for finite lexicographic entailment embeds through equal masses. The weighted problem also has a plausible \(\Delta_2^p\) upper bound: there are polynomially many degree levels, and with binary rational masses the lexicographic objective values have polynomial-size exact representations. Each level can be optimized with polynomially many NP-oracle queries, followed by a query for an optimal policy that falsifies \(Q\). The mirror is therefore a Class B candidate, not an argument that population continuity makes this entailment tractable. Further questions include whether weighted lexicographic entailment is complete under the same reductions, and whether useful tractable cases arise when the support or formula structure is restricted.
The scope is just Proposition 6’s lexicographic entailment result. This does not continuize the policy outcomes: a fractional assignment to propositions is not the object. The continuous quantity is the society’s distribution over preference types.
The weak point is that the paper treats a theory as a set of formulas, while this mirror treats formula types as population groups whose masses affect the objective. The original semantics count each formula equally; the mirror gives each type weight according to its prevalence. Authors working on preference theories could reasonably recognize this as a weighted, population-level extension of their problem, especially since equal masses recover their semantics. They might instead regard formulas as abstract constraints rather than stakeholder types. That is the main acceptance risk, and it is why I would present this as a focused, plausible mirror rather than claim that the paper already studies populations.
The only anchor is Proposition 6. The strongest objection is that the proposed population objective does not follow naturally from the problem that proposition solves. In the paper, \(T\) is a set of formulas in one theory. Its formulas are jointly required to have finite satisfaction degree; they are not explicitly voters whose influence should scale with prevalence. The proposition proves an algorithm correct for that finite entailment problem.
That distinction exposes a sharp problem in the proposed mirror. A policy must satisfy every supported formula to a finite degree, so even a type of mass \(\varepsilon>0\) can rule out policies that fail its formula. Its mass affects the lexicographic scores only among policies that survive this unanimity filter. The model therefore treats a tiny group as having a veto, while a type of mass zero has no effect at all. This discontinuity is especially awkward for a continuous population, where the intended quantity is supposed to be the share of society.
There are repairs, but they make the mirror less direct. One could put unsatisfied formulas in a final, infinite-degree tier, allowing the population to trade off disagreement against satisfied preferences. Or one could define each type as a person’s complete preference theory rather than a single formula, to avoid making a person’s influence depend on how their statement is split into formulas. Both are sensible models. But the first changes the paper’s hard requirement that every formula be satisfied, and the second requires a new rule for aggregating each person’s theory into population-level scores. They are new weighted preference-aggregation problems, not immediate continuizations of Proposition 6.
That is the best case against the anchor, but it does not defeat it. A municipality or organization with many stakeholders, a shared set of policy variables, and repeated complete preference types is a plausible high-multiplicity regime. Weighted lexicographic entailment in that setting is a well-posed computational question. The paper’s motivation and semantics give the authors a plausible basis to recognize it, even if the mirror needs a more careful treatment of disagreement.
So I cannot honestly sustain the universal negative. The proposal as stated has a serious unanimity and type-definition problem; its repaired versions need more semantic choices than the case admits. But those choices do not show that no worthwhile continuous mirror exists. The strongest negative conclusion supported by the paper is that this anchor is under-specified, not that it fails.
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.