Computing winning committees

One of the main goals of abcvoting is to provide a simple way to compute winning committees for a given ABC rule. Here is a bit more detailed explanation of how to do this. (A first, simple explanation can be found here.

First steps

ABC rules are identified by an identifier called rule_id. Here is a list of these identifiers. Say we are interested in Proportional Approval Voting, short: PAV. Its rule_id is “pav”.

The input of an ABC rule consists of a profile and a desired committee size. Once we know the rule_id and have a profile and a desired committee size, we can compute the ABC rule. In the following, we use the simple example used previously.

>>> from abcvoting.preferences import Profile
>>> from abcvoting import abcrules

>>> rule_id = "pav"
>>> profile = Profile(num_cand=5)
>>> profile.add_voters([{0, 1, 2}, {3}, {0, 1, 2, 3}, {0, 1, 2, 4}, {0, 1}, {4}])
>>> print(abcrules.compute("pav", profile, committeesize=3))
[CandidateSet({0, 1, 3}), CandidateSet({0, 1, 4})]

The output of all ABC is rules is a list of CandidateSet (abcvoting.misc.CandidateSet). This is a subclass of set and represents a set of candidates.

Number of winning committees

Most ABC voting rules may return more than one winning committees; these committees are “tied”. Sometimes one is only interested in one (or a just few) winning committees. As it is generally computationally more difficult to compute all winning committees, also runtime considerations may necessitate a limit.

There are two ways how to determine the maximum number of winning committees: the parameter resolute and the parameter max_num_of_committees. Both are implemented for the compute functions of all ABC rules.

If resolute=True, only one winning committee is returned.

>>> committees = abcrules.compute("pav", profile, committeesize=3, resolute=True)
>>> len(committees)
1

If resolute=False (which is the default), the maximum number of winning committees is determined by max_num_of_committees.

>>> committees = abcrules.compute("pav", profile, committeesize=3, max_num_of_committees=1)
>>> len(committees)
1

>>> committees = abcrules.compute("pav", profile, committeesize=3, max_num_of_committees=4)
>>> len(committees)
2

While most ABC rule are implemented for both resolute=True and resolute=False, for some one choice is more natural than the other. The default value for resolute is chosen to reflect this. For example,

>>> abcrules.get_rule("pav").resolute_values
(False, True)

The first entry in this list is the default choice. That is, if we do not provide the resolute parameter when computing PAV, all winning committees are computed (resolute=False). For sequential rules (such as Sequential PAV and Reverse Sequential PAV), the default choice is resolute=True.

Finally, the default choice of max_num_of_committees is

>>> print(abcrules.MAX_NUM_OF_COMMITTEES_DEFAULT)
None

i.e., when resolute=False, indeed all winning committees are computed.

Important

Note that max_num_of_committees=None (i.e., an unrestricted maximum number of winning committees) can lead to runtime and memory problems when there is a huge number of winning committees.

Algorithms

Most ABC rules can be computed with several algorithms. For example, for PAV, we have

>>> print(abcrules.get_rule("pav").algorithms)
('gurobi', 'mip-gurobi', 'mip-cbc', 'branch-and-bound', 'brute-force')

These algorithms are sorted by speed (in approximation). By default, ABC rules are computed with algorithm=”fastest”, which picks the first available algorithm in this list.

Not all algorithms are necessarily available as some of them have optional dependencies. Let us briefly discuss these.

Throughout abcvoting, the following kinds of algorithms are used:

>>> for algo_id, description in abcrules.ALGORITHM_NAMES.items():
...     print(f"{algo_id:20s} : {description}")
gurobi               : Gurobi ILP solver
branch-and-bound     : branch-and-bound
brute-force          : brute-force
mip-cbc              : CBC ILP solver via Python MIP library
mip-gurobi           : Gurobi ILP solver via Python MIP library
standard             : Standard algorithm
standard-fractions   : Standard algorithm (using standard Python fractions)
gmpy2-fractions      : Standard algorithm (using gmpy2 fractions)
float-fractions      : Standard algorithm (using floats instead of fractions)
ortools-cp           : OR-Tools CP-SAT solver

In addition to the dependencies of abcvoting [1], some algorithms have additional requirements:

  • gurobi and mip-gurobi require Gurobi (installation)

  • gmpy2-fractions requires the Python module gmpy2.

  • All other algorithms work “out of the box”.