Cost-Free Neutrality for the River Method¶

Conference: AAAI 2026 arXiv: 2512.14409 Code: None Area: Other (Computational Social Choice / Voting Theory) Keywords: River voting method, parallel universes tiebreaking, neutrality, polynomial-time algorithm, social choice function

TL;DR¶

For the Parallel Universes Tiebreaking (PUT) problem applied to the River voting method, this paper proves that the winner set can be computed in polynomial time (in contrast to the NP-completeness of Ranked Pairs), and proposes the Fused-Universe (FUN) algorithm, which simulates all possible tiebreaking orders in a single pass and provides a constructive certificate for each winner.

Background & Motivation¶

Social choice functions aggregate individual preferences into collective decisions, serving as the foundation of democratic processes and increasingly being applied to AI alignment (e.g., aggregating diverse user feedback). Within the family of margin-based voting methods (which determine outcomes via pairwise comparisons and winning margins), five important methods exist: Split Cycle, Ranked Pairs, Stable Voting, Beat Path, and River.

Problem: Tiebreaking Violates Neutrality¶

Ranked Pairs, Stable Voting, and River require a tiebreaker—a total ordering over all margin-tied edges—when processing edges with equal margins. Such tiebreakers typically violate neutrality (the principle that no candidate should be favored a priori).

Parallel Universes Tiebreaking (PUT)¶

To restore neutrality, PUT considers all possible tiebreaking orders and returns the union of candidates that win under any such order. However, determining whether a candidate is a winner under Ranked Pairs + PUT has been shown to be NP-complete.

Core Problem and Surprising Discovery¶

The River method closely resembles Ranked Pairs (both process edges in decreasing margin order and reject edges that create cycles), differing only in that River additionally requires at most one incoming edge per candidate (the branching condition), so River always produces a directed tree rooted at the winner. One might expect River-PUT to be similarly NP-hard, but this paper proves the opposite: River-PUT can be computed in polynomial time.

Method¶

Overall Architecture¶

The FUN algorithm proceeds in two steps: 1. Compute the Fused-Universe graph: In a single pass over the margin graph, simultaneously simulate all possible tiebreaking orders to construct a subgraph containing all edges that appear in at least one universe. 2. Read off the winner set from edge/vertex states: Determine PUT winners based on each candidate's domination status.

Key Designs¶

1. Critical Structural Advantage of the River Method¶

The sole difference between River and Ranked Pairs—the branching condition (at most one incoming edge per candidate)—yields: - River always produces a directed tree (whereas Ranked Pairs only guarantees an acyclic subgraph). - One can deterministically reason about whether an edge is added or rejected across all universes. - Once all incoming edges of margin \(\geq k\) for candidate \(y\) have been processed, \(y\)'s domination status is determined across all universes.

Design Motivation: Exploit the branching condition to compress the exponential search space into a structure tractable in polynomial time.

2. Precise Classification into Four Edge States¶

FUN assigns each edge one of four states:

State	Meaning	Implication
Fix	Added in every universe	\(y\) is dominated by \((x,y)\) in every universe
BC (Branch Choice)	Added in some but not all universes; a partner edge of equal margin exists	\(y\) is dominated by some edge of margin \(k\) in every universe
CC (Cycle Choice)	May be added in some universes; an alternative \(y\)–\(x\) path exists	There exists a universe in which \(y\) is not dominated by \((x,y)\)
CBC (Cycle-Branch Choice)	BC but contingent on the choice of another CC edge	\(y\) is dominated by some edge of margin \(\geq k\) in every universe

3. Three Vertex States¶

State	Property in FUN graph	PUT winner?
Undominated	No incoming edges	✓
Fixedly dominated	Has a unique Fix incoming edge, or at least one BC/CBC incoming edge	✗
Cyclically dominated	Has at least one incoming edge and all incoming edges are CC	✓

Core Theorem (Theorem 4.1): \(a \in \text{RV-PUT}(\mathcal{P}) \Leftrightarrow a\) is "cyclically dominated" or "undominated" in the FUN graph.

4. Computational Procedure of FUN (Algorithm 1)¶

For each edge \((x,y)\) processed in decreasing margin order:

Phase 1: Whether the edge is rejected in all universes - Branch rejection check: If \(y\) is already fixedly dominated with an incoming edge of margin \(> k\) → reject. - Cycle rejection check: If adding \((x,y)\) creates a cycle with a path of strength \(> k\) (in all universes) → reject (checked via BFS).

Phase 2: Assign edge state - Based on the current state of target vertex \(y\), assign a preliminary state (Fix/BC/CBC). - Then check whether the edge forms a cycle with an equal-margin edge in the FUN graph → if so, update to CC.

Complexity Analysis (Theorem 3.1): All operations reduce to \(\mathcal{O}(|E|)\) BFS calls; the overall runtime is polynomial in the number of candidates \(|A|\).

