User:BenBE/Schulze method: Difference between revisions
m
removing header template that makes this page appear among task category
(Simplified the description a bit.) |
m (removing header template that makes this page appear among task category) |
||
| (4 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 Schwartz set if for all (other) options B, either A transitively defeats B, or B does not transitively defeat A.
# 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.
Line 18:
Unfortunately noone of the management had any time to spare for counting the ballots for the poor developers after the election as they had just too many candidates, a much to big community and too much own work on their desks. Also they wanted to get the winning team quickly. So they were looking to automatically get the ranking given all the (digitized) ballots or accumulated rankings (i.e. number of ballots with a given variant of ranking).
In order to prepare the ceremony for the winning team a first pre-election to determine who was going to hand over the flowers to the winners was held yielding the following outcome
5 A>C>B>E>D
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>
| |||