abcvoting.abcrules

Approval-based committee (ABC) voting rules.

Expand for references to abcvoting.abcrules

Computing winning committees / First steps

A simple example

Properties of committees

abcvoting.abcrules.ALGORITHM_NAMES = {'branch-and-bound': 'branch-and-bound', 'brute-force': 'brute-force', 'float-fractions': 'Standard algorithm (using floats instead of fractions)', 'gmpy2-fractions': 'Standard algorithm (using gmpy2 fractions)', 'gurobi': 'Gurobi ILP solver', 'mip-cbc': 'CBC ILP solver via Python MIP library', 'mip-gurobi': 'Gurobi ILP solver via Python MIP library', 'ortools-cp': 'OR-Tools CP-SAT solver', 'standard': 'Standard algorithm', 'standard-fractions': 'Standard algorithm (using standard Python fractions)'}

A dictionary containing mapping all valid algorithm identifiers to full names (i.e., descriptions).

abcvoting.abcrules.MAIN_RULE_IDS = ['av', 'sav', 'pav', 'slav', 'cc', 'lexcc', 'geom2', 'seqpav', 'revseqpav', 'seqslav', 'seqcc', 'seqphragmen', 'minimaxphragmen', 'leximaxphragmen', 'maximin-support', 'monroe', 'greedy-monroe', 'minimaxav', 'lexminimaxav', 'equal-shares', 'equal-shares-with-av-completion', 'equal-shares-with-increment-completion', 'phragmen-enestroem', 'consensus-rule', 'trivial', 'rsd', 'eph']

List of rule identifiers (rule_id) for the main ABC rules included in abcvoting.

This selection is somewhat arbitrary. But all really important rules (that are implemented) are contained in this list.

Expand for references to abcvoting.abcrules.MAIN_RULE_IDS

ABC rules

abcvoting.abcrules.MAX_NUM_OF_COMMITTEES_DEFAULT = None

The maximum number of committees that is returned by an ABC voting rule.

If MAX_NUM_OF_COMMITTEES_DEFAULT ist set to None, then there is no constraint on the maximum number of committees. Can be overridden with the parameter max_num_of_committees in any compute function.

exception abcvoting.abcrules.NoAvailableAlgorithm(rule_id, algorithms)

Exception: none of the implemented algorithms are available.

This error occurs because no solvers are installed.

Parameters:
rule_idstr

The ABC rule for which no algorithm are available.

algorithmstuple of str

List of algorithms for this rule (none of which are available).

class abcvoting.abcrules.Rule(rule_id)

A class that contains the main information about an ABC rule.

Parameters:
rule_idstr

The rule identifier.

Expand for references to abcvoting.abcrules.Rule

abcvoting.abcrules

compute(profile, committeesize, **kwargs)

Compute rule using self._compute_fct.

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

**kwargsdict

Optional arguments for computing the rule (e.g., resolute).

Returns:
list of CandidateSet

A list of winning committees.

fastest_available_algorithm()

Return the fastest algorithm for this rule that is available on this system.

An algorithm may not be available because its requirements are not satisfied. For example, some algorithms require Gurobi, others require gmpy2 - both of which are not requirements for abcvoting.

Returns:
str
verify_compute_parameters(profile, committeesize, algorithm, resolute, max_num_of_committees=None)

Basic checks for parameter values when computing an ABC rule.

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

resolutebool

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
bool
exception abcvoting.abcrules.UnknownAlgorithm(rule_id, algorithm)

Error: unknown algorithm for a given ABC rule.

Parameters:
rule_idstr

The ABC rule for which the algorithm is not known.

algorithmstr

The unknown algorithm.

exception abcvoting.abcrules.UnknownRuleIDError(rule_id)

Error: unknown rule id.

Parameters:
rule_idstr

The unknown rule identifier.

abcvoting.abcrules.compute(rule_id, profile, committeesize, result=None, **kwargs)

