| paper | d4-conf-ecai-2008-0046 |
| 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: \(\mathrm{NP}\)-complete, even for \(\tau=1\), \(\mu_1=1\), \(\theta=\tfrac12\), and a total preorder with three indifference classes. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite support of PBAT types \(T_t=(A,C_t,\succeq_t)\) over a shared argument set \(A\), a common queried argument \(a\in A\), binary-rational masses \(\mu_t\) summing to \(1\), and a rational threshold \(\theta\), decide whether \(\sum_t \mu_t \mathbf{1}[a\text{ belongs to some stable extension of }T_t]\ge\theta\).
A high-multiplicity population of agents using PBATs over a shared argument vocabulary, with each type specified by its conflict relation and preference preorder. The decision variable is the credulous-status indicator for each type; the objective is the total mass of types whose stable extensions include the queried argument.
The paper gives no direct model of a society of agents with heterogeneous PBATs; the proposed prevalence task adds aggregation over separate theories, and their statuses do not affect one another.
fatal: False
The mirror covers Theorem 4’s credulous reasoning result and Proposition 3’s skeptical reasoning result. It leaves the paper’s structural characterizations, coherence results, stable-extension algorithm, and enumeration results aside.
The strongest mirror I see is a population of agents that each use a PBAT to assess the same policy claim. For example, a large consultation platform could have many deployed argumentation agents using recurring argument maps and preference profiles. The arguments remain discrete; the continuous object is the population of agents. A type is a complete PBAT profile, including its arguments, conflict relation, preference preorder, and the argument representing the queried claim. Agents of the same type are indistinguishable for this computation. In a high-multiplicity regime, millions of agents might share a relatively small number \(\tau\) of standardized profiles.
For each supported type \(t\), let \(T_t=(A_t,C_t,\succeq_t)\), where \(C_t\) is symmetric and irreflexive and \(\succeq_t\) is a partial preorder. Its attack relation is \(R_t\), with \((u,v)\in R_t\) exactly when \((u,v)\in C_t\) and \(v\not\succ_t u\). Let \(a_t\) represent the common queried claim in that type, and let \(\mu_t\) be the type’s binary-rational share of the population, with \(\sum_t\mu_t=1\).
My lead anchor is Theorem 4, proved in this paper. It states that, given a PBAT \(T=(A,R)\) and \(a\in A\), deciding whether \(a\) is a credulous conclusion—whether some stable extension contains \(a\)—is NP-hard. The paper proves this by reducing from 3SAT: its constructed PBAT has a stable extension containing the argument for the whole theory exactly when the formula is satisfiable.
The corresponding continuous question is Credulous-PBAT-Mass Threshold. For each type \(t\), let \(x_t=1\) if some stable extension of \(T_t\) contains \(a_t\), and \(x_t=0\) otherwise. Compute the population share \(M_{\mathrm{cred}}=\sum_t\mu_t x_t\), or, in the decision version, determine whether \(M_{\mathrm{cred}}\ge\theta\), for an input rational threshold \(\theta\). The \(x_t\) are forced by the PBAT semantics; there is no intervention to optimize. The quantity being measured is the fraction of agents for whom the claim is a possible conclusion.
A second worthwhile anchor is Proposition 3, also proved here. It states that deciding whether \(a\) is a skeptical conclusion of a PBAT—whether every stable extension contains \(a\)—is coNP-hard. The paper sketches a reduction from unsatisfiability, adding an argument \(t'\) that is skeptical exactly when the source theory is unsatisfiable.
Its separate mirror is Skeptical-PBAT-Mass Threshold: set \(y_t=1\) exactly when every stable extension of \(T_t\) contains \(a_t\), and determine whether \(M_{\mathrm{skept}}=\sum_t\mu_t y_t\ge\theta\), or return that exact share. This measures the fraction of agents for whom the claim survives every stable resolution of their profile.
Both continuous questions are expected to be Class B: hardness transfers. With one supported type of mass \(1\) and threshold \(\theta=1\), each question is exactly its paper anchor. Thus Credulous-PBAT-Mass Threshold remains NP-hard and Skeptical-PBAT-Mass Threshold remains coNP-hard, even at \(\tau=1\). This is not a claim that population size causes the hardness; it shows that making the population continuous does not remove the underlying reasoning difficulty. Useful follow-up questions include the complexity of returning the exact mass, whether shared structure across types permits faster aggregation, and which graph or preference-order restrictions make either threshold problem tractable. The mirror covers the credulous and skeptical reasoning results, not the paper’s full structural analysis of PBATs.
The weak point is that the paper studies the status of an argument in one PBAT, while these mirrors measure status across many agents’ PBATs. The population mass weights the answers but does not change each agent’s attack graph or semantics, so continuous-optimization methods have no obvious role. If the authors regard a PBAT only as one shared global theory, they may see this as a new aggregate task rather than their problem continuized. I think the case remains plausible because PBATs can represent individual reasoning profiles, and the paper itself motivates argumentation partly through agent technology. The proposed questions preserve its exact semantics and ask about the share of a high-multiplicity population for whom its named reasoning predicates hold.
Both anchors are real computational results: Theorem 4 gives NP-hard credulous reasoning, and Proposition 3 gives coNP-hard skeptical reasoning. The strongest objection is not that either result would stay hard, but that the proposed population statistic wraps two single-theory questions in a distribution without making either one a collective problem.
If everyone uses the same PBAT and asks about the same argument, the credulous and skeptical indicators are constant across the population, so each reported share is \(0\) or \(1\). To get a nontrivial share, the model needs agents with different PBATs. The most sympathetic version would hold the argument set, conflict relation, and queried claim fixed, while allowing a finite set of preference profiles. That makes repeated types plausible and gives the resulting fractions a possible interpretation.
But the fractions still measure how often a *property of a theory* holds across the chosen profiles. Credulousness means that some stable extension contains the argument; skeptical status means that every stable extension does. Neither says what an agent accepts or does. One could ask agents to report those statuses, but then the continuous task is weighted aggregation of independent PBAT evaluations. The masses do not affect the semantics, constrain the evaluations, or define a collective decision. The same task could be stated as prevalence over a weighted list of inputs, without a population model.
That objection applies to both mirrors, though the mismatch differs: the credulous share counts profiles in which acceptance is possible, while the skeptical share counts profiles in which it is unavoidable. A campaign to push either share past a threshold could create a genuinely coupled population problem, but it would require specifying what can be changed, at what cost, and how changes affect agents’ PBATs. Those are new modeling choices; neither named result supplies them.
So the negative case is that these are distributional extensions of the paper’s reasoning problems, rather than continuizations of its argumentation problem. That is a real limitation, but not a decisive one: a shared debate with standardized preference profiles is plausible, and measuring the prevalence of these statuses could be useful to argumentation researchers. I would call the case against worthwhile mirrors weak, especially if the programme accepts population-level prevalence questions as sufficient.
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.