User:BenBE/Schulze method: Difference between revisions
m
removing header template that makes this page appear among task category
m (Linked Schwartz set, explaination inline would go too far.) |
m (removing header template that makes this page appear among task category) |
||
| (2 intermediate revisions by one other user not shown) | |||
Line 8:
# From the list of pairwise defeats, we generate a set of transitive defeats.
## An option A transitively defeats an option C if A defeats C or if there is some other option B where A defeats B AND B transitively defeats C.
# We construct the [[wp:Schwartz set|Schwartz set]] from the set of transitive defeats.
## An option A is in the
# If there are defeats between options in the Schwartz set, we drop the weakest such defeats from the list of pairwise defeats, and return to step 3.
## A defeat (A,X) is weaker than a defeat (B,Y) if V(A,X) is less than V(B,Y). Also, (A,X) is weaker than (B,Y) if V(A,X) is equal to V(B,Y) and V(X,A) is greater than V(Y,B).
Line 39:
Please also include the '''Matrix of pairwise preferences''' and '''Strengths of the strongest paths''' together with the pairwise and transitive defeats in the output alongside the final candidate ranking.
==PHP==
Doesn't fully cover tie resolution in the Schwartz set yet, but should give proper results for the other cases.
<lang php>
<?php
//header('Content-Type: text/plain; charset=utf8;');
//Counted ballots by ranking
$votes = array(
'5 A>C>B>E>D',
'5 A>D>E>C>B',
'8 B>E>D>A>C',
'3 C>A>B>E>D',
'7 C>A>E>B>D',
'2 C>B>A>D>E',
'7 D>C>E>B>A',
'8 E>B>A>D>C'
);
//The candidates to elect
$candidates = array('A', 'B', 'C', 'D', 'E');
//Initialize the defeats counter
$defeats = array_fill_keys($candidates, array_fill_keys($candidates, 0));
//Count votes to determine pairwise defeats
foreach($votes as $vote) {
//separate count and ranking
list($vote_count, $vote_ranking) = explode(' ', trim($vote), 2);
//Split by explicit preference
$vote_pref = explode('>', $vote_ranking);
//Assume everyone is unranked and thus least preferred
$ranking = array_fill_keys($candidates, count($candidates)+1);
//Get ranking
$rank = 1;
foreach($vote_pref as $pref) {
$vote_pref_same = explode('=', $pref);
foreach($vote_pref_same as $pref_same) {
$pref_same = trim($pref_same);
if(false === array_search($pref_same, $candidates, true)) {
die("Candidate $pref_same of ballot $vote doesn't exist!");
}
if($ranking[$pref_same] < $rank) {
die("Candidate $pref_same of ballot $vote already ranked!");
}
$ranking[$pref_same] = $rank;
}
$rank += count($vote_pref_same);
}
if($rank > count($candidates)+1) {
die("Internal error on ballot $vote");
}
foreach($candidates as $c1) {
foreach($candidates as $c2) {
if($c1 != $c2) {
//Smaller rankings indicate preference
if($ranking[$c1] < $ranking[$c2]) {
//echo "Counting votes on $c1 over $c2 another $vote_count votes<br/>\n";
$defeats[$c1][$c2] += $vote_count;
}
}
}
}
}
//Matrix of pairwise defeats
//var_dump($defeats);
//Generate the list of pairwise defeats
$pairwise_defeats = array();
foreach($candidates as $c1) {
foreach($candidates as $c2) {
if($c1 != $c2) {
//Smaller rankings indicate preference
if($defeats[$c1][$c2] > $defeats[$c2][$c1]) {
//echo "Direct pairwise defeat for $c1 over $c2<br/>\n";
$pairwise_defeats[] = array($c1, $c2);
}
}
}
}
//List of pairwise direct defeats
//var_dump($pairwise_defeats);
//Determine strongest paths
$paths = array_fill_keys($candidates, array_fill_keys($candidates, 0));
foreach($candidates as $c1) {
foreach($candidates as $c2) {
if($c1 != $c2) {
//Smaller rankings indicate preference
if($defeats[$c1][$c2] > $defeats[$c2][$c1]) {
$paths[$c1][$c2] = $defeats[$c1][$c2];
} else {
$paths[$c1][$c2] = 0;
}
}
}
}
foreach($candidates as $c1) {
foreach($candidates as $c2) {
if($c1 != $c2) {
foreach($candidates as $c3) {
if($c1 != $c3 && $c2 != $c3) {
$paths[$c2][$c3] = max( $paths[$c2][$c3], min( $paths[$c2][$c1], $paths[$c1][$c3]));
}
}
}
}
}
//Output the strongest paths
//var_dump($paths);
//Generate list of transitive defeats
$transitive_defeats = array();
foreach($candidates as $c1) {
foreach($candidates as $c2) {
if($c1 != $c2) {
//Smaller rankings indicate preference
if($paths[$c1][$c2] > $paths[$c2][$c1]) {
//echo "Transitive defeat for $c1 over $c2<br/>\n";
$transitive_defeats[] = array($c1, $c2);
}
}
}
}
//List of transitive defeats
//var_dump($transitive_defeats);
//Determine the ranking
$final_ranking = array();
$final_rank = 1;
$unranked_candidates = $candidates;
while(count($unranked_candidates)) {
$ranking_candidates = $unranked_candidates;
foreach($ranking_candidates as $k1 => $c1) {
foreach($ranking_candidates as $c2) {
if($c1 != $c2) {
//Smaller rankings indicate preference
if($paths[$c1][$c2] > $paths[$c2][$c1]) {
continue;
}
if(!($paths[$c1][$c2] < $paths[$c2][$c1])) {
continue;
}
unset($ranking_candidates[$k1]);
break;
}
}
}
$final_ranking[$final_rank] = array_values($ranking_candidates);
$final_rank += count($ranking_candidates);
foreach($ranking_candidates as $k1 => $c1) {
unset($unranked_candidates[$k1]);
}
}
var_dump($final_ranking);
</lang>
| |||