Compute winning committees with an ABC rule given by rule_id.

Parameters:
rule_idstr

The rule identifier.

profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

resultlist of CandidateSet, optional

Expected winning committees.

This is used in unit tests to verify correctness. Raises ValueError if result is different from actual winning committees.

**kwargsdict

Optional arguments for computing the rule (e.g., resolute).

Returns:
list of CandidateSet

A list of the winning committees.

If resolute=True, the list contains only one winning committee.

Expand for references to abcvoting.abcrules.compute

Computing winning committees / First steps

Computing winning committees / Number of winning committees

A simple example

abcvoting.abcrules.compute_av(profile, committeesize, algorithm='fastest', resolute=False, max_num_of_committees=None)

Approval Voting (AV).

AV is both a Thiele method and a separable rule. Seperable rules can be computed much faster than Thiele methods (in general), thus compute_separable_rule is used to compute AV.

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for AV:

>>> Rule("av").algorithms
('standard',)
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_cc(profile, committeesize, algorithm='fastest', resolute=False, max_num_of_committees=None)

Compute winning committees with Approval Chamberlin-Courant (CC).

This ABC rule belongs to the class of Thiele methods.

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Approval Chamberlin-Courant (CC):

>>> Rule("cc").algorithms  
('gurobi', 'mip-gurobi', 'ortools-cp', 'branch-and-bound', 'brute-force',
 'mip-cbc')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_consensus_rule(profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None)

Compute winning committees with the Consensus rule.

Based on Perpetual Consensus from Martin Lackner Perpetual Voting: Fairness in Long-Term Decision Making In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020)

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for the Consensus rule:

>>> Rule("consensus-rule").algorithms
('float-fractions', 'gmpy2-fractions', 'standard-fractions')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_eph(profile, committeesize, algorithm='float-fractions', resolute=False, max_num_of_committees=None)

Compute winning committees with the “E Pluribus Hugo” (EPH) voting rule.

This rule is used by the Hugo Awards as a shortlisting voting rule. It is described in the following paper under the name “Single Divisible Vote with Least-Popular Elimination (SDV-LPE)”: “A proportional voting system for awards nominations resistant to voting blocs.” Jameson Quinn, and Bruce Schneier. <https://www.schneier.com/wp-content/uploads/2016/05/Proportional_Voting_System.pdf>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Random Serial Dictator:

>>> Rule("eph").algorithms
('float-fractions', 'gmpy2-fractions', 'standard-fractions')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_equal_shares(profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None, completion='seqphragmen')

Compute winning committees with the Method of Equal Shares (aka Rule X).

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5> See also <https://arxiv.org/pdf/1911.11747.pdf>, page 7

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for the Method of Equal Shares:

>>> Rule("equal-shares").algorithms
('float-fractions', 'gmpy2-fractions', 'standard-fractions')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

completionstr, default=”seqphragmen”

As Equal Shares does not necessarily return the desired number of committee members, it requires an additional method to fill the remaining seats. The default is to use Sequential Phragmén.

The following options are available:

  • “seqphragmen”: Use Sequential Phragmén to fill seats.

  • “av”: Use Approval Voting to fill seats (i.e., take those with most approvals).

  • “increment”: Increase the budget of voters by virtually incrementing the committee size. This step is repeated until a committee of size committeesize is found.

  • None: Do not fill the remaining seats. The resulting committees may contain fewer than committeesize members.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_greedy_monroe(profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None)

Compute winning committees with Greedy Monroe.

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Greedy Monroe:

>>> Rule("greedy-monroe").algorithms
('standard',)
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_lexcc(profile, committeesize, algorithm='fastest', resolute=False, max_num_of_committees=None)

Compute winning committees with a Lexicographic Chamberlin-Courant (lex-CC).

