Rules module

Meta Rule

Generic schemes to compute outcomes of rules via integer linear programs.

class ILPNotOptimalError

Bases: ValueError

Exception raised when the outcome of the ILP solver is not proven to be an optimal solution.

class ILPBuilder(profile: AbstractTrichotomousProfile, max_size_selection: int, initial_selection: Selection = None, max_seconds: int = 600, verbose: bool = False, solver_name: ILPSolver = None)

Bases: ABC

Abstract class used to define ILP programs that are then passed to the ilp_optimiser_rule() function for the actual solving.

Parameters:

• profile (AbstractTrichotomousProfile) – The trichotomous profile.

• max_size_selection (int) – Maximum number of alternatives to select.

• initial_selection (Selection, optional) – An initial selection that fixes some alternatives as selected or rejected. If implicit_reject is True, no alternatives are fixed to be rejected.

• max_seconds (int, optional) – Maximum number of seconds to run the ILP solver for. Defaults to 600 seconds (10 minutes).

• verbose (bool, optional) – If True the output of the ILP solver is not silenced. Defaults to False.

• solver_name (ILPSolver) – Name of the ILP solver to use.

model_name

Name of the model, used when writing the LP files.

Type:

str

profile

The trichotomous profile.

Type:

AbstractTrichotomousProfile

max_size_selection

Maximum number of alternatives to select.

Type:

int

initial_selection

An initial selection that fixes some alternatives as selected or rejected. If implicit_reject is True, no alternatives are fixed to be rejected.

Type:

Selection, optional

model

The actual PuLP model.

Type:

LpProblem

vars

The variables used in the ILP model, mapping type of variable to dictionary containing LpVariable.

Type:

dict[str, dict]

apply_constraints()

Applies the different constraints to the model.

ban_selection(selection: Selection) → None

Adds the constraints to ban a given selection.

Parameters:

selection (Selection) – The selection to ban.

constrain_initial_selection()

Adds the constraints related to the initial selection to the model.

constrain_max_size_selection()

Adds the constraint related to the maximum size of the selections.

force_objective_value(v: int | float | mpq)

Adds a constraint to the model to force the objective to have a specific value.

Parameters:

v (Numeric) – The value of the objective.

init_selection_vars()

Initialises the selections variables. Other function assumes that self.vars[“selection”] exists and correspond to the variables indicating whether an alternative is selected or not.

init_vars() → None

Initialises the variables. This function is meant to be overridden. The super() needs to be called to ensure the initialisation of all the variables that are shared by all ILP models.

abstractmethod objective() → LpAffineExpression

Returns the objective function of the ILP.

set_objective()

Sets the objective function to the model itself.

solve() → int

Optimises the model and return the optimisation status.

Returns:

The optimisation status of the solver.

Return type:

int

class ILPSolver(*values)

Bases: Enum

Enumerates the different solvers available.

CBC = 'CBC'

Cbc (Coin-or branch and cut) is an open-source mixed integer linear programming solver

HIGHS = 'HIGHS'

open-source software to solve linear programming

Type:

HiGHS

ilp_optimiser_rule(ilp_builder: ILPBuilder, resoluteness: bool = True) → Selection | list[Selection]

Rule that optimises an ILP and returns the corresponding selection(s). Returns the first optimal solution found if resoluteness = True and, all the optimal solutions otherwise.

Thiele Methods

A Thiele rule returns selections that maximises a score defined as a function of (1) the number of approved and selected alternatives, (2) the number of disapproved and selected alternatives, (3) the number of approved and rejected alternatives, and (4) the number of disapproved and rejected alternatives.

class ThieleScore(max_size_selection: int)

Bases: ABC

Class used to define score function for Thiele methods. Defines the elements that are needed for both the ILP solver approach and the sequential approach.

abstractmethod score_function(num_app_sel: int = 0, num_disapp_sel: int = 0, num_app_rej: int = 0, num_disapp_rej: int = 0)

Actual scoring function. Can only depend on:

• the number of approved and selected alternatives;

• the number of disapproved and selected alternatives;

• the number of approved and rejected alternatives; and on

• the number of disapproved and rejected alternatives.

Parameters:

• num_app_sel (int, optional) – The number of approved and selected alternatives

• num_disapp_sel (int, optional) – The number of disapproved and selected alternatives

• num_app_rej (int, optional) – The number of approved and rejected alternatives

• num_disapp_rej (int, optional) – The number of disapproved and rejected alternatives

score_selection(profile: AbstractTrichotomousProfile, selection: Selection, extra_accept: Iterable[Alternative] = None, extra_reject: Iterable[Alternative] = None) → int | float | mpq

