| paper | d4-conf-aaai-2023-0147 |
| 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: \(\Pi_2^p\)-complete under polynomial-time many-one reductions, hence \(\mathrm{NP}\)-hard, already for \(\tau=1\) and mass \(1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite argumentation framework \(\Lambda=(A,\Omega)\), a support \(T\) of \(\tau\) well-formed conditional-preference bases \(\Gamma_t\) with positive binary-rational masses \(\mu_t\) summing to \(1\), and a proposed set \(S\), decide whether \(S\) is a preferred extension of \(\Lambda\) that is unbeaten by weighted majority. For each pair of preferred extensions \(E,F\), each type compares them by the paper’s flat KTV criterion; define \(w_\mu(E,F)=\sum_{t:E\succ_{k,t}F}\mu_t\), with ties and incomparisons abstaining, and say \(E\succ_\mu F\) iff \(w_\mu(E,F)>w_\mu(F,E)\). The question is whether there is no \(F\in pr(\Lambda)\) with \(F\succ_\mu S\).
A shared argument graph \(\Lambda\) and a distribution \(\mu\) over complete stakeholder types \(\Gamma_t\); the output is whether a proposed preferred extension is unbeaten under the weighted-majority aggregation of the types’ flat KTV comparisons.
The paper models one preference base, whereas the mirror adds pairwise majority across types; because KTV comparisons need not be transitive, the resulting majority relation can cycle and may have no unbeaten extension.
fatal: False
This mirror covers the preferred-KTV verification result in Theorem 3. It leaves the other verification combinations and the credulous and skeptical acceptance results in Theorems 4 and 5 unaddressed.
The strongest mirror I see is a large public review of a shared controversy. The argument graph records a common dossier: its arguments and attacks are fixed for everyone. Participants differ in their conditional preferences about which arguments are better in which contexts. A type is a complete conditional preference base over that graph; agents of the same type are interchangeable. If \(N_t\) people have type \(t\), then \(\mu_t=N_t/N\) is their population share. A large review panel or online community could have enormous \(N\) but relatively small support \(\tau\), because the same preference profiles recur.
Here is the specific problem I would hand to a prover: Continuous CPAF Preferred-KTV Verification. An instance consists of a finite AF \(\Lambda=(A,\Omega)\), a support \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\), a well-formed conditional preference base \(\Gamma_t\) for each type, and a proposed set \(S\subseteq A\). Each type compares preferred extensions using the paper’s flat KTV criterion. For preferred extensions \(E,F\), let
\[
w_\mu(E,F)=\sum_{\{t:E\succ_{k,t}F\}}\mu_t,
\]
where \(E\succ_{k,t}F\) is the strict KTV preference of type \(t\), with rule bodies evaluated as in the paper. Types that tie or cannot compare the pair abstain. The population prefers \(E\) to \(F\) when \(w_\mu(E,F)>w_\mu(F,E)\). Its best preferred extensions are
\[
\mathsf{Best}_{pr}(\Lambda,\mu)
=\{E\in pr(\Lambda):\nexists F\in pr(\Lambda)\text{ with }F\succ_\mu E\}.
\]
The decision question is whether \(S\in\mathsf{Best}_{pr}(\Lambda,\mu)\). This is a verification problem, so its decision object is the proposed extension \(S\); there is no cost-minimization objective.
My anchor is Theorem 3, proved in this paper. Its relevant entry says that \(\mathrm{Ver}_{prk}\), the problem of deciding whether a given set is a best preferred extension under the KTV criterion and flat interpretation, is \(\Pi_2^p\)-complete. The theorem also gives \(\Pi_2^p\)-completeness for the corresponding closed-interpretation problem \(\mathrm{Ver}_{pr^*k}\); the question above uses the flat version. The result is about verifying a best preferred extension of the underlying argumentation framework, not about verifying an encoding.
This is a close population extension of that problem: it keeps the common AF, the preferred semantics, the conditional KTV comparisons, and the best-extension question, while making preference input a distribution across stakeholders. With \(\tau=1\) and \(\mu_1=1\), the population comparison is exactly the paper’s comparison. Thus the discrete hardness embeds directly, and I expect the continuous problem to remain \(\Pi_2^p\)-hard—likely \(\Pi_2^p\)-complete, since comparisons between two extensions are polynomial and the remaining search over preferred extensions has the same quantifier shape. The hardness is driven by the argument structure, not by the number of people, so this is a Class B case: continuization does not remove the anchored hardness. This mirror covers the preferred-KTV verification result, not the paper’s other semantics or acceptance problems.
The main plausibility question is the population comparison. The paper studies one preference base at a time; it does not define a population that votes over extension comparisons. But the lift is explicit: each type uses the paper’s own comparison, and population mass aggregates those comparisons pairwise. That is a recognizable group-decision extension of the authors’ problem, and the paper itself points to a future connection with social choice theory. Further questions include whether hardness already holds for \(\tau=2\), how flat and closed interpretations compare under aggregation, and the cost of shifting mass between types to make an argument credulously or skeptically accepted.
My weakest point is that majority aggregation is a new modeling choice, not a result or semantics supplied by the paper. The one-type case establishes an exact anchor and a hardness transfer, but by itself says little about the computational effect of fractional population masses. A referee could accept the multi-type version as a natural group extension while still asking whether it is the continuous form of the authors’ problem.
The paper clearly has computational results: Theorems 3–5 classify verification and acceptance problems. So the strongest negative case cannot dismiss the proposed anchor for lack of a result to mirror.
The proponent’s construction is formally coherent. In a large consultation over a shared argument graph, participants could have recurring conditional-preference bases, with population shares given as rational masses. The one-type case recovers the paper’s \(\mathrm{Ver}_{\mathrm{pr}k}\) problem exactly. That is a plausible high-multiplicity regime, and the paper itself points to a future connection with social choice theory. I cannot rule it out by arguing that argumentation has no population scenario.
The best objection is that the multi-type problem adds a new collective-choice semantics. In the paper, a conditional-preference base describes one user’s comparisons between extensions; the paper does not say that several users should vote pairwise over those comparisons. The proposed strict-majority rule, its treatment of incomparable extensions as abstentions, and its definition of “best” are all additional choices. Since the paper notes that KTV comparisons need not be transitive, a population majority can cycle and leave no unbeaten extension. That makes the proposal an interesting group-decision problem, but weakens the claim that its multi-type part is a continuization of the paper’s own computational problem. The exact link to the theorem is strongest at one type, where there is no population effect.
A more direct lift would ask what fraction of the population credulously or skeptically accepts an argument. But that can be computed by evaluating the paper’s acceptance problem for each type and summing the corresponding masses; it adds a population statistic without much interaction between types. A campaigning or robustness problem could create that interaction, but it would need a model of the cost of changing a person’s conditional-preference base, which the paper does not supply.
That is the strongest case against, but it does not defeat the anchor. The aggregation choices are genuine modeling decisions, not fatal defects, and a large stakeholder consultation makes them plausible. I can argue that this is a new social-choice layer rather than a direct mirror; I cannot honestly support the universal claim that no worthwhile continuous mirror exists in any scenario.
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.