Rules module

Module introducing known rules for computing the outcome of participatory budgeting elections.

The rules implemented are:

• The utilitarian welfare maximiser: max_additive_utilitarian_welfare()

• The greedy approximation of the utilitarian welfare maximiser: greedy_utilitarian_welfare()

• The method of equal shares: method_of_equal_shares()

• The sequential Phragmén rule: sequential_phragmen()

Given that some rules may not used up the budget as much as possible (notably the method of equal shares and the sequential Phragmén rule), we also implement methods to make the outcome exhaustive. Specifically, we implemented:

• The completion method by rule combination: completion_by_rule_combination()

• The exhaustion method by budget increase: exhaustion_by_budget_increase()

All rules return one or several lists of projects called budget allocations, represented by the class BudgetAllocation.

Budget Allocation

class BudgetAllocation(init: Iterable[Project] = (), details: AllocationDetails | None = None)

A budget allocation is the outcome of rule. It simply corresponds to a list of projects. Additional information can also be stored in this class, for instance for explanation purposes.

Parameters:

• init (Iterable[Project], optional) – An iterable of Project that is used an initializer for the list.

• details (AllocationDetails, optional) – Used for storing various additional information about a participatory budgeting rule run. Defaults to None.

details

Used for storing various additional information about a participatory budgeting rule run. Defaults to None.

Type:

AllocationDetails, optional

class AllocationDetails

Class representing participatory budgeting rule run details. Used as a parent class which can be inherited.

Greedy Utilitarian Rule

greedy_utilitarian_welfare(instance: Instance, profile: AbstractProfile, sat_class: type[SatisfactionMeasure] | None = None, sat_profile: GroupSatisfactionMeasure | None = None, is_sat_additive: bool | None = None, tie_breaking: TieBreakingRule | None = None, resoluteness: bool = True, initial_budget_allocation: Collection[Project] | None = None, analytics: bool = False) → BudgetAllocation | list[BudgetAllocation]

General greedy scheme for approximating the utilitarian welfare. It selects projects in rounds, each time selecting a project that lead to the highest increase in total satisfaction divided by the cost of the project. Projects that would lead to a violation of the budget constraint are skipped.

Parameters:

• instance (Instance) – The instance.

• profile (AbstractProfile) – The profile.

• sat_class (type[SatisfactionMeasure]) – The class defining the satisfaction function used to measure the social welfare. It should be a class inhereting from SatisfactionMeasure. If no satisfaction is provided, a satisfaction profile needs to be provided. If a satisfation profile is provided, the satisfaction argument is disregarded.

• sat_profile (GroupSatisfactionMeasure) – The satisfaction profile corresponding to the instance and the profile. If no satisfaction profile is provided, but a satisfaction function is, the former is computed from the latter.

• is_sat_additive (bool) – A boolean indicating if the satisfaction function is additive. This is directly deducted if sat_class is provided.

• initial_budget_allocation (Iterable[Project]) – An initial budget allocation, typically empty.

• tie_breaking (TieBreakingRule, optional) – The tie-breaking rule used. Defaults to the lexicographic tie-breaking.

• resoluteness (bool, optional) – Set to False to obtain an irresolute outcome, where all tied budget allocations are returned. Defaults to True.

• analytics (bool, optional) – (De)Activate the calculation of analytics. Defaults to False.

Returns:

The selected budget allocation if resolute (resoluteness == True), or the set of budget allocations if irresolute (resoluteness == False).

Return type:

BudgetAllocation | Collection[BudgetAllocation]

class GreedyWelfareAllocationDetails

Additive Utilitarian Welfare Maximiser

enum MaxAddUtilWelfareAlgo(value)

Constants use to represent different algorithms that can be used to compute budget allocations maximising the additive utilitarian welfare.

Valid values are as follows:

ILP_SOLVER = <MaxAddUtilWelfareAlgo.ILP_SOLVER: 1>

Converts the instance into a integer linear program (ILP) and uses an ILP solver to compute the outcome.

PRIMAL_DUAL = <MaxAddUtilWelfareAlgo.PRIMAL_DUAL: 2>

Uses state-of-the-art primal/dual solvers for knapsack problems to compute the outcome.

