| paper | d4-conf-ijcai-2022-0221 |
| 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: All three decision problems are \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, even for equal positive dyadic masses. Verification is \(\mathrm{coNP}\)-complete. None is in \(\mathrm{P}\) unless \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite set of participant-argument types \(T\), an attack relation \(R\subseteq T\times T\), binary-rational masses \(\mu_t>0\) summing to \(1\), and a goal type \(g\), consider the complete extensions of the AF \((T,R)\). For a complete extension \(E\), let \(D(E)=\{t\in T:\exists u\in E,\ (u,t)\in R\}\), \(U(E)=T\setminus(E\cup D(E))\), and \(u_\mu(E)=\sum_{t\in U(E)}\mu_t\). Decide whether a supplied \(E\) minimizes \(u_\mu\) among complete extensions, whether some such minimizing extension contains \(g\), or whether every such minimizing extension contains \(g\).
A consultation population is distributed over interchangeable participant-argument types, each with the same attack relationships to every type. The AF is defined on those types; an extension selects types as units, and the mass \(\mu_t\) measures each type's share of participants. The c-ss criterion minimizes the total mass of undecided types.
The mirror covers Theorem 4's c-ss verification and acceptance questions; the proponent also proposes a weighted c-pr variant, whose arbitrary-weight complexity remains open. It leaves the PAF and AFP results and the other cardinality semantics without a mirror.
The strongest mirror is the paper’s cardinality-based acceptance result, especially c-ss. It is the part of the paper where mass has a natural job: the authors select extensions by comparing how many arguments they accept, defeat, or leave undecided.
Consider a large public consultation with many submissions but relatively few recurring argument forms. A type records a submission’s argumentative role, including which other types it attacks; submissions of the same type have identical relationships to every type. Let \(T\) be the types present, \(R\subseteq T\times T\) their attack relation, and \(\mu_t>0\) the fraction of submissions of type \(t\), with \(\sum_{t\in T}\mu_t=1\). The regime is many submissions per type, with the number of types \(\tau=|T|\) much smaller than the number of submissions. The mass of a type is the share of the consultation represented by that argument form.
An extension selects argument types, and hence all submissions of each selected type. This preserves the paper’s central object: complete extensions of an argumentation framework. For \(E\subseteq T\), write \(D(E)=\{t:\exists u\in E,\ (u,t)\in R\}\) and \(U(E)=T\setminus(E\cup D(E))\). Call \(E\) complete when it is a complete extension under the usual Dung conditions on \((T,R)\). Its accepted, defeated, and undecided masses are \(a_\mu(E)=\sum_{t\in E}\mu_t\), \(d_\mu(E)=\sum_{t\in D(E)}\mu_t\), and \(u_\mu(E)=\sum_{t\in U(E)}\mu_t\).
My lead question is Continuous Cardinality-Semi-Stable Acceptance. An instance consists of \((T,R,\mu)\), a goal type \(g\), and a query asking for verification, credulous acceptance, or skeptical acceptance. A complete extension is c-ss if it minimizes \(u_\mu(E)\) among complete extensions. Verification asks whether a supplied \(E\) is c-ss; credulous acceptance asks whether some c-ss extension contains \(g\); skeptical acceptance asks whether every c-ss extension contains \(g\). Each query has a yes/no answer. This is the strongest mirror because minimizing undecided mass directly replaces the paper’s minimum number of undecided arguments.
The anchor is Theorem 4, stated and proved in this paper. In full, it says that verification is coNP-complete for both c-pr and c-ss; credulous and skeptical acceptance under c-pr are each \(\Theta^P_2\)-hard and in \(\Delta^P_2\); and both acceptance problems under c-ss are \(\Theta^P_2\)-complete. I would expect the c-ss mirror’s hardness to transfer. Given any finite AF with \(n\) arguments, make each argument a type of mass \(1/n\), retaining the original attacks. Weighted undecided mass is then the original undecided count divided by \(n\), so the selected extensions and acceptance answers are unchanged. The same replication can be read as a high-multiplicity instance: make many interchangeable copies of every argument. The hard combinatorics remain in the number and interaction of types, rather than in the number of copies.
The same model gives a separate variant, Continuous Cardinality-Preferred Acceptance: select complete extensions for which no other complete extension has at least as much accepted mass and at least as much defeated mass, with one comparison strict. Its verification and acceptance queries are defined as above. This mirrors c-pr’s Pareto comparison of accepted and defeated counts. Theorem 4’s c-pr bounds transfer under the uniform-mass embedding; the exact upper bound for arbitrary binary-rational masses is a further question, since unequal weights may produce many incomparable mass pairs.
I think the authors could recognize both as direct weighted extensions of their cardinality semantics. The paper explicitly motivates those semantics by users wanting “optimal” extensions, and consultation mass gives a natural interpretation of their counts. The mirror covers Theorem 4’s cardinality-based semantics and acceptance problems; it does not claim to continuize the paper’s PAF preferences or AFP priority-rule language.
The soft spot is that arguments are not literally voters: repeated submissions may not normally count as distinct arguments, and an author might regard collapsing interchangeable arguments into types as changing what cardinality is intended to measure. This mirror is convincing when the application treats each submission as an argument token and wants to optimize the share of submissions accommodated or resolved. It is weaker if the objects are abstract claims that should be deduplicated regardless of how many people express them. A further question is whether arbitrary rational weights preserve the paper’s stated upper bounds, particularly for c-pr, or make weighted Pareto selection harder.
Theorem 4 is a real anchor: it gives named complexity results for c-pr and c-ss acceptance, so “there is no computational result to mirror” cannot carry the negative case.
The strongest version of the proposed mirror is a large consultation where each participant contributes an argument, and participants with the same argument and attack pattern form a type. Then c-ss minimizes the mass of unresolved participants’ argument types, while c-pr compares accepted and defeated mass. The paper’s Example 5, which treats arguments as people invited to a party, makes this framing more recognizable to the authors than a generic claim that argument nodes are voters.
The objection is that this interpretation needs a careful choice of what the mass counts. If repeated statements are the same proposition, their frequency is evidence of support, not additional arguments in a Dung framework. If the nodes instead represent individual people, the attacks must describe their relationships. Grouping people is valid only when they are interchangeable in every such relationship. In the cleanest case, where same-type copies have no internal attacks and identical links to other types, their extension labels move together: the continuous variant is a finite AF with rational weights on its types. That is a legitimate weighted problem, but its population interpretation is doing the substantive work; continuity itself adds no fractional choices to the extension semantics.
Allowing people of one type to receive different labels would make the consultation story richer, but it would no longer be the proposed type-level c-pr or c-ss semantics. It would need an additional rule for partial acceptance or for mixing extensions. That is a different model, and may shift the question toward fractional or probabilistic outcomes.
This is a case for treating the mirror as a narrower, potentially low-yield weighted-argumentation project: its value depends on whether the authors regard argument-bearing people and their mass as a central application, rather than external weights on logical nodes. But it does not defeat the anchor universally. A sufficiently coherent population of interchangeable argument-bearing participants makes weighted c-ss acceptance a well-posed mirror, and the paper itself offers a foothold for that interpretation. I cannot honestly argue that no worthwhile scenario exists.
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.