pivot-libre/tideman

Implementation of the Tideman ranked pairs algorithm

0.8.1 2020-02-19 02:10 UTC

Requires

• clue/graph: 0.9.0
• graphp/algorithms: 0.8.1
• psr/log: ^1.0.2

Requires (Dev)

• cadre/sniffs: ^0.1.0
• monolog/monolog: ^1.23.0
• pds/skeleton: ^1.0.0
• phing/phing: ^2.16.0
• phpstan/phpstan: ^0.6.3
• phpunit/phpunit: ^6.2.3
• satooshi/php-coveralls: ^1.0.1
• squizlabs/php_codesniffer: ^3.0.1

Apache-2.0

• voting
• ranked pairs
• Tideman
• preferential voting
• Condorcet

README

Purpose

This algorithm takes a collection of rankings and produces a reasonably fair aggregate ranking using T.N. Tideman's Ranked Pairs Algorithm.

Background

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.

Summary

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.

Usage

Add pivot-libre/tideman as a dependency in your project's composer.json. See tests/RankedPairsCalculatorTest.php for example usage.

Details

Papers

• 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.

Pairwise Tie-Breaking

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.

Additional Reading

• 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.
  • Direct Link
  • Book Homepage
• 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...".

Contributing

Setup

• 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

Working With the Code

• Fork this repo.
• Clone your fork.
• Add this repo as upstream.
  • Examples:
    • git remote add upstream [e-mail]:pivot-libre/tideman.git
    • git remote add upstream https://github.com/pivot-libre/tideman.git
• Download the dependencies
  • composer install
• Build the project
  • vendor/bin/phing
  • 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 BUILD FAILLED.

Visualizing Test Coverage

• Make sure you have installed xdebug.
• Run
• vendor/bin/phing coverage
• Open a web browser to file:///<file-path-to-cloned-repo>tideman/build/coverage/index.html
• For example: file:///home/john_doe/src/tideman/build/coverage/index.html

Sharing Your Work

• Git add, and commit your local changes
• Push your changes to your GitHub fork
  • git push origin
• Create a pull request between your fork and the PivotLibre/tideman repo.

Getting Updates

• 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