River

River is a cloneproof monotonic Condorcet ambiguity resolution method with similarities to both Ranked Pairs and Schulze, but when cycles exist, can in rare cases find a different winner than either of the other two methods.

It was first proposed in 2004 by Jobst Heitzig on the Election-methods mailing list. Jobst later refined the definition to be more similar to Ranked Pairs.

Summary

Quick summary of method, which is identical to Ranked Pairs except where emphasized:

• Rank defeats in descending order of winning vote strength.
• Starting with the strongest defeat, affirm defeats unless a cycle is created or a candidate is defeated twice.

The result is that only sufficient defeat information to determine the winner is included.

Because not all defeats are processed, the social ordering is not linear—in general, it is a tree (or river) diagram, with the victor at the base of the river.

Examples

• Example using 2004 baseball scores. This shows how a 14-candidate election winner can be determined much more quickly using River than with RP or Schulze.
• Early criticism of the River method. This shows that the River method violates mono-add-top and mono-remove-bottom.

River can be interpreted as a Minmax method, Minmax(non-cyclic pairwise loss) or MMNCPL. It is similar to Minmax(winning votes) except that River elects the candidate whose greatest non-cyclic pairwise loss to another candidate is least. As in Ranked Pairs, the greatest pairwise loss (GPL) of each candidate is considered in order from largest (among all candidates) to smallest and locked. If a candidate's GPL is cyclic, it is discarded, and the next-greatest pairwise loss of that candidate is added to the list. When the non-cyclic greatest pairwise losses of (N-1) candidates have been locked, the remaining candidate is the winner.

Runtime

The River method constructs a maximum spanning tree from the undirected multigraph whose adjacency matrix is based on the Condorcet matrix. The wv and pairwise opposition variants use the Condorcet matrix $C$ as the adjacency matrix, whereas the margins variant uses a matrix $D$ with $D_{A>B}=C_{A>B}-C_{B>A}$.

Since it's possible to determine the minimum spanning tree of a dense graph in $O(|E|)$ time, it is possible to determine the winner of the River method in $O(c^{2})$ time, where $c$ is the number of candidates. Warren provides such an algorithm in his paper.

Criterion compliances

River passes Condorcet, Smith, the monotonicity criterion, independence of clones, and independence of Pareto-dominated alternatives. It fails mono-add-top, later-no-harm, and the participation criterion.

In addition, River passes Heitzig's independence of strongly dominated alternatives criterion, which is weaker than independence of uncovered alternatives and stronger than independence of Pareto-dominated alternatives.

Smith

Suppose A is in the Smith set and B is not. By definition, A beats B pairwise. In the absence of any constraints, A>B will be locked before B>A. The only possible constraints preventing A>B from being locked are that someone else over B is already locked; or that B beats someone who beats A, so that locking A>B would create a cycle. Since B is not in the Smith set, the latter can't happen. If some other X>B is already locked, then either X is in the Smith set or not. If X is in the Smith set, then Smith is already satisfied (even if the winner happens to not be A). On the other hand, if X is not in the Smith set, then the proof can be repeated with X in the place of B.

Independence of clones

Suppose A is cloned into two candidates A1 and A2. Every voter who ranked some candidate X above A now ranks X over both clones, and every voter who ranked A above X now ranks both clones above X. For any other candidate, Y>A1 is thus locked iff Y>A was locked in the original election, and A1>Y is locked iff A>Y was locked in the original election. As a consequence, pairwise contests not involving the clones are locked iff they were locked in the original election. So A can't lose by being cloned, can't win by being cloned, and can't affect what other candidate X wins, by being cloned.