julien-boudry/condorcet

Complete election manager, providing natively many methods of Condorcet : Condorcet basic / Copeland / Dodgson / Kemeny–Young / Minimax / Ranked Pairs / Schulze

v2.1-beta2 2019-12-06 21:52 UTC

README

Condorcet

Build Status License Packagist Packagist Download GitHub contributors GitHub code size in bytes Codacy Badge Codacy Badge

Main Author: Julien Boudry
License: MIT - Please say hello if you like or use this code!
Contribute: Contribute File
Donation: bc1qesj74vczsetqjkfcwqymyns9hl6k220dhl0sr9 or Github Sponsor Page
You can also offer me a bottle of good wine.

Methods provided natively: Condorcet / Borda (+ Nauru variant) / Copeland / Dodgson (2 Approximations) / FTPT / Instant-runoff (alternative vote) / Kemeny–Young / Minimax (+ variants) / Ranked Pairs (+ variants) / Schulze (+ variants)

Condorcet PHP

Presentation | Manual | Methods References | Tests

Condorcet is an application implementing the Condorcet voting system and many other methods like the Schulze, Tideman, Borda or Alternative Voting. And also a powerful election manager allowing the logical management of a phased election, with many natives options and elections methodes included.

Two different ways to use Condorcet:

  • A command line application, for quick use of essential features without complicated technical knowledge. Allowing you to easily compute your elections results and stats.
  • A PHP library that you can include in your code to take advantage of 100% of the advanced features (abstraction, control, interaction, extensions).

Read more about alternative voting methods >> https://en.wikipedia.org/wiki/Condorcet_method

Summary

  1. Project State and Specifications
  2. Main features
  3. Supported Methods
    a. Methods provided natively
    b. Add your own method
  4. Use Condorcet as a command line application
    a. Install as an application
    b. Condorcet Wiki - Command Line Manual
    c. Command Line - Examples
  5. Use Condorcet as a PHP Library
    a. Install / Autoloading
    b. Condorcet Wiki Manual
    c. Class & Methods reference
    d. PHP Library - Examples Have a look on Examples!
    e. Really quick and simple example
  6. Performance & Coding style considerations
  7. Roadmap for further releases
  8. Related projects / They use Condorcet

Project State and Specifications

Releases Notes

  • Stable Version: 2.1.x
      • PHP Requirement: PHP 7.4 with Json PHP extension. (tested up to PHP 7.4)
  • Old Stable: 2.0.x support provided
    • PHP Requirement: PHP 7.1 with Ctype, MB_String, Json common extensions. (tested up to PHP 7.4)
  • Very Old Stable: 1.0.x Support requiring some bait.
    • PHP Requirement: PHP 5.6 with Ctype, MB_String, Json common extensions. (tested up to PHP 7.1)

Some support and fix can be done for 0.14 version on demand. Since v0.90, you should consider then it's a new project (api, engine).

Main features

  • Manage an election
    • Respect an election cycle: Registering candidate, registering a vote, get results from many algorithms.
    • Ordered votes, delete it, simulate partials results.
    • Many input type available (String, Json, Parse text, Objects...)
    • Integrity check (checksumming) and logs.
    • Support for storing elections (serializing Election object, export data...)
    • Some methods can be used nearly front final user (anti-spam check, parsing input, human-friendly results and stats, vote constraints...)
  • Get election results and stats
    • Get the natural Condorcet Winner, Loser, Pairwise, Paradox...
    • Get full ranking from advanced methods (Schulze, Copeland, Ranked Pairs, Kemeny–Young, Minimax...)
    • Get some additional stats from these methods
    • Force ranking all candidate implicitly (default) or allow voters to not rank all candidates.
    • Put weight for each vote, give more importance to certain voters.
  • Be more powerful
    • All are objects, all are abstract (But there are many higher-level functions and inputs types).
    • Candidates and Votes are objects which can take part to multiples elections at the same time and change her name or ranking dynamically. That allows powerful tools to simulate elections.
    • Manage hundred billions of votes by activating an external driver to store (instead of RAM) an unlimited number of votes during the computation phase. A PDO driver is provided by default, an example is provided with SQLite, an interface allows you to design other drivers.
  • Extend it! Configure it!
    • Modular architecture to extend it without fork Condorcet PHP! Just make your own module on your own namespace.
      • Election, Candidate and Vote class are extensible.
      • Add your own ranking algorithm.
      • Create your own votes constraints.
    • Allow you to use your own datastore driver to manage very large elections at your way without ram limit. A first driver for PDO (and Sqlite example) is provided.
    • Many configurations options and methods.

