Judgment Aggregation with Rationality and Feasibility Constraints (d4-conf-atal-2018-0021)

Given a finite alternative set \(X\) and a rational distribution \(\mu\) over complete ranking types \(r\in X!\), represented by its nonzero support, return all \(x\in X\) maximizing \(B_\mu(x)=\sum_r\mu_r|\{y\in X:x\succ_r y\}|\); equivalently, return the \(Winner\)-feasible judgments maximizing expected agreement under \(\mathrm{max\text{-}sum}\).

Let \(X\) be a nonempty finite alternative set, with \(m=|X|\); types are strict complete rankings \(r\in X!\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_r\) a binary rational, with \(\sum_r\mu_r=1\). Here \(\tau\) is the support size, not \(m!\); let \(L\) be the total input bit length. State running times in \(m,\tau,L\).
Return every alternative maximizing \(B_\mu(x)=\sum_r\mu_r|\{y\in X:x\succ_r y\}|\), retaining all ties.
For the judgment formulation, the agenda is \(\Phi=\{p_{a\succeq b}:a,b\in X\}\), including diagonal items. The ranking judgment satisfies \(J_r(p_{a\succeq b})=1\) exactly when \(a=b\) or \(a\succ_r b\).
The \(\mathrm{Winner}\)-feasible judgments are exactly \(\{J_x:x\in X\}\), where \(J_x(p_{a\succeq b})=1\) exactly when \(a=x\) or \(b\ne x\): one alternative is strictly above all others, which are mutually indifferent.
The mass version of \(\mathrm{max\text{-}sum}\) returns all feasible judgments maximizing \(\sum_r\mu_r|\{p\in\Phi:J(p)=J_r(p)\}|\); return their top alternatives.

Can this winner determination problem be solved in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finite profiles of strict rankings, \(\mathrm{max\text{-}sum}\) with \(\mathrm{Winner}\) feasibility selects exactly the Borda winners; discrete Borda winner determination is polynomial-time computable. [Verified source](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p946.pdf)
No separate result for the precise binary-rational mass formulation was verified.

Result

Both formulations are polynomial-time solvable in \(m,\tau,L\), with all ties retained. A sufficient bound, using elementary exact integer arithmetic, is
\[ O\!\left(L+m\tau\bigl(L+\log(m+1)\bigr)^2\right). \]

The proof below applies directly to binary-rational masses; it does not require expanding them into a finite electorate.

1. Agreement maximization equals weighted Borda maximization

Write \(s_r(x)=|\{y\in X:x\succ_r y\}|\), and define the agreement score
\[ A_\mu(x)=\sum_r\mu_r|\{p\in\Phi:J_x(p)=J_r(p)\}|. \]

Fix \(x\in X\) and a supported ranking \(r\). Partition the agenda as follows.

• Diagonal items. Both judgments assign value \(1\) to every \(p_{a\succeq a}\), giving \(m\) agreements.

• Comparisons between distinct alternatives other than \(x\). For each unordered pair \(\{a,b\}\subseteq X\setminus\{x\}\), the judgment \(J_x\) assigns value \(1\) to both orientations. Strictness of \(r\) means that \(J_r\) assigns value \(1\) to exactly one orientation. Thus each such pair contributes exactly one agreement, giving \((m-1)(m-2)/2\) agreements.

• Comparisons involving \(x\). For each \(y\ne x\), the values of \(J_x\) on \((p_{x\succeq y},p_{y\succeq x})\) are \((1,0)\). The ranking judgment agrees on both items if \(x\succ_r y\), and on neither otherwise. These pairs therefore contribute \(2s_r(x)\) agreements.

Consequently,
\[ |\{p\in\Phi:J_x(p)=J_r(p)\}| =m+\frac{(m-1)(m-2)}2+2s_r(x). \]

Using \(\sum_r\mu_r=1\), we obtain
\[ A_\mu(x)=m+\frac{(m-1)(m-2)}2+2B_\mu(x). \]

The first two terms are independent of \(x\), and the coefficient of \(B_\mu(x)\) is positive. Hence the maximizing alternatives, including every tie, coincide exactly.

This extends the finite-profile equivalence established in Theorem 3 of [Endriss’s paper](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p946.pdf). Here the identity has been proved directly for the mass formulation. For \(m=1\), it also holds: the Borda score is zero and the unique alternative is returned.

2. Exact algorithm

Represent each input mass as \(\mu_r=p_r/q_r\), where \(p_r,q_r\) are positive integers written in binary. Reduced fractions are unnecessary. Set
\[ D=\prod_{r\in\operatorname{supp}(\mu)}q_r, \qquad w_r=p_r(D/q_r). \]

Every division is exact, and \(w_r=D\mu_r\). In particular,
\[ \sum_r w_r=D. \]

Initialize an integer score \(T_x=0\) for each alternative. For every supported ranking, written from best to worst as
\[ r=(x_{r,1},\ldots,x_{r,m}), \]
perform the updates
\[ T_{x_{r,j}}\leftarrow T_{x_{r,j}}+(m-j)w_r \qquad\text{for every }j\in\{1,\ldots,m\}. \]

