d4-journals-jair-2022-0068

The best positive case is a population of people submitting cases to a service that reasons with weakly preferred argumentation semantics. In a standardized appeals or advice system, many submissions can have exactly the same argument graph and queried claim. The regime I have in mind has \(n\) very large—perhaps millions of submissions—and \(\tau\) much smaller because cases reuse a catalog of argumentation templates.

A type is the complete pair \(t=(F_t,a_t)\): the finite argumentation framework, including all its arguments and attacks, and the queried argument \(a_t\). People of that type have identical inputs to the reasoning task. Their mass \(\mu_t\) is their fraction of the case population. This makes the population continuous at the case level; it does not assign fractional mass to arguments inside one framework.

My lead mirror is Continuous Credulous Prevalence for Weakly Preferred Semantics. An instance gives the \(\tau\) positive-mass types \((F_t,a_t,\mu_t)\), with binary-rational masses summing to \(1\), and a binary-rational threshold \(\theta\in[0,1]\). For each type, let \(z_t=1\) if \(a_t\) belongs to some weakly preferred extension of \(F_t\), and \(z_t=0\) otherwise. The task is to decide whether

\[ \sum_{t=1}^{\tau}\mu_t z_t \geq \theta. \]

Equivalently, the service reports the exact fraction of the population whose queried argument is credulously accepted. A correct solution to the decision version is “yes” or “no” for the specified threshold.

The anchor is Theorem 3.16, proved in this paper. It states that \(\mathrm{Cred}_{\mathrm{adm}^w}\), \(\mathrm{Ver}_{\mathrm{adm}^w}\), and \(\mathrm{NEmpty}_{\mathrm{adm}^w}\) are PSPACE-complete; and that \(\mathrm{Cred}_\sigma\), \(\mathrm{Skept}_\sigma\), \(\mathrm{Ver}_\sigma\), and \(\mathrm{NEmpty}_\sigma\) are PSPACE-complete for each \(\sigma\in\{\mathrm{co}^w,\mathrm{gr}^w,\mathrm{pr}^w\}\). Skeptical acceptance for weak admissibility is the trivial exception, since the empty set is always weakly admissible. I use the \(\mathrm{Cred}_{\mathrm{pr}^w}\) result: given an AF \(F\) and an argument \(a\), deciding whether \(a\) belongs to some weakly preferred extension of \(F\) is PSPACE-complete. The theorem is proved here by a reduction from valid quantified Boolean formulas; the paper notes that the underlying reduction had appeared in earlier work.

The mirror preserves that per-person question exactly. Setting \(\tau=1\), \(\mu_1=1\), and \(\theta=\tfrac12\) recovers the paper’s credulous-acceptance problem, so the mirror is PSPACE-hard. It is also in PSPACE: evaluate the \(\tau\) credulous-acceptance instances in sequence and accumulate their rational masses using polynomial space. The expected outcome is therefore hardness transfers. The result does not promise that continuity makes weakly preferred reasoning tractable; it says a population-level acceptance-rate question remains hard even when the society is represented by a distribution over case types.

This mirrors only credulous acceptance for weakly preferred semantics, not the paper’s full complexity landscape. Further questions include whether the same prevalence task is useful for weakly complete or weakly grounded acceptance, and whether structural restrictions on each case graph make aggregate computation easier.

The weakest point is the location of the population: each type contains an entire AF and query. The authors could reasonably view this as a continuous workload of their problem rather than a continuization of the arguments within one AF. The case for keeping it is that the social unit is a person bringing a case, the output is a population share, and the inner computational question remains precisely theirs. Its plausibility depends on a real setting where many people share exact argumentation types; if \(\tau\) grows nearly as fast as \(n\), the high-multiplicity rationale weakens.