Rules

For reference, see the module rules.

We provide the implementation of the most celebrated rules for participatory budgeting.

Budget Allocation

All rules return a BudgetAllocation object. The BudgetAllocation class inherits from list and behave similarly. It is used to store additional information about the outcome (for visualisation/explanation purposes).

Additive Utilitarian Welfare Maximiser

max_additive_utilitarian_welfare()

The first rule provided is the Additive Utilitarian Welfare Maximiser. It aims to return budget allocations that maximize the utilitarian social welfare when the satisfaction measure is additive.

from pabutools.election import Instance, Project, ApprovalProfile, ApprovalBallot, Cost_Sat
from pabutools.rules import max_additive_utilitarian_welfare, MaxAddUtilWelfareAlgo

p = [Project("p" + str(i), 1) for i in range(10)]
instance = Instance(p, budget_limit=5)
profile = ApprovalProfile([
    ApprovalBallot(p),
    ApprovalBallot(p[:4]),
    ApprovalBallot({p[0], p[8]})
])

# By passing a sat_class, the profile is automatically converted to a satisfaction profile
outcome = max_additive_utilitarian_welfare(
    instance,
    profile,
    sat_class=Cost_Sat
)

# Or we can directly pass the satisfaction profile
outcome = max_additive_utilitarian_welfare(
    instance,
    profile,
    sat_profile=profile.as_sat_profile(Cost_Sat)
)

# An initial budget allocation can be given
outcome = max_additive_utilitarian_welfare(
    instance,
    profile,
    sat_profile=profile.as_sat_profile(Cost_Sat),
    initial_budget_allocation=[p[1], p[2]]
)

# We can get the irresolute outcome, i.e., a set of tied budget allocations
irresolute_outcome = max_additive_utilitarian_welfare(
    instance,
    profile,
    sat_class=Cost_Sat,
    resoluteness=False
)

# We can force the use of the ILP solver
irresolute_outcome = max_additive_utilitarian_welfare(
    instance,
    profile,
    sat_class=Cost_Sat,
    resoluteness=False,
    inner_algo=MaxAddUtilWelfareAlgo.ILP_SOLVER
)

The outcome of the utilitarian welfare maximiser can be computed either using a integer linear program (ILP) solver (through the mip package) or using the primal/dual approach for solving knapsack problems.

Only the ILP solver supports irresolute outcomes. Irresolute outcomes are computed by iteratively adding constraints excluding previously returned budget allocations. Note that because the computation is handled via a linear program solver, we have no control as to how ties are broken.

Note that this can only be used for additive satisfaction measures. There is no general solution for non-additive satisfaction measures.

Greedy Approximation of the Welfare Maximiser

greedy_utilitarian_welfare()

The library also implements standard greedy rules. The primary rule used in this context is the Greedy Utilitarian Welfare. It behaves similarly to the Utilitarian Welfare Maximiser but offers additional functionalities: it is not limited to additive satisfaction measures (and runs faster).

from pabutools.election import Instance, Project, ApprovalProfile, ApprovalBallot, Cost_Sat
from pabutools.rules import greedy_utilitarian_welfare
from pabutools.tiebreaking import app_score_tie_breaking

p = [Project("p" + str(i), 1) for i in range(10)]
instance = Instance(p, budget_limit=5)
profile = ApprovalProfile([
    ApprovalBallot(p),
    ApprovalBallot(p[:4]),
    ApprovalBallot({p[0], p[8]})
])

# By passing a sat_class, the profile is automatically converted to a satisfaction profile
outcome = greedy_utilitarian_welfare(
    instance,
    profile,
    sat_class=Cost_Sat
)

# Or we can directly pass the satisfaction profile
outcome = greedy_utilitarian_welfare(
    instance,
    profile,
    sat_profile=profile.as_sat_profile(Cost_Sat)
)

# If the satisfaction is known to be additive, we can say so to speed up computations
# This is highly recommended
outcome = greedy_utilitarian_welfare(
    instance,
    profile,
    sat_profile=profile.as_sat_profile(Cost_Sat),
    is_sat_additive=True
)

# An initial budget allocation can be given
outcome = greedy_utilitarian_welfare(
    instance,
    profile,
    sat_profile=profile.as_sat_profile(Cost_Sat),
    initial_budget_allocation=[p[1], p[2]]
)

# The tie-breaking rule can be decided
outcome = greedy_utilitarian_welfare(
    instance,
    profile,
    sat_profile=profile.as_sat_profile(Cost_Sat),
    tie_breaking=app_score_tie_breaking
)

# We can get the irresolute outcome, i.e., a set of tied budget allocations
irresolute_outcome = greedy_utilitarian_welfare(
    instance,
    profile,
    sat_class=Cost_Sat,
    resoluteness=False
)

