| paper | d4-conf-aaai-2021-1122 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathsf{NP}\)-hard, even when \(\tau=1\), \(C=\varnothing\), and \(|W|=2\), with weights \(2\) and \(1\). A polynomial-time algorithm would imply \(\mathsf P=\mathsf{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given an argumentation framework \(\langle A,R\rangle\), strong constraints \(C\), weak constraints \(W\), target argument \(a\), and a finite support \(T\) of types with binary-rational masses \(\mu_t\) and binary-rational preference weights \(w_{t,\omega}\) over \(W\), let \(\mathcal{P}_C\) be the preferred extensions satisfying \(C\), and define \(U_\mu(E)=\sum_{t\in T}\mu_t\sum_{\omega\in W}w_{t,\omega}\mathbf{1}[E\models\omega]\). Decide whether some utility-maximizing extension in \(\mathcal{P}_C\) contains \(a\).
In a large consultation, types are stakeholders with identical preferences over the weak constraints, represented by mass \(\mu_t\). The choices are preferred extensions satisfying \(C\); their objective is aggregate satisfaction utility \(U_\mu\), and the query asks whether a utility-maximizing extension contains \(a\).
The stakeholder population is added to a framework whose weak constraints are modeler-chosen criteria, and aggregate utility reduces the distribution to one coefficient per criterion; this leaves some uncertainty about whether the authors would regard stakeholder welfare as their problem.
fatal: False
The mirror covers Theorem 3’s preferred credulous acceptance result under maximum-cardinality semantics; it leaves the paper’s other semantics and complexity results unaddressed.
My lead mirror is Population-Weighted Preferred Acceptance (PWPA), for large public consultations or platform policy reviews. The arguments are claims in a shared debate, attacks represent conflicts among claims, strong constraints encode feasibility conditions, and weak constraints express desiderata for a coherent position. There may be hundreds of thousands of stakeholders but only a comparatively small set of distinct preference profiles: people with the same preferences on every criterion relevant to the decision are one type.
Precisely, an instance gives an argumentation framework \(\langle A,R\rangle\), strong constraints \(C\), a finite set \(\Omega\) of weak constraints, a target argument \(a\in A\), and a society of types \(T\) with binary-rational masses \(\mu_t\geq 0\), where \(\sum_{t\in T}\mu_t=1\). Each type \(t\) has a rational preference vector \(w_{t,\omega}\geq 0\) over \(\Omega\), with \(\sum_{\omega\in\Omega}w_{t,\omega}=1\). Its utility for an extension \(E\) is
\[
u_t(E)=\sum_{\omega\in\Omega}w_{t,\omega}\mathbf{1}[E\models\omega],
\]
using the paper’s constraint-satisfaction semantics. Among the preferred extensions of \(\langle A,R\rangle\) satisfying \(C\), define \(U_\mu(E)=\sum_{t\in T}\mu_t u_t(E)\). PWPA asks: is there a preferred extension satisfying \(C\) that contains \(a\) and maximizes \(U_\mu\)? A yes solution is such an extension together with its exact rational utility and the claim that no feasible preferred extension has greater utility; otherwise the answer is no. This keeps the argumentation task intact while making the population’s share of support count.
The anchor is Theorem 3, proved in this paper. It states that for any WAF with \(|W|=n\), both credulous and skeptical acceptance under maximum-cardinality semantics are \(\Delta^P_2[\log n]\)-complete for complete and stable semantics, and \(\Delta^P_3[\log n]\)-complete for preferred and semi-stable semantics. Here credulous acceptance asks whether the argument occurs in at least one maximum-cardinality extension; skeptical acceptance asks whether it occurs in every such extension. I rely specifically on the preferred, credulous result.
The continuous problem contains that result exactly: given a WAF with \(n\) weak constraints, make \(n\) stakeholder types, one per constraint, assign each type mass \(1/n\), and give it all its preference weight on its own constraint. Then \(U_\mu(E)\) is the number of satisfied weak constraints divided by \(n\). The socially optimal preferred extensions are exactly the maximum-cardinality preferred extensions. Thus the theorem’s \(\Delta^P_3[\log n]\)-hardness transfers to PWPA. Repeating each type across an arbitrarily large population preserves the same masses, so the interpretation can be high-multiplicity even though the embedded paper instance has \(n\) distinct desiderata.
I expect hardness to transfer. This does not establish the exact complexity of PWPA with binary-encoded masses and preference weights. A threshold test for whether some preferred extension reaches a given utility, followed by search over the rational objective values, suggests an upper bound in \(\Delta^P_3\); whether that bound is tight is a further question. Other natural questions are whether the problem becomes tractable or admits useful approximation when the support size \(\tau=|T|\) is small, and how its skeptical version behaves.
The mirror covers only Theorem 3’s maximum-cardinality preferred credulous-acceptance result. It does not purport to continuize the paper’s other semantics or complexity results. It is a population model: the selected outcome remains a discrete set of arguments.
The soft spot is that the paper’s weak constraints are criteria, not explicitly citizens’ preferences. PWPA interprets their satisfaction as stakeholder utility and replaces equal counting with population-weighted utility. That is a real co-modification, though it preserves the paper’s central question of which preferred extensions are best according to weak constraints. The interpretation has some foothold in the paper’s discussion of preference and weighted weak constraints, but whether these authors would accept the stakeholder model is the case’s main uncertainty.
The strongest negative case is that PWPA may be a population interpretation of weighted weak-constraint optimization, rather than a distinct continuization of the paper’s problem. In the WAF, weak constraints are criteria chosen by the modeler. The paper has no electorate or individual preference profiles. PWPA adds both: it asks stakeholders to assign utilities to those criteria, then uses aggregate welfare to choose an extension.
For the proposed utility, every population distribution collapses to a coefficient for each weak constraint:
\[
q_\omega=\sum_{t\in T}\mu_t w_{t,\omega},
\qquad
U_\mu(E)=\sum_{\omega\in W}q_\omega\,\mathbf{1}[E\models\omega].
\]
So populations with the same \(q\) are indistinguishable to the problem, regardless of their support size or the number of people represented. The exact embedding of Theorem 3 makes this especially clear: one type per weak constraint, each caring only about that constraint, yields the original maximum-cardinality objective divided by \(n\). Replicating those types changes the headcount, but not the instance’s computational content. The paper itself already discusses weighted weak constraints, which makes the population weights look like a familiar way to supply objective coefficients.
That is a real reservation about what continuization adds, but it does not defeat the anchor. Theorem 3 is a named computational result, and the proposed construction preserves its preferred credulous acceptance question exactly: an argument belongs to some socially optimal preferred extension iff it belongs to some maximum-cardinality preferred extension. A stronger version—participants expressing complete preferences over desired argumentation properties—still gives a coherent high-multiplicity population, and the paper’s focus on choosing preferred extensions by constraints makes it plausible that the authors would recognize the resulting optimization question.
I therefore cannot honestly make the universal negative case the prompt asks for. The population is added to the model rather than recovered from an electorate already present in the paper, and its aggregate utility compresses to weighted criteria. But those points leave a worthwhile, if narrow, mirror standing: this paper’s maximum-cardinality preferred-acceptance result has an exact continuous-population formulation.
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.