d4-conf-aaai-2026-1047 (d4-conf-aaai-2026-1047)

Given a candidate set \(A\) and a support of \(\tau\) rankings \(t\), each with positive binary-rational mass \(\mu_t\) summing to \(1\), compute the set of alternatives selected by River under at least one descending tie-breaking order of the margin edges, where \(m_\mu(x,y)=\sum_{t:x\succ_t y}\mu_t-\sum_{t:y\succ_t x}\mu_t\).

Let \(A\) be a nonempty candidate set with \(m=|A|\). A society is given by its support: \(\tau\) distinct strict linear rankings \(t\) of \(A\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
Define \(m_\mu(x,y)=\sum_{t:x\succ_t y}\mu_t-\sum_{t:y\succ_t x}\mu_t\). The margin graph has edges \(E=\{(x,y):x\ne y,\ m_\mu(x,y)\ge0\}\), weighted by their margins; a zero-margin pair contributes both directed edges.
A descending tiebreaker is any total order of \(E\) with nonincreasing weights. River starts with an empty directed graph on \(A\) and processes this order, adding \((x,y)\) unless \(y\) already has an incoming edge or its addition creates a directed cycle. Its winner is the unique vertex with no incoming edge after processing all edges.
Let \(W_\mu\) be the set of River winners obtained under at least one descending tiebreaker.

Can \(W_\mu\) be computed in polynomial time in \(m,\tau,L\), or is deciding whether a designated candidate belongs to \(W_\mu\) NP-hard?

For finite electorates, River with parallel-universe tiebreaking has a polynomial-time algorithm on the margin graph, with runtime polynomial in \(m\). [Source](https://arxiv.org/html/2512.14409v2)
No separate result for the binary-rational support formulation was identified in the literature search.

Result

The full set \(W_\mu\) is computable in polynomial time in \(m,\tau,L\). In particular, designated-candidate membership belongs to \(\mathsf{P}\).

The proof reduces the given society to a polynomial-size finite electorate with exactly the same possible River outcomes, then applies the cited finite-electorate theorem.

For \(m=1\), the sole candidate wins. Henceforth assume \(m\geq 2\).

1. Compute exact margins in polynomial time

Write each encoded mass as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive integers, and define
\(Q=\prod_t b_t\) and \(c_t=a_t(Q/b_t)\).

The binary length of \(Q\) is at most the sum of the binary lengths of the denominators, hence is \(O(L)\). Each \(c_t\) is an integer, and the normalization assumption gives
\(\sum_t c_t=Q\).

For distinct candidates, compute the scaled margin
\(S(x,y)=\sum_{t:x\succ_t y}c_t-\sum_{t:y\succ_t x}c_t\).
Then \(S(x,y)=Qm_\mu(x,y)\) and \(\lvert S(x,y)\rvert\leq Q\).

Thus every scaled margin has \(O(L)\) bits. By first recording candidate positions in each ranking, all scaled margins can be computed using \(O(\tau m^2)\) additions and subtractions of integers of polynomial bit length. Their signs, equalities, and ordering are therefore computable in polynomial time.

2. River depends only on the edge set and weight ordering

Lemma. Suppose two weighted directed graphs have the same vertex and edge sets, and their weights \(w,w'\) satisfy
\(w(e)\leq w(f)\Longleftrightarrow w'(e)\leq w'(f)\)
for every pair of edges. Then their sets of possible River winners coincide.

Proof. The displayed equivalence preserves both strict comparisons and equalities. Consequently, the descending total edge orders permitted by the two weight functions are exactly the same.

Fix any such order. Induct over its edges. Initially, both River executions have the same empty graph. If their current graphs coincide, the next edge is rejected in one execution precisely when it is rejected in the other: both rejection conditions depend only on the current graph and that edge. Their graphs therefore coincide after every step, and their winners coincide.

Taking the union over the common set of descending orders proves the lemma. \(\square\)

Let \(\lambda_1<\cdots<\lambda_s\) be the distinct positive values among the scaled margins. There are at most \(p=\binom m2\) such values.

Define an antisymmetric integer margin function \(C\) as follows:

• If \(S(x,y)=\lambda_j>0\), set \(C(x,y)=2j\).
• If \(S(x,y)<0\), set \(C(x,y)=-C(y,x)\).
• If \(S(x,y)=0\), set \(C(x,y)=0\).

The nonnegative-margin edge set is unchanged. In particular, every zero-margin pair still contributes both directed edges. On this edge set, the weights preserve every comparison and equality. By the lemma, replacing \(m_\mu\) by \(C\) preserves \(W_\mu\).

Moreover, every entry of \(C\) has absolute value at most \(2p\), and hence has \(O(\log m)\) bits.

3. Realize the compressed margins by a small finite electorate

We now prove that \(C\) is the margin function of an explicit finite electorate of polynomial size.

Pair gadget. Fix distinct candidates \(x,y\), and enumerate the others as \(z_1,\ldots,z_k\). Introduce two voters with rankings
\(x\succ y\succ z_1\succ\cdots\succ z_k\)
and
\(z_k\succ\cdots\succ z_1\succ x\succ y\).

Both voters rank \(x\) above \(y\), so their combined margin for \((x,y)\) is \(2\). Every other pair is ordered oppositely by the two voters:

• For two candidates among the \(z_i\), their orders are reversed.
• For either \(x\) or \(y\) against a \(z_i\), the former is above \(z_i\) in the first ranking and below it in the second.

Thus this gadget contributes \(2\) to the margin of \(x\) over \(y\), contributes \(-2\) in the reverse direction, and contributes zero to every other pair.

For every unordered pair with positive compressed margin \(C(x,y)=2j\), include \(j\) copies of its pair gadget. Since ordinary electorate margins add over voters, the resulting margins equal \(C\) on every pair.

Finally, add any ranking and its reverse. These two voters contribute zero to all margins and ensure that the electorate is nonempty even when \(s=0\).

Call the resulting profile \(\mathcal P\). Its number of voters satisfies
\(N=2+2\sum_{C(x,y)>0}C(x,y)/2\leq 2+2ps\leq 2+2p^2\).

Therefore \(N=O(m^4)\). Writing all rankings explicitly requires \(O(m^5\log m)\) bits under a standard candidate encoding. This profile can be constructed in polynomial time, and its margins are exactly \(C\).

4. Apply the finite-electorate theorem

The cited result establishes that the FUN algorithm computes all River PUT winners from a finite profile’s margin graph in polynomial time in the number of candidates: correctness is Theorem 4.1, and the runtime bound is Theorem 3.1. Its definitions use nonnegative-margin edges, descending total edge orders, and the same branching and cycle rejection conditions as this task. [Döring, Malanowski, and Neubert, *Cost-Free Neutrality for the River Method*, Sections 2–4](https://arxiv.org/html/2512.14409v2).

Its hypotheses hold for \(\mathcal P\): it is a nonempty finite electorate of strict linear rankings, and its ordinary integer margin graph is exactly the graph defined by \(C\), including both directions of every zero-margin pair. Its edge weights also have \(O(\log m)\) bits, so weight comparisons have polynomial bit cost.

Apply that algorithm to this graph. By Section 2, its returned winner set is exactly \(W_\mu\).

All preprocessing takes polynomial time in \(m,\tau,L\), and the final finite-electorate computation takes polynomial time. Thus the entire winner set is polynomial-time computable. Designated-candidate membership consequently lies in \(\mathsf{P}\), and cannot be NP-hard under polynomial-time many-one reductions unless \(\mathsf{P}=\mathsf{NP}\).

⟨structured verdict parsed — rendered above⟩

The argument resolves the intended complexity question in substance: the full winner set is polynomial-time computable. I found one minor domain omission in the invariance lemma, but no major gap or incorrect computation.

1. Exact margin computation is valid.

For the encoded positive rational masses, the product \(Q=\prod_t b_t\) is a positive common denominator. Its binary length is bounded by the sum of the denominator lengths, hence by \(O(L)\). Computing this product, the exact divisions \(Q/b_t\), and the integers \(c_t=a_t(Q/b_t)\) requires polynomial-time integer arithmetic.

Normalization gives \(\sum_t c_t=Q\). Consequently, each scaled margin satisfies
\[ S(x,y)=Qm_\mu(x,y),\qquad |S(x,y)|\leq Q. \]
Thus all intermediate sums and final margins have polynomial bit length. The stated \(O(\tau m^2)\) count of additions and subtractions is valid after recording positions in the rankings. Exact signs, ties, and comparisons are therefore available in polynomial time.

No issue was found in this step.

2. Preservation of River outcomes is correct on the inputs used.

The comparison equivalence in the lemma preserves equalities and strict inequalities, so the admissible descending total orders are identical. For any fixed admissible order, the induction is valid: both rejection conditions depend only on the current accepted graph and the next edge. Identical initial states therefore produce identical accepted graphs.

There is one minor issue: the lemma is stated for arbitrary weighted directed graphs, whereas the task defines River’s winner as the unique vertex with no incoming edge. Such a winner need not exist uniquely on arbitrary graphs. For example, an edgeless graph on two vertices leaves both vertices without incoming edges.

This omission does not undermine the application, which concerns margin graphs of the specified kind. The minimum clarification is to restrict the lemma to graphs on which the stated River procedure has a unique winner for every admissible order, or explicitly to the margin graphs used here.

The compression itself is correct. Positive scaled margins are replaced by their distinct-value ranks multiplied by two. This preserves every positive comparison and tie, preserves zero margins, and leaves the nonnegative-margin edge set unchanged. Negative values are defined consistently by antisymmetry. Since \(Q>0\), comparisons of the original margins also agree with comparisons of the scaled margins.

The bound \(s\leq p=\binom m2\) is valid, and all compressed margins have absolute value at most \(2p\).

3. The finite-electorate construction is correct.

The two rankings in the pair gadget both place \(x\) above \(y\), giving margin two in that direction. Every other pair receives opposite contributions:

• Pairs among the remaining candidates are reversed.
• Each remaining candidate appears below both \(x,y\) in the first ranking and above both in the second.

The gadget therefore has exactly the claimed margin contribution. This remains valid when \(m=2\), where there are no remaining candidates.

Including \(j\) copies for a positive compressed margin \(2j\) gives that margin exactly. Contributions to all other unordered pairs vanish, so adding gadgets introduces no unintended margins. The final ranking and its reverse cancel on every pair and ensure a nonempty electorate.

The voter-count calculation is correct:
\[ N=2+2\sum_{C(x,y)>0}\frac{C(x,y)}2 \leq 2+2ps \leq 2+2p^2. \]
There is at most one positive orientation per unordered pair. Hence \(N=O(m^4)\), and the stated \(O(m^5\log m)\) explicit encoding bound follows after indexing candidates.

The case \(s=0\) is covered: only the two cancelling voters are needed, producing all-zero margins.

No issue was found in this step.

4. The cited theorem applies.

I checked the cited source. Section 2 allows nonnegative-margin edges and arbitrary descending total edge orders, and specifies the same incoming-edge and cycle rejection conditions. Thus zero-margin pairs are included; there is no stated restriction to odd electorates or strictly positive margins.

Theorem 3.1 gives polynomial runtime in the number of alternatives. Theorem 4.1 states that, for every finite preference profile and candidate, River PUT membership is equivalent to being cycle dominated or not dominated in the FUN diagram. These are precisely the states returned by the algorithm. [Döring, Malanowski, and Neubert, Sections 2–4](https://arxiv.org/html/2512.14409v2).

The constructed profile satisfies the theorem’s hypotheses: it is nonempty and consists of strict linear rankings. Its margins equal \(C\). The compressed weights have \(O(\log m)\) bits, so accounting for comparison costs preserves polynomial runtime.

No unverified theorem application remains.

5. Final conclusion and scope.

Combining the verified preprocessing, outcome preservation, electorate construction, and cited algorithm establishes polynomial-time computation of the entire \(W_\mu\). The separately handled case \(m=1\) is correct.

Designated-candidate membership consequently belongs to \(\mathsf P\). The conditional statement excluding NP-hardness under polynomial-time many-one reductions unless \(\mathsf P=\mathsf{NP}\) is also correct.

The only requested repair is the routine domain restriction in the invariance lemma; no additional mathematics is needed.

⟨structured verdict parsed — rendered above⟩