Sequential Phragmén’s Rule

sequential_phragmen()

Another rule provided is the Sequential Phragmén’s Rule, which is different from the previous two as it does not rely on a satisfaction measure.

from pabutools.election import Instance, Project, ApprovalProfile, ApprovalBallot, Cost_Sat
from pabutools.rules import sequential_phragmen
from pabutools.tiebreaking import app_score_tie_breaking

p = [Project("p" + str(i), 1) for i in range(10)]
instance = Instance(p, budget_limit=5)
profile = ApprovalProfile([
    ApprovalBallot(p),
    ApprovalBallot(p[:4]),
    ApprovalBallot({p[0], p[8]})
])

# By passing a sat_class, the profile is automatically converted to a satisfaction profile
outcome = sequential_phragmen(
    instance,
    profile
)

# An initial budget allocation can be given
outcome = sequential_phragmen(
    instance,
    profile,
    initial_budget_allocation=[p[1], p[2]]
)

# The tie-breaking rule can be decided
outcome = sequential_phragmen(
    instance,
    profile,
    tie_breaking=app_score_tie_breaking
)

# We can get the irresolute outcome, i.e., a set of tied budget allocations
irresolute_outcome = sequential_phragmen(
    instance,
    profile,
    resoluteness=False
)

Method of Equal Shares (MES)

method_of_equal_shares()

The Method of Equal Shares is another rule that returns budget allocations based on the satisfaction measure provided. For more details, see the equalshares.net website.

from pabutools.election import Instance, Project, ApprovalProfile, ApprovalBallot, Cost_Sat
from pabutools.rules import method_of_equal_shares
from pabutools.tiebreaking import app_score_tie_breaking

p = [Project("p" + str(i), 1) for i in range(10)]
instance = Instance(p, budget_limit=5)
profile = ApprovalProfile([
    ApprovalBallot(p),
    ApprovalBallot(p[:4]),
    ApprovalBallot({p[0], p[8]})
])

# By passing a sat_class, the profile is automatically converted to a satisfaction profile
outcome = method_of_equal_shares(
    instance,
    profile,
    sat_class=Cost_Sat
)

# Or we can directly pass the satisfaction profile
outcome = method_of_equal_shares(
    instance,
    profile,
    sat_profile=profile.as_sat_profile(Cost_Sat)
)

# An initial budget allocation can be given
outcome = method_of_equal_shares(
    instance,
    profile,
    sat_profile=profile.as_sat_profile(Cost_Sat),
    initial_budget_allocation=[p[1], p[2]]
)

# The tie-breaking rule can be decided
outcome = method_of_equal_shares(
    instance,
    profile,
    sat_profile=profile.as_sat_profile(Cost_Sat),
    tie_breaking=app_score_tie_breaking
)

# We can get the irresolute outcome, i.e., a set of tied budget allocations
irresolute_outcome = method_of_equal_shares(
    instance,
    profile,
    sat_class=Cost_Sat,
    resoluteness=False
)

MES can significantly under-use the budget. The idea of running the rule for different initial budget for the voters has been proposed in the scientific literature as a fix for that problem. The next section will present general methods to do so. For optimal performances, one should use the following:

outcome = method_of_equal_shares(
    instance,
    profile.as_multiprofile(), # Faster in general (typically if ballots repeat each others)
    sat_class=Cost_Sat,
    voter_budget_increment=1 # As soon as not-None, mes iterated is used
)

Exhaustion Methods

completion_by_rule_combination()

exhaustion_by_budget_increase()

Since not all rules return exhaustive budget allocations, the library offers standard methods to render their outcome exhaustive.

Two methods are provided: the first applies a sequence of rules until achieving an exhaustive budget allocation.

from pabutools.election import Instance, Project, ApprovalProfile, ApprovalBallot
from pabutools.election import Cost_Sat, Cardinality_Sat
from pabutools.rules import greedy_utilitarian_welfare, method_of_equal_shares
from pabutools.rules import completion_by_rule_combination

p = [Project("p" + str(i), 1) for i in range(10)]
instance = Instance(p, budget_limit=5)
profile = ApprovalProfile([
    ApprovalBallot(p),
    ApprovalBallot(p[:4]),
    ApprovalBallot({p[0], p[8]})
])

# Here we apply two rules: first MES with the cost satisfaction,
# and then the greedy rule with the cardinality satisfaction
budget_allocation_mes_completed = completion_by_rule_combination(
    instance,
    profile,
    [method_of_equal_shares, greedy_utilitarian_welfare],
    [{"sat_class": Cost_Sat}, {"sat_class": Cardinality_Sat}],
)