max_additive_utilitarian_welfare(instance: Instance, profile: AbstractProfile, sat_class: type[SatisfactionMeasure] | None = None, sat_profile: GroupSatisfactionMeasure | None = None, resoluteness: bool = True, initial_budget_allocation: Collection[Project] | None = None, inner_algo: MaxAddUtilWelfareAlgo | None = None) → BudgetAllocation | list[BudgetAllocation]

Rule returning the budget allocation(s) maximizing the utilitarian social welfare. The utilitarian social welfare is defined as the sum of the satisfactin of the voters, where the satisfaction is computed using the satisfaction measure given as a parameter. The satisfaction measure is assumed to be additive.

The outcome can be computed either via a integer linear program solver or with a primal/dual approach. Note that depending on the selected algorithm, not all functionalities are supported (with the ILP solver ties cannot be handled while the primal/dual approach does not support irresolute outcomes).

Parameters:

• instance (Instance) – The instance.

• profile (AbstractProfile) – The profile.

• sat_class (type[SatisfactionMeasure]) – The class defining the satisfaction function used to measure the social welfare. It should be a class inhereting from pabutools.election.satisfaction.satisfactionmeasure.SatisfactionMeasure. If no satisfaction is provided, a satisfaction profile needs to be provided. If a satisfation profile is provided, the satisfaction argument is disregarded.

• sat_profile (GroupSatisfactionMeasure) – The satisfaction profile corresponding to the instance and the profile. If no satisfaction profile is provided, but a satisfaction function is, the former is computed from the latter.

• initial_budget_allocation (Iterable[Project]) – An initial budget allocation, typically empty.

• resoluteness (bool, optional) – Set to False to obtain an irresolute outcome, where all tied budget allocations are returned. Defaults to True.

• inner_algo (MaxAddUtilWelfareAlgo, optional) – The inner algorithm used. See MaxAddUtilWelfareAlgo for the available choices. Defaults to MaxAddUtilWelfareAlgo.PRIMAL_DUAL if resoluteness == True, otherwise defaults to MaxAddUtilWelfareAlgo.ILP_SOLVER.

Returns:

The selected projects if resolute (resoluteness == True), or the set of selected projects if irresolute (resoluteness == False).

Return type:

BudgetAllocation | list[BudgetAllocation]

Sequential Phragmén’s Rule

sequential_phragmen(instance: Instance, profile: AbstractApprovalProfile, initial_loads: list[int | float | mpq] | None = None, initial_budget_allocation: Collection[Project] | None = None, tie_breaking: TieBreakingRule | None = None, resoluteness: bool = True) → BudgetAllocation | list[BudgetAllocation]

Phragmén’s sequential rule. It works as follows. Voters receive money in a virtual currency. They all start with a budget of 0 and that budget continuously increases. As soon asa group of supporters have enough virtual currency to buy a project they all approve, the project is bought. The rule stops as soon as there is a project that could be bought but only by violating the budget constraint.

Note that this rule can only be applied to profile of approval ballots.

Parameters:

• instance (Instance) – The instance.

• profile (AbstractProfile) – The profile.

• initial_loads (list[Numeric], optional) – A list of initial load, one per ballot in profile. By defaults, the initial load is 0.

• initial_budget_allocation (Iterable[Project]) – An initial budget allocation, typically empty.

• tie_breaking (TieBreakingRule, optional) – The tie-breaking rule used. Defaults to the lexicographic tie-breaking.

• resoluteness (bool, optional) – Set to False to obtain an irresolute outcome, where all tied budget allocations are returned. Defaults to True.

Returns:

The selected projects if resolute (resoluteness == True), or the set of selected projects if irresolute (resoluteness == False).

Return type:

BudgetAllocation | list[BudgetAllocation]

Method of Equal Shares (MES)

method_of_equal_shares(instance: Instance, profile: AbstractProfile, sat_class: type[SatisfactionMeasure] | None = None, sat_profile: GroupSatisfactionMeasure | None = None, tie_breaking: TieBreakingRule | None = None, resoluteness: bool = True, initial_budget_allocation: Iterable[Project] | None = None, voter_budget_increment=None, binary_sat=None, skipped_project: Project | None = None, analytics: bool = False, verbose: bool = False) → BudgetAllocation | list[BudgetAllocation]

The Method of Equal Shares (MES). See the website equalshares.net for details about how to compute the outcome of the rule. Note that the satisfaction measure is assumed to be additive.

Parameters:

• instance (Instance) – The instance.

• profile (AbstractProfile) – The profile.

