River: Difference between revisions
no edit summary
imported>MarkusSchulze No edit summary |
No edit summary |
||
| (13 intermediate revisions by 9 users not shown) | |||
Line 1:
'''River''' is a cloneproof monotonic [[
It was first proposed in 2004 by [[User:Heitzig-j|Jobst Heitzig]] on the [[Election-methods mailing list]].<ref name="River initial">{{cite web | title=Hello again -- and a new method for you! | website=Election-Methods mailing list | url=http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-April/078029.html | access-date=2020-02-17 |date=2004-04-10 |last=Heitzig|first=Jobst}}</ref><ref name="River refinement">{{cite web | title=Hello again -- and a new method for you! | website=Election-Methods mailing list | url=http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-April/110761.html | access-date=2020-02-17 |date=2004-04-11|last=Heitzig|first=Jobst}}</ref>
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.
Line 7 ⟶ 12:
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
==Examples==
* [http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-October/
* [http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-April/
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==
▲* [http://lists.electorama.com/pipermail/election-methods-electorama.com/2004-October/014102.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 Beatpath.
▲* [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
[[Category:Smith-efficient Condorcet methods]]
[[Category:Defeat-dropping Condorcet methods]]
| |||