Implementation of the Tideman ranked pairs algorithm
This algorithm takes a collection of rankings and produces a reasonably fair aggregate ranking using T.N. Tideman's Ranked Pairs Algorithm.
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.
pivot-libre/tideman as a dependency in your project's composer.json.
See tests/RankedPairsCalculatorTest.php for example usage.
- Independence of Clones as a Criterion for Voting Rules. Tideman, T.N. Soc Choice Welfare (1987) 4: 185. https://doi.org/10.1007/BF00433944
- Complete Independence of Clones in the Ranked Pairs Rule. Zavist, T.M. & Tideman, T.N. Soc Choice Welfare (1989) 6: 167. https://doi.org/10.1007/BF00303170
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.
- Wikipedia's Ranked Pairs article
- Canadian MP Ron McKinnon's condorcet.ca offers an excellent layperson-oriented survey of Ranked Pairs. Be sure to explore the various in-page dropdown sections and tabs, as some important parts of the site’s content are hidden inside.
- The Cambridge Press Handbook of Computational Social Choice is available as a free pdf. Tideman’s Ranked Pairs Algorithm is described on page 98-101.
- An alternate description of the Tideman-Zavist tie-breaking rule is in an electorama mailing list post by Dr. Markus Schulze. The explanation is just a few lines long, starting with "Thomas Zavist suggested that...".
- Install PHP 7.1 and composer.
- The library is known to work when the following PHP extensions are installed, though the minimal list of extensions is probably shorter (See Issue #51): ctype,curl,dom,iconv,json,mbstring,openssl,pdo,pdo_sqlite,phar,sqlite3,tokenizer,xmlreader,xmlwriter,zlib
- Fork this repo.
- Clone your fork.
- Add this repo as upstream.
git remote add upstream firstname.lastname@example.org:pivot-libre/tideman.git
git remote add upstream https://github.com/pivot-libre/tideman.git
- Download the dependencies
- Build the project
- This command checks the syntax of the files, run tests, checks for formatting conformance, and performs static code quality analysis.
- At the end of the output you should see
BUILD FINISHED. You should not see
- Make sure you have installed xdebug.
- Open a web browser to
- For example:
commityour local changes
- Push your changes to your GitHub fork
git push origin
- Create a pull request between your fork and the PivotLibre/tideman repo.
git fetch upstream
- Depending on whether you are using a merge-based or rebase-based workflow you will run one of:
git merge upstream/0.x
git rebase upstream/0.x