| paper | d4-journals-jair-2017-0001 |
| 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}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 9
statement extracted from the paper’s text layer
Given a finite argument set \(\mathcal{A}\), a fixed attack relation \(\alpha\), a bound \(k \ge 3\), and a rational distribution \(\mu\) over reported audience types \(t=(S_t,D_t)\), does there exist a value set \(V\) with \(|V| \le k\), a common labelling \(\lambda:\mathcal{A}\to V\), and a preference preorder \(\succeq_t\) for each \(t\) with \(\mu_t>0\), such that for all \(a,b\in S_t\), \((a,b)\in D_t\) if and only if \((a,b)\in\alpha\) and \(\neg(\lambda(b)\succ_t\lambda(a))\)?
A society is a rational distribution \(\mu\) over audience types \(t=(S_t,D_t)\), where \(S_t\) is the set of arguments considered and \(D_t\) the reported defeat relation. The decision variables are one shared value set and labelling, plus a preference preorder for each supported type; the question is whether all positive-mass types are simultaneously rationalisable.
Exact rationalisability depends only on support, so a rare positive-mass report constrains the common explanation as much as a large cohort; the proponent acknowledges this but does not fully address its significance for the population interpretation.
fatal: False
Covers Propositions 9 and 10; leaves the single-agent characterisations, other tractability cases, and expansion-semantics results unmirrored.
The lead mirror is the paper’s standard rationalisability problem for a population of audiences. Let \(A\) be the finite set of arguments and \(\alpha\) the fixed master attack relation. A type \(t=(S_t,D_t)\) records the arguments an audience considers and the defeat relation it reports on them. The society is a rational distribution \(\mu\) over these types. In a large policy debate or online consultation, many participants could share the same visible arguments and reported defeats, so the population may be large while the number \(\tau\) of distinct types is modest. Here mass means the fraction of participants in a cohort; it is not uncertainty about an individual’s report.
Call the resulting decision problem Continuous Bounded-Value Rationalisability. An instance is \(A\), fixed \(\alpha\), a bound \(k\ge 3\), and the positive-mass types of \(\mu\). The question is whether there are a value set \(V\) with \(|V|\le k\), a common labelling \(\lambda:A\to V\), and a preference preorder \(\succeq_t\) for each supported type such that, for every \(A_1,A_2\in S_t\),
\[
(A_1,A_2)\in D_t
\quad\Longleftrightarrow\quad
(A_1,A_2)\in\alpha\ \text{and}\
\neg\bigl(\lambda(A_2)\succ_t\lambda(A_1)\bigr).
\]
A solution is this common labelling and a preference witness for every supported type. The question is feasibility, as in the paper’s decision version. Giving identical types the same witness loses nothing: their constraints are identical, and preferences are existential rather than observed input.
My lead anchor is Proposition 9, proved in this paper. It says that deciding whether a profile of argumentation frameworks is rationalisable with a given fixed master attack relation and at most \(k\) values is NP-complete when \(k\ge3\), allowing agents to consider different argument sets. Its proof reduces Graph Colouring: orient the graph’s edges to form the fixed attack relation, and create an agent for each pair of arguments who sees just that pair and reports no defeat. Each graph edge then forces its endpoints to receive different values. For the continuous mirror, give each pair type mass \(1/\binom{m}{2}\). A \(k\)-colouring gives a common labelling and suitable preferences; any rationalisation gives a \(k\)-colouring. Thus the mirror is NP-hard even with uniform masses. The hardness is over the argument set and graph structure, so I expect it to transfer (Class B), not dissolve with population size. The finite-to-continuous dictionary is exact: a finite profile yields masses \(n_t/n\), and rational masses can be scaled to integer multiplicities in a high-multiplicity representation.
As a useful second anchor, Proposition 10, also proved here, says that rationalisability is decidable in polynomial time when all agents consider the same argument set, the master attack relation is fixed, and at most two values are allowed. Its continuous counterpart, Continuous Two-Value Common-Agenda Rationalisability, has a measure over types \(t=(A,D_t)\), the same fixed relation \(\alpha\), and asks for a common labelling with at most two values and a preference preorder per supported type satisfying the same condition. This is a plausible large deliberation cohort facing one shared docket, with participants grouped by their reported defeat relations. I expect this case to remain tractable in \(m=|A|\), \(\tau\), and the mass encoding length. Proposition 10’s proof reduces the constraints to a two-colour graph problem. This is a meaningful boundary for the same underlying question, though it is secondary to the hardness anchor.
The authors should recognize both as their rationalisability problem on a society represented by frequencies of indistinguishable audiences. The mirror keeps the shared master framework, global value assignment, type-specific preferences, and observed defeats; it does not replace the society with lotteries over outcomes or ask an axiomatic question.
The main soft spot is that the masses affect feasibility only through which types have positive mass. This is a faithful compression of the paper’s constraints, but it does not create a new continuous-optimization problem or make Proposition 9’s hardness go away. The hardness construction also uses pairwise awareness types, so its high-multiplicity story is strongest for repeated cohorts in a distributed consultation, rather than a single group all considering the same arguments. The paper’s open questions become natural next cases for the mirror: whether hardness persists with two values when awareness sets vary, and whether arbitrary value bounds become tractable when everyone shares an argument set.
The strongest case against these anchors is that the proposed population has no role in either decision criterion beyond deciding which report types are present. Let \(t=(S_t,D_t)\) denote a distinct reported framework. With the master attack relation and value bound fixed, the continuous question asks whether one common labelling and suitable preferences can explain every type with positive mass. Duplicating a report changes nothing, and for identical reports the same preference witness can be reused. Thus
\[
\mathrm{Rat}(\mu)=\mathrm{Rat}(\operatorname{supp}\mu).
\]
This is not an objection that the answer transfers from the discrete case; it is a modelling concern. A type of mass \(\varepsilon>0\) constrains rationalisability as much as a type holding half the population. Letting \(\varepsilon\) tend to zero can change the answer abruptly when the type disappears. The proposed continuum records prevalence but the question ignores it.
For Proposition 9, the graph-colouring construction has a distinct type for each pair of arguments, each with mass \(1/\binom m2\). One can tell a plausible story in which many participants share each pair-specific report, but repeating those reports does not make the population’s composition relevant. The result remains a question about whether the set of distinct reports admits a common explanation. A stronger-looking version might put everyone on the same agenda; that is a natural restriction, but the paper already identifies that finite-profile case as open. Writing the profiles as masses does not supply a population-level quantity or continuous-optimization problem for it.
Proposition 10 has the same problem even in its more plausible shared-agenda setting. A cohort with one positive-mass dissenting report has the same effect on exact rationalisability whether it is tiny or nearly half the society. So the two-value tractability result is a tractable support question, not a frequency-sensitive population result. The difficulty is not that its answer is known or that its complexity comes from the alternatives; it is that the masses do not express anything the theorem asks about.
There is a mass-sensitive extension one could study: maximize \(\sum_{t\text{ explained}}\mu_t\), or ask whether at least \(1-\varepsilon\) of the population can be explained. That could be a worthwhile weighted model-fitting problem, especially if rare reports are treated as outliers. But it replaces the paper’s question—whether the whole observed profile is rationalisable—with a question about tolerated exceptions. It also requires a choice of error threshold or penalty that the paper does not motivate. I can’t rule out that extension as a useful project; that is where the negative case is weakest. For the two results raised, though, the continuous reading adds a distribution that the underlying rationalisability question cannot use.
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.