• sat_class (type[SatisfactionMeasure]) – The class defining the satisfaction function used to measure the social welfare. It should be a class inhereting from pabutools.election.satisfaction.satisfactionmeasure.SatisfactionMeasure. If no satisfaction is provided, a satisfaction profile needs to be provided. If a satisfation profile is provided, the satisfaction argument is disregarded.

• sat_profile (GroupSatisfactionMeasure) – The satisfaction profile corresponding to the instance and the profile. If no satisfaction profile is provided, but a satisfaction function is, the former is computed from the latter.

• initial_budget_allocation (Iterable[Project]) – An initial budget allocation, typically empty.

• tie_breaking (TieBreakingRule, optional) – The tie-breaking rule used. Defaults to the lexicographic tie-breaking.

• resoluteness (bool, optional) – Set to False to obtain an irresolute outcome, where all tied budget allocations are returned. Defaults to True.

• voter_budget_increment (Numeric, optional) – Any value that is not None will lead to the iterated variant of MES where voter_budget_increment units of budget are added to the initial budget of the voters until an exhaustive budget allocation is found, or one that is no longer feasible with the initial budget constraint.

• binary_sat (bool, optional) – Uses the inner algorithm for binary satisfaction if set to True. Should typically be used with approval ballots to gain on the runtime. Automatically set to True if an approval profile is given.

• skipped_project (MESProject, optional,) – Project from instance which shouldn’t be considered in calculations and for which effective support will be calculated, if analytics is true. Solely used by analytics module.

• analytics (bool, optional) – (De)Activate the computation of analytics. These are additional details that can be accessed from the BudgetAllocation object returned by the rule to perform analyses. Defaults to False.

• verbose (bool, optional) – (De)Activate the display of additional information. Defaults to False.

Returns:

The selected projects if resolute (resoluteness == True), or the set of selected projects if irresolute (resoluteness == False).

Return type:

BudgetAllocation | list[BudgetAllocation]

class MESAllocationDetails(voter_multiplicity: list[int])

Class representing the details of MES rule. This class represents the MES details using an iteration approach: at each iteration of the MES rule some crucial information is saved which allow for reconstruction of the whole run. An iteration corrosponds to one call to mes_inner_algo, and each iteration corrosponds to one project being picked.

iterations

A list of all iterations of a MES rule run. It is progressively populated during a MES rule run.

Type:

Iterable[MESIteration]

class MESIteration(voters_budget: list[int | float | mpq] | None = None, voters_budget_after_selection: list[int | float | mpq] | None = None, selected_project: Project | None = None)

Class representing a single iteration of a MES rule run, solely used in MESAllocationDetails. Each iteration consist of information necessary for reconstructing a MES rule run. This includes the list of projects that were considered in this iteration, the budget of all the voters and the project that was selected at the end of the iteration.

Parameters:

• voters_budget (list[int], optional) – The budget of all voters at the start of the iteration. Defaults to None.

• voters_budget_after_selection (list[int], optional) – The budget of all voters after the selected project was covered. Defaults to None.

• selected_project (Project, optional) – The project that was selected at the end of the iteration. Defaults to None.

voters_budget

The budget of all voters at the start of the iteration. Defaults to None.

Type:

list[int], optional

voters_budget_after_selection

The budget of all voters after the selected project was covered. Defaults to None.

Type:

list[int], optional

selected_project

The project that was selected at the end of the iteration. Defaults to None.

Type:

Project, optional

Exhaustion Methods

completion_by_rule_combination(instance: Instance, profile: AbstractProfile, rule_sequence: Collection[Callable], rule_params: Collection[dict] | None = None, initial_budget_allocation: Iterable[Project] | None = None, resoluteness: bool = True) → BudgetAllocation | list[BudgetAllocation]

Runs the given rules on the given instance and profile in sequence until an exhaustive budget allocation has been reached (or all rules have been applied). This is useful if the first rules are non-exhaustive. In the irresolute version, all outcomes are completed separately.

Parameters:

• instance (Instance) – The instance.

• profile (AbstractProfile) – The profile.

• rule_sequence (Iterable[Callable]) – Iterable of the rule functions.

• rule_params (Iterable[dict], optional) – Iterable of dictionaries of additional parameters that are passed as keyword arguments to the rule functions. Defaults to {}.

• initial_budget_allocation (Iterable[Project], optional) – An initial budget allocation, typically empty. Defaults to [].

