This algorithm takes a collection of rankings and produces a reasonably fair aggregate ranking using T.N. Tideman's Ranked Pairs Algorithm.
This documentation's intended audience is programmers. See Wikipedia's Ranked Pairs article or Canadian MP Ron McKinnon's condorcet.ca for layperson-oriented explanations.
This algorithm first computes the difference in popular support between all pairs of candidates across all ballots. This pairwise difference between two candidates is called a margin. Next, the algorithm sorts the margins in order of descending difference. The algorithm then builds a graph data structure by iterating through the sorted list of margins from largest difference to smallest difference, adding an edge that points from the winning candidate to the losing candidate of each margin. If adding a margin's edge would introduce a cycle, the margin is ignored. The winning candidate is the candidate who has no edges pointing at them once the graph has been completed. In other words, the winner is the source node in the completed graph. If multiple winners are desired, then the entire algorithm is repeated without considering candidates that have already won.
Add pivot-libre/tideman
as a dependency in your project's composer.json.
See tests/RankedPairsCalculatorTest.php for example usage.
The original 1987 Ranked Pairs paper lacked a tie-breaking rule. The follow-up 1989 paper added a tie-breaking rule.
When ranking pairs of candidates, it is possible that the difference in popular support between two candidates is equal to the difference in popular support between two other candidates. In that case, the tie between the pairs of candidates must be broken by a pairwise tie-breaking rule. This library breaks pairwise ties according to a user-specified tie-breaking Ballot object. If the user of the library specifies a tie-breaking Ballot object that contains ties within it (i.e. ties between candidates), the library breaks all of that Ballot object's ties using PHP's default random number generator. The library does not enforce the source of the tie-breaking Ballot object. If a user wished to follow the tie-breaking rule specified in Zavist, Tideman 1989, they should randomly select a Ballot object from among those submitted by the electorate, and use it as the tie-breaking Ballot object.
git remote add upstream git@github.com:pivot-libre/tideman.git
git remote add upstream https://github.com/pivot-libre/tideman.git
composer install
vendor/bin/phing
BUILD FINISHED
. You should not see BUILD FAILLED
.vendor/bin/phing coverage
file:///<file-path-to-cloned-repo>tideman/build/coverage/index.html
file:///home/john_doe/src/tideman/build/coverage/index.html
add
, and commit
your local changesgit push origin
git fetch upstream
git merge upstream/0.x
git rebase upstream/0.x