Python implementations of approval-based committee (multi-winner) rules
Project description
abcvoting
Python implementations of approval-based committee (multi-winner) rules
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 as a detailed introduction to ABC rules and related research directions [2]. 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 ...
Example
The following code computes the Proportional Approval Voting (PAV) rule for a profile with 6 voters and 5 candidates. Candidates correspond to the numbers 0 to 4.
from abcvoting.preferences import Profile
from abcvoting import abcrules
# a preference profile with 5 candidates (0, 1, 2, 3, 4)
profile = Profile(5)
# add six voters, specified by the candidates that they approve;
# the first voter approves candidates 0, 1, and 2,
# the second voter approves candidates 0 and 1, etc.
profile.add_voters([{0,1,2}, {0,1}, {0,1}, {1,2}, {3,4}, {3,4}])
committeesize = 3
# find winning committees for this profile according to PAV
print(abcrules.compute_pav(profile, committeesize))
The output is
[{0, 1, 3}, {0, 1, 4}]
which corresponds to the two winning committees {0,1,3} and {0,1,4}. Further examples can be found in the directory examples/. In examples/abcsurvey/, all examples from the survey on ABC rules [2] are implemented.
Usage
At the moment there is no command line interface. The package can be used only as Python model as shown in the example above.
Notes:
- 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.
- 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. - All voting methods have a parameter
resolute
. If it is set to true, only one winning committee is computed. In most cases,resolute=True
speeds up the computation. - It is possible to specify the maximum number of committees that are returned by ABC rules via the parameter
max_num_of_committees
. This parameter has no effect ifresolute
is true.
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
- Gurobi (gurobipy)
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
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distribution
Hashes for abcvoting-2.1.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d404f9648ea06e8c776f82caa2a42631a2beb573149e78126ac97758bb464926 |
|
MD5 | 935949c2f18b630b578fd466fb9b6f2b |
|
BLAKE2b-256 | 81aef2a8d7d4a766b510d693b53328bc4547441ff9db0623bf2077eaa6d8ae29 |