Egalitarian Judgment Aggregation (d4-conf-atal-2021-0218)

Given an agenda \(\Phi\), its admissible judgment set \(\mathcal J(\Phi)\), and a rational finite-support distribution \(\mu\) over \(\mathcal J(\Phi)\), define \(\rho_\mu(K)=\max_{J\in\operatorname{supp}(\mu)}H(J,K)-\min_{J\in\operatorname{supp}(\mu)}H(J,K)\). Decide whether \(\min_{K\in\mathcal J(\Phi)}\rho_\mu(K)\) is divisible by \(4\).

An agenda is an explicitly encoded list \(\Phi=(\varphi_1,\ldots,\varphi_m)\) of propositional formulas, with \(m\geq1\). Its admissible judgments are \(\mathcal J(\Phi)=\{(\alpha(\varphi_1),\ldots,\alpha(\varphi_m)): \alpha\text{ is a truth assignment}\}\); this set is represented implicitly by the formulas.
A society is given by its support: a nonempty list of \(\tau\) distinct admissible judgment types with positive binary rational masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Let \(H\) denote Hamming distance. Collective judgments remain in \(\mathcal J(\Phi)\). Define \(\rho_\mu(K)=\max_{J\in\operatorname{supp}(\mu)}H(J,K)-\min_{J\in\operatorname{supp}(\mu)}H(J,K)\) and \(r(\Phi,\mu)=\min_{K\in\mathcal J(\Phi)}\rho_\mu(K)\).
Is deciding whether \(r(\Phi,\mu)\in4\mathbb Z\) solvable in polynomial time, or is it NP-hard?
For finite profiles, the corresponding divisibility decision problem is \(\Theta_2^p\)-complete, as also stated in the [2023 journal version](https://link.springer.com/article/10.1007/s10458-023-09598-6). No separately verified result for the distribution formulation is available here.

The problem is \(\mathrm{NP}\)-hard, even when \(m=\tau=2\). Using the stated finite-profile theorem, it is in fact \(\Theta_2^p\)-complete under polynomial-time many-to-one reductions.

• The objective depends only on the support.

For any nonempty finite collection of real numbers, the largest absolute difference equals its maximum minus its minimum. Consequently, for every admissible \(K\),

\(\rho_\mu(K)=\max_{J,J'\in\operatorname{supp}(\mu)}|H(J,K)-H(J',K)|.\)

Thus positive masses and repeated occurrences of a judgment do not affect the objective. In particular, \(\tau=1\) always gives \(r(\Phi,\mu)=0\). The hardness below concerns the first nontrivial support size.

• A direct, self-contained proof of \(\mathrm{NP}\)-hardness.

Let \(F\) be an arbitrary propositional satisfiability instance. Introduce fresh variables \(a,b\), and construct the agenda

\(\Phi_F=(a,\ a\lor(b\land F)).\)

Give each of the two support types \(J^0=(0,0)\) and \(J^1=(1,1)\) mass \(\frac12\).

This is a valid society for every \(F\): setting \(a=b=0\) realizes \(J^0\), while setting \(a=1\) realizes \(J^1\). The support types are distinct, their masses are positive, and their masses sum to \(1\).

We now characterize every admissible collective judgment:

• If \(a=1\), the judgment is \((1,1)\).
• If \(a=0\), the judgment is \((0,b\land F)\).
• Therefore \((1,0)\) is impossible, and \((0,1)\) is admissible exactly when \(F\) is satisfiable.

It follows that \(\mathcal J(\Phi_F)=\{(0,0),(1,1)\}\) when \(F\) is unsatisfiable, and \(\mathcal J(\Phi_F)=\{(0,0),(0,1),(1,1)\}\) when \(F\) is satisfiable.

For \(K=(0,0)\), the distances to the two support types are \(0\) and \(2\), so \(\rho_\mu(K)=2\). For \(K=(1,1)\), the distances are \(2\) and \(0\), again giving \(\rho_\mu(K)=2\). For \(K=(0,1)\), both distances are \(1\), giving \(\rho_\mu(K)=0\).

Hence \(r(\Phi_F,\mu)=0\) if \(F\) is satisfiable, and \(r(\Phi_F,\mu)=2\) otherwise. Since \(0\in4\mathbb Z\) and \(2\notin4\mathbb Z\),

\(F\text{ is satisfiable}\ \Longleftrightarrow\ r(\Phi_F,\mu)\in4\mathbb Z.\)

The construction has \(m=\tau=2\), output length \(L=O(|F|+1)\), and polynomial construction time in the encoding length \(|F|\). This proves the requested hardness independently of the finite-profile result.

• Exact transfer of the finite-profile completeness theorem.

The known theorem states that, given an explicitly listed finite profile \(P=(J_1,\ldots,J_n)\), deciding whether

\(\min_{K\in\mathcal J(\Phi)}\max_{1\leq i,j\leq n}|H(J_i,K)-H(J_j,K)|\)

belongs to \(4\mathbb Z\) is \(\Theta_2^p\)-complete. This is Proposition 8 of the [2023 journal article](https://link.springer.com/article/10.1007/s10458-023-09598-6).

To reduce that problem to the present one, retain the agenda, delete duplicate profile types, and assign mass \(\frac1\tau\) to each remaining type. These types are admissible because they came from a valid profile. The masses are positive binary rationals summing to \(1\), each requiring \(O(\log(\tau+1))\) bits. By the identity in the first item, this transformation preserves the objective for every \(K\), and therefore preserves its minimum and the divisibility answer.

For an explicitly listed source profile, deduplication by sorting takes \(O(nm\log(n+1))\) word operations. The output length is \(O(|\Phi|+\tau m+\tau\log(\tau+1))\), hence polynomial in the source length. This proves \(\Theta_2^p\)-hardness for the distribution formulation.

Conversely, replace a distribution by a profile containing each of its \(\tau\) support types once. The same identity preserves the optimum. If the finite-profile convention requires at least two agents and \(\tau=1\), repeat its sole type twice. This transformation takes \(O(L+\tau m)\) time and produces a profile of polynomial length.

Both transformations use the explicitly listed support. Neither expands a rational mass into a corresponding number of voters.

• Upper bound and running times.

Membership in \(\Theta_2^p\) also follows directly. For an integer threshold \(c\), consider the question whether there exists a truth assignment \(\alpha\) whose induced judgment \(K_\alpha\) satisfies \(\rho_\mu(K_\alpha)\leq c\).

This threshold question is in \(\mathrm{NP}\). A certificate is the assignment \(\alpha\) to all variables occurring in the agenda. It has at most \(L\) bits. Evaluate all agenda formulas, compute the \(\tau\) Hamming distances, and take their maximum minus minimum. On a standard word RAM, verification takes \(O(L+\tau m)\) operations; ordinary bit implementations also take polynomial time in \(m,\tau,L\).

Every Hamming distance lies between \(0\) and \(m\), so \(0\leq r(\Phi,\mu)\leq m\). The threshold predicate is monotone in \(c\), and a truth assignment always induces an admissible judgment. Binary search therefore finds the exact optimum using at most \(\lceil\log_2(m+1)\rceil\) queries to this \(\mathrm{NP}\) predicate, with query encodings of length \(O(L+\log(m+1))\) and polynomial deterministic overhead. Since \(m\leq L\), the number of queries is \(O(\log L)\).

Testing the resulting integer for divisibility by \(4\) proves membership in \(\Theta_2^p=\mathrm P^{\mathrm{NP}[O(\log L)]}\). Together with the preceding reduction, this establishes completeness. A polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The output resolves the task correctly. Its self-contained reduction proves \(\mathrm{NP}\)-hardness even when \(m=\tau=2\), and its support-preserving transfer of the stated finite-profile theorem establishes \(\Theta_2^p\)-completeness. I found no major or minor mathematical issues.

• Dependence only on support.

The identity
\[ \max_{J,J'\in\operatorname{supp}(\mu)} |H(J,K)-H(J',K)| = \max_{J\in\operatorname{supp}(\mu)}H(J,K) - \min_{J\in\operatorname{supp}(\mu)}H(J,K) \]
is correct: every absolute difference is at most the range, and a pair attaining the maximum and minimum attains that range. The support is finite and nonempty, so both extrema exist.

Consequently, the masses and repetitions do not affect the objective. The statement that \(\tau=1\) implies \(r(\Phi,\mu)=0\) is also correct.

• Validity of the satisfiability reduction.

The variables \(a,b\) are explicitly fresh, so their values can be chosen independently of any assignment to the variables of \(F\). The agenda contains exactly two explicitly encoded formulas.

Both support types are admissible for every \(F\): the stated assignments realize them without requiring \(F\) to be satisfiable. They are distinct, and their masses satisfy all input requirements. Thus the reduction always produces a valid instance.

The characterization of admissible collective judgments is exhaustive. When \(a=1\), both coordinates equal \(1\). When \(a=0\), the second coordinate is \(b\land F\). Therefore \((1,0)\) is impossible, and \((0,1)\) is attainable exactly when \(F\) is satisfiable. There are no other binary vectors to consider.

• Distance computations and reduction direction.

The distance pairs to the two support types are respectively \((0,2)\), \((2,0)\), and \((1,1)\) for the three potentially admissible collective judgments. Their ranges are therefore \(2\), \(2\), and \(0\), as stated.

Hence the optimum is \(0\) for satisfiable \(F\) and \(2\) for unsatisfiable \(F\). Since \(0\in4\mathbb Z\) and \(2\notin4\mathbb Z\), the equivalence has the correct direction for a many-to-one reduction from satisfiability.

The construction copies \(F\) once and adds constant-size syntax and support data. Its output length and construction time are polynomial in the source encoding length. Fixing \(m=\tau=2\) does not fix the input length: the second formula still contains \(F\). The claimed restricted hardness follows.

• Finite-profile theorem and its transfer.

Proposition 8 of the cited article states the finite-profile divisibility completeness result for the same pairwise distance-gap objective. Its proof explicitly identifies polynomial-time many-to-one hardness. The article uses formula agendas and admissible profiles, matching the relevant source-instance requirements. [2023 journal article](https://link.springer.com/article/10.1007/s10458-023-09598-6)

Deduplication preserves the extrema for every collective judgment. Assigning mass \(1/\tau\) produces positive masses summing to \(1\). Under the standard interpretation of binary rational encoding—binary numerator and denominator—each mass requires \(O(\log(\tau+1))\) bits. The stated output-length and sorting bounds are polynomial.

The reverse transformation likewise preserves every objective value. Repeating the sole support type when the profile convention requires two agents preserves the objective and handles the singleton case correctly. Neither transformation requires expansion according to rational denominators.

• Oracle upper bound.

A truth assignment to the agenda variables is a polynomial-size certificate. It induces an admissible judgment automatically, and formula evaluation followed by the \(\tau\) distance computations verifies the threshold condition in polynomial time. The stated word-RAM bound \(O(L+\tau m)\) is appropriate under standard indexed formula encoding.

The optimum is an integer in \(\{0,\ldots,m\}\). The threshold predicate is monotone, and the threshold \(m\) always succeeds. Binary search over these \(m+1\) possibilities uses at most \(\lceil\log_2(m+1)\rceil\) queries. This also covers \(m=1\).

Since the agenda is explicitly encoded, \(m\leq L\), giving \(O(\log L)\) NP queries with polynomial deterministic overhead. Membership in \(\Theta_2^p\), and therefore completeness together with the transferred hardness theorem, follows.

No additional clarification or repair is required under the standard encoding conventions. The final implication that a polynomial-time algorithm would yield \(\mathrm P=\mathrm{NP}\) follows already from the direct reduction.

⟨structured verdict parsed — rendered above⟩