abcvoting

Python implementations of approval-based committee (multi-winner) rules

Documentation is available!

Approval-based committee rules (ABC rules) are voting methods for selecting a committee, i.e., a fixed-size subset of candidates. ABC rules are also known as approval-based multi-winner rules. The input of such rules are approval ballots. We recommend the book Multi-Winner Voting with Approval Preferences (freely available) by Lackner and Skowron [2] as a detailed introduction to ABC rules and related research directions. In addition, the survey by Faliszewski et al. [1] is useful as a more general introduction to committee voting (not limited to approval ballots).

The following ABC rules are implemented:

• Approval Voting (AV)

• Satisfaction Approval Voting (SAV)

• Proportional Approval Voting (PAV)

• Sequential Proportional Approval Voting (seq-PAV)

• Reverse Sequential Proportional Approval Voting (revseq-PAV)

• Approval Chamberlin-Courant (CC)

• Phragmén's sequential rule

• Monroe's rule

• Minimax Approval Voting (MAV)

• Greedy Monroe

• Rule X

• Phragmén's First Method (Eneström's Method)

• and many more ...

Installation

Using pip:

pip install abcvoting

Latest development version from source:

git clone https://github.com/martinlackner/abcvoting/
python setup.py install

Requirements:

• Python 3.6+
• see setup.py for 3rd party dependencies

Optional requirements:

• gmpy2: Some functions use fractions (e.g., compute_seqphragmen). These compute significantly faster if the module gmpy2 is available. If gmpy2 is not available, the much slower Python module fractions is used.
• Gurobi (gurobipy): Most computationally hard rules are also implemented via the ILP solver Gurobi. The corresponding functions require gurobipy. If Gurobi is not available, the open-source solver CBC is a (slower) alternative.

Documentation

A documentation can be found here.

How to Cite

If you would like to cite abcvoting in a research paper or text, please use the following (or a similar) citation:

M. Lackner, P. Regner, B. Krenn, and S. S. Forster.
abcvoting: A Python library of approval-based committee voting rules, 2021.
URL https://doi.org/10.5281/zenodo.3904466.
Current version: https://github.com/martinlackner/abcvoting.

Bibtex:

@misc{abcvoting,
  author       = {Martin Lackner and
                  Peter Regner and
                  Benjamin Krenn and
                  Stefan Schlomo Forster},
  title        = {{abcvoting: A Python library of approval-based
                   committee voting rules}},
  year         = 2021,
  publisher    = {Zenodo},
  doi          = {10.5281/zenodo.3904466},
  url          = {https://doi.org/10.5281/zenodo.3904466},
  note         = {Current version: \url{https://github.com/martinlackner/abcvoting}}
}

Development

Install all dependencies including development requirements and the abcvoting package in development mode:

pip install -e .[dev]

Basic unit tests can be run by excluding tests which require additional dependencies:

pytest  -m "not gurobi and not scip and not cbc and not glpk_mi and not cvxpy and not gmpy2 and not slow" tests/

For development, configure the black formatter and pre-commit hooks - see below. Also installing all optional dependencies is recommended.

A development package is build for every commit on the master branch and uploaded to the test instance of PyPI. It can be installed using the following command:

python3 -m pip install --index-url https://test.pypi.org/simple/ --extra-index-url https://pypi.org/simple abcvoting

Black formatting

Code needs to be formatted using the black formatter. This is checked by Github actions. Configure your editor, to run the black formatter.

Pre-commit hooks

Pre-commit hooks are not required, but they are recommended for development. Pre-commit is used to manage and maintain pre-commit hooks. Install pre-commit (e.g. via apt, conda or pip) and then run $ pre-commit install to install the hooks.

Acknowledgements

The following people have contributed code to this package or provided help with technical and scientific questions (in alphabetic order): Piotr Faliszewski, Stefan Schlomo Forster, Andrzej Kaczmarczyk, Benjamin Krenn, Martin Lackner, Pawel Batko, Dominik Peters, Peter Regner, Piotr Skowron.

The development of this module has been supported by the Austrian Science Fund FWF, grant P31890.

References

[1] Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Multiwinner voting: A new challenge for social choice theory. In Ulle Endriss, editor, Trends in Computational Social Choice, chapter 2, pages 27–47. AI Access, 2017. http://research.illc.uva.nl/COST-IC1205/BookDocs/Chapters/TrendsCOMSOC-02.pdf

[2] Lackner, Martin, and Piotr Skowron. "Multi-Winner Voting with Approval Preferences" arXiv preprint arXiv:2007.01795. 2020. https://arxiv.org/abs/2007.01795