Returns the total score of a selection for a given profile according to the scoring function.

Use the extra_accept and extra_reject parameters to extend the selection without having to copy it.

Parameters:

• profile (AbstractTrichotomousProfile) – The profile.

• selection (Selection) – The selection.

• extra_accept (Iterable[Alternative], optional) – Additional alternative to consider as being part of the selection. Defaults to the empty list.

• extra_reject (Iterable[Alternative], optional) – Additional alternative to consider as being rejected in the selection. Defaults to the empty list.

property ilp_builder: type[ILPBuilder]

Return the ILPBuilder class used for the ILP optimising version of the Thiele rule.

class PAVScoreKraiczy2025(max_size_selection: int)

PAV scoring function as defined in Section 3.3 of Proportionality in Thumbs Up and Down Voting (Kraiczy, Papasotiropoulos, Pierczyński and Skowron, 2025). The objective is to maximise the PAV score where both approved and selected, and disapproved and not selected alternatives contribute positively.

class PAVScoreTalmonPaige2021(max_size_selection: int)

PAV scoring function as defined in Section 4.2 of Proportionality in Committee Selection with Negative Feelings (Talmon and Page, 2021). The objective is to maximise the difference between (1) the PAV score in which approved and selected alternatives are taken into account, and (2) the PAV score in which disapproved but selected alternatives are taken into account.

class PAVScoreHervouin2025(max_size_selection: int)

PAV scoring function as defined by Matthieu Hervouin in his PhD Thesis. The objective is to maximise the sum of (1) the PAV score in which approved and selected alternatives are taken into account, and (2) the PAV score over the maximum size of the selection minus the number of disapproved but selected alternatives.

class ApprovalThieleScore(max_size_selection: int)

Thiele scoring function in which the score of a selection is equal to its approval score: the sum over all ballots of the number of approved and selected alternatives.

class NetSupportThieleScore(max_size_selection: int)

Thiele scoring function in which the score of a selection is equal to its net support: the sum over all ballots of the number of approved and selected alternatives minus the number of disapproved but selected ones.

thiele_method(profile: AbstractTrichotomousProfile, max_size_selection: int, thiele_score_class: type[ThieleScore], initial_selection: Selection | None = None, resoluteness: bool = True, verbose: bool = False, max_seconds: int = 600) → Selection | list[Selection]

Compute the selections of a Thiele rule described described via a ThieleScore class. The selections are computed by solving integer linear programs (ILP).

Parameters:

• profile (AbstractTrichotomousProfile) – The trichotomous profile.

• max_size_selection (int) – Maximum number of alternatives to select.

• thiele_score_class (type[ThieleScore]) – The Thiele score class used to define the Thiele rule.

• initial_selection (Selection, optional) – An initial partial selection fixing some alternatives as selected or rejected. If implicit_reject is True in the initial selection, no alternatives are fixed to be rejected. Defaults to None.

• resoluteness (bool, optional) – If True, returns a single optimal selection (resolute). If False, returns all tied optimal selections (irresolute). Defaults to True.

• verbose (bool, optional) – If True, enables ILP solver output. Defaults to False.

• max_seconds (int, optional) – Time limit in seconds for the ILP solver. Defaults to 600.

Returns:

The selection if resolute (resoluteness == True), or a list of selections if irresolute (resoluteness == False).

Return type:

Selection | list[Selection]

sequential_thiele(profile: AbstractTrichotomousProfile, max_size_selection: int, thiele_score_class: type[ThieleScore], initial_selection: Selection | None = None, tie_breaking: TieBreakingRule | None = None, resoluteness: bool = True) → Selection | list[Selection]

Compute the selections of a sequential Thiele rule described via a ThieleScore class.

The alternatives are selected sequentially one after the other, each time selecting the alternative that would lead to the best improve in score. Alternatives from the current selection that have a negative marginal contribution to the score are removed.

Parameters:

• profile (AbstractTrichotomousProfile) – The trichotomous profile.

• max_size_selection (int) – Maximum number of alternatives to select.

• thiele_score_class (type[ThieleScore]) – The Thiele score class used to define the Thiele rule.

• initial_selection (Selection, optional) – An initial selection that fixes some alternatives as selected or rejected. If implicit_reject is True, no alternatives are fixed to be rejected.

• tie_breaking (TieBreakingRule, optional) – Tie-breaking rule used when multiple alternatives tie. Defaults to lexicographic tie-breaking.

• resoluteness (bool, optional) – If True, returns a single selection (resolute). If False, returns all tied optimal selections (irresolute). Defaults to True.

