| paper | d4-conf-ijcai-2023-0066 |
| 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: \(\Sigma_2^p\)-complete, hence \(\mathrm{NP}\)-hard; a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
Given a shared argumentation framework \(\Lambda=\langle A,R\rangle\), an argument \(g\in A\), a rational threshold \(q\in(0,1]\), and a finite support of valid ePCAF profiles \(\Delta_j=\langle A,R,C_j,\succ_j\rangle\) with positive rational masses \(\mu_j\) summing to \(1\), decide whether at least a \(q\)-fraction of the society has \(g\) credulously accepted under complete semantics and the paper's KTV comparison. Equivalently, set \(z_j=1\) iff some \(E\in\mathrm{co}_k(\Delta_j)\) contains \(g\), and decide whether \(\sum_{j=1}^{\tau}\mu_j z_j\ge q\).
Types are complete ePCAF profiles sharing one argument graph; each type has mass \(\mu_j\). The decision variables \(z_j\in\{0,1\}\) indicate whether that type has a best complete extension containing \(g\); the query tests whether their mass-weighted sum reaches \(q\).
The paper explicitly places collective and multi-criteria decision questions outside its scope, so it does not establish that the authors would endorse a thresholded population share.
fatal: False
The mirror uses Theorem 4's possible credulous acceptance result under complete semantics; it leaves the other acceptance variants and semantics aside, and the paper's fixed-\(n\) bounds do not classify the variable-\(\tau\) problem.
The strongest mirror is Mass Credulous Acceptance for ePCAF populations. It takes the paper’s multi-agent setting seriously: many people assess the same argument graph, but share a relatively small set of complete profiles of subjective constraints and preferences.
A plausible regime is a large public consultation around a shared policy dossier. The arguments and attacks are common to everyone; each person’s type is their full constraint set \(C_j\) and extended preference relation \(\succ_j\). People with the same pair are indistinguishable for this problem. If millions of residents use a few hundred recurring profiles, the population size \(N\) can be far larger than the support size \(\tau\). The mass \(\mu_j\) is the fraction of residents with profile \(j\). This is not uncertainty over which argument graph is true: the graph stays fixed, and the continuous object is the population.
The anchor is Theorem 4, proved in this paper. For multi-agent ePCAF with an arbitrary but fixed number of agents, it establishes that possible and necessary verification are coNP-complete under complete and stable semantics, and \(\Pi^p_2\)-complete under preferred and semi-stable semantics. Possible and necessary credulous acceptance are \(\Sigma^p_2\)-complete under complete and stable semantics, and \(\Sigma^p_2\)-hard and in \(\Sigma^p_3\) under preferred and semi-stable semantics. Possible and necessary skeptical acceptance are \(\Pi^p_2\)-complete under complete and stable semantics, and \(\Pi^p_2\)-hard and in \(\Pi^p_3\) under preferred and semi-stable semantics. The result is explicitly for fixed \(n\), the number of agents. My lead anchor is its \(\Sigma^p_2\)-completeness result for possible credulous acceptance under complete semantics; the corresponding necessary-acceptance result has the same bound.
Here is the continuous problem. An instance consists of a shared AF \(\Lambda=\langle A,R\rangle\), an argument \(g\in A\), a rational threshold \(q\in(0,1]\), and a finite support of valid ePCAF types \(\Delta_j=\langle A,R,C_j,\succ_j\rangle\), each with positive binary-rational mass \(\mu_j\), where \(\sum_j\mu_j=1\). Fix complete semantics and the paper’s KTV comparison of extensions. Set \(z_j=1\) exactly when some best complete extension of \(\Delta_j\) contains \(g\), and \(z_j=0\) otherwise. Ask whether
\[ \sum_{j=1}^{\tau}\mu_j z_j \ge q. \]
The answer is yes precisely when at least a \(q\)-fraction of the population has \(g\) credulously accepted under its own profile. This is a threshold decision problem, not an optimization over argument graphs or outcomes. It extends the paper’s possible-versus-necessary distinction: with \(n\) equally weighted profiles, threshold \(1/n\) asks whether any profile qualifies, while threshold \(1\) asks whether every profile qualifies.
This looks like a recognizable extension of the authors’ problem, rather than a tractable surrogate. The paper already models agents sharing one AF while expressing different subjective constraints and preferences, and identifies collective and multi-criteria decisions as outside its scope. Weighted population support is a direct way to ask such a collective question. The paper’s existing multi-agent result also supports the premise that this is a meaningful regime. Its probabilistic argumentation neighbours do not already answer it: the masses here describe how many agents have a profile, not uncertainty over arguments or extensions.
I expect hardness to transfer, at least. With one type of mass \(1\) and \(q=1/2\), the continuous problem is exactly the underlying single-agent credulous acceptance question. Thus the \(\Sigma^p_2\)-hardness survives even at \(\tau=1\); it comes from the combinatorics of argumentation semantics and extension comparison, not from a large population. I would not claim that Theorem 4 gives the exact complexity when \(\tau\) varies: aggregating many type-level acceptance predicates could raise the upper bound. That is itself a complexity question for the mirror.
The scope here is deliberately narrow: only possible credulous acceptance under complete semantics, anchored in Theorem 4. Natural further questions are the exact complexity for variable \(\tau\), the weighted version of skeptical acceptance, and whether approximation of the accepted population share is easier than exact threshold decisions.
The weakest point is that the continuous problem aggregates the paper’s individual acceptance tests; it does not uncover a new optimization structure or promise a tractability gain. Also, “credulously accepted by a person’s type” means possible under that type’s best extensions, not settled endorsement by that person. A reviewer could reasonably ask whether the weighted share is the community-level quantity they intended to study. The case survives because it preserves the paper’s exact agent model, turns its possible/necessary questions into population-share questions, and exposes a concrete boundary: this continuization is plausible, but its central hardness already persists without population multiplicity.
The strongest objection is that Theorem 4 does not analyze a growing population. Its complexity claims assume an arbitrary but fixed number \(n\) of agents. The proposed threshold problem becomes a population problem only when the support size \(\tau\) can grow and agents receive masses. That is a sensible extension, but it is not the regime of the theorem’s stated result. With fixed \(n\), equal masses, and thresholds \(1/n\) or \(1\), the aggregate query reduces to the paper’s possible or necessary question. With variable \(\tau\), the result to investigate is a new weighted aggregation of many acceptance instances. The hardness at \(\tau=1\) comes from the single-agent ePCAF problem in Theorem 3; it does not establish a high-multiplicity result for Theorem 4.
The proposed public-consultation story also needs exact repetition of a fairly rich profile. A type includes the agent’s full set of logical constraints and a strict partial order over argument-status pairs. Two people who differ in one constraint or one preference relation are distinct types if that difference can change acceptance. The paper’s common argument graph supplies shared context, but its constraints and preferences are expressly subjective. A consultation using a small menu of standardized profiles could have many people per type; the paper gives no reason to rule that out. Still, without such templates, the support could grow nearly one-for-one with the number of people, leaving little high-multiplicity compression.
A stronger version would count the share for whom \(g\) is skeptically accepted, or report both credulous and skeptical shares. That makes the aggregate easier to interpret: credulous acceptance means \(g\) occurs in at least one best extension, while skeptical acceptance means it occurs in every best extension. Either query remains a sum of type-level acceptance indicators weighted by mass. It is a plausible population statistic, but the paper does not choose an aggregation rule; the threshold \(q\) supplies one from outside the individual-agent model. The authors do explicitly identify collective decisions as a broader area beyond the paper’s scope, so this is a limitation of the paper’s result, not evidence that they would reject the question.
I cannot make a strong universal case that no worthwhile mirror exists. Exact-profile populations may be uncommon, and the proposed statistic adds a layer of aggregation without an evident continuous-optimization structure. But standardized profile populations are plausible, and the resulting weighted acceptance question is well-posed and computational. Since the programme treats even a hard or unhelpful answer as worth establishing, those objections do not defeat the anchor; the honest negative case is weak.
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.