Abstract
We introduce River, a novel Condorcet-consistent voting method based on pairwise majority margins. River can be viewed as a simplified variation of Tideman's Ranked Pairs method, designed to be easy to explain, compute by hand, and interpret via a directed tree "certificate." As a refinement of the Split Cycle method, River shares many desirable properties with Ranked Pairs and Schulze's Beat Path method, such as independence of clones. Crucially, River is uniquely resistant to agenda manipulation, satisfying the strong property of Independence of Pareto-dominated Alternatives (IPDA).
Introduction: The Challenge of Social Choice
In social choice theory, a Condorcet winner—a candidate who defeats every other candidate in head-to-head matchups—is considered the ideal outcome. However, voter preferences frequently result in "cycles" (e.g., A beats B, B beats C, and C beats A), where no Condorcet winner exists.
Existing methods to resolve these cycles, such as Ranked Pairs or the Schulze method, are mathematically robust but face two significant hurdles:
- Interpretability: They often produce dense, complex graphs that are difficult for voters to understand or for officials to verify manually.
- Agenda Manipulation: Most methods are vulnerable to the introduction of "spoiler" candidates. Specifically, they often violate the Independence of Pareto-dominated Alternatives (IPDA), meaning the addition of a universally disliked candidate (one who is Pareto-dominated) can flip the election result.
The River Algorithm
The River Method addresses these issues by operating on a margin graph, where edges represent majority wins and weights indicate the size of the majority.
The algorithm follows a simple, greedy process:
- Sort: Rank all pairwise majority defeats by the size of their margin, from largest to smallest.
- Build: Starting with an empty graph, add these edges one by one in descending order of margin.
- Filter: An edge is only added if it does not create:
- A Cycle: This maintains acyclicity, similar to Ranked Pairs.
- A Branching: This ensures that no candidate has more than one "incoming" defeat edge.
- Result: This process naturally constructs a spanning tree (specifically, an arborescence). The "source" or root of this tree is the unique winner.
By prohibiting branching, River ensures that every defeated candidate is linked to the winner by a single, unambiguous path of "rebuttals," providing a clear certificate of victory.
Theoretical Advantages: Solving the Spoiler Problem
The most significant theoretical breakthrough of the River Method is its satisfaction of IPDA. In many other methods, a universally "bad" candidate can still influence the final ranking by participating in cycles.
Because River processes the strongest margins first and prevents branching, a Pareto-dominated candidate—who necessarily loses by a large margin to their dominator—is "locked in" as a loser early in the process. This prevents them from interfering with the more competitive cycles among top-tier candidates. Beyond IPDA, River satisfies other critical criteria, including Monotonicity, the Smith Criterion, and Independence of Smith-Dominated Alternatives (ISDA).
Practical Clarity and Interpretability
To demonstrate the method's practical utility, the authors compared it against established methods using both synthetic profiles and real-world data, such as the 2004 American League Baseball standings.
While methods like Ranked Pairs can result in a "hairball" of edges in complex scenarios, River consistently produces a clean, readable tree. In the baseball example, while Ranked Pairs created a cluttered graph for the 14 teams, River identified a clear "champion" at the root of a simple hierarchy. This "computability by hand" makes River a highly transparent and trustworthy method for real-world applications.
Limitations and Future Work
Despite its strengths, River is a "resolute" method, meaning it aims to produce a single winner. In some contexts, returning a set of winners (like the Smith Set) might be preferred. Additionally, like all resolute methods, River depends on a tiebreaker when margins are identical. While the choice of tiebreaker can influence the winner in close elections, the authors define "Pareto-consistent" tiebreakers to preserve axiomatic properties. Future research may further explore River's resistance to strategic voting beyond agenda manipulation.
Summary updated