An alternative in position \(j\) has exactly \(m-j\) alternatives below it. Therefore the resulting scores satisfy
\[ T_x=\sum_r w_rs_r(x)=D B_\mu(x). \]

Since \(D>0\), returning every alternative whose integer score equals \(\max_{y\in X}T_y\) returns precisely all required winners. Integer equality retains ties exactly.

3. Bit complexity

The total binary encoding length of the denominators is at most \(L\). Therefore
\[ \log_2 D=\sum_r\log_2 q_r\le L, \]
so \(D\) has at most \(L+1\) bits.

Positivity and normalization imply \(\mu_r\le1\), hence \(w_r\le D\). Moreover, every completed or partial score satisfies
\[ 0\le T_x\le(m-1)\sum_r w_r=(m-1)D. \]

Thus all integers used in the algorithm have
\[ O\!\left(L+\log(m+1)\right) \]
bits. This includes intermediate denominator products and individual score contributions.

Constructing \(D\) and the weights requires \(O(\tau)\) integer arithmetic operations. Processing the rankings requires \(O(m\tau)\) operations, and finding all maxima requires \(O(m)\) comparisons. Elementary multiplication and division on integers of this bit length each cost
\[ O\!\left(\bigl(L+\log(m+1)\bigr)^2\right) \]
bit operations; addition and comparison cost no more. Including input processing gives the stated bound
\[ O\!\left(L+m\tau\bigl(L+\log(m+1)\bigr)^2\right), \]
because \(m,\tau\ge1\).

The numerical value of \(D\) may be exponentially large, but its binary representation has polynomial length. The algorithm processes only the explicitly listed \(\tau\) rankings and never enumerates all \(m!\) types.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output resolves both formulations for the stated binary-rational input, retains all ties, and establishes the claimed polynomial running time. No major or minor mathematical issues were found.

• Agenda partition and agreement count.

The three categories are disjoint and exhaust the agenda: diagonal items, ordered comparisons between distinct alternatives other than \(x\), and ordered comparisons involving \(x\).

The diagonal contribution is exactly \(m\). For each unordered pair excluding \(x\), \(J_x\) accepts both orientations, while a strict ranking accepts exactly one; hence the contribution is \((m-1)(m-2)/2\). For each \(y\ne x\), the two orientations involving \(x\) contribute two agreements when \(x\succ_r y\), and zero otherwise.

Thus the stated identity
\( |\{p\in\Phi:J_x(p)=J_r(p)\}|=m+(m-1)(m-2)/2+2s_r(x) \)
is correct, including the diagonal items required by the task.

• Equivalence of the maximizers.

Weighting the identity by the masses and using their normalization correctly gives
\(A_\mu(x)=m+(m-1)(m-2)/2+2B_\mu(x)\).

The additive constant is independent of \(x\), and the multiplicative coefficient is positive. Therefore score orderings and ties coincide exactly. The task explicitly supplies the complete feasible set \(\{J_x:x\in X\}\), so there are no additional feasible judgments to consider.

The historical attribution is also accurate: Theorem 3 of [Endriss’s paper](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p946.pdf) states the finite-profile Borda equivalence. The present argument establishes the mass version directly and does not depend on applying that theorem beyond its stated setting.

• Common-denominator construction.

Each \(q_r\) is positive and divides \(D=\prod_rq_r\). Consequently, every weight \(w_r=p_r(D/q_r)\) is an exact positive integer satisfying \(w_r=D\mu_r\). Normalization then gives \(\sum_rw_r=D\).

Reduced fractions are unnecessary. The construction operates on the binary representations and does not expand the masses into individual voters.

• Score computation and output correctness.

In a strict complete ranking, the alternative at position \(j\) has exactly \(m-j\) alternatives below it. The updates therefore compute \(T_x=DB_\mu(x)\) exactly.

Since \(D>0\), taking the maximum integer score identifies precisely the Borda winners. Returning every alternative with that score preserves all ties and, by the preceding equivalence, returns precisely the required top alternatives for the judgment formulation.

• Bit-length bounds.

The denominator encoding lengths sum to at most \(L\), so \(\log_2D\le L\), and \(D\) has at most \(L+1\) bits.

Positivity and normalization imply \(0<\mu_r\le1\), hence \(w_r\le D\). Every partial score is nonnegative and bounded by the completed score, which is at most \((m-1)D\). Intermediate denominator products are at most \(D\), and individual score contributions satisfy the same score bound.

Thus the stated \(O(L+\log(m+1))\) bound covers the integers used by the algorithm. No hidden dependence on the numerical value of \(D\) invalidates the analysis.

• Operation count and edge cases.

Constructing the denominator and weights takes \(O(\tau)\) arithmetic operations; accumulating scores takes \(O(m\tau)\); identifying all maxima takes \(O(m)\) comparisons. Elementary binary multiplication and division have the stated quadratic bit-cost upper bound. Including input processing yields
\(O(L+m\tau(L+\log(m+1))^2)\).

Nonemptiness and normalization ensure \(m,\tau\ge1\), justifying absorption of the smaller operation counts. For \(m=1\), the agreement score is one, the Borda score is zero, and the sole alternative is returned. The algorithm examines only the listed support.

Repair feedback: None required. The proof and complexity analysis are verifiable as written.

⟨structured verdict parsed — rendered above⟩