Returns:

The selection if resolute (resoluteness == True), or a list of selections if irresolute (resoluteness == False).

Return type:

Selection | list[Selection]

Sequential Phragmén’s Rule

Phragmén’s rules compute selections that try to balance the load carried by each voter to achieve proportional selections.

sequential_phragmen(profile: AbstractTrichotomousProfile, max_size_selection: int, initial_loads: list[int | float | mpq] | None = None, initial_selection: Selection | None = None, tie_breaking: TieBreakingRule | None = None, resoluteness: bool = True) → Selection | list[Selection]

Compute the selections of the sequential Phragmén’s rule.

The definition of the sequential Phragmén’s rule for the trichotomous context is taken from Section 3.2 of Proportionality in Thumbs Up and Down Voting (Kraiczy, Papasotiropoulos, Pierczyński and Skowron, 2025).

Parameters:

• profile (AbstractTrichotomousProfile) – The trichotomous profile.

• max_size_selection (int) – Maximum number of alternatives to select.

• initial_loads (list of Numeric, optional) – Initial loads for each ballot in the profile. Defaults to zero for all ballots.

• initial_selection (Selection, optional) – An initial selection that fixes some alternatives as selected or rejected. If implicit_reject is True, no alternatives are fixed to be rejected.

• tie_breaking (TieBreakingRule, optional) – Tie-breaking rule used when multiple alternatives tie. Defaults to lexicographic tie-breaking.

• resoluteness (bool, optional) – If True, returns a single selection (resolute). If False, returns all tied optimal selections (irresolute). Defaults to True.

Returns:

The selection if resolute (resoluteness == True), or a list of selections if irresolute (resoluteness == False).

Return type:

Selection | list[Selection]

Tax-Based Rules

Tax rules are rules that transform the trichotomous profile into a participatory budgeting (PB) instance and then use PB rules to compute selections for the trichotomous profile.

class TaxFunction(profile: AbstractTrichotomousProfile, max_size_selection: int)

Bases: ABC

Abstract class representing tax functions. A tax function associates a tax (i.e., the cost of a project on the PB side) to alternatives.

preprocess() → None

Preprocessing of the profile used to save up time on expensive computations that would be otherwise repeated.

abstractmethod tax_alternative(alternative: Alternative) → int | float | mpq | None

Returns the tax corresponding to the alternative. If None is returned, no project corresponding to the alternative is added to the PB instance.

class TaxKraiczy2025(profile: AbstractTrichotomousProfile, max_size_selection: int)

Tax function proposed in Proportionality in Thumbs Up and Down Voting (Kraiczy, Papasotiropoulos, Pierczyński and Skowron, 2025). The cost of a project is equal to its approval score divided by its support (approval minus disapproval score). If the support is negative, then the project is skipped.

class DisapprovalLinearTax(profile: AbstractTrichotomousProfile, max_size_selection: int, weight=None, class_method_call=False)

Disapproval linear tax function for which the cost of a project is equal to its disapproval multiplied by a fixed factor.

tax_pb_instance(profile: AbstractTrichotomousProfile, max_size_selection: int, initial_selection: Selection | None = None, tax_function: type[TaxFunction] = None) → tuple[Instance, ApprovalMultiProfile, dict[Project, Alternative]]

Construct a Participatory Budgeting (PB) instance and PB profile from a trichotomous profile.

This function translates the trichotomous voting profile into a PB instance, setting project costs inversely proportional to net support.

Parameters:

• profile (AbstractTrichotomousProfile) – The trichotomous profile.

• max_size_selection (int) – The budget limit or maximum number of alternatives to be selected.

• initial_selection (Selection or None, optional) – An initial selection fixing some alternatives as selected or rejected.

• tax_function (type[TaxFunction], optional) – A tax function defined as a subclass of the TaxFunction class. Defaults to TaxKraiczy2025.

Returns:

• pb_election.Instance – The generated PB instance containing projects.

• pb_election.ApprovalMultiProfile – The PB profile created from approval ballots derived from the trichotomous profile.

• dict – A mapping from PB projects back to the original alternatives.

tax_pb_rule_scheme(profile: AbstractTrichotomousProfile, max_size_selection: int, pb_rule: Callable, tax_function: type[TaxFunction], initial_selection: Selection | None = None, tie_breaking: TieBreakingRule | None = None, resoluteness: bool = True, pb_rule_kwargs: dict = None) → Selection | list[Selection]

Apply a participatory budgeting rule to a trichotomous profile by translating it into a suitable PB instance with opposition tax.

