| paper | d4-conf-atal-2016-0076 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, already for \(k=3\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 8 (General case)
statement extracted from the paper’s text layer
Given a finite argument set \(A\), a fixed irreflexive master attack relation \(\alpha\), a bound \(k\ge 3\), and a rational distribution \(\mu\) over report types \(t=(A_t,D_t)\), does there exist a value set \(V\) with \(|V|\le k\), a common map \(\mathrm{val}:A\to V\), and a preorder \(\succeq_t\) for each \(t\) with \(\mu_t>0\), such that for every \(a,b\in A_t\), \((a,b)\in D_t\) if and only if \((a,b)\in\alpha\) and \(\mathrm{val}(b)\not\succ_t\mathrm{val}(a)\)?
A large debating-platform population represented by report types \(t=(A_t,D_t)\) and rational masses \(\mu_t\). The witness uses one shared master relation \(\alpha\), one shared value assignment \(\mathrm{val}\), and a preorder \(\succeq_t\) per positive-mass type; this is a feasibility question with no objective.
The Proposition 8 reduction uses a different argument set for each pair-type, so it does not establish hardness when all types share the same argument set, a restriction the paper leaves open.
fatal: False
The mirror covers the fixed-master, bounded-value multiagent cases of Propositions 8 and 9. It leaves the single-agent cases, unconstrained cases, and any prevalence-weighted fitting question aside.
The strongest honest mirror is the paper’s multiagent rationalisability problem when the observed views occur in a large population with repeated report types. It mirrors a substantial computational question from the paper, though its weakness is that the exact yes/no question depends on which types occur, not how much mass each has.
Take a fixed argument set \(A\). A type \(t\) is a complete reported framework \((A_t,D_t)\), where \(A_t\subseteq A\) is the set of arguments the agent considers and \(D_t\) is that agent’s defeat relation on \(A_t\). The society is a distribution \(\mu\) over a finite support \(T\): \(\mu_t>0\) is the fraction of people with report \(t\), and the rational masses sum to \(1\). This is plausible for a large online consultation or debating platform about one shared issue, especially when a structured interface or recurring templates produce many repeated reports. There might be hundreds of thousands of participants but only dozens or hundreds of distinct reports.
The type records everything the paper’s input uses about an agent. Preferences are unknowns in the rationalisability witness, not observed input traits. If two people submit the same report, the paper’s question does not require recovering distinct latent preferences for them; a single witnessing preference order explains both. The shared objects are a master attack relation \(\alpha\) on \(A\) and a value assignment \(\mathrm{val}:A\to V\). Each report type has its own preference preorder \(\succeq_t\) over \(V\).
My lead anchor is Proposition 8 (General case), proved in this paper. It states that deciding whether a profile of argumentation frameworks is rationalisable by an AVAF with a given fixed master attack relation and a given upper bound of at least \(3\) on the number of values is NP-complete. The paper proves this by reduction from Graph Colouring.
The corresponding continuous decision problem is Mass Rationalisability with at most \(k\) values. An instance consists of \(A\), a fixed irreflexive master relation \(\alpha\), a rational distribution \(\mu\) over report types \(t=(A_t,D_t)\), and \(k\ge 3\). A solution is a set \(V\) with \(|V|\le k\), a common map \(\mathrm{val}:A\to V\), and one preorder \(\succeq_t\) for every positive-mass type, such that for every \(a,b\in A_t\),
\[
(a,b)\in D_t
\quad\Longleftrightarrow\quad
(a,b)\in\alpha\ \text{and not }\mathrm{val}(b)\succ_t\mathrm{val}(a).
\]
The question is whether such a witness exists for all positive-mass types. This is a feasibility problem, not an optimization problem.
I expect this mirror to be NP-complete, with hardness transferring from the discrete problem (Class B). The paper’s Graph Colouring construction gives each pair of arguments its own two-argument report type; assign each such type equal positive mass. A graph edge forces its corresponding attack to be suppressed, requiring different values at its endpoints. Thus the construction works directly for a rational distribution. Repeating every report type many times in a finite population leaves the distribution and the rationalisability condition unchanged. The hard combinatorics live in the argument set and the bounded number of values, not in the number of people.
A second, independently useful anchor is Proposition 9 (Large bound on values), also proved here. It states that for any fixed constant \(d\), deciding rationalisability under a fixed master attack relation with at most \(|A|-d\) values is polynomial-time solvable. Its continuous mirror is the same Mass Rationalisability problem with \(k=|A|-d\) and fixed \(d\). I expect this version to be tractable as well: the paper enumerates the possible ways to merge \(d\) pairs of arguments into value classes, then checks each resulting fixed value labelling. With \(\tau\) support types, those checks can be performed across the support, giving a running time polynomial in \(|A|\), \(\tau\), and the input bit length. This is an algorithmic anchor, but Proposition 8 is the stronger one for the programme because it starts from a hardness result.
These mirrors cover the paper’s constrained, multiagent rationalisability results about a fixed master attack relation and a bound on the number of values. They do not try to continuize argumentation outcomes, aggregation rules, or the paper’s other cases. The authors should recognize them as their problem: the continuous question asks whether the same common framework and value labelling can explain the population’s reported views under the same defeat semantics.
The weakest point is that the exact all-types question is indifferent to the masses: a type with mass \(1\%\) is just as binding as one with mass \(90\%\). So the input is a continuous population description, but these anchors do not make proportions operational. A natural next question would be maximum-mass rationalisability: find the greatest total mass of report types that one common model can explain, or decide whether it can explain at least a threshold \(q\). That would make prevalence matter directly, though it is a follow-on question rather than the result established by either proposition.
The strongest case against the two proposed anchors is that their continuous versions never use the population’s proportions. Proposition 8 can be phrased over a distribution of reported frameworks, but its witness must explain every type with positive mass. For any two distributions \(\mu\) and \(\nu\) with the same support, rationalisability is identical. Reweighting a report from \(1\%\) to \(90\%\) changes nothing; adding a duplicate person changes nothing. The problem is therefore whether the *set of distinct reports* admits a common explanation. That is a coherent question, but it gives the continuous population no role beyond compressing a finite profile into its support.
Proposition 8’s hardness construction reinforces the concern: it gives a different argument set to each agent, one for each pair of arguments in the graph-colouring instance. Those reports are all distinct. Repeating each type many times preserves the reduction, but the hardness still comes from the catalogue of reports and the argument set, not from population mass. A shared argument set is a plausible regime for an online debate about one issue; the paper leaves the complexity there open. This does not defeat the broader support-based mirror, but it makes the named hardness result a poor demonstration of what continuizing the population adds.
Proposition 9 has the same limitation. Its algorithm checks candidate value assignments against the reports; duplicate reports can be discarded, and their weights are irrelevant. It is a useful result about profile rationalisability, but its continuous restatement does not create a mass-sensitive computational question. The direct translations of Propositions 8 and 9 are thus weak ChoCo contributions: their inputs can be written as distributions, while their semantics and computation depend only on support.
A stronger candidate would ask for the greatest mass of reports one common model can rationalise, or whether at least a fraction \(q\) can be rationalised. That makes prevalence matter and suits noisy consultations. It also changes the paper’s question from explaining the whole profile to fitting a selected share of it. A policy for excluding some reports needs justification; nevertheless, “what fraction of society shares a common value-based explanation?” is a plausible question the authors could recognise.
So the negative case can challenge the exact mirrors on relevance: they test a set of report types, not a population quantity. It cannot honestly rule out every worthwhile mirror. The mass-coverage version remains a live possibility, and the paper gives no basis for saying it would be uninteresting. The case against is strongest when the target is fidelity to the paper’s all-reports rationalisability problem; it is weak as a universal claim.
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.