5. Constructive Proof of Winner Certificates¶

For each PUT winner \(a\), the DirectedMaxPrim algorithm (analogous to Prim's maximum spanning tree algorithm) extracts a certificate tree \(T^a\) rooted at \(a\) from the FUN graph, and then constructs a corresponding tiebreaking order \(\tau^a\) such that \(\text{RV}(\mathcal{P}, \tau^a) = \{a\}\).

Key Lemma (Lemma 4.5): If the FUN graph contains a path \(P_{ab}\) from \(a\) to \(b\), then the certificate tree contains a path \(P'_{ab}\) from \(a\) to \(b\) with \(\text{strength}(P'_{ab}) \geq \text{strength}(P_{ab})\).

Proof Structure¶

Forward direction (Theorem 4.4): Via inductive proof of Lemma 4.2—Fix edges must appear in all River graphs; BC/CBC edges guarantee that the target vertex is dominated in every universe → fixedly dominated candidates cannot be winners in any universe.
Backward direction (Theorem 4.9): For a candidate \(a\) that is "cyclically dominated" or "undominated," prove that certificate tree \(T^a\) is a spanning tree (Lemma 4.8), then show that under the certificate tiebreaking \(\tau^a\), the River graph equals exactly \(T^a\).

Key Experimental Results¶

Experimental Setup¶

Synthetic elections without a Condorcet winner were generated using the normalized Mallows model (dispersion parameter 0.7), with number of candidates \(m \in [5, 50]\) and number of voters \(n \in \{10, 50, 100, 200\}\).

Main Results: Scalability¶

Method	Number of Candidates	Runtime
RV-PUT (brute force)	Timeout (30 min) at \(m \geq 7\)	Exponential growth
RP-PUT (brute force)	Timeout (30 min) at \(m \geq 7\)	Exponential growth
FUN algorithm	Completes for \(m = 7\)–\(50\)	\(< 0.1\) seconds

Ablation / Comparison: Against Other Polynomial Methods¶

Candidate Range	FUN vs. Split Cycle	FUN vs. Beat Path	FUN vs. Stable Voting
\(m \leq 16\)	Slightly slower	Slightly slower	Slightly slower
\(m \geq 17\)	Comparable	Comparable	Faster
\(m \geq 20\)	On par or faster	On par or faster	Faster

Key Findings¶

FUN makes River-PUT feasible on moderate-scale elections: On the same instances where brute-force methods timeout in 30 minutes, FUN completes in under 0.1 seconds.
FUN's performance is comparable to existing polynomial methods such as Split Cycle and Beat Path, and outperforms them on large instances.
The number of voters affects performance: Runtime increases when \(n\) is small relative to \(m\) (likely due to more near-tied edges).

Highlights & Insights¶

Unexpected complexity gap: The sole difference between River and Ranked Pairs—the branching condition—causes the complexity of PUT computation to drop from NP-complete to P. This phenomenon, where a minor design difference leads to a dramatic complexity separation, is striking.
Elegant edge-state classification: The four edge states (Fix/BC/CC/CBC) combined with three vertex states precisely encode the intricate scenarios of which edges are added or rejected across universes.
Practical value of certificate construction: The algorithm not only determines who wins, but also provides an interpretable certificate for each winner explaining why it dominates all other candidates.
Connection to AI alignment: Social choice theory for aggregating diverse human preferences is becoming an important tool in AI alignment.

Limitations & Future Work¶

The FUN graph may contain edges that appear in no actual River graph: The algorithm only removes edges rejected in all universes for the same reason, without distinguishing edges that are "sometimes rejected due to branching, sometimes due to cycle conditions."
Insufficient axiomatic analysis: As a new social choice function, a systematic comparison of RV-PUT against PUT-Ranked Pairs and River with respect to axioms such as clone independence remains incomplete.
Experiments are limited to synthetic data, lacking validation on real-world election datasets.
The Python implementation is unoptimized: No comparison was made against Wang et al.'s optimized implementation of RP-PUT.

Brill & Fischer (2012) proved that Ranked Pairs + PUT is NP-complete—this paper provides a contrasting result for River.
The River method itself was proposed by Döring et al. (2025) as a refinement of Split Cycle.
Insight: In algorithm design, even seemingly minor structural constraints (such as the branching condition) can yield qualitative improvements in computational complexity.

Rating¶

Novelty: ⭐⭐⭐⭐⭐ (Unexpected positive complexity result; elegant FUN algorithm design)
Experimental Thoroughness: ⭐⭐⭐⭐ (Systematic runtime comparisons, but lacks real-world data)
Writing Quality: ⭐⭐⭐⭐⭐ (Clear proof structure with sufficient intuitive explanation)
Value: ⭐⭐⭐⭐ (Important theoretical contribution to voting theory, though the application domain is relatively niche)