Answer: Polynomial-time solvable, with exact preservation of all ties.
Proposition 7.6 — class: algorithmic
Given a finite type set \(T\), binary-rational masses \(\mu_i\) summing to one, and a link matrix \(A\) where \(A_{ij}=1\) means every member of type \(i\) links to every member of type \(j\), compute the exact weak order of the types. Let \(D\) be the least common denominator of the masses and define \(d_j=D\sum_i\mu_iA_{ij}\). Rank types by the scores \(q_j=0\) when \(j\) has no predecessor type, and otherwise \(q_j=(d_j+\max_{i:A_{ij}=1}q_i)/(D+1)\), including ties.
A society is given by its support \(T=\{1,\ldots,\tau\}\): the list of types with positive binary-rational masses \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types. The agents and alternatives are the same society.
The input also contains \(A\in\{0,1\}^{\tau\times\tau}\), where \(A_{ij}=1\) means every member of type \(i\) links to every member of type \(j\); diagonal entries and directed cycles are allowed. Let \(m=\sum_{i,j}A_{ij}\) and let \(L\) be the total input bit length.
Write each mass in lowest terms and let \(D\) be the least common multiple of its denominators. Define \(P(j)=\{i:A_{ij}=1\}\) and \(d_j=D\sum_i\mu_iA_{ij}\).
The scores are the unique vector \(q\in[0,1]^\tau\) satisfying \(q_j=0\) if \(P(j)=\varnothing\), and otherwise \(q_j=(d_j+\max_{i\in P(j)}q_i)/(D+1)\). The required output is the exact weak order \(j\preceq k\iff q_j\le q_k\), preserving all ties.
Is computing this exact weak order solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For explicitly listed finite agents, identity-rank recursive in-degree ranking has a claimed \(O(|V|\,|E|)\)-time algorithm. [Altman and Tennenholtz (2008)](https://auld.aaai.org/Papers/JAIR/Vol31/JAIR-3114.pdf).
No result settling the exact rational-mass problem above was identified in the literature search.
1. Result
Computing the exact weak order is polynomial-time solvable in the binary input model, including preservation of every tie.
The proof below works directly with the support representation. It does not require expanding the society into explicitly listed agents or invoking the finite-agent algorithm in [Altman and Tennenholtz (2008)](https://auld.aaai.org/Papers/JAIR/Vol31/JAIR-3114.pdf).
2. Integer normalization and approximation
Write each mass in lowest terms as \(\mu_i=a_i/b_i\), and set \(B=D+1\). The integers \(w_i=a_i(D/b_i)\) satisfy \(w_i>0\) and \(\sum_i w_i=D\). Consequently,
\(d_j=\sum_{i\in P(j)}w_i\) is an integer satisfying \(0\le d_j\le D\).
Define \(F:[0,1]^\tau\to[0,1]^\tau\) by
\[ F(x)_j= \begin{cases} 0,&P(j)=\varnothing,\\ (d_j+\max_{i\in P(j)}x_i)/B,&P(j)\ne\varnothing. \end{cases} \]
Here and below, displayed equations are understood as the corresponding inline mathematics: \(F(x)_j=0\) for empty predecessor sets, and \(F(x)_j=(d_j+\max_{i\in P(j)}x_i)/B\) otherwise.
The map takes the cube into itself because \(d_j\le D=B-1\). For any nonempty predecessor set,
\(\left|\max_{i\in P(j)}x_i-\max_{i\in P(j)}y_i\right|\le\|x-y\|_\infty\).
Thus \(\|F(x)-F(y)\|_\infty\le B^{-1}\|x-y\|_\infty\). Since \(B\ge2\), the contraction mapping theorem applies to the complete metric space \([0,1]^\tau\), giving the unique fixed point \(q\).
Starting with \(x^{(0)}=0\), compute \(x^{(t+1)}=F(x^{(t)})\). Monotonicity of \(F\), together with \(0\le q\), gives \(x^{(t)}\le q\) coordinatewise. The contraction estimate gives
\(0\le q_j-x_j^{(t)}\le B^{-t}\qquad\text{for every }j.\)
Approximation alone does not certify ties. The next bound supplies that certification.
3. A denominator bound for the exact scores
For every \(j\) with nonempty \(P(j)\), choose a predecessor \(p(j)\) attaining \(\max_{i\in P(j)}q_i\). This choice is used only in the proof. Then
\(Bq_j=d_j+q_{p(j)}.\)
Follow the chosen predecessors from any starting vertex \(j\). Since there are only \(\tau\) vertices, the walk either reaches a vertex with no predecessors or enters a cycle.
If it reaches such a vertex after \(h\) steps, write the visited vertices as \(v_0=j,\ldots,v_h\). Since \(q_{v_h}=0\), repeated substitution yields
\(q_j=\sum_{r=0}^{h-1}d_{v_r}B^{-(r+1)}.\)
Its reduced denominator therefore divides \(B^h\), and \(h\le\tau-1\).
Otherwise, let the tail length be \(h\) and the cycle length be \(\ell\). The vertices \(v_0,\ldots,v_{h+\ell-1}\) are distinct, so \(h+\ell\le\tau\). Substitution around the cycle gives
\(q_{v_h}=\sum_{r=0}^{\ell-1}d_{v_{h+r}}B^{-(r+1)}+B^{-\ell}q_{v_h}.\)
Hence
\(q_{v_h}=C/(B^\ell-1),\qquad C=\sum_{r=0}^{\ell-1}d_{v_{h+r}}B^{\ell-1-r}\in\mathbb Z.\)
Substituting along the tail shows that the reduced denominator of \(q_j\) divides \(B^h(B^\ell-1)\), which is less than or equal to \(B^\tau\). This argument includes self-loops.
Therefore every score can be written in lowest terms as \(q_j=u_j/v_j\), with \(1\le v_j\le B^\tau\). If two scores differ, their cross-multiplied numerator is a nonzero integer, giving the separation bound
\(|q_j-q_k|\ge 1/(v_jv_k)\ge B^{-2\tau}.\)
4. Recovering all comparisons, including ties
Take \(N=2\tau+2\) and \(\varepsilon=B^{-N}\). The approximation bound gives errors \(e_j=q_j-x_j^{(N)}\) satisfying \(0\le e_j\le\varepsilon\).
We claim that
\(q_j\le q_k\quad\Longleftrightarrow\quad x_j^{(N)}-x_k^{(N)}\le\varepsilon.\)
If \(q_j\le q_k\), then
\(x_j^{(N)}-x_k^{(N)}=q_j-q_k-e_j+e_k\le\varepsilon.\)
If \(q_j>q_k\), the separation bound instead gives
\(x_j^{(N)}-x_k^{(N)}\ge B^{-2\tau}-\varepsilon=(B^2-1)\varepsilon\ge3\varepsilon>\varepsilon.\)
This proves the claim in both directions.
To implement it using integers, put \(z_j^{(t)}=B^t x_j^{(t)}\). Starting from \(z_j^{(0)}=0\), the recurrence is
\(z_j^{(t+1)}=d_jB^t+\max_{i\in P(j)}z_i^{(t)}\)
when \(P(j)\ne\varnothing\), and \(z_j^{(t+1)}=0\) otherwise. Every \(z_j^{(t)}\) is an integer.
The exact output rule is consequently
\(j\preceq k\quad\Longleftrightarrow\quad z_j^{(N)}-z_k^{(N)}\le1.\)
In particular,
\(q_j=q_k\quad\Longleftrightarrow\quad |z_j^{(N)}-z_k^{(N)}|\le1.\)
Thus ties are certified exactly.
5. Polynomial bit complexity
The algorithm is:
Since \(D\le\prod_i b_i\), its binary length is at most a constant plus the sum of the input denominator lengths, hence \(O(L+1)\). Computing it by successive greatest-common-divisor and least-common-multiple operations takes polynomial time.
Moreover, \(0\le x_j^{(t)}\le1\), so \(0\le z_j^{(t)}\le B^t\). Every integer used during the iterations therefore has \(O(\tau(L+1))\) bits.
Each iteration requires \(O(m+\tau)\) integer operations: scan the edges to compute predecessor maxima, then update the coordinates. There are \(O(\tau)\) iterations and at most \(O(\tau^2)\) output comparisons. All arithmetic is on integers of polynomial bit length.
Therefore the entire computation takes polynomial time in \(m,\tau,L\), even when the numerical value of \(D\) is exponentially large.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the assigned problem: the exact weak order, including all ties, is computable in polynomial time in the binary input model. No major or minor mathematical issues were found.
Since the positive masses sum to \(1\), the support is nonempty, \(D\ge1\), and \(B=D+1\ge2\). Each \(b_i\) divides \(D\), so \(w_i=a_i(D/b_i)\) is a positive integer. The identity \(\sum_i w_i=D\) follows directly from the normalization of the masses. Consequently, every \(d_j\) is an integer in \([0,D]\).
The proposed map \(F\) maps the cube into itself: for a nonempty predecessor set, its numerator lies between \(0\) and \(D+1=B\); for an empty predecessor set, its value is \(0\).
The maximum inequality is valid, and the empty-predecessor coordinates have difference zero. Hence the claimed contraction factor \(B^{-1}<1\) holds in the supremum norm. The contraction mapping theorem is applied with its required hypotheses: a self-map of a nonempty complete metric space with contraction constant strictly below \(1\). It establishes existence and uniqueness of the required fixed point.
The map \(F\) is coordinatewise monotone. Starting from zero therefore gives \(x^{(t)}\le q\) for every nonnegative integer \(t\).
Applying the contraction estimate repeatedly gives
\[
\|x^{(t)}-q\|_\infty
\le B^{-t}\|q\|_\infty
\le B^{-t}.
\]
Together with the coordinatewise inequality, this verifies the stated one-sided error bound. The base case \(t=0\) is also covered.
For every nonempty predecessor set, a maximizing predecessor exists because the set is finite. Fixing these choices gives the displayed linear relation \(Bq_j=d_j+q_{p(j)}\). This choice is used only to establish a bound; the algorithm does not need to compute it.
Following these fixed choices produces either a path ending at an empty-predecessor vertex or a tail followed by a cycle. These exhaust the possibilities in a finite functional graph.
In the terminating case, the substitution formula is correct, and its denominator divides \(B^h\). The bound \(h\le\tau-1\) follows because all \(h+1\) visited vertices are distinct. The case \(h=0\), when the starting vertex already has no predecessors, gives score zero and denominator \(1\).
In the cyclic case, the substitution around the cycle correctly yields
\[
(B^\ell-1)q_{v_h}
=\sum_{r=0}^{\ell-1}d_{v_{h+r}}B^{\ell-1-r}.
\]
Here \(\ell\ge1\), so the denominator is nonzero. Substitution along the tail gives a denominator dividing \(B^h(B^\ell-1)\). Since \(h+\ell\le\tau\), this is at most \(B^\tau\).
Thus rationality and the reduced-denominator bound are both established. The argument includes tails of length zero, self-loops, and cycles of arbitrary allowed length.
For unequal scores in reduced rational form, the cross-multiplied numerator is a nonzero integer. Therefore the separation bound
\[
|q_j-q_k|\ge B^{-2\tau}
\]
is valid, including comparisons involving zero.
With \(N=2\tau+2\) and \(\varepsilon=B^{-N}\), the one-sided errors justify both comparison directions:
\[ x_j^{(N)}-x_k^{(N)} \ge(B^2-1)\varepsilon \ge3\varepsilon>\varepsilon. \]
The constants and strict inequality are correct for every \(B\ge2\). Consequently, the claimed comparison equivalence holds, and applying it in both directions correctly detects every tie.
Multiplying the iteration by \(B^{t+1}\) gives precisely the stated recurrence for \(z^{(t+1)}\). Scaling commutes with the predecessor maximum because \(B^t>0\). Integrality follows inductively from the zero initial vector.
Since \(B^N\varepsilon=1\), the threshold becomes exactly
\[
j\preceq k
\quad\Longleftrightarrow\quad
z_j^{(N)}-z_k^{(N)}\le1.
\]
The absolute-difference tie criterion follows correctly. In particular, approximate values need not coincide for tied scores; the threshold accounts for this without creating false ties.
The bound \(D\le\prod_i b_i\) gives polynomial binary length for \(D\), \(B\), and all normalized weights. Fraction reduction and successive integer greatest-common-divisor and least-common-multiple computations are polynomial-time operations on these lengths.
The bound \(z_j^{(t)}\le B^t\) gives \(O(\tau(L+1))\) bits throughout the required iterations. The powers \(B^t\) and the intermediate products in the recurrence also have polynomial bit length and can be computed within the claimed polynomial bound.
Each iteration uses \(O(m+\tau)\) integer operations. There are \(O(\tau)\) iterations, and explicitly outputting all comparisons requires at most \(O(\tau^2)\) further comparisons. Polynomial-length integer arithmetic therefore establishes polynomial total bit complexity.
The proof directly addresses the supplied support representation and does not depend on the cited finite-agent algorithm. The edgeless case, diagonal entries, directed cycles, and singleton support are all covered.
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.