• resoluteness (bool, optional) – Set to False to obtain an irresolute outcome, where all tied budget allocations are returned. Defaults to True.

Returns:

The selected projects.

Return type:

BudgetAllocation | list[BudgetAllocation]

exhaustion_by_budget_increase(instance: Instance, profile: AbstractProfile, rule: Callable, rule_params: dict | None = None, initial_budget_allocation: Iterable[Project] | None = None, resoluteness: bool = True, exhaustive_stop: bool = True, budget_step: int | float | mpq | None = None, budget_bound: int | float | mpq | None = None) → BudgetAllocation | list[BudgetAllocation]

Runs the given rule iteratively with increasing budget, until an exhaustive allocation is retrieved or the budget limit is exceeded by the rule with increased budget. In the irresolute version, as soon as one outcome is exhaustive or infeasible, the procedure stops.

If you are interested to only stop when the returned budget allocation is not feasible (and thus not when it is exhaustive), set exhaustive_stop=False.

Parameters:

• instance (Instance) – The instance.

• profile (AbstractProfile) – The profile.

• rule – The rule function

• rule_params (dict, optional) – Dictionary of additional parameters that are passed as keyword arguments to the rule function. Defaults to {}.

• initial_budget_allocation (Collection[Project], optional) – An initial budget allocation, typically empty. Defaults to []. Overrides the parameter in rule_params.

• resoluteness (bool, optional) – Set to False to obtain an irresolute outcome, where all tied budget allocations are returned. Defaults to True.

• exhaustive_stop (bool, optional) – Set to False to disable the exhaustive allocation stop condition, leaving only the non-feasibility as the stop condition of this rule. Defaults to True.

• budget_step (Numeric) – The step at which the budget is increased. Defaults to 1% of the budget limit.

• budget_bound (Numeric) – An upper bound on the budget limit. The method stops if this bound is exceeded. Defaults to the budget limit multiplied by the number of agents plus 1.

Returns:

The selected budget allocation if resolute (resoluteness == True), or the set of budget allocations if irresolute (resoluteness == False).

Return type:

BudgetAllocation | Iterable[BudgetAllocation]

Rule Composition

popularity_comparison(instance: Instance, profile: Profile, sat_class: type[SatisfactionMeasure], rule_sequence: Collection[Callable], rule_params: Collection[dict] | None = None, initial_budget_allocation: Iterable[Project] | None = None) → list[BudgetAllocation]

Compute the outcome of several rules and returns the ones that are the most preferred by the largest set of voters, according to a given satisfaction measure. Should only be applied to resolute rules.

Parameters:

• instance (Instance) – The instance.

• profile (AbstractProfile) – The profile.

• sat_class (type[SatisfactionMeasure]) – The satisfaction measure used to do the comparison.

• rule_sequence (Collection[Callable]) – Iterable of the rule functions.

• rule_params (Collection[dict], optional) – Iterable of dictionaries of additional parameters that are passed as keyword arguments to the rule functions. Defaults to {}.

• initial_budget_allocation (Iterable[Project], optional) – An initial budget allocation, typically empty. Defaults to [].

Returns:

All the budget allocations yielding the maximum total satisfaction for the outcomes of the rules.

Return type:

list[BudgetAllocation]

social_welfare_comparison(instance: Instance, profile: Profile, sat_class: type[SatisfactionMeasure], rule_sequence: Collection[Callable], rule_params: Collection[dict] | None = None, initial_budget_allocation: Iterable[Project] | None = None) → list[BudgetAllocation]

Compute the outcome of several rules and returns the one that is the most preferred by the voters according to a given satisfaction measure. Should only be applied to resolute rules.

Parameters:

• instance (Instance) – The instance.

• profile (AbstractProfile) – The profile.

• sat_class (type[SatisfactionMeasure]) – The satisfaction measure used to do the comparison.

• rule_sequence (Collection[Callable]) – Iterable of the rule functions.

• rule_params (Collection[dict], optional) – Iterable of dictionaries of additional parameters that are passed as keyword arguments to the rule functions. Defaults to {}.

• initial_budget_allocation (Iterable[Project], optional) – An initial budget allocation, typically empty. Defaults to [].

Returns:

All the budget allocations yielding the maximum total satisfaction for the outcomes of the rules.

Return type:

list[BudgetAllocation]