d4-conf-aaai-2023-1322

A defensible mirror treats argument occurrences as the population. Consider a large public deliberation or collective fact-checking system in which many contributors make arguments from recurring templates. A type records everything relevant to the paper’s reasoning: the argument’s claim, its attack relations to other types, and its preference relations. For example, arguments from the same evidence template and reliability tier may be indistinguishable to the acceptance semantics. The regime is many occurrences \(N\) and a smaller support of \(\tau\) types; a type is complete only when its members really are identical for the problem.

Here is a common continuous model for the verification results. The input is a finite type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), a claim map \(q:T\to Q\), an attack relation \(R\subseteq T\times T\), an asymmetric preference relation \(\succ\), a preference reduction \(i\), a semantics \(\sigma\), and a target claim set \(C\subseteq Q\). The type-level CAF must be well-formed: types with the same claim have the same outgoing attacks. Represent type \(t\) by an interval \(I_t\) of length \(\mu_t\), and lift attacks, claims, and preferences to every occurrence in those intervals according to its type. A candidate accepted population is a measurable set \(E\); its accepted mass of type \(t\) is \(x_t=\lambda(E\cap I_t)\), and its claim set is
\[ Q(E)=\{q(t):x_t>0\}. \]
The decision question is whether there is an \(E\) that is a \(\sigma\)-extension after applying reduction \(i\) and has \(Q(E)=C\). There is no optimization objective in these anchors: they are verification problems, so the output is yes/no, with an accepted-mass vector \(x\) as a witness.

The repeated occurrences in each type have identical attack and defense behavior. Thus a witness can be taken to include either all or none of each type’s mass: for admissible extensions, filling out a partially selected type preserves admissibility and the claim set; complete and stable extensions require the same all-or-none behavior; and a partial type cannot be maximal under preferred, semi-stable, or stage semantics. This gives the continuous question a finite type-level representation without changing the paper’s acceptance question.

My lead is Continuous R1 Claim-Mass Verification. Its anchor is Proposition 10, proved in this paper: for \(\sigma\in\{\mathrm{stb},\mathrm{adm},\mathrm{com}\}\), verifying whether a specified set of claims belongs to \(\sigma^1_p(F)\) is NP-complete, even when preferences are transitive. The mirror takes the continuous instance above with reduction 1 and asks the same verification question for stable, admissible, or complete semantics. I expect hardness to transfer: the 3-SAT structure in the proof lives in the arrangement of claims, attacks, and argument roles, not in the number of repeated occurrences. A finite instance can be represented by one type per argument, and each type can then be given arbitrarily many indistinguishable occurrences without changing which claim sets are extensions.

A second mirror is Continuous Complete-Claim Verification by Reduction. Proposition 14, proved here, gives the useful boundary: complete-semantics verification with reduction 3 is in P, while with reductions 2 and 4 it is NP-complete, even for transitive preferences. The continuous problem uses the same input and asks whether \(C\) is a complete claim-extension after the selected reduction. I expect the reduction-3 case to remain tractable and the reduction-2 and reduction-4 cases to remain hard, for the same type-symmetry reason. This comparison is valuable because it mirrors a distinction the paper itself establishes among its preference-handling methods.

The third mirror is Continuous R1 Maximal-Claim Verification. Proposition 11, also proved here, states that verification is \(\Sigma^P_2\)-complete for \(\sigma\in\{\mathrm{prf},\mathrm{sem},\mathrm{stg}\}\), even with transitive preferences; its hardness proof adapts a standard translation for skeptical preferred acceptance. The continuous version asks whether \(C\) is the claim set of a preferred, semi-stable, or stage extension of the lifted R1 framework. I expect \(\Sigma^P_2\)-hardness to transfer. A natural next question is whether useful restrictions on the type interaction graph or on the number of distinct claims yield fixed-parameter algorithms.

These are recognizable as the paper’s problems: the candidate extensions still arise from its CAF attacks, preference reductions, claim map, and Dung semantics. The paper’s claim-centric perspective also makes repeated argument occurrences a natural unit to aggregate. I would limit the mirror to these verification results; it does not claim a continuous version of the paper’s structural characterizations or I-maximality results.

The weakness is that, under these set-based semantics, the *values* of the positive masses do not affect verification: only whether a type has positive mass matters. This is a population continuization, but not a mass-sensitive optimization problem, and it offers no reason to expect the anchored hardness to dissolve. The authors could reasonably ask whether argument occurrences are a meaningful population in the proposed deliberation scenario. The case survives if the question is whether their complexity landscape persists when a large population is compressed into repeated, indistinguishable argument roles. If a worthwhile mirror must make fractional mass itself change the acceptance question, this is a weak candidate.