| paper | d4-conf-ecai-2012-0017 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: For each fixed \(\sigma\in\{st,pr,co,ad\}\), the decision problem is \(\mathrm{NP}\)-complete. An exact algorithm takes \(O(2^{\tau-|C|}\tau^2L^2)=O(2^{m-|C|}m^2L^2)\) bit operations. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 12
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), a baseline attack relation \(R\subseteq T\times T\), a target \(C\subseteq T\), and \(\sigma\in\{st,pr,co,ad\}\), choose a relation \(R'\) and a \(\sigma\)-extension \(E\) of \((T,R')\) with \(C\subseteq E\) minimizing \(\sum_{(t,u)\in R\triangle R'}\mu_t\mu_u\). Each type-pair edit applies uniformly to all ordered argument-instance pairs in that block.
A block-symmetric population of argument instances, represented by types \(T\) with rational masses \(\mu\), a type-level attack relation \(R\), and a target set of types \(C\). The decision is a revised relation \(R'\) and an extension \(E\supseteq C\); the cost is the total mass of affected ordered pairs, \(\sum_{(t,u)\in R\triangle R'}\mu_t\mu_u\).
The paper does not establish that collapsing interchangeable argument instances into types preserves enforcement when targets or attacks can distinguish individual instances; the mirror therefore applies to type-uniform targets and block edits.
fatal: False
The mirror covers Theorem 12’s arbitrary-modification characteristic for stable, preferred, complete, and admissible semantics, with attack edits weighted by type-pair mass. It leaves the expansion-specific results and the minimal-equivalence characterizations aside.
The strongest mirror I can defend is a high-multiplicity version of argument enforcement. Imagine a large public consultation or online debate in which many participants contribute instances of arguments from a fixed catalogue. A type \(t\) is a complete argument profile for this problem: its argument identity and its attack relations to every other type. The mass \(\mu_t\) is the fraction of argument instances of type \(t\). The plausible regime has a very large number \(N\) of instances but relatively small support \(\tau\), because claims and attack patterns recur.
My lead problem is Mass-Weighted Minimal Attack-Change Enforcement. Its input is a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), an attack relation \(R\subseteq T\times T\), a desired set \(C\subseteq T\), and a semantics \(\sigma\in\{st,pr,co,ad\}\). Find an attack relation \(R'\) and an extension \(E\) of \((T,R')\) under \(\sigma\), with \(C\subseteq E\), minimizing
\[
\sum_{(t,u)\in R\triangle R'}\mu_t\mu_u.
\]
A type-level attack \(t\to u\) applies to every ordered pair of argument instances in those two types. Its cost is the fraction of all pairs affected. In a discrete population with \(n_t\) instances of each type, this is the number of affected pairs divided by \(N^2\). If every argument has its own type, each edit costs \(1/N^2\), so the objective preserves the discrete edit-count optimum up to a common factor.
My anchor is Theorem 12, proved in this paper. It gives an exact characterization of arbitrary-modification enforcement. For any AF \(F\), the stable characteristic of \(C\) is
\[
\min_{C\subseteq E\subseteq A(F)}
\left(
|R(F)\cap(E\times E)|+
|A(F)\setminus R_F^+(E)|
\right).
\]
For each \(\sigma\in\{pr,co,ad\}\), the \(\sigma\)-characteristic is
\[
\min_{C\subseteq E\subseteq A(F)}
\left(
|R(F)\cap(E\times E)|+
|R_F^-(E)\setminus R_F^+(E)|
\right).
\]
Here \(R_F^+(E)\) contains \(E\) and the arguments attacked by \(E\), while \(R_F^-(E)\) contains \(E\) and the arguments attacking \(E\). The first term counts attacks that must be removed to make \(E\) conflict-free; the second counts uncovered arguments for stability, or attackers that still need to be countered for admissibility. The theorem identifies the characteristic with these values; it does not claim a polynomial-time bound or a complexity classification.
The weighted mirror asks whether the same local structure yields an efficient algorithm with masses. For a fixed candidate \(E\), clearing attacks within \(E\) has cost \(\sum_{(t,u)\in R\cap(E\times E)}\mu_t\mu_u\). For stability, each outside type not attacked by \(E\) can be covered by an added attack from the least-mass type in \(E\). For admissibility, each undefended attacker can be countered with an added attack or neutralized by deleting its attacks into \(E\), choosing the cheaper option. Enumerating \(E\supseteq C\) therefore gives an \(O(2^\tau\operatorname{poly}(\tau,L))\) algorithm for this mirror. For preferred and complete semantics, an admissible set extends to a preferred extension, which is complete. This is my derivation for the proposed weighted model, not a result proved in the paper.
My expectation is parameterized tractability in \(\tau\), with the unrestricted-\(\tau\) question left open. The finite-support scan is fixed-parameter tractable, though it does not establish a polynomial-time algorithm in \(\tau\). The uniform, one-type-per-argument case embeds the finite problem, so any hardness of that discrete problem would transfer. The paper itself does not establish such hardness. The next questions are whether the weighted scan can be improved to polynomial time in \(\tau\), and whether allowing edits within only part of a type pair admits a coherent continuum semantics and changes the answer.
This mirror covers Theorem 12’s arbitrary attack modifications for stable, preferred, complete, and admissible semantics. It does not cover the paper’s equivalence results or its distinctions among expansion types.
The weak point is the population interpretation. Arguments are not naturally voters, and repeated argument occurrences may collapse to one argument in ordinary Dung frameworks. The type-level edit also assumes that an attack rule changes uniformly across a pair of types. Still, the model keeps the paper’s central question—how much attack structure must change to enforce a desired set—and its finite blow-up recovers the discrete objective. I think that makes it a plausible, narrow mirror, rather than a claim that all argumentation is a population process.
The proponent has chosen the paper’s strongest anchor: Theorem 12 gives a local formula for the minimum attack changes needed to enforce a set. But the formula is about editing edges in a finite graph whose vertices are named arguments. Its target \(C\) is a set of those particular arguments. The paper gives no complexity classification for this optimization problem; the theorem characterizes its value. A continuous mirror would therefore need to supply a new population model as well as a new computational question.
The proposed “many argument instances” model has a basic aggregation problem. For an argument to belong to a type, its identity and its relations to other arguments must be interchangeable for the question at hand. In a generic AF, attack neighborhoods distinguish vertices, so the number of such types can be close to the number of arguments. Repeated claims with identical neighborhoods offer a possible exception. Yet if duplicate claims are collapsed, their frequency has no role in Dung semantics; if they remain separate vertices, their multiplicity can affect extensions and maximality. The model must choose between erasing the population and changing the argumentation framework.
Treating participants as agents who endorse arguments does not resolve this. The framework’s accepted objects are arguments, not people. A mass of endorsers does not change whether an argument is conflict-free, defended, or in an extension. Making the target “a fraction of participants accepts \(C\)” could be useful, but it adds an aggregation rule such as a threshold and changes the enforcement problem.
The weighted objective is a more serious attempt. It makes an edit to a type pair cost \(\mu_t\mu_u\), as though the attack relation were a dense interaction between every pair of agents in those types. That is a coherent graph-editing model, but it edits an entire block at once. In the one-argument-per-type case it recovers edge count up to a common scale; there is then no multiplicity to aggregate. With a small number of types, the theorem’s extension choices still range over subsets of types, and mass enters the edit costs rather than the extension semantics. This may be worth studying as weighted argumentation, but the continuous population is not what makes enforcement computationally different.
A stronger version could make attacks a measurable relation over an atomless population and minimize the measure of edited pairs. That leads toward graphon-style argumentation. It also forces a semantic choice absent from the finite theorem: Dung’s defense conditions quantify over individual attackers, while an area-based objective assigns zero cost to changes on null sets. An “almost every argument” semantics avoids that mismatch only by changing which attackers matter. Requiring a positive-mass target cohort helps with the vanishing-target problem, but it still makes enforcement a density-level graph problem with newly specified semantics.
So the negative case is that the paper’s central object is a finite relational structure, not a society of interchangeable agents. Every plausible population reading either leaves the AF unchanged and makes mass irrelevant, or introduces block-weighted or measure-theoretic graph editing whose semantics and objective need independent justification. This is not airtight: authors who want to study dense argumentation networks could regard that graphon model as a worthwhile continuation. The weak point in the case against is that such a model can be made coherent; the harder question is whether it is a continuous mirror of this paper’s enforcement problem, rather than a new model of argumentation.
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.