A Python library of ordinal-based committee (OBC) voting rules
Project description
Votepy
Votepy provides ready-to-use tools to calculate multi-winning ordinal elections, under different voting rules.
Installation
- Clone the repository:
git clone https://github.com/Janix4000/votepy.git path/to/lib
- Create and source new virtual environment:
cd path/to/your/project && python3 -m venv venv && source venv/bin/activate
- Install the main package:
pip3 install -e path/to/lib/votepy
Usage
Ordered preference and election
When working with the ordered elections, we need to represent such data. Given n
candidates, we can represent voter's preference by permutation of length n
, using a standard Python list:
n = 4
voting_preference = [2, 1, 3, 0]
We will call such a preference a voting ballot
.
Having m
voters, we can group their preferences into the ordered election
:
n = 4
m = 3
voting = [
[2, 1, 3, 0], # first voter's preference
[1, 2, 3, 0], # second voter's preference
[3, 0, 2, 1] # third voter's preference
]
Votepy also provides special data types for them, but they are not obligatory and all functions support python's primitives. However, they give additional functionalities, such as mapping candidates to more human-readable representations:
from votepy.ordinal_election import OrdinalElection, OrdinalBallot
mapping = {0: 'Joe', 1: 'John', 2: 'Sue', 3: 'Anna'}
single_voting_preference = OrdinalBallot([2, 1, 3, 0], mapping=mapping)
voting = OrdinalElection([
[2, 1, 3, 0], # first voter's preference
[1, 2, 3, 0], # second voter's preference
[3, 0, 2, 1] # third voter's preference
], mapping=mapping)
print(voting) # prints election using mapping representation
Voting rules
For a given election, we want to choose a set of representatives, with the predefined number k
(or committee size
) of the delegates.
However, there are many strategies to choose such a committee
. These strategies are commonly called voting rules
and may optimize different objectives. We can print all of the implemented voting rules, with the corresponding python functions:
import votepy as vp
print(vp.get_rules()) # prints rule_name->rule_function dictionary
Let's use for an example bloc
rule on the previously defined election:
committee_size = 2
committee = vp.rules.bloc(voting, committee_size)
print(committee)
Votepy gives additional way to call the voting rules:
# this is equivalent of calling vp.rules.bloc
committee = vp.solve('bloc', voting, committee_size)
Voting-solving algorithms
Some of the voting rules are extremely costly to compute and finding the best committee may be very time-consuming for a greater number of candidates and voters. Luckily, many voting rules are defined by the maximization of some objective function (scoring function
), so the best committees can be approximated using different tricks and methods.
Let's look at the chamberlin_courant
(shortly cc
) rule, which turns out to be NP-Complete, and so no efficient algorithm is known for finding the best committees for the given election. For such a rules additional parameter algorithm
must be provided. Algorithms can be specified by their name:
committee = vp.rules.chamberlin_courant(
voting,
committee_size,
algorithm='brute_force'
)
or by using their corresponding algorithms objects:
from votepy.algorithms import BruteForce
# this is equivalent of 'brute_force' string name
committee = vp.rules.chamberlin_courant(
voting,
committee_size,
algorithm=BruteForce()
)
In this case, the brute force
algorithm will check every possible combination of the candidates and take the best one to create committee.
Some algorithms can accept additional parameters, and it is only possible by using their corresponding classes:
# numeric algorithm, similar to simulated annealing, giving approximate results
from votepy.algorithms import BasinHopping
committee = vp.rules.chamberlin_courant(
voting,
committee_size,
algorithm=BasinHopping(niter=100, seed=1)
)
There are better methods than brute force for getting exact solutions. We can check all algorithms implemented for the cc rule:
# prints rule_name->algorithm_class dictionary
print(vp.get_algorithms('chamberlin_courant'))
One of the most common technice used for solving NP-Complete problems is using ILP
solvers. However, in contrast to the brute force algorithm, we need to specify solver engine during the initialization of the ILP.
from votepy.algorithms import ILP
# Gurobi solver must be previously installed and activated on the machine
from votepy.generic_ilp import Gurobi
committee = vp.rules.chamberlin_courant(
voting,
committee_size,
algorithm=ILP(Gurobi)
)
Contribution guide
Installation
- Clone the repository:
git clone https://github.com/Janix4000/votepy.git && cd votepy
- Create and source new virtual environment:
python3 -m venv venv && source venv/bin/activate
- Install the main package:
pip3 install -e .
- Install development packages:
pip3 install -r ./requirements_dev.txt
- Run tests:
pytest
Adding a new voting rule
See the guide for adding new voting rule.
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.