Answer: \(\mathrm{NP}\)-complete, already for \(k=3\).
Proposition 8 (General case) — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDeciding whether a profile of AF’s 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 an NP-complete problem.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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)\)?
Given a finite argument set \(A\), let \(m=|A|\). The input includes an irreflexive master attack relation \(\alpha\subseteq A\times A\) and a binary-encoded integer \(k\ge 3\).
A society is given by its support: a list of \(\tau\) distinct report types \(t=(A_t,D_t)\), each with a positive binary rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Each \(A_t\subseteq A\), with \(A=\bigcup_t A_t\), and each \(D_t\subseteq A_t\times A_t\) is irreflexive. Reports may use different argument sets.
A rationalisation consists of a finite value set \(V\) with \(|V|\le k\), a common map \(\mathrm{val}:A\to V\), and a preorder \(\succeq_t\) on \(V\) for every supported type. Preorders may allow indifference and incomparability; \(\succ_t\) denotes their strict part.
It must satisfy, for every supported \(t\) and every \(a,b\in A_t\), \((a,b)\in D_t\iff (a,b)\in\alpha\ \land\ \neg(\mathrm{val}(b)\succ_t\mathrm{val}(a))\).
Is deciding whether such a rationalisation exists solvable in polynomial time in \(m,\tau,L\), including the binary encoding of \(k\), or is it \(\mathrm{NP}\)-hard?
For a finite list of agents, this decision problem with a fixed master attack relation and a value bound of at least three is \(\mathrm{NP}\)-complete. With both the master attack relation and the value-labelling fixed, discrete rationalisability is decidable in polynomial time.
The decision problem is \(\mathrm{NP}\)-complete, already for the fixed bound \(k=3\), equal masses, empty defeat relations, and reports containing at most two arguments. Consequently, a polynomial-time algorithm in \(m,\tau,L\) exists only if \(\mathrm{P}=\mathrm{NP}\).
Here the master relation is part of the input, as specified in the question, and is common to all reports.
A preorder is a reflexive, transitive relation. Its strict part satisfies \(x\succ_t y\) precisely when \(x\succeq_t y\) and \(y\not\succeq_t x\).
If \(m=0\), every valid instance is feasible. Assume henceforth that \(m\ge1\).
Suppose a rationalisation exists. Restrict its value set to the image \(V'=\mathrm{val}(A)\), and restrict every preorder to \(V'\times V'\). These restrictions remain reflexive and transitive. Moreover, for any two used values, both directions of the preorder are unchanged, so their strict comparison is unchanged. Thus the restricted rationalisation remains valid and uses \(q=|V'|\le\min(k,m)\) values.
After renaming those values, a certificate consists of:
The verifier checks reflexivity and transitivity of each matrix. It then checks, for every \(a,b\in A_t\), the equivalence
\((a,b)\in D_t\iff (a,b)\in\alpha\land\neg\bigl(S_t[f(b),f(a)]\land\neg S_t[f(a),f(b)]\bigr)\).
The certificate uses \(O(m\log(m+1)+\tau m^2)\) bits. Transitivity checks take \(O(\tau m^3)\) Boolean operations, and the report checks take \(O(\tau m^2)\).
Crucially, the verifier compares \(q\) with the binary-encoded \(k\); it never allocates a structure of size \(k\). Input validity, including positivity and exact normalization of rational masses, can also be checked in polynomial time using exact integer arithmetic. The product of all input denominators has bit length bounded by their total input bit length.
Therefore the problem belongs to \(\mathrm{NP}\).
We use the standard theorem that deciding whether a finite simple undirected graph admits a proper colouring with at most three colours is \(\mathrm{NP}\)-complete. See [Garey, Johnson, and Stockmeyer, *Some simplified NP-complete graph problems*](https://doi.org/10.1016/0304-3975%2876%2990059-1).
Let \(G=(U,E)\) be such a graph. We may assume \(U\ne\varnothing\): adding an isolated vertex preserves three-colourability. Fix an ordering of \(U\).
Construct the instance as follows:
These types are distinct: different edges have different endpoint sets, different singleton types have different vertices, and singleton sets differ from two-element sets. Their argument sets cover \(A\), their masses are positive and sum to one, and both the master relation and every report relation are irreflexive.
The construction has polynomial size. In particular, each mass has a binary representation of length \(O(\log(\tau+1))\).
Suppose the constructed instance has a rationalisation.
Consider an edge \(\{u,v\}\in E\), with \(u<v\). In its report, \((u,v)\in\alpha\) but \((u,v)\notin D_{t_{\{u,v\}}}\). The required equivalence therefore forces
\(\mathrm{val}(v)\succ_{t_{\{u,v\}}}\mathrm{val}(u)\).
The strict part of any preorder is irreflexive: \(x\succ_t x\) would require both \(x\succeq_t x\) and its negation. Hence \(\mathrm{val}(u)\ne\mathrm{val}(v)\).
This holds for every graph edge. The value map therefore gives a proper colouring using at most three colours.
Conversely, suppose \(c:U\to\{1,2,3\}\) is a proper colouring. Set \(V=\{1,2,3\}\) and \(\mathrm{val}=c\).
For the report corresponding to an edge \(\{u,v\}\), with \(u<v\), define
\(\succeq_{t_{\{u,v\}}}=\{(x,x):x\in V\}\cup\{(c(v),c(u))\}\).
Because the colouring is proper, \(c(v)\ne c(u)\). This relation is reflexive and transitive. To verify transitivity, compositions involving an identity pair preserve the other pair; two nonidentity pairs cannot compose, because that would require \(c(u)=c(v)\). Also, the reverse pair \((c(u),c(v))\) is absent. Thus \(c(v)\succ_{t_{\{u,v\}}}c(u)\).
Within this report’s argument set, the only master attack is \((u,v)\). That attack is suppressed by the strict comparison just established. Every other ordered pair is absent from \(\alpha\), so the required equivalence makes it absent from the defeat relation as well. The resulting defeat relation is exactly \(\varnothing\), as required.
For each singleton report, use the identity preorder on \(V\). Its only argument pair is diagonal, and the master relation is irreflexive, so its defeat relation is likewise empty.
These choices rationalise every supported type.
We have proved that \(G\) is three-colourable if and only if the constructed support instance is rationalisable with \(k=3\). This establishes \(\mathrm{NP}\)-hardness; membership proved above establishes \(\mathrm{NP}\)-completeness.
The masses do not change this conclusion. Feasibility requires a suitable preorder for each supported report, independently of its positive mass. The reduction uses only \(\tau=|E|+|U|\) explicitly listed types and equal masses of polynomial bit length. It requires neither expansion into individual agents nor enumeration of possible report types.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct: the decision problem is \(\mathrm{NP}\)-complete, including when \(k=3\), all masses are equal, all defeat relations are empty, and every report contains at most two arguments. No major or minor mathematical issues were found.
The proof addresses the support representation specified in the task. It correctly treats \(\alpha\) as an input relation common to every report, while allowing each report its own preorder on the common value set. Its definition of the strict part,
\(x\succ_t y\) exactly when \(x\succeq_t y\) and \(y\not\succeq_t x\), agrees with the task.
Restricting the value set to \(\mathrm{val}(A)\) preserves reflexivity and transitivity. For every pair of used values, both directed relation entries remain unchanged, so the strict comparison remains unchanged as well. Consequently, every rationalisation constraint is preserved. The bound \(q\le\min(k,m)\) follows directly.
The treatment of \(m=0\) is also valid: there are no argument pairs imposing constraints, and a value set satisfying the bound can be chosen.
The certificate contains enough information to reconstruct a candidate rationalisation. Reflexivity and transitivity are precisely the required preorder conditions; neither totality nor antisymmetry is required.
The displayed verification formula correctly tests whether the target value strictly exceeds the source value. Checking it for every ordered pair in each \(A_t\) covers attacks, nonattacks, and diagonal pairs. In particular, a defeat outside \(\alpha\) would be rejected.
The stated certificate bound \(O(m\log(m+1)+\tau m^2)\) is valid. Encoding \(q\) adds only \(O(\log(m+1))\) bits. The transitivity and report checks have the claimed bounds \(O(\tau m^3)\) and \(O(\tau m^2)\), respectively. Comparing \(q\) with binary-encoded \(k\) avoids any dependence polynomial in the numerical magnitude of \(k\).
The normalization claim for rational masses is sound: the product of the denominators has bit length bounded by the sum of their input bit lengths, so exact arithmetic remains polynomial in \(L\). This establishes membership in \(\mathrm{NP}\).
The cited theorem is stated precisely enough: proper three-colourability of finite simple undirected graphs is \(\mathrm{NP}\)-complete. The cited [Garey–Johnson–Stockmeyer paper](https://doi.org/10.1016/0304-3975%2876%2990059-1) supports this hardness statement. The reduction uses graphs satisfying those hypotheses.
Adding an isolated vertex preserves three-colourability and ensures \(\tau>0\). Orienting each edge by a vertex ordering produces an irreflexive master relation. Simplicity of the source graph ensures distinct edge endpoint sets, so the edge report types are distinct. Singleton types are distinct from one another and from edge types, and they ensure that the report argument sets cover \(A\).
The equal masses \(1/\tau\) are positive and sum to one. Each has polynomial encoding length, and the number of reports is polynomial in the source graph size. Thus the construction is a valid polynomial reduction.
For an oriented graph edge \((u,v)\), the corresponding report contains the master attack but omits its defeat. Substituting these facts into the required equivalence forces
\(\mathrm{val}(v)\succ_t\mathrm{val}(u)\).
The strict part is irreflexive, so these values must differ. Applying this argument separately to every graph edge shows that the common value map is a proper colouring. The bound \(|V|\le3\) supplies the required colour bound. No consistency between different reports’ preorders is needed.
The proposed edge-report relation consists of the identity relation together with \((c(v),c(u))\). Proper colouring makes this added pair nonidentity. The supplied transitivity check is complete: identity pairs cause no difficulty, and two copies of the sole nonidentity pair cannot compose because \(c(u)\ne c(v)\).
The reverse pair is absent, so the required strict comparison holds. Within the two-argument report, the only master attack is the oriented graph edge, and this comparison suppresses it. Every remaining ordered pair is absent from \(\alpha\), yielding exactly the prescribed empty defeat relation.
For singleton reports, the only ordered argument pair is diagonal. Irreflexivity of \(\alpha\) therefore gives the required empty defeat relation. All preorders are defined on the same value set, as required.
Both directions of the reduction are established. Hardness already holds in the restricted family with \(k=3\), and the certificate argument covers the general binary-encoded bound. Together they establish \(\mathrm{NP}\)-completeness.
The discussion of masses is accurate: the feasibility constraints depend on which types are supported, independently of their positive masses. The reduction uses an explicit polynomial-sized support and requires no expansion into individual agents. The conclusion that a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\) follows.
No additional clarification or repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.