Anonymous user
River: Difference between revisions
minor grammatical change for clarity, adding section about number of operations
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).
<!--
| |||