This ABC rule is a lexicographic variant of Approval Chamberlin-Courant (CC). It maximizes the CC score, i.e., the number of voters with at least one approved candidate in the winning committee. If there is more than one such committee, it chooses the committee with most voters having at least two approved candidates in the committee. This tie-breaking continues with values of 3, 4, .., k if necessary.

This rule can be seen as an analogue to the leximin social welfare ordering for utility functions.

Important

Very slow due to lexicographic optimization.

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Lexicographic Chamberlin-Courant (lex-CC):

>>> Rule("lexcc").algorithms
('gurobi', 'brute-force')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_leximaxphragmen(profile, committeesize, algorithm='fastest', resolute=False, max_num_of_committees=None, lexicographic_tiebreaking=False)

Compute winning committees with Phragmen’s leximax rule (leximax-Phragmen).

Lexicographically minimize the maximum loads. Details in Markus Brill, Rupert Freeman, Svante Janson and Martin Lackner. Phragmen’s Voting Methods and Justified Representation. <https://arxiv.org/abs/2102.12305>

Important

Very slow due to lexicographic optimization.

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Phragmen’s leximax rule (leximax-Phragmen):

>>> Rule("leximaxphragmen").algorithms
('gurobi',)
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

lexicographic_tiebreakingbool

Require lexicographic tiebreaking among tied committees.

This requires the computation of all winning committees and is therefore very slow.

Important

lexicographic_tiebreaking=True is only valid in “combination with resolute=True.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_lexminimaxav(profile, committeesize, algorithm='fastest', resolute=False, max_num_of_committees=None)

Compute winning committees with Lexicographic Minimax AV (lex-MAV).

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5> (Remark 2)

If lexicographic_tiebreaking is True, compute all winning committees and choose the lexicographically smallest. This is a deterministic form of tiebreaking; if only resolute=True, it is not guaranteed how ties are broken.

Important

Very slow due to lexicographic optimization.

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Lexicographic Minimax AV:

>>> Rule("lexminimaxav").algorithms
('gurobi', 'brute-force')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_maximin_support(profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None)

Compute winning committees with the maximin support method (MMS).

Details in Luis Sánchez-Fernández, Norberto Fernández, Jesús A. Fisteus, Markus Brill The maximin support method: an extension of the D’Hondt method to approval-based multiwinner elections <https://arxiv.org/abs/1609.05370>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for the maximin support method (MMS):

>>> Rule("maximin-support").algorithms
('gurobi', 'mip-gurobi', 'mip-cbc')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_minimaxav(profile, committeesize, algorithm='fastest', resolute=False, max_num_of_committees=None)

Compute winning committees with Minimax Approval Voting (MAV).

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Minimax AV:

>>> Rule("minimaxav").algorithms
('gurobi', 'mip-gurobi', 'ortools-cp', 'mip-cbc', 'brute-force')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_minimaxphragmen(profile, committeesize, algorithm='fastest', resolute=False, max_num_of_committees=None)

Compute winning committees with Phragmen’s minimax rule (minimax-Phragmen).

Minimizes the maximum load.

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Does not include the lexicographic optimization as specified in Markus Brill, Rupert Freeman, Svante Janson and Martin Lackner. Phragmen’s Voting Methods and Justified Representation. <https://arxiv.org/abs/2102.12305> Instead: minimizes the maximum load (without consideration of the second-, third-, …-largest load. The lexicographic method is this one: compute_leximaxphragmen().

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Phragmen’s minimax rule (minimax-Phragmen):

>>> Rule("minimaxphragmen").algorithms
('gurobi', 'mip-gurobi', 'mip-cbc')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_monroe(profile, committeesize, algorithm='fastest', resolute=False, max_num_of_committees=None)

Compute winning committees with Monroe’s rule.

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Monroe:

>>> Rule("monroe").algorithms
('gurobi', 'mip-gurobi', 'mip-cbc', 'ortools-cp', 'brute-force')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_pav(profile, committeesize, algorithm='fastest', resolute=False, max_num_of_committees=None)

