| paper | d4-journals-jair-2010-0031 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: The exact optimization is polynomial-time solvable, and the budget decision version belongs to \(\mathrm{P}\). It is not NP-hard unless \(\mathrm{P}=\mathrm{NP}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 1(6)
statement extracted from the paper’s text layer
Given a rational distribution \(\mu\) over types \(t\), where each type specifies a finite framework \(G_t\), a claim \(q_t\), interactions \(I_t\) for a proposed argument \(z\), and cost \(c_t\), choose mass \(x_t\in[0,\mu_t]\) to receive \(z\) with interactions \(I_t\). Let \(b_t\) and \(g_t\) indicate whether \(q_t\) is in the grounded extension before and after addition. What minimum \(\sum_t c_tx_t\) achieves accepted mass \(\sum_t((\mu_t-x_t)b_t+x_tg_t)\ge\theta\), or is the target infeasible?
Types are complete individual frameworks with their claims, response to the proposed argument, and costs; the society is the rational mass vector \(\mu\). The decision is how much mass of each type receives the argument, and the objective is minimum total cost subject to the target grounded-acceptance share.
The campaign optimization couples otherwise independent framework computations, so its tractability comes largely from a new allocation wrapper; the paper’s multi-agent discussion supports the setting but does not itself study bulk delivery or costs.
fatal: False
The mirror covers grounded acceptance after adding one argument across framework types; it leaves the paper’s preferred-semantics results and its structural classifications of extension-set changes aside.
The best positive case is narrow: Grounded Acceptance Mass after Argument Addition. Its algorithmic anchor is Proposition 1(6), cited from Dung (1995), not proved by these authors: for finite \(R\), the grounded extension can be computed by iteratively applying the characteristic function \(F\), starting from the empty set. The paper does not state a complexity classification for its argument-addition problems. Still, this algorithm implies polynomial time on a finite attack graph: the iteration can strictly grow only finitely many times, and each application of \(F\) is computable in polynomial time. If the anchor rule requires an explicit “in P” statement, rather than an explicitly given algorithm with a polynomial bound, then the paper has no qualifying anchor.
Here is a concrete population mirror of that computation combined with the paper’s argument-addition operation. Consider many people evaluating the same claim, each using an argumentation framework to organize their reasons. A person’s type \(t\) specifies their complete framework \(G_t=(A_t,R_t)\), their corresponding claim \(q_t\), their response to a proposed argument \(z\) (the interactions \(I_t\)), and the cost \(c_t\) of reaching them. The society is a rational distribution \(\mu\) over the \(\tau\) supported types. This fits settings such as large-scale standardized appeals or deliberations where many people use a small number of recurring argument templates.
The instance also gives a target acceptance share \(\theta\). Choose \(x_t\in[0,\mu_t]\), the mass of type \(t\) to receive \(z\), adding \(z\) and \(I_t\) to each recipient’s framework. Let \(b_t\) indicate whether \(q_t\) belongs to the grounded extension before the addition, and \(g_t\) whether it belongs afterward. The question is to minimize \(\sum_t c_t x_t\), subject to
\[ \sum_t\bigl((\mu_t-x_t)b_t+x_tg_t\bigr)\ge\theta. \]
A solution is an exact rational vector \(x\) and its cost, or a report that the target is infeasible. Proposition 1(6) computes the grounded extension for each type before and after the change; the remaining optimization is a linear program. The expected classification is tractable, with running time polynomial in the supported types, their framework sizes, and the rational input length.
The population regime is plausible when many people share the same complete reasoning template and cost: the number of people can be large while \(\tau\) stays moderate. A finite election with counts \(n_t\) corresponds to \(\mu_t=n_t/n\); the continuous version allows the campaign to reach fractional mass within a type. The paper’s introduction discusses argument exchange among agents and choosing arguments to achieve a desired outcome, which gives this application some foothold. Its Proposition 8 also gives a relevant local guarantee under grounded semantics: if the added argument is not attacked by the original framework, it belongs to the new grounded extension.
This mirror covers only aggregate acceptance of a designated claim under grounded semantics after one argument addition. It does not mirror the paper’s full study of preferred extensions or structural changes to the extension set. Its weakest point is that the paper models one argumentation framework, while this proposal places a framework inside each person and aggregates across people. The cited algorithm is also a standard result about grounded semantics, not a new complexity result for the paper’s change operation. The case survives only if the authors would accept individual reasoning frameworks and bulk argument delivery as a natural high-multiplicity use of their addition model.
The strongest anchor is Proposition 1(6): it gives an iterative algorithm for computing the grounded extension of a finite framework. That is a real computational foothold, but it is not a complexity result about argument addition. The paper imports it from Dung and gives no complexity analysis of its change operation or algorithm for finding an addition that achieves a desired property. Proposition 8 is closer to the paper’s subject, but only gives a sufficient condition for the new argument to enter the grounded extension. Neither result, by itself, studies a population.
The proposed population of repeated frameworks is the best route to a mirror, and it is not inherently implausible. Many people or cases could share a reasoning template. But it leaves a basic choice about what the population represents. If they share one framework, repeating an argument or its proponent does not create fractional arguments: the framework records a set of arguments and attacks, and its semantics responds to their presence, not their mass. If they instead have separate frameworks, the addition is evaluated independently in each one. A type then contains a whole framework, its target claim, and its response to the proposed argument.
In that second version, Proposition 1(6) computes each type’s before-and-after status, and Proposition 8 can identify some of those outcomes from a local condition. The aggregate optimization then acts on those precomputed outcomes. For example, if \(\Delta_t\) is the change in acceptance for type \(t\), choosing mass \(x_t\) changes the aggregate by \(\sum_t x_t\Delta_t\). With per-type costs and a target share, the remaining problem is a small fractional allocation problem. It is well-posed, but its coupling comes from a newly added population campaign objective; the paper’s argumentation results supply independent type-level inputs. The same wrapper could be placed around almost any efficiently computed per-instance predicate.
That distinction matters here because the paper’s object is one framework and the effect of adding one argument to it. Its introduction does mention agents, dialogue strategies, and achieving goals, which gives an aggregate campaign variant some foothold. But distributing an argument across many independent frameworks is a different problem from changing one shared dialogue. I would reject the proposed formulation as a strong mirror of the paper’s named results: its continuous tractability comes from divisible reach and type-level accounting, not from continuizing the paper’s study of argument addition.
This negative case is strongest on programme fit and weakest on the authors’ recognition gate. The authors’ interest in multi-agent settings could make an aggregate campaign question attractive as a follow-on problem. So the paper gives little support for a continuous mirror of its core results, but I cannot honestly claim that no plausible scenario could yield a worthwhile adjacent problem.
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.