Answer: \(\mathrm{NP}\)-hard; using the stipulated discrete hardness theorem, \(\Delta_2^p\)-complete.
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe model checking problem for judgment aggre- gation logic, assuming the representation of JARs described above, is Δp 2-hard; it is np-hard even if the formula to be checked is of the form ψ, where ψ contains no further □or operators.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite agenda \(A\), underlying logic \(L\), roles \(R\) with fixed rational shares \(q_r\), a finite-support rational society \(\mu_0\) over types \((r,J)\) with \(J\in J(A,L)\), an agenda item \(p\), a formula \(\phi\), and a polynomial-time representation of a discrete rule \(f\), decide whether \(\mathcal F_f,\mu_0,p\models\phi\). Define \(D_r(\mu)\) as the tie-broken judgment set of greatest mass within role \(r\), set \(\mathcal F_f(\mu)=f(D_1(\mu),\ldots,D_n(\mu))\), interpret each role atom using \(D_r(\mu)\), and let \(\Box\) range over all rational societies with those role shares.
Take the underlying logic \(\mathsf L\) to be classical propositional logic. Let \(A\) be a nonempty finite agenda consisting of formula–negation pairs, with \(m=|A|\), and let \(J(A,\mathsf L)\) denote its complete, consistent judgment sets; assume this set is nonempty.
Let \(R=\{1,\ldots,n\}\), where \(n\geq2\), with positive binary rational shares \(q_r\) satisfying \(\sum_r q_r=1\). A society \(\mu\) is a rational probability distribution on \(R\times J(A,\mathsf L)\) satisfying \(\sum_J\mu(r,J)=q_r\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types.
Order the agenda as part of the input. Define \(D_r(\mu)\) as the judgment set maximizing \(\mu(r,J)\), breaking ties by the lexicographically least membership vector in that order; absent types have mass zero.
The input rule \(f:J(A,\mathsf L)^n\to J(A,\mathsf L)\) is represented by a Boolean circuit on judgment-set membership vectors, promised to return an admissible judgment set on every admissible profile. Set \(\mathcal F_f(\mu)=f(D_1(\mu),\ldots,D_n(\mu))\).
Formulas have grammar \(\phi::=r\mid\sigma\mid h_a\mid\neg\phi\mid(\phi\land\phi)\mid\Box\phi\mid\blacksquare\phi\), with \(r\in R\) and \(a\in A\). At \((\mu,p)\), atoms \(r,\sigma,h_a\) mean respectively \(p\in D_r(\mu)\), \(p\in\mathcal F_f(\mu)\), and \(p=a\); Boolean connectives have their usual semantics.
The operator \(\Box\) quantifies over every rational society with the prescribed role shares, keeping the agenda item fixed; \(\blacksquare\) quantifies over every agenda item, keeping the society fixed. Neither operator changes the rule or shares.
Given these data, an initial society \(\mu_0\), \(p\in A\), and \(\phi\), is deciding \(\mathcal F_f,\mu_0,p\models\phi\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,n,|\phi|\), and the total input bit length \(L\).
Discrete judgment aggregation model checking with succinct polynomial-time rule evaluation is \(\Delta_2^p\)-hard, and is already \(\mathrm{NP}\)-hard for \(\Diamond\psi\) with no further profile modalities, where \(\Diamond=\neg\Box\neg\). [Verified discrete result](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/jaamas2011a.pdf).
No result settling this exact rational-society model was located.
The problem is \(\mathrm{NP}\)-hard, even with \(\,n=\tau=2\), equal shares, an agenda of independent propositional atoms and their negations, and the fixed formula \(\Diamond\sigma\).
Moreover, using the discrete \(\Delta_2^p\)-hardness result stipulated in the question, the full problem is \(\Delta_2^p=\mathrm P^{\mathrm{NP}}\)-complete. The rational societies introduce no additional semantic complexity: every admissible discrete profile is realizable, and the language observes a society only through that profile.
All complexity statements below concern the promised valid inputs.
Write \(\mathcal J=J(A,\mathsf L)\), and define the effective profile of a society by
\[ \pi(\mu)=(D_1(\mu),\ldots,D_n(\mu)). \]
Because \(q_r>0\), some type belonging to role \(r\) has positive mass. Consequently, the maximum defining \(D_r(\mu)\) is positive, so absent types cannot attain it. Thus \(D_r(\mu)\) can be computed entirely from the supplied support, including the prescribed lexicographic tie-breaking.
Lemma 1. For every profile \(\gamma=(J_1,\ldots,J_n)\in\mathcal J^n\), there is a rational society \(\mu_\gamma\) with support size exactly \(n\) such that \(\pi(\mu_\gamma)=\gamma\).
Proof. Define
\[ \mu_\gamma(r,J)= \begin{cases} q_r,&J=J_r,\\ 0,&J\ne J_r. \end{cases} \]
The masses are rational, positive on exactly \(n\) distinct role–judgment types, and sum to \(\sum_r q_r=1\). Each role has the required marginal \(q_r\). For role \(r\), \(J_r\) is the unique positive-mass judgment set, hence the unique maximizer. Therefore \(D_r(\mu_\gamma)=J_r\). \(\square\)
Let \(f,\gamma,p\models_{\mathrm{disc}}\theta\) denote the corresponding discrete semantics, in which \(\Box\) quantifies over \(\mathcal J^n\) and \(\blacksquare\) quantifies over \(A\).
Lemma 2. For every society \(\mu\), item \(p\), and formula \(\theta\),
\[ \mathcal F_f,\mu,p\models\theta \quad\Longleftrightarrow\quad f,\pi(\mu),p\models_{\mathrm{disc}}\theta. \]
Proof. We use structural induction on \(\theta\).
For role atoms, the equivalence is the definition of \(\pi\). For \(\sigma\), it follows from \(\mathcal F_f(\mu)=f(\pi(\mu))\). For \(h_a\), both semantics test \(p=a\). Negation and conjunction preserve the induction hypothesis.
For \(\blacksquare\psi\), both semantics quantify over precisely the same items \(a\in A\), while retaining respectively \(\mu\) and \(\pi(\mu)\). Apply the induction hypothesis at every such item.
For \(\Box\psi\), the induction hypothesis gives
\[ \mathcal F_f,\mu,p\models\Box\psi \quad\Longleftrightarrow\quad \text{for every rational society }\nu,\ f,\pi(\nu),p\models_{\mathrm{disc}}\psi. \]
Every \(\pi(\nu)\) is admissible, and Lemma 1 shows that every admissible profile occurs as some \(\pi(\nu)\). The last condition is therefore exactly the discrete interpretation of \(\Box\psi\). \(\square\)
In particular, rational mass precision, support multiplicity, and tie-breaking do not change the set of profiles quantified over.
We give a reduction from propositional satisfiability that is independent of the cited discrete theorem.
Let \(G(x_1,\ldots,x_t)\) be a SAT instance. A dummy variable may be added to ensure \(t\geq1\). Introduce a fresh atom \(y\), and take
\[ A=\{x_i,\neg x_i:1\leq i\leq t\}\cup\{y,\neg y\}. \]
Thus \(m=2(t+1)\). Since all agenda issues are independent atoms, admissible judgment sets correspond exactly to truth assignments to \(x_1,\ldots,x_t,y\).
Set \(n=2\) and \(q_1=q_2=1/2\). Define \(f\) by the following output choices:
This is a Boolean circuit of size \(O(|G|+t)\). Its output specifies a truth assignment to the independent agenda atoms, so it is admissible on every admissible input profile. The rule promise is therefore satisfied.
Let \(J^-\) contain all the negative agenda items. Supply the initial society
\[ \mu_0(1,J^-)=\mu_0(2,J^-)=1/2, \]
which has \(\tau=2\). Choose \(p=y\) and \(\phi=\Diamond\sigma=\neg\Box\neg\sigma\).
We claim that
\[ G\text{ is satisfiable} \quad\Longleftrightarrow\quad \mathcal F_f,\mu_0,y\models\Diamond\sigma. \]
If \(G\) is satisfiable, choose an admissible \(J_1\) whose \(x_i\)-choices give a satisfying assignment, and choose any admissible \(J_2\). Lemma 1 realizes this profile as a society. By construction, its aggregate accepts \(y\), witnessing \(\Diamond\sigma\).
Conversely, a society witnessing \(\Diamond\sigma\) has \(y\in f(D_1(\mu),D_2(\mu))\). The definition of \(f\) then says that role \(1\)'s \(x_i\)-choices satisfy \(G\).
The construction has polynomial input length. This proves the stated restricted \(\mathrm{NP}\)-hardness. Consequently, a polynomial-time algorithm for the full problem would imply \(\mathrm P=\mathrm{NP}\).
Put \(s=|\phi|\), and let \(b\leq s\) be the number of occurrences of \(\Box\).
For each occurrence \(u=\Box\psi\), its truth value depends on the agenda item but not on the current society. We compute its table
\[ T_u(a)= \begin{cases} 1,&f,\gamma,a\models_{\mathrm{disc}}\Box\psi,\\ 0,&\text{otherwise}, \end{cases} \qquad a\in A, \]
processing occurrences from the inside out.
Suppose all strict descendant \(\Box\)-occurrences have already been tabulated. For each \(a\), ask whether there exists an admissible profile \(\gamma\) at which \(\psi\) is false, interpreting descendant occurrences using their tables. Negating this existential answer gives \(T_u(a)\).
This existential question belongs to \(\mathrm{NP}\). To verify this explicitly, let \(v\) be the number of distinct propositional variables occurring in the agenda. Guess one assignment to these variables for each role, using \(nv\) bits. Evaluate every agenda formula under each assignment to obtain the profile.
These guesses cover exactly all admissible profiles:
Evaluate \(f\) once on the guessed profile. After replacing descendant \(\Box\)-occurrences by their tables, the remaining formula has only Boolean connectives and \(\blacksquare\). It can be evaluated by storing, for each subformula, its truth values at all \(m\) agenda items. A \(\blacksquare\)-node takes the conjunction of its child's \(m\) entries. Thus arbitrary nesting of \(\blacksquare\) does not require repeated branching.
If \(C\) is the circuit size, verification takes polynomial time, with a basic-operation bound
\[ O(nL+nm+C+ms). \]
There are at most \(mb\leq ms\) oracle queries. Once their answers are tabulated, evaluate \(\phi\) at \(\pi(\mu_0),p\) by the same finite-item computation. Hence the full problem belongs to \(\mathrm P^{\mathrm{NP}}\).
The same certificate argument proves that the fragment \(\Diamond\psi\), where \(\psi\) has no profile modalities, belongs to \(\mathrm{NP}\). Together with Section 2, that fragment is \(\mathrm{NP}\)-complete.
The following bounds distinguish the input support size \(\tau\) from the number of possible judgment sets.
Scan the \(\tau\) support entries, retaining each role's greatest mass and lexicographically least judgment vector among ties. Comparing binary rational masses uses cross-multiplication; schoolbook arithmetic gives the conservative bound
\[ O\bigl(\tau(m+L^2)+nm\bigr). \]
There is no enumeration of absent types.
If \(\phi\) contains no \(\Box\), the complete computation therefore takes
\[ O\bigl(\tau(m+L^2)+nm+C+ms\bigr) \]
basic operations, apart from polynomial indexing overhead. In particular, this fragment is polynomial-time solvable.
For unrestricted formulas, the oracle algorithm uses the same preprocessing, polynomial additional work in \(L,m,n,s\), and at most \(ms\) \(\mathrm{NP}\)-oracle calls.
Let \(k=|\mathcal J|\). With \(m/2\) formula–negation pairs,
\[ 1\leq k\leq 2^{m/2}. \]
Enumerate all \(2^v\) truth assignments to agenda variables, evaluate their membership vectors, and deduplicate them. As proved above, this produces exactly \(\mathcal J\).
Next enumerate its \(k^n\) profiles and evaluate the rule once per profile. Compute a truth table for every subformula on all \(k^n m\) profile–item states. At a \(\Box\)-node, conjoin over profiles; at a \(\blacksquare\)-node, conjoin over items.
A basic-operation bound is
\[ O\bigl( \tau(m+L^2)+nm+2^vL+ k^n(C+nm+ms) \bigr). \]
Allowing polynomial overhead for bit-level indexing, a conservative deterministic bit-time bound is
\[ \bigl(\tau+2^v+2^{mn/2}\bigr)\operatorname{poly}(L), \qquad v\leq L. \]
The exponential profile count concerns possible societies, not the \(\tau\) types listed in the initial society. Indeed, the hardness construction has initial support size only two.
The discrete \(\Delta_2^p\)-hardness theorem supplied in the question transfers through Lemma 2. Given a discrete initial profile, use equal shares \(q_r=1/n\) and place mass \(1/n\) on its judgment set for each role. This produces a support-\(n\) society of polynomial encoding length, preserving every formula's truth.
The cited construction uses dictatorship, \(f(J_1,\ldots,J_n)=J_1\), which has an immediate Boolean-circuit representation and satisfies the admissibility promise. Thus its rule representation fits the present input model. [Ågotnes, van der Hoek and Wooldridge, Theorem 2](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/jaamas2011a.pdf).
Taking that stipulated discrete theorem as a premise, the transferred lower bound and Section 3 give \(\Delta_2^p\)-completeness. The requested \(\mathrm{NP}\)-hardness conclusion also has the independent complete proof in Section 2.
⟨structured verdict parsed — rendered above⟩
The output resolves the requested question: the rational-society model is \(\mathrm{NP}\)-hard, including the stated restriction \(n=\tau=2\). Its stronger \(\Delta_2^p\)-completeness claim is also supported, taking the discrete hardness theorem supplied in USER_TASK as a premise. I found one minor omission in the justification of the explicit deterministic running time.
For each role \(r\), the marginal condition and \(q_r>0\) imply that some supplied type has positive mass. Since the support is finite, a positive maximum exists. Every absent type has mass zero and therefore cannot maximize the mass.
Consequently, scanning the supplied support suffices to compute \(D_r(\mu)\). The proposed comparison procedure also implements the specified lexicographic tie-breaking correctly. This argument does not assume that \(\tau\) counts all possible types.
The construction assigns mass \(q_r\) to \((r,J_r)\). These are exactly \(n\) distinct types because their role coordinates differ, even when several \(J_r\) are equal.
All masses are rational and positive, the role marginals are correct, and the total mass is one. Each \(J_r\) is its role’s unique positive-mass judgment set and hence its unique maximizer. No tie-breaking issue arises.
The construction also has polynomial encoding length: it copies the supplied shares and the profile membership vectors.
The atomic and Boolean cases follow from the definitions. The item-modality case preserves the same society/profile and quantifies over the same finite agenda.
In the profile-modality case, the induction hypothesis is applied to every quantified society. Lemma 1 supplies the required surjectivity onto all admissible profiles. Thus neither direction of the equivalence loses possible witnesses or universal cases.
This establishes equivalence for arbitrarily nested formulas. Crucially, the quantified societies are unrestricted by the initial support size; the proof correctly uses the semantics specified in USER_TASK.
The independent-atom agenda makes admissible judgment sets exactly the assignment membership vectors. The circuit copies the first role’s choices on the original variables, computes \(G\) for the fresh positive item, and outputs complementary choices for every negative item. Its output is therefore admissible on every admissible profile, satisfying the rule promise.
The initial society has exactly two positive types, the shares are valid, and the queried item belongs to the agenda. The formula is fixed.
Both implications are justified: a satisfying assignment yields an admissible profile realizable by Lemma 1, while any witnessing society supplies a first-role assignment satisfying \(G\). Adding an unused variable handles the stated variable-count edge case without changing satisfiability.
The construction has polynomial size. This independently establishes the requested \(\mathrm{NP}\)-hardness, without relying on the external theorem.
Each profile-box occurrence is independent of the current profile, although its truth can depend on the current agenda item. Computing an item-indexed table is therefore appropriate.
Processing strict descendant boxes first removes all remaining profile quantification from each oracle verifier. Guessing one propositional assignment per role gives polynomial-size certificates. The two stated coverage properties hold in classical propositional logic: assignments induce admissible judgments, and every complete consistent judgment set has a satisfying assignment whose agenda membership vector agrees with it.
Circuit evaluation is polynomial. The finite-item dynamic program correctly handles arbitrary nesting of the item modality without exponential branching. The stated verifier bound is conservative, and there are at most \(mb\leq m|\phi|\) oracle queries.
The same reasoning validates membership in \(\mathrm{NP}\) for the stated diamond fragment. Combined with the direct reduction, its \(\mathrm{NP}\)-completeness claim follows.
Rational comparison by cross-multiplication is exact. With operands bounded by the total input length, the stated schoolbook bound is conservative. The additional membership-vector comparisons and profile initialization are accounted for.
The bound \(1\leq k\leq 2^{m/2}\) follows from completeness and consistency on the agenda’s formula–negation pairs. Enumerating propositional assignments covers all admissible judgment sets. Enumerating profiles and evaluating subformulas on all profile–item states gives the stated exponential dependence.
Minor issue: the term \(2^vL\) includes enumeration and deduplication, but the deduplication implementation and its cost are not specified. An unrestricted comparison-based implementation need not satisfy that particular basic-operation bound.
Minimum clarification: state the deduplication procedure and justify that its total cost fits the displayed bound. This is a routine implementation clarification; it does not affect the complexity classification.
The cited theorem concerns the same discrete modalities and gives the stipulated stronger hardness. Its construction uses the rule that copies the first agent’s judgment, which fits the circuit representation and admissibility promise here. These details are confirmed in [Theorem 2 and its proof](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/jaamas2011a.pdf).
Encoding a discrete initial profile using equal positive shares and one supported type per role preserves formula truth by Lemma 2 and has polynomial length. Together with the established upper bound, this supports the claimed completeness result. No assertion that arbitrary succinct rule representations automatically translate to small circuits 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.