abcvoting 2.0.1

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

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 ''Approval-Based Committee Voting'' 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.
• 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.

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
• cvxpy
• solvers:
  • Gurobi
  • GLPK_MI
  • CBC
  • Scip

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. "Approval-Based Committee Voting: Axioms, Algorithms, and Applications." arXiv preprint arXiv:2007.01795. 2020. https://arxiv.org/abs/2007.01795