Condorcet PHP is not designed for high performances. But can handle virtually unlimited voting without limit or degrading performance, it's a linear and predictable scheme.
And has no certification or proven implementation that would guarantee a very high level of reliability. However, there are many written tests for each voting methods and features. This ensures an excellent level of confidence in the results.

Supported Methods

Methods provided natively

All explanations and implementation choices on this documentation

Add your own method as module

Condorcet is designed to be easily extensible with new algorithms (they don't need to share the same namespace).
More explanations in the documentation below

Use Condorcet as a command line application

I have undertaken and continues to undertake efforts to reform and improve the documentation. Thereof is not yet satisfactory and perfectly updated. Your help is welcome!

Install as an application

Option 1: Build it yourself with composer

(you must have PHP >= 7.4 and composer)

mkdir Condorcet && cd Condorcet
composer require julien-boudry/condorcet
./vendor/bin/condorcet --help

# Execute a command, example:
./vendor/bin/condorcet election -c "A;B;C" -w "A>B;A>C;C>B" -r

Option 2: From Docker Container

You must install Docker first. See installation instructions.

From a public image
docker pull julienboudry/condorcet:latest
docker run --hostname=condorcet -it --rm julienboudry/condorcet bash

# Execute a command, example:
root@condorcet:/usr/src/condorcetapp# condorcet election -c "A;B;C" -w "A>B;A>C;C>B" -r
From docker file
git clone https://github.com/julien-boudry/Condorcet.git
cd Condorcet
docker build -t condorcet .
docker run --hostname="condorcet" --rm -it condorcet bash

# Execute a command, example:
root@condorcet:/usr/src/condorcetapp# condorcet election -c "A;B;C" -w "A>B;A>C;C>B" -r

Condorcet Wiki - Command Line Manual

Incomming

Command Line - Some Quick Examples

See your installation method upside for main call. Below from the official docker image with command condorcet.

A simple and short election

condorcet election --candidates="A;B;C" --votes="A>B ; myTag1||C=B>A ; A>C ; B>C;A" -lr Schulze Borda Minimax
+-----------+- Registered Vote List --+-----------+
| Vote Num. | Vote      | Vote Weight | Vote Tags |
+-----------+-----------+-------------+-----------+
| 1         | A > B > C | 1           |           |
| 2         | B = C > A | 1           | myTag1    |
| 3         | A > C > B | 1           |           |
| 4         | B > C > A | 1           |           |
| 5         | A > B = C | 1           |           |
+-----------+-----------+-------------+-----------+

Condorcet Natural Winner & Loser
--------------------------------
+------ Natural Condorcet -------+
| Type               | Candidate |
+--------------------+-----------+
| * Condorcet Winner | A         |
| # Condorcet Loser  | C         |
+--------------------+-----------+

Results per Methods
-------------------
+-- Results: Schulze Winning ---+
|       Rank       | Candidates |
+------------------+------------+
|        1         | A*         |
|        2         | B          |
|        3         | C#         |
+------------------+------------+
+----- Results: BordaCount -----+
|       Rank       | Candidates |
+------------------+------------+
|        1         | A*         |
|        2         | B          |
|        3         | C#         |
+------------------+------------+
+-- Results: Minimax Winning ---+
|       Rank       | Candidates |
+------------------+------------+
|        1         | A*         |
|        2         | B,C        |
+------------------+------------+

 [OK] Success

From Files / With Stats

You can print stats. And load candidates or votes from file. See Condorcet Manual for more details.

condorcet election --stats --candidates /path/to/myCandidates.text --votes /path/to/myVotes.txt 

Results per Methods
-------------------
+---- Results: Kemeny–Young ----+
|       Rank       | Candidates |
+------------------+------------+
|        1         | A*         |
|        2         | B          |
|        3         | C#         |
+------------------+------------+
+---------- Stats: Kemeny–Young -----------+
| Stats                                    |
+------------------------------------------+
| bestScore: 11                            |
| rankingScore:                            |
|     -                                    |
|         1: A                             |
|         2: B                             |
|         3: C                             |
|         score: 11                        |
|     -                                    |
|         1: A                             |
|         2: C                             |
|         3: B                             |
|         score: 9                         |
|     -                                    |
|         1: B                             |
|         2: A                             |
|         3: C                             |
|         score: 9                         |
|     -                                    |
|         1: B                             |
|         2: C                             |
|         3: A                             |
|         score: 7                         |
|     -                                    |
|         1: C                             |
|         2: A                             |
|         3: B                             |
|         score: 7                         |
|     -                                    |
|         1: C                             |
|         2: B                             |
|         3: A                             |
|         score: 5                         |
|                                          |
+------------------------------------------+

 [OK] Success

Votes Weight / Implicit Ranking Mode / No-Tie constraint

condorcet election --candidates="A;B;C" --votes="A>B ^10 ; B>A ; B>A" -lr --allows-votes-weight
+-----------+- Registered Vote List --+-----------+
| Vote Num. | Vote      | Vote Weight | Vote Tags |
+-----------+-----------+-------------+-----------+
| 1         | A > B > C | 10          |           |
| 2         | B > A > C | 1           |           |
| 3         | B > A > C | 1           |           |
+-----------+-----------+-------------+-----------+

Condorcet Natural Winner & Loser
--------------------------------
+------ Natural Condorcet -------+
| Type               | Candidate |
+--------------------+-----------+
| * Condorcet Winner | A         |
| # Condorcet Loser  | C         |
+--------------------+-----------+
condorcet election --candidates="A;B;C" --votes="A>B>C ; B>A ; A" -lr -i --desactivate-implicit-ranking
+-----------+- Registered Vote List --+-----------+
| Vote Num. | Vote      | Vote Weight | Vote Tags |
+-----------+-----------+-------------+-----------+
| 1         | A > B > C | 1           |           |
| 2         | B > A     | 1           |           |
| 3         | A         | 1           |           |
+-----------+-----------+-------------+-----------+

Condorcet Natural Winner & Loser
--------------------------------
+------ Natural Condorcet -------+
| Type               | Candidate |
+--------------------+-----------+
| * Condorcet Winner | NULL      |
| # Condorcet Loser  | C         |
+--------------------+-----------+
condorcet election --candidates="A;B;C" --votes="A>B ; B>C=A ; C=B>A ; B" -lr --no-tie
+-----------+- Registered Vote List --+-----------+
| Vote Num. | Vote      | Vote Weight | Vote Tags |
+-----------+-----------+-------------+-----------+
| 1         | A > B > C | 1           |           |
+-----------+-----------+-------------+-----------+

Condorcet Natural Winner & Loser
--------------------------------
+------ Natural Condorcet -------+
| Type               | Candidate |
+--------------------+-----------+
| * Condorcet Winner | A         |
| # Condorcet Loser  | C         |
+--------------------+-----------+

Use Condorcet as a PHP Library

Install / Autoloading

This project is consistent with the standard PSR-4 and can be loaded easily and without modification in most frameworks or Composer autoloader. Namespace \CondorcetPHP is used. The examples also provide an easy way of implementation using an optional Condorcet autoloader. If you don't want to use composer or others PSR-4 autoloader.

Please visit the install section from the wiki

Condorcet Wiki Manual

Living and learning examples, giving an overview but not exhaustive of the possibilities of the library.

Class & Methods reference

The precise documentation of methods is not a wiki. It can be found in the form of Markdown in the "Documentation" folder for each release.

PHP Library - Examples

Great overview

With Html output basics examples

Specifics examples

Really quick and simple example

OK: sacrifice to the local tradition of lazy.

  use CondorcetPHP\Condorcet\Condorcet;
  use CondorcetPHP\Condorcet\Election;
  use CondorcetPHP\Condorcet\Candidate;
  use CondorcetPHP\Condorcet\CondorcetUtil;
  use CondorcetPHP\Condorcet\Vote;

  $myElection1 = new Election () ;

  // Create your own candidate object
  $candidate1 = new Candidate ('Candidate 1'); 
  $candidate2 = new Candidate ('Candidate 2');
  $candidate3 = new Candidate ('Candidate 3');

  // Register your candidates
  $myElection1->addCandidate($candidate1);
  $myElection1->addCandidate($candidate2);
  $myElection1->addCandidate($candidate3);
  $candidate4 = $myElection1->addCandidate('Candidate 4');

  // Add some votes, by some ways
  $myElection1->addVote(  array(
                              $candidate2, // 1
                              [$candidate1, $candidate4] // 2 - Tie
                              // Last rank is optionnal. By default, it will be implicitly completed in $candidate3. This behaviour can be changed by election, before, during or after the vote. The initial submission being preserved.
                          )
  );

  $myElection1->addVote('Candidate 2 > Candidate 3 > Candidate 4 = Candidate 1'); // Last rank can also be omitted

  $myElection1->parseVotes(
              'Candidate 1 > Candidate 2 = Candidate 4 > Candidate 3 * 4
              Candidate 3 > Candidate 1 * 3'
  ); // Powerfull, it add 7 votes

  $myElection1->addVote( new Vote ( [   $candidate4,
                                        $candidate2 ]
                                        // You can ignore the over. They will be at the last rank in the contexte of each election. 
                                  )
  );


  // Get Result

    // Natural Condorcet Winner
    $myWinner = $myElection1->getWinner(); // Return a candidate object
          echo 'My winner is ' . $myCondorcetWinner->getName();

    // Natural Condorcet Loser
    $myLoser = $myElection1->getLoser(); // Return a candidate object
          echo 'My loser is ' . $myCondorcetLoser->getName();

    // Schulze Ranking
    $myResultBySchulze = $myElection1->getResult('Schulze'); // Return a multi-dimensional array, filled with objects Candidate (multi-dimensional if tie on a rank)
      # Echo it easily 
      var_dump( CondorcetUtil::format($myResultBySchulze) );

    // Get Schulze advanced computing data & stats
    $mySchulzeStats = $myElection1->getResult('Schulze')->getStats();

    // Get Copeland Ranking
    $myResultByCopeland = $myElection1->getResult('Copeland');

    // Get Pairwise
    $myPairwise = $myElection1->getPairwise();

  // How long computation time behind us?
  $timer = $myElection1->getGlobalTimer();

  // SHA-2 checksum and sleep
  $myChecksum = $myElection1->getChecksum();
  $toStore = serialize($myElection1);
  $comeBack = unserialize($toStore);
  $comeBack->getChecksum() === $myChecksum; // True


  # And many many more than that. Read the doc. & look at advanced examples.

Performance & Coding style considerations

Coding standards:

The code is close to the respect of PSR-1 (lacks only the naming of methods), and freely influenced by PSR-2 when it is not unnecessarily authoritarian.

Performance:

  • Complete and huge use case with all algorithms chained, 6 candidates and one thousand votes (many with implicit ranking).
    • Memory usage: less than 6M
    • Execution time: less than 600ms
Kemeny-Youg case:
  • use Kemeny-Young 6 candidates: 5MB - 150ms
  • use Kemeny-Young 7 candidates: 32MB - 600ms
  • use Kemeny-Young 8 candidates: 135MB - 2500ms
Massive election case:

Extending PHP memory_limit allows you to manage hundreds of thousands of votes, but it can be a bit slower than outsource this data (PHP don't like that) and it's not extensive to infinity.

If you need to manage an election with more than 50 000 votes. You should consider externalizing your data, Condorcet provides a simple PDO driver to store data outside RAM between processing steps, this driver stores it into a classical relational database system, it supports hundreds millions votes (or more). A very simple example with Sqlite is provided and very easy to activate.

You can also develop your own datastore driver (to store into NoSQL... all your fantasy), the modular architecture allows you to link it easily.

Have a look to the manual

Benchmark on a modern machine (linux - x64 - php 7.4 - cli).

Roadmap for further releases

  • Rebuild Exception System
  • Research reference librarians !!

Related projects / They use Condorcet

  • From August 2014: Condorcet.Vote Web services to create and store online Condorcet election. Including interactives and collaborative features.
    It is based in large part on this project and uses the library as a real election manager for computing, storage & stats.
  • Mahler-S2-BlindTest-Condorcet (French interface) Web wrapper to compute and show the result for classical music blind challenge with the Condorcet Class full potential (can also be used and adapted for any elections).
    Look like the examples provided here, but better: Gustav Mahler blind listening test