River: Difference between revisions
imported>Araucaria (Minmax interpretation of River) |
imported>Araucaria (minor grammatical change for clarity, adding section about number of operations) |
||
Line 16:
* [http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-April/012678.html 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
Number of operations: for each candidate, determine greatest pairwise loss [O(N)]; For all unlocked candidates' GPLs, determine maximum GPL [O(N)]. So the complexity is O(N^2) at best. At worst, N-1 of the candidates could have N-1 cyclic GPLs each, requiring another O(N) max-searches each, taking the order of operations up to O(N^3).
<!--
| |||
Revision as of 20:17, 28 February 2007
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.
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.
It was first proposed by Jobst Heitzig on the Election-methods mailing list:
- First proposal
- slight refinement
- More concise definition. In this last version, River is defined very similarly to ranked pairs.
- 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.
Number of operations: for each candidate, determine greatest pairwise loss [O(N)]; For all unlocked candidates' GPLs, determine maximum GPL [O(N)]. So the complexity is O(N^2) at best. At worst, N-1 of the candidates could have N-1 cyclic GPLs each, requiring another O(N) max-searches each, taking the order of operations up to O(N^3).