This function converts the given profile into a PB instance and profile, applies the specified PB rule using pabutools, and converts the results back.

The taxed PB rule scheme has been defined in Section 4.2 of Proportionality in Thumbs Up and Down Voting (Kraiczy, Papasotiropoulos, Pierczyński and Skowron, 2025).

In case there are alternatives whose corresponding projects have cost 0, it can happen that too many projects are selected on the PB side. In this case, the tie breaking function is used to select the right number of alternatives.

Parameters:

• profile (AbstractTrichotomousProfile) – The trichotomous profile.

• max_size_selection (int) – The maximum number of alternatives allowed in the selection.

• pb_rule (callable) – The participatory budgeting rule function to apply.

• tax_function (type[TaxFunction]) – A tax function defined as a subclass of the TaxFunction class.

• initial_selection (Selection or None, optional) – An initial selection fixing some alternatives as selected or rejected.

• tie_breaking (TieBreakingRule or None, optional) – Tie-breaking rule used for resolving ties. Defaults to lexicographic tie-breaking if None.

• resoluteness (bool, optional) – Whether to return a single resolute selection (True) or all tied selections (False). Defaults to True.

• pb_rule_kwargs (dict, optional) – Additional keyword arguments passed to the PB rule.

Returns:

The resulting selection(s) after applying the PB rule.

Return type:

Selection or list of Selection

tax_method_of_equal_shares(profile: AbstractTrichotomousProfile, max_size_selection: int, tax_function: type[TaxFunction] = None, initial_selection: Selection | None = None, tie_breaking: TieBreakingRule | None = None, resoluteness: bool = True) → Selection | list[Selection]

Apply the Tax method of equal shares to a trichotomous profile.

This method uses participatory budgeting rules to compute proportional selections with the method of equal shares adapted for approval-disapproval profiles.

Parameters:

• profile (AbstractTrichotomousProfile) – The input profile.

• max_size_selection (int) – The maximum number of alternatives to select.

• tax_function (type[TaxFunction], optional) – A tax function defined as a subclass of the TaxFunction class. Defaults to TaxKraiczy2025.

• initial_selection (Selection or None, optional) – Initial fixed selection state.

• tie_breaking (TieBreakingRule or None, optional) – Tie-breaking rule. Defaults to lexicographic.

• resoluteness (bool, optional) – Whether to return a single or multiple tied selections.

Returns:

The selection if resolute (resoluteness == True), or a list of selections if irresolute (resoluteness == False).

Return type:

Selection | list[Selection]

tax_sequential_phragmen(profile: AbstractTrichotomousProfile, max_size_selection: int, tax_function: type[TaxFunction] = None, initial_selection: Selection | None = None, tie_breaking: TieBreakingRule | None = None, resoluteness: bool = True) → Selection | list[Selection]

Apply Tax sequential Phragmén method on a trichotomous profile.

This rule transforms the profile into a participatory budgeting instance and applies sequential Phragmén via pabutools.

Parameters:

• profile (AbstractTrichotomousProfile) – The input voting profile.

• max_size_selection (int) – The maximum size of the selection.

• tax_function (type[TaxFunction], optional) – A tax function defined as a subclass of the TaxFunction class. Defaults to TaxKraiczy2025.

• initial_selection (Selection or None, optional) – Initial fixed selections.

• tie_breaking (TieBreakingRule or None, optional) – Tie-breaking rule, defaulting to lexicographic.

• resoluteness (bool, optional) – Whether to return one selection or all tied selections.

Returns:

The selection if resolute (resoluteness == True), or a list of selections if irresolute (resoluteness == False).

Return type:

Selection | list[Selection]

Chamberlin-Courant Rule

The Chamberlin-Courant rule returns selection maximising the number of voters with positive ‘satisfaction’, i.e., with strictly more selected and approved alternatives than selected but disapproved ones.

chamberlin_courant(profile: AbstractTrichotomousProfile, max_size_selection: int, initial_selection: Selection = None, resoluteness: bool = True, max_seconds: int = 600, verbose: bool = False) → Selection | list[Selection]

Compute the selections of the Chamberlin-Courant rule.

The Chamberlin-Courant returns selections that maximise the number of covered voter. A voter is covered if strictly more approved alternatives are selected than disapproved ones.

The outcome of the rule is computed via an Integer Linear Program (ILP).

Parameters:

• profile (AbstractTrichotomousProfile) – The trichotomous profile.

• max_size_selection (int) – Maximum number of alternatives to select.

• initial_selection (Selection, optional) – An initial selection that fixes some alternatives as selected or rejected. If implicit_reject is True, no alternatives are fixed to be rejected.