Compute winning committees with Proportional Approval Voting (PAV).

This ABC rule belongs to the class of Thiele methods.

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for PAV:

>>> Rule("pav").algorithms
('gurobi', 'mip-gurobi', 'mip-cbc', 'branch-and-bound', 'brute-force')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

Expand for references to abcvoting.abcrules.compute_pav

A simple example

abcvoting.abcrules.compute_phragmen_enestroem(profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None)

Compute winning committees with Phragmen-Enestroem.

This ABC rule is also known as Phragmen’s first method and Enestroem’s method.

In every round the candidate with the highest combined budget of their supporters is put in the committee. Method described in: Svante Janson Phragmén’s and Thiele’s election methods <https://arxiv.org/pdf/1611.08826.pdf> (Section 18.5, Page 59)

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Phragmen-Enestroem:

>>> Rule("phragmen-enestroem").algorithms
('float-fractions', 'gmpy2-fractions', 'standard-fractions')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_revseq_thiele_method(scorefct_id, profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None)

Reverse sequential Thiele methods.

For a mathematical description of these rules, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
scorefct_idstr

A string identifying the score function that defines the Thiele method.

profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_revseqpav(profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None)

Reverse Sequential PAV (revseq-PAV).

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Reverse Sequential PAV:

>>> Rule("revseqpav").algorithms
('standard',)
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_rsd(profile, committeesize, algorithm='standard', resolute=True, max_num_of_committees=None)

Compute winning committees with the Random Serial Dictator rule.

This rule randomy selects a permutation of voters. The first voter in this permutation adds all approved candidates to the winning committee, then the second voter, then the third, etc. At some point, a voter has more approved candidates than can be added to the winning committee. In this case, as many as possible are added (candidates with smaller index first). In this way, the winning committee is constructed.

Important

This algorithm is not deterministic and relies on the Python module random.

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Random Serial Dictator:

>>> Rule("rsd").algorithms
('standard',)
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_rule_x(profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None, skip_phragmen_phase=False)

Compute winning committees with the Method of Equal Shares (aka Rule X).

Deprecated since version 2.4.0: Use compute_equal_shares() instead. (Rule X has been renamed by the authors to Method of Equal Shares and this appears to be the new standard name used in the literature by now.)

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for the Method of Equal Shares:

>>> Rule("equal-shares").algorithms
('float-fractions', 'gmpy2-fractions', 'standard-fractions')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

skip_phragmen_phasebool, default=False

Omit the second phase (that uses seq-Phragmen).

May result in a committee that is too small (length smaller than committeesize).

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_sav(profile, committeesize, algorithm='fastest', resolute=False, max_num_of_committees=None)

Compute winning committees with Satisfaction Approval Voting (SAV).

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for SAV:

>>> Rule("sav").algorithms
('standard',)
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_separable_rule(rule_id, profile, committeesize, algorithm, resolute=True, max_num_of_committees=None)

Separable rules (such as AV and SAV).

For a mathematical description of separable rules (for ranking-based rules), see E. Elkind, P. Faliszewski, P. Skowron, and A. Slinko. Properties of multiwinner voting rules. Social Choice and Welfare, 48(3):599–632, 2017. <https://link.springer.com/article/10.1007/s00355-017-1026-z>

Parameters:
rule_idstr

The rule identifier for a separable rule.

profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for AV:

>>> Rule("av").algorithms
('standard',)
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_seq_thiele_method(scorefct_id, profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None)

Sequential Thiele methods.

For a mathematical description of these rules, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
scorefct_idstr

A string identifying the score function that defines the Thiele method.

profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_seqcc(profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None)

Sequential Chamberlin-Courant (seq-CC).

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Sequential CC:

>>> Rule("seqcc").algorithms
('standard',)
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_seqpav(profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None)

Sequential PAV (seq-PAV).

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Sequential PAV:

