User:BenBE/Schulze method

The Debian developer team has long been thinking of establishing a new team of people that should review community feedback and forward sensible suggestions to the developers so they would get less infeasable requests and more tasks they really should do to further their goals.

As there were many more developers willing to listen to the community and communicate the good ideas to their fellow workmates the developers decided on doing an election as it usually is helt when electing people for posts to fill. And so they announced they are going to have an alection following the usual Debian voting procedure:

1. Each voter's ballot ranks the options being voted on. Not all options need be ranked. Ranked options are considered preferred to all unranked options. Voters may rank options equally. Unranked options are considered to be ranked equally with one another.
2. From the list of options, we generate a list of pairwise defeats.
   1. An option A defeats an option B, if V(A,B) is strictly greater than V(B,A), where V(A,B) is the number of ballots ranking A (strictly) before B.
3. From the list of pairwise defeats, we generate a set of transitive defeats.
   1. 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.
4. We construct the Schwartz set from the set of transitive defeats.
   1. 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.
5. 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.
   1. 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).
   2. A weakest defeat is a defeat that has no other defeat weaker than it. There may be more than one such defeat.
6. If there are no defeats within the Schwartz set, then the winner is chosen from the options in the Schwartz set. If there is only one such option, it is the winner. If there are multiple options, the more preferred option wins; on a tie all options are ranked the same.
7. As long as there are options not yet ranked, remove all relations directly involving a candidate already ranked.

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 (example from English Wikipedia):

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

That is 5 voters ranked the candidates in the order strictly preferring A over C over B over E over D. Equally ranked candidates would have been delimited with an equal sign between them (e.g. A>C=B>E>D meaning C and B ranked the same).

Counting this preselection they found the following ranking:

1. E
2. A
3. C
4. B
5. D

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
\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
\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
\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>