| paper | d4-conf-aaai-2008-0040 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; the grounded labelling is the unique Pareto-optimal complete labelling. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite argumentation framework \(AF=(A,\rightharpoonup)\) and a rational finite-support distribution \(\mu\) over types \(t=(A_t,\mathrm{reject})\), where \(A_t\subseteq A\), find the complete labellings that are Pareto optimal when each positive-mass type has utility \(u_t(L)=-|out(L)\cap A_t|\).
The population is a distribution \(\mu\) over stakeholder types sharing argument portfolios and rejection-minimizing preferences. The decision is a complete labelling of the fixed framework; Pareto dominance compares utilities across positive-mass types, while \(\mu\)'s proportions do not affect the comparison.
The mirror covers Theorem 3 for rejection-minimizing preferences. It leaves the results for other preference classes and the social-welfare refinements aside.
The positive case is a real one, with an important limit: this paper contains no named complexity result saying that a problem is in P, NP-hard, or otherwise classified. Its strongest usable anchor is a named structural result about welfare outcomes. So the mirror below is credible as a continuous-population problem, but it does not supply the programme’s usual discrete-hardness-versus-continuous-tractability comparison.
A plausible regime is a large public consultation with many people but relatively few stakeholder classes. Each class shares the same portfolio of arguments and the same preference criterion. Take a fixed argumentation framework \(AF=(A,\rightharpoonup)\), and let a type be \(t=(A_t,\mathrm{reject})\), where \(A_t\subseteq A\) is the type’s argument portfolio and members want to minimize how many of their arguments are rejected. A society is a finite-support distribution \(\mu\) over these types, with rational masses \(\mu_t>0\) summing to one. The population can be very large while the number \(\tau\) of distinct types remains small. Assume every argument belongs to some positive-mass type, as fits the paper’s setting of arguments put forward by participating agents.
Call the mirror Continuous Rejection-Minimizing Pareto Labelling. Its instance is \(AF\) and \(\mu\); its possible decisions are the complete labellings \(L\) of \(AF\). Type \(t\)’s utility is \(u_t(L)=-|out(L)\cap A_t|\). A labelling is a solution if it is Pareto optimal: there is no other complete labelling \(L'\) with \(u_t(L')\ge u_t(L)\) for every positive-mass type and strict inequality for at least one such type. In the continuum, requiring a strictly better type to have positive mass captures improvement for a positive measure of people, rather than for a single measure-zero individual.
The anchor is Theorem 3, proved in this paper. It states that when agents have rejection-minimizing preferences, every outcome is either the grounded extension or is Pareto dominated by the grounded extension. Thus the grounded extension is the unique Pareto-optimal outcome. The theorem’s proof uses the fact, cited to Caminada (2006a), that the grounded labelling has a minimal set of out-labelled arguments. In the continuous mirror, that strict improvement benefits every member of at least one positive-mass type, since every argument in the difference is owned by a supported type.
I expect this restricted mirror to be tractable: compute the grounded labelling by iterating the characteristic function, then return it as the sole solution. That is polynomial in the argumentation-framework size; the population masses matter only in establishing which types have positive support. This mirrors Theorem 3’s welfare characterization, not a complexity classification asserted by the paper. Its scope is specifically the rejection-minimizing result, not the paper’s other preference classes or its full discussion of social welfare.
The mirror is plausible to the authors because their model already makes agent type determine both an argument portfolio and a preference criterion; the continuous version groups many agents sharing that complete description. The paper’s existing type-based model supports the high-multiplicity regime rather than disqualifying it. The argumentation framework and its labellings remain discrete: the continuous object is the population distribution.
The weakest point is that Pareto efficiency largely ignores the *amount* of each type: changing positive masses without changing support leaves the comparison unchanged. This is a genuine continuous-population model, but its key theorem is driven by which types are present, not their proportions. Natural next questions are whether mixed preference types yield a useful characterization or efficient way to find the Pareto frontier, and whether mass-weighted utilitarian or egalitarian selection makes the proportions computationally consequential. Neither is an anchor established by this paper.
The proposed anchor does not clear ChoCo’s computational gate. The paper states no named theorem about complexity, nor does it classify an algorithmic problem. Theorem 3 is a welfare characterization for a fixed argumentation framework: it relates rejection-minimizing preferences to the grounded extension. Calling the usual computation of that extension a continuous algorithm does not make the theorem a complexity result about a continuous society.
There is also a more basic problem with this particular mirror. For type \(t\), the proposed utility is \(u_t(L)=-|out(L)\cap A_t|\). Pareto comparisons depend on which types have positive mass, not on their masses: every supported type counts as a participant, however small its share. So the proposed problem’s social order factors through the support of \(\mu\); changing the proportions while keeping that support fixed changes none of its comparisons. That is a continuum degeneration in the model, not merely a prediction that the answer will be uninteresting.
The paper’s fixed argument graph helps explain why. Agents’ portfolios and preferences assess labellings, but the population does not determine which labellings are feasible. A stronger version of this anchor could preserve the rejection-minimizing preferences and use mass-weighted welfare, but then it changes the criterion from Pareto optimality to a cardinal social welfare objective. A broader mixed-type version, such as maximizing \(W_\mu(L)=\sum_t\mu_tu_t(L)\), is more genuinely mass-sensitive, and the paper’s social-welfare discussion makes it a plausible adjacent question. It is not, however, a mirror of Theorem 3, and the paper gives no computational result for it.
So the negative case is strong against the anchor actually offered: its continuous population affects the Pareto comparison only through type presence, and its named theorem is not a complexity result. It is not strong enough to establish the universal claim that no worthwhile mirror exists. The paper’s own discussion of social welfare leaves a plausible mass-sensitive direction open.
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.