River: Difference between revisions
no edit summary
imported>Araucaria No edit summary |
No edit summary |
||
| (21 intermediate revisions by 11 users not shown) | |||
Line 1:
'''River''' is a cloneproof monotonic [[Condorcet method#Different ambiguity resolution methods|Condorcet ambiguity resolution method]] with similarities to both [[Ranked Pairs]] and [[
It was first proposed in 2004 by [[User:Heitzig-j|Jobst Heitzig]] on the
Jobst later refined the definition to be more similar to Ranked Pairs.<ref name="River concise">{{cite web | title=River method -- updated summary | website=Election-Methods mailing list | url=http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-October/014018.html | access-date=2020-02-17 |date=2004-10-06|last=Heitzig|first=Jobst}}</ref>
<!-- Say something about its use in an interactive setting? Damming rivers etc. -->
==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==
* [http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-October/014147.html 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 method|Schulze]].
* [http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-April/012713.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 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.<ref name="Votedesc">{{cite web |url=http://9mail-de.spdns.de/m-schulze/votedesc.pdf |access-date=2020-02-17 |date=2007-06-12|last=Smith|first=Warren D.|pages=12-13|title=Descriptions of single-winner voting systems}}</ref> The wv and pairwise opposition variants use the Condorcet matrix <math> C</math> as the adjacency matrix, whereas the margins variant uses a matrix <math>D</math> with <math>D_{A>B} = C_{A>B} - C_{B>A}</math>.
Since it's possible to determine the [[w:Minimum spanning tree|minimum spanning tree]] of a dense graph in <math>O(|E|)</math> time, it is possible to determine the winner of the River method in <math>O(c^2)</math> time, where <math>c</math> is the number of candidates. Warren provides such an algorithm in his paper.<ref name="Votedesc"/>
==Criterion compliances==
River passes [[Condorcet criterion|Condorcet]], [[Smith set|Smith]], the [[monotonicity criterion]]<ref name="Votedesc"/>, independence of clones, and independence of Pareto-dominated alternatives.<ref name="IPDA">{{cite web | title=River method - a refinement, minor computational evidence, and a generalized IPDA criterion ISDA | website=Election-Methods mailing list | url=http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-April/078100.html | access-date=2020-02-17 |date=2004-04-24 |first=Jobst |last=Heitzig}}</ref> 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.
==References==
[[Category:Smith-efficient Condorcet methods]]
[[Category:Defeat-dropping Condorcet methods]]
| |||