The second method consists of increasing the budget limit of the instance, in the hope that the rule would then return a budget allocation that is exhaustive for the original instance. If at any point the rule returns a budget allocation that is not feasible for the original budget limit, then the previously returned budget allocation is returned.

from pabutools.election import Instance, Project, ApprovalProfile, ApprovalBallot, Cost_Sat
from pabutools.rules import method_of_equal_shares, exhaustion_by_budget_increase
from pabutools.fractions import frac

p = [Project("p" + str(i), 1) for i in range(10)]
instance = Instance(p, budget_limit=5)
profile = ApprovalProfile([
    ApprovalBallot(p),
    ApprovalBallot(p[:4]),
    ApprovalBallot({p[0], p[8]})
])

# Here we apply the MES rule with cost satisfaction until finding a suitable outcome
budget_allocation_mes_iterated = exhaustion_by_budget_increase(
    instance,
    profile,
    method_of_equal_shares,
    {"sat_class": Cost_Sat},
    budget_step=instance.budget_limit * frac(1, 100), # Important for runtime, default is 1
)

Note that since these two functions behave as rules, they can be combined. For instance, one can first run MES with an increasing budget, and then complete the outcome with the greedy method (which only does something if the outcome is not already exhaustive).

completion_by_rule_combination(
    instance,
    profile,
    [exhaustion_by_budget_increase, greedy_utilitarian_welfare],
    [
        {
            "rule": method_of_equal_shares,
            "rule_params": {"sat_class": Cost_Sat},
        },
        {"sat_class": Cost_Sat},
    ],
)

Remember that for MES specifically, it is much faster to use the voter_budget_increment parameter directly to obtain the iterated version.

Rule Composition

popularity_comparison()

social_welfare_comparison()

The library also provides ways to compose rules, such as selecting the outcome that is preferred by the largest number of voters for a given satisfaction measure.

from pabutools.election import Instance, Project, ApprovalProfile, ApprovalBallot
from pabutools.election import Cost_Sat, Cardinality_Sat
from pabutools.rules import greedy_utilitarian_welfare, method_of_equal_shares
from pabutools.rules import popularity_comparison

p = [Project("p" + str(i), 1) for i in range(10)]
instance = Instance(p, budget_limit=5)
profile = ApprovalProfile([
    ApprovalBallot(p),
    ApprovalBallot(p[:4]),
    ApprovalBallot({p[0], p[8]})
])

# Here we apply two rules: MES and greedy with the cost satisfaction,
# and return the most preferred outcome based on Cardinality_Sat
outcome = popularity_comparison(
    instance,
    profile,
    Cardinality_Sat,
    [method_of_equal_shares, greedy_utilitarian_welfare],
    [{"sat_class": Cost_Sat}, {"sat_class": Cost_Sat}],
)

To run the rule as it was implemented in Wieliczka and Świece, for instance, one would run the following:

from pabutools.election import Instance, Project, ApprovalProfile, ApprovalBallot
from pabutools.election import Cost_Sat, Cardinality_Sat
from pabutools.rules import greedy_utilitarian_welfare, method_of_equal_shares
from pabutools.rules import completion_by_rule_combination, popularity_comparison

p = [Project("p" + str(i), 1) for i in range(10)]
instance = Instance(p, budget_limit=5)
profile = ApprovalProfile([
    ApprovalBallot(p),
    ApprovalBallot(p[:4]),
    ApprovalBallot({p[0], p[8]})
])

# First define MES iterated and completed (to simplify)
def mes_full(instance, profile, initial_budget_allocation=None):
    return completion_by_rule_combination(
        instance,
        profile,
        [method_of_equal_shares, greedy_utilitarian_welfare],
        [
            {
                "sat_class": Cost_Sat,
                "voter_budget_increment": 1,
            },
            {"sat_class": Cost_Sat},
        ],
    )

# Then run a popularity comparison between MES in full and Greedy Cardinality
popularity_comparison(
    instance,
    profile,
    Cardinality_Sat,
    [mes_full, greedy_utilitarian_welfare],
    [{}, {"sat_class": Cardinality_Sat}]
)

We also provide a similar comparison using utilitarian social welfare through the function social_welfare_comparison().

Details for the Budget Allocation Rule

Some rules, for instance greedy_utilitarian_welfare() or method_of_equal_shares(), accept a analytics boolean argument to activate the storage of additional information regarding the budget allocations output by the rule. When analytics = True, the rule populate the details member of the BudgetAllocation object it returns. The stored information can then be used for analytical purposes.

Rule	Details class
greedy_utilitarian_welfare()	GreedyWelfareAllocationDetails
method_of_equal_shares()	MESAllocationDetails

See the Outcome Visualisation page for more details.