• resoluteness (bool, optional) – If True, returns a single selection (resolute). If False, returns all tied optimal selections (irresolute). Defaults to True.

• max_seconds (int, optional) – Maximum number of seconds to run the ILP solver for. Defaults to 600 seconds (10 minutes).

• verbose (bool, optional) – If True the output of the ILP solver is not silenced. Defaults to False.

Returns:

The selection if resolute (resoluteness == True), or a list of selections if irresolute (resoluteness == False).

Return type:

Selection | list[Selection]

class ChamberlinCourantILPBuilder(profile: AbstractTrichotomousProfile, max_size_selection: int, initial_selection: Selection = None, max_seconds: int = 600, verbose: bool = False, solver_name: ILPSolver = None)

Builder class for the ILP corresponding to the Chamberlin-Courant rule. Used in the function chamberlin_courant().

chamberlin_courant_brute_force(profile: AbstractTrichotomousProfile, max_size_selection: int, initial_selection: Selection = None, resoluteness: bool = True) → Selection | list[Selection]

Compute the selections of the Chamberlin-Courant rule using a brute-force approach. The approach is simple: each possible selection is generated and the ones with the highest Chamberlin-Courant score are returned. The Chamberlin-Courant score is equal to the number of voters with strictly more selected and approved alternatives than selected but disapproved ones.

Used mostly for testing purposes.

Parameters:

• profile (AbstractTrichotomousProfile) – The trichotomous profile.

• max_size_selection (int) – Maximum number of alternatives to select.

• initial_selection (Selection, optional) – An initial selection that fixes some alternatives as selected or rejected. If implicit_reject is True, no alternatives are fixed to be rejected.

• resoluteness (bool, optional) – If True, returns a single selection (resolute). If False, returns all tied optimal selections (irresolute). Defaults to True.

Returns:

The selection if resolute (resoluteness == True), or a list of selections if irresolute (resoluteness == False).

Return type:

Selection | list[Selection]

Max Net Support Rule

The max net support rule returns selections maximising the total net support of the voters. The net support of a voter for a given selection is defined as the number of approved and selected alternatives minus the number of disapproved but selected ones.

max_net_support(profile: AbstractTrichotomousProfile, max_size_selection: int, initial_selection: Selection = None, resoluteness: bool = True) → Selection | list[Selection]

Compute the selections maximising the total net support of the voters by sequentially selecting up to max_size_selection alternatives with positive highest net support.

The net support of an alternative is the number of voters approving of it minus the number of voters disapproving of it.

Parameters:

• profile (AbstractTrichotomousProfile) – The trichotomous profile.

• max_size_selection (int) – Maximum number of alternatives to select.

• initial_selection (Selection, optional) – An initial selection that fixes some alternatives as selected or rejected. If implicit_reject is True, no alternatives are fixed to be rejected.

• resoluteness (bool, optional) – If True, returns a single selection (resolute). If False, returns all tied optimal selections (irresolute). Defaults to True.

Returns:

The selection if resolute (resoluteness == True), or a list of selections if irresolute (resoluteness == False).

Return type:

Selection | list[Selection]

max_net_support_ilp(profile: AbstractTrichotomousProfile, max_size_selection: int, initial_selection: Selection = None, resoluteness: bool = True, max_seconds: int = 600, verbose: bool = False) → Selection | list[Selection]

Compute the selections maximising the total net support of the voters via an ILP solver.

Used mostly for debugging purposes, the function max_net_support() being much more efficient.

Parameters:

• profile (AbstractTrichotomousProfile) – The trichotomous profile.

• max_size_selection (int) – Maximum number of alternatives to select.

• initial_selection (Selection, optional) – An initial selection that fixes some alternatives as selected or rejected. If implicit_reject is True, no alternatives are fixed to be rejected.

• resoluteness (bool, optional) – If True, returns a single selection (resolute). If False, returns all tied optimal selections (irresolute). Defaults to True.

• max_seconds (int, optional) – Maximum number of seconds to run the ILP solver for. Defaults to 600 seconds (10 minutes).

• verbose (bool, optional) – If True the output of the ILP solver is not silenced. Defaults to False.

Returns:

The selection if resolute (resoluteness == True), or a list of selections if irresolute (resoluteness == False).

Return type:

Selection | list[Selection]

class MaxNetSupportILPBuilder(profile: AbstractTrichotomousProfile, max_size_selection: int, initial_selection: Selection = None, max_seconds: int = 600, verbose: bool = False, solver_name: ILPSolver = None)

Builder class for the ILP corresponding to the max net support rule. Used in the function max_net_support_ilp().