>>> Rule("seqpav").algorithms
('standard',)
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_seqphragmen(profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None)

Compute winning committees with Phragmen’s sequential rule (seq-Phragmen).

For a mathematical description of this rule, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Phragmen’s sequential rule (seq-Phragmen):

>>> Rule("seqphragmen").algorithms
('float-fractions', 'gmpy2-fractions', 'standard-fractions')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

Expand for references to abcvoting.abcrules.compute_seqphragmen

Properties of committees

abcvoting.abcrules.compute_seqslav(profile, committeesize, algorithm='fastest', resolute=True, max_num_of_committees=None)

Sequential Sainte-Lague Approval Voting (SLAV).

For a mathematical description of SLAV, see e.g. Martin Lackner and Piotr Skowron Utilitarian Welfare and Representation Guarantees of Approval-Based Multiwinner Rules In Artificial Intelligence, 288: 103366, 2020. <https://arxiv.org/abs/1801.01527>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for Sequential SLAV:

>>> Rule("seqslav").algorithms
('standard',)
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_slav(profile, committeesize, algorithm='fastest', resolute=False, max_num_of_committees=None)

Compute winning committees with Sainte-Lague Approval Voting (SLAV).

This ABC rule belongs to the class of Thiele methods.

For a mathematical description of this rule, see e.g. Martin Lackner and Piotr Skowron Utilitarian Welfare and Representation Guarantees of Approval-Based Multiwinner Rules In Artificial Intelligence, 288: 103366, 2020. <https://arxiv.org/abs/1801.01527>

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for SLAV:

>>> Rule("slav").algorithms
('gurobi', 'mip-gurobi', 'mip-cbc', 'branch-and-bound', 'brute-force')
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.compute_thiele_method(scorefct_id, profile, committeesize, algorithm='fastest', resolute=False, max_num_of_committees=None)

Compute winning committees with Thiele methods.

Compute winning committees according to a Thiele method specified by a score function (scorefct_id). Examples of Thiele methods are PAV, CC, and SLAV. An exception is Approval Voting (AV), which should be computed using compute_av(). (AV is polynomial-time computable (separable) and can thus be computed much faster.)

For a mathematical description of Thiele methods, see e.g. “Multi-Winner Voting with Approval Preferences”. Martin Lackner and Piotr Skowron. <http://dx.doi.org/10.1007/978-3-031-09016-5>

Parameters:
scorefct_idstr

A string identifying the score function that defines the Thiele method.

profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

If resolute=True, the list contains only one winning committee.

abcvoting.abcrules.compute_trivial_rule(profile, committeesize, algorithm='standard', resolute=False, max_num_of_committees=None)

Compute winning committees with the trivial rule (all committees are winning).

Parameters:
profileabcvoting.preferences.Profile

A profile.

committeesizeint

The desired committee size.

algorithmstr, optional

The algorithm to be used.

The following algorithms are available for the trivial rule:

>>> Rule("trivial").algorithms
('standard',)
resolutebool, optional

Return only one winning committee.

If resolute=False, all winning committees are computed (subject to max_num_of_committees).

max_num_of_committeesint, optional

At most max_num_of_committees winning committees are computed.

If max_num_of_committees=None, the number of winning committees is not restricted. The default value of max_num_of_committees can be modified via the constant MAX_NUM_OF_COMMITTEES_DEFAULT.

Returns:
list of CandidateSet

A list of winning committees.

abcvoting.abcrules.get_rule(rule_id)

Get instance of Rule for the ABC rule specified by rule_id.

Deprecated since version 2.3.0: Function get_rule(rule_id) is deprecated, use Rule(rule_id) instead.

Parameters:
rule_idstr

The rule identifier.

Returns:
Rule

A corresponding Rule object.

Expand for references to abcvoting.abcrules.get_rule

ABC rules

Computing winning committees / Algorithms

Computing winning committees / Number of winning committees