Satisfaction module

Contents

Satisfaction module#

Module introducing different ways to approximate the voters’ satisfaction given their ballots. See the see the ballot module for more details on the ballots.

This module introduces general ways to define satisfaction measures together with a large set of already implemented satisfaction measures.

First thing first, two abstract classes define satisfaction measures:

As is the case for the profiles (see the module profile), we introduce satisfaction profiles—in the class SatisfactionProfile—and satisfaction multiprofiles—in the class SatisfactionMultiProfile.

Individual satisfaction measures are defined according to three different classes:

The following satisfaction measures have already been implemented. Note that they do not apply to all types of ballots.

Satisfaction Measure

Class

Type

Ballot Type

Chamberlin-Courant

CC_Sat

FunctionalSatisfaction

AbstractApprovalBallot AbstractCardinalBallot

Cost

Cost_Sat

AdditiveSatisfaction

all

Relative Cost

Relative_Cost_Sat

AdditiveSatisfaction

all

Approx Normaliser Relative Cost

Relative_Cost_Approx_Normaliser_Sat

AdditiveSatisfaction

all

Cost Square Root

Cost_Sqrt_Sat

FunctionalSatisfaction

AbstractApprovalBallot

Additive Cost Square Root

Additive_Cost_Sqrt_Sat

AdditiveSatisfaction

AbstractApprovalBallot

Cost Log

Cost_Log_Sat

FunctionalSatisfaction

AbstractApprovalBallot

Additive Cost Log

Additive_Cost_Log_Sat

AdditiveSatisfaction

AbstractApprovalBallot

Cardinality

Cardinality_Sat

AdditiveSatisfaction

all

Relative Cardinality

Relative_Cardinality_Sat

AdditiveSatisfaction

all

Effort

Effort_Sat

AdditiveSatisfaction

AbstractApprovalBallot

Additive for Cardinal Ballots

Additive_Cardinal_Sat

AdditiveSatisfaction

AbstractCardinalBallot

Relative Additive for Cardinal Ballots

Additive_Cardinal_Relative_Sat

AdditiveSatisfaction

AbstractCardinalBallot

Additive Borda

Additive_Borda_Sat

PositionalSatisfaction

AbstractOrdinalBallot
class SatisfactionMeasure(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Bases: ABC

Abstract class representing a satisfaction measure for a given ballot. Importantly, a satisfaction measure is always linked to a specific ballot, part of a specific profile, given a specific instance.

Satisfaction measures are hased and compared based solely based on the ballot they correspond to. The profile and the instance are thus ignored.

This class is only meant to be inherited.

Parameters:
instance#

The instance.

Type:

Instance

profile#

The profile.

Type:

AbstractProfile

ballot#

The ballot.

Type:

AbstractBallot

abstract sat(projects: Collection[Project]) → int | float | mpq[source]#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

abstract sat_project(project: Project) → int | float | mpq[source]#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class GroupSatisfactionMeasure[source]#

Bases: ABC, Iterable[SatisfactionMeasure]

Abstract class representing a collection of satisfaction measure, one per voter.

abstract multiplicity(sat: SatisfactionMeasure) → int[source]#

Returns the multiplicity of the given satisfaction measure.

Parameters:

sat (SatisfactionMeasure) – The satisfaction measure.

Returns:

The multiplicity of the satisfaction measure.

Return type:

int

abstract remove_satisfied(sat_bound: dict[AbstractBallot, int | float | mpq], projects: Collection[Project]) → GroupSatisfactionMeasure[source]#

Returns a new satisfaction profile excluding the satisfaction measurs corresponding to satisfied voters, i.e., who have met or exceeded their satisfaction bound for a given collection of projects.

Parameters:

  • sat_bound (dict[str, Numeric]) – A dictionary of ballot names to numbers, specifying for each ballot the satisfaction bound above which the voter is considered satisfied. Note that the keys are ballot names, and that nothing ensures ballot names to be unique, so be careful here.

  • projects (Iterable[Project]) – The collection of projects.

Returns:

The new satisfaction profile.

Return type:

GroupSatisfactionMeasure

total_satisfaction(projects: Collection[Project]) → int | float | mpq[source]#

Sums up the satisfaction of all the satisfaction measures for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The total satisfaction for the collection of projects.

Return type:

Numeric

total_satisfaction_project(project: Project) → int | float | mpq[source]#

Sums up the satisfaction of all the satisfaction measures for the given project.

Parameters:

project (Project) – The project.

Returns:

The total satisfaction for the collection of projects.

Return type:

Numeric

class SatisfactionMultiProfile(init: Iterable[SatisfactionMeasure] | dict[SatisfactionMeasure, int] | None = None, instance: Instance | None = None, profile: Profile | None = None, multiprofile: MultiProfile | None = None, sat_class: type[SatisfactionMeasure] | None = None, inner_sat_class: type[SatisfactionMeasure] | None = None)[source]#

Bases: Counter, GroupSatisfactionMeasure

A multiprofile of satisfaction measure, i.e., a collection of satisfaction measures together with their multiplicity. This class inherits from the Python Counter class and can thus be used as one.

Parameters:

  • init (Iterable[SatisfactionMeasure] or) – dict[SatisfactionMeasure, int] The initialiser for the Counter. Can either be an iterable of SatisfactionMeasure or a mapping of SatisfactionMeasure to int.

  • instance (Instance, optional) – The instance corresponding to the satisfaction profile. Defaults to Instance().

  • profile (Profile) – A profile to extract the ballots from. If the profile argument is used, the sat_class argument should be used as well. In this case, the satisfaction profile is initialized with the satisfaction measure corresponding to the ballots in the profile given the satisfaction measure class passed as sat_class.

  • multiprofile (MultiProfile) – A multiprofile to extract the ballots from. If the multiprofile argument is used, the sat_class argument should be used as well. In this case, the satisfaction profile is initialized with the satisfaction measure corresponding to the ballots in the multiprofile given the satisfaction measure class passed as sat_class.

  • sat_class (type[SatisfactionMeasure]) – A satisfaction class to use for converting a potentially given profile. Can only be used if either the profile or the multiprofile argument are also used. Note that we need here the class of the satisfaction measure, and not an instance of it.

  • inner_sat_class (type[SatisfactionMeasure]) – The satisfaction class that needs to be stored in the sat_class attribute. Rarely useful (but needed for deepcopy).

instance#

The instance corresponding to the satisfaction profile.

Type:

Instance

sat_class#

The satisfaction class used to generate the satisfaction profile.

Type:

type[SatisfactionMeasure]

append(element: SatisfactionMeasure) → None[source]#

Adds a satisfaction measure to the profile.

Parameters:

element (SatisfactionMeasure) – A satisfaction measure to add to the profile.

clear() → None.  Remove all items from D.#
copy(*args)#

Return a shallow copy.

elements()#

Iterator over elements repeating each as many times as its count.

>>> c = Counter('ABCABC')
>>> sorted(c.elements())
['A', 'A', 'B', 'B', 'C', 'C']

Knuth’s example for prime factors of 1836: 2**2 * 3**3 * 17**1

>>> import math
>>> prime_factors = Counter({2: 2, 3: 3, 17: 1})
>>> math.prod(prime_factors.elements())
1836

Note, if an element’s count has been set to zero or is a negative number, elements() will ignore it.

extend_from_multiprofile(profile: MultiProfile, sat_class: type[SatisfactionMeasure]) → None[source]#

Extends the satisfaction multiprofile with the multiprofile passed as argument using the satisfaction class passed as argument.

Parameters:

  • profile (MultiProfile) – The multiprofile to extend from.

  • sat_class (type[SatisfactionMeasure]) – The satisfaction class used to convert the ballots into satisfaction measures.

extend_from_profile(profile: Profile, sat_class: type[SatisfactionMeasure]) → None[source]#

Extends the satisfaction multiprofile with the profile passed as argument using the satisfaction class passed as argument.

Parameters:

  • profile (Profile) – The collection of ballots to extend from.

  • sat_class (type[SatisfactionMeasure]) – The satisfaction class used to convert the ballots into satisfaction measures.

classmethod fromkeys(iterable, v=None)#

Create a new dictionary with keys from iterable and values set to value.

get(key, default=None, /)#

Return the value for key if key is in the dictionary, else default.

items() → a set-like object providing a view on D's items#
keys() → a set-like object providing a view on D's keys#
most_common(n=None)#

List the n most common elements and their counts from the most common to the least. If n is None, then list all element counts.

>>> Counter('abracadabra').most_common(3)
[('a', 5), ('b', 2), ('r', 2)]
multiplicity(sat: SatisfactionMeasure) → int[source]#

Returns the multiplicity of the given satisfaction measure.

Parameters:

sat (SatisfactionMeasure) – The satisfaction measure.

Returns:

The multiplicity of the satisfaction measure.

Return type:

int

pop(k[, d]) → v, remove specified key and return the corresponding value.#

If the key is not found, return the default if given; otherwise, raise a KeyError.

popitem()#

Remove and return a (key, value) pair as a 2-tuple.

Pairs are returned in LIFO (last-in, first-out) order. Raises KeyError if the dict is empty.

remove_satisfied(sat_bound: dict[AbstractBallot, int | float | mpq], projects: Collection[Project]) → SatisfactionMultiProfile[source]#

Returns a new satisfaction profile excluding the satisfaction measurs corresponding to satisfied voters, i.e., who have met or exceeded their satisfaction bound for a given collection of projects.

Parameters:

  • sat_bound (dict[str, Numeric]) – A dictionary of ballot names to numbers, specifying for each ballot the satisfaction bound above which the voter is considered satisfied. Note that the keys are ballot names, and that nothing ensures ballot names to be unique, so be careful here.

  • projects (Iterable[Project]) – The collection of projects.

Returns:

The new satisfaction profile.

Return type:

GroupSatisfactionMeasure

setdefault(key, default=None, /)#

Insert key with a value of default if key is not in the dictionary.

Return the value for key if key is in the dictionary, else default.

subtract(iterable=None, /, **kwds)#

Like dict.update() but subtracts counts instead of replacing them. Counts can be reduced below zero. Both the inputs and outputs are allowed to contain zero and negative counts.

Source can be an iterable, a dictionary, or another Counter instance.

>>> c = Counter('which')
>>> c.subtract('witch')             # subtract elements from another iterable
>>> c.subtract(Counter('watch'))    # subtract elements from another counter
>>> c['h']                          # 2 in which, minus 1 in witch, minus 1 in watch
0
>>> c['w']                          # 1 in which, minus 1 in witch, minus 1 in watch
-1
total()[source]#

Sum of the counts

total_satisfaction(projects: Collection[Project]) → int | float | mpq#

Sums up the satisfaction of all the satisfaction measures for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The total satisfaction for the collection of projects.

Return type:

Numeric

total_satisfaction_project(project: Project) → int | float | mpq#

Sums up the satisfaction of all the satisfaction measures for the given project.

Parameters:

project (Project) – The project.

Returns:

The total satisfaction for the collection of projects.

Return type:

Numeric

update(iterable=None, /, **kwds)#

Like dict.update() but add counts instead of replacing them.

Source can be an iterable, a dictionary, or another Counter instance.

>>> c = Counter('which')
>>> c.update('witch')           # add elements from another iterable
>>> d = Counter('watch')
>>> c.update(d)                 # add elements from another counter
>>> c['h']                      # four 'h' in which, witch, and watch
4
values() → an object providing a view on D's values#
class SatisfactionProfile(init: Iterable[SatisfactionMeasure] = (), instance: Instance | None = None, profile: Profile | None = None, sat_class: type[SatisfactionMeasure] | None = None)[source]#

Bases: list[SatisfactionMeasure], GroupSatisfactionMeasure

A profile of satisfaction measure, i.e., a collection of satisfaction measures, one per voter. This class inherits from the Python list class and can thus be used as one.

Parameters:

  • init (Iterable[SatisfactionMeasure]) – An iterable of SatisfactionMeasure used as initialize of the list.

  • instance (Instance, optional) – The instance corresponding to the satisfaction profile. Defaults to Instance().

  • profile (Profile) – A profile to extract the ballots from. If the profile argument is used, the sat_class argument should be used as well. In this case, the satisfaction profile is initialized with the satisfaction measure corresponding to the ballots in the profile given the satisfaction measure class passed as sat_class.

  • sat_class (type[SatisfactionMeasure]) – A satisfaction class to use for converting a potentially given profile. Can only be used if the profile argument is also used. Note that we need here the class of the satisfaction measure, and not an instance of it.

instance#

The instance corresponding to the satisfaction profile.

Type:

Instance

sat_class#

The satisfaction class used to generate the satisfaction profile.

Type:

type[SatisfactionMeasure]

append(object, /)#

Append object to the end of the list.

clear()#

Remove all items from list.

copy(*args)#

Return a shallow copy of the list.

count(value, /)#

Return number of occurrences of value.

extend(iterable, /)#

Extend list by appending elements from the iterable.

extend_from_profile(profile: Profile, sat_class: type[SatisfactionMeasure]) → None[source]#

Extends the satisfaction profile with the profile passed as argument using the satisfaction class passed as argument.

Parameters:

  • profile (Profile) – The collection of ballots to extend from.

  • sat_class (type[SatisfactionMeasure]) – The satisfaction class used to convert the ballots into satisfaction measures.

index(value, start=0, stop=9223372036854775807, /)#

Return first index of value.

Raises ValueError if the value is not present.

insert(index, object, /)#

Insert object before index.

multiplicity(sat: SatisfactionMeasure) → int[source]#

Returns 1 regardless of the input (even if the satisfaction measure does not appear in the profile, to save up computation).

Parameters:

sat (SatisfactionMeasure) – The satisfaction measure.

Returns:

1

Return type:

int

pop(index=-1, /)#

Remove and return item at index (default last).

Raises IndexError if list is empty or index is out of range.

remove(value, /)#

Remove first occurrence of value.

Raises ValueError if the value is not present.

remove_satisfied(sat_bound: dict[str, int | float | mpq], projects: Collection[Project]) → SatisfactionProfile[source]#

Returns a new satisfaction profile excluding the satisfaction measurs corresponding to satisfied voters, i.e., who have met or exceeded their satisfaction bound for a given collection of projects.

Parameters:

  • sat_bound (dict[str, Numeric]) – A dictionary of ballot names to numbers, specifying for each ballot the satisfaction bound above which the voter is considered satisfied. Note that the keys are ballot names, and that nothing ensures ballot names to be unique, so be careful here.

  • projects (Iterable[Project]) – The collection of projects.

Returns:

The new satisfaction profile.

Return type:

GroupSatisfactionMeasure

reverse(*args)#

Reverse IN PLACE.

sort(*, key=None, reverse=False)#

Sort the list in ascending order and return None.

The sort is in-place (i.e. the list itself is modified) and stable (i.e. the order of two equal elements is maintained).

If a key function is given, apply it once to each list item and sort them, ascending or descending, according to their function values.

The reverse flag can be set to sort in descending order.

total_satisfaction(projects: Collection[Project]) → int | float | mpq#

Sums up the satisfaction of all the satisfaction measures for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The total satisfaction for the collection of projects.

Return type:

Numeric

total_satisfaction_project(project: Project) → int | float | mpq#

Sums up the satisfaction of all the satisfaction measures for the given project.

Parameters:

project (Project) – The project.

Returns:

The total satisfaction for the collection of projects.

Return type:

Numeric

class FunctionalSatisfaction(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot, func: Callable[[Instance, AbstractProfile, AbstractBallot, Collection[Project]], Numeric])[source]#

Bases: SatisfactionMeasure

Class representing satisfaction measures that are simply defined via functions of the ballot and a subset of projects.

Parameters:
instance#

The instance.

Type:

Instance

profile#

The profile.

Type:

AbstractProfile

ballot#

The ballot.

Type:

AbstractBallot

func#

The actual satisfaction function, i.e., a function returning the satisfaction for a given collection of projects, given the instance, the profile and the ballot under consideration.

Type:

Callable[[Instance, AbstractProfile, AbstractBallot, Iterable[Project], Numeric]

sat(projects: Collection[Project]) → int | float | mpq[source]#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq[source]#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class CC_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Bases: FunctionalSatisfaction

Chamberlin-Courant satisfaction. It can only be applied to approval or cardinal ballots.

In the case of approval ballots, it is equal to 1 if at least one selected project is approved, and 0 otherwise.

In the case of cardinal ballots, it is equal to the maximum score assigned to a selected project in the ballot, and 0 if no selected project has been assigned a score.

Parameters:
sat(projects: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Cost_Sqrt_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Bases: FunctionalSatisfaction

Cost square root satisfaction. It can only be applied to approval ballots. It is equal to the square root of the total cost of the approved and selected projects.

Parameters:
sat(projects: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Cost_Log_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Bases: FunctionalSatisfaction

Cost log satisfaction. It can only be applied to approval ballots. It is equal to the log of 1 plus the total cost of the approved and selected projects.

Parameters:
sat(projects: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class AdditiveSatisfaction(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot, func: Callable[[Instance, AbstractProfile, AbstractBallot, Project, dict], Numeric])[source]#

Bases: SatisfactionMeasure

Class representing additive satisfaction measures, that is, satisfaction functions for which the total satisfaction is exactly the sum of the satisfaction of the individual projects. To speed up computations, scores are only computed once and for all.

Parameters:
instance#

The instance.

Type:

Instance

profile#

The profile.

Type:

AbstractProfile

ballot#

The ballot.

Type:

AbstractBallot

func#

A function taking as input an instance, a profile, a ballot, a project and dictionary of precomputed values and returning the score of the project as a fraction.

Type:

Callable[[Instance, AbstractProfile, AbstractBallot, Project, dict[str, str]], Numeric]

precomputed_values#

A dictionary of precomputed values. Initialised via the preprocessing method.

Type:

dict[str, str]

get_project_sat(project: Project) → int | float | mpq[source]#

Given a project, computes the corresponding satisfaction. Stores the score after computation to avoid re-computing it.

Parameters:

project (Project) – The instance.

Returns:

The satisfaction of the project.

Return type:

Numeric

preprocessing(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot) → dict[source]#

Preprocessing based on the instance, the profile and the ballot that returns a dictionary of precomputed values. The precomputed_values dictionary is initialised via this method.

Parameters:
Returns:

The precomputed values.

Return type:

dict[str, str]

sat(proj: Collection[Project]) → int | float | mpq[source]#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq[source]#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Cardinality_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Bases: AdditiveSatisfaction

The cardinality satisfaction for ballots. It is equal to the number of selected projects appearing in the ballot. It applies to all ballot types that support the in operator.

Parameters:
get_project_sat(project: Project) → int | float | mpq#

Given a project, computes the corresponding satisfaction. Stores the score after computation to avoid re-computing it.

Parameters:

project (Project) – The instance.

Returns:

The satisfaction of the project.

Return type:

Numeric

preprocessing(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot) → dict#

Preprocessing based on the instance, the profile and the ballot that returns a dictionary of precomputed values. The precomputed_values dictionary is initialised via this method.

Parameters:
Returns:

The precomputed values.

Return type:

dict[str, str]

sat(proj: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Relative_Cardinality_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Bases: AdditiveSatisfaction

The cardinality satisfaction for ballots. If the project appears in the ballot, it is equal to 1 divided by the largest number of projects from the ballot that can be selected in any budget allocation. If the project does not appear in the ballot, or if the previous denominator is 0, then it is equal to 0. It applies to all ballot types that support the in operator.

Parameters:
get_project_sat(project: Project) → int | float | mpq#

Given a project, computes the corresponding satisfaction. Stores the score after computation to avoid re-computing it.

Parameters:

project (Project) – The instance.

Returns:

The satisfaction of the project.

Return type:

Numeric

preprocessing(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Preprocessing based on the instance, the profile and the ballot that returns a dictionary of precomputed values. The precomputed_values dictionary is initialised via this method.

Parameters:
Returns:

The precomputed values.

Return type:

dict[str, str]

sat(proj: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Cost_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Bases: AdditiveSatisfaction

The cost satisfaction for ballots. It is equal to the total cost of the selected projects appearing in the ballot. It applies to all ballot types that support the in operator.

Parameters:
get_project_sat(project: Project) → int | float | mpq#

Given a project, computes the corresponding satisfaction. Stores the score after computation to avoid re-computing it.

Parameters:

project (Project) – The instance.

Returns:

The satisfaction of the project.

Return type:

Numeric

preprocessing(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot) → dict#

Preprocessing based on the instance, the profile and the ballot that returns a dictionary of precomputed values. The precomputed_values dictionary is initialised via this method.

Parameters:
Returns:

The precomputed values.

Return type:

dict[str, str]

sat(proj: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Relative_Cost_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Bases: AdditiveSatisfaction

The relative cost satisfaction for ballots. It is equal to the total cost of the selected projects appearing in the ballot, divided by the total cost of the most expensive subset of projects appearing in the ballot. It applies to all ballot types that support the in operator.

Parameters:
get_project_sat(project: Project) → int | float | mpq#

Given a project, computes the corresponding satisfaction. Stores the score after computation to avoid re-computing it.

Parameters:

project (Project) – The instance.

Returns:

The satisfaction of the project.

Return type:

Numeric

preprocessing(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Preprocessing based on the instance, the profile and the ballot that returns a dictionary of precomputed values. The precomputed_values dictionary is initialised via this method.

Parameters:
Returns:

The precomputed values.

Return type:

dict[str, str]

sat(proj: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Relative_Cost_Approx_Normaliser_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Bases: AdditiveSatisfaction

The cost relative satisfaction for ballots, used with an approximate normaliser (since the exact version can take long to compute). It is equal to the total cost of the selected projects appearing in the ballot, divided by the total cost of the projects appearing in the ballot. It applies to all ballot types that support the in operator.

Parameters:
get_project_sat(project: Project) → int | float | mpq#

Given a project, computes the corresponding satisfaction. Stores the score after computation to avoid re-computing it.

Parameters:

project (Project) – The instance.

Returns:

The satisfaction of the project.

Return type:

Numeric

preprocessing(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Preprocessing based on the instance, the profile and the ballot that returns a dictionary of precomputed values. The precomputed_values dictionary is initialised via this method.

Parameters:
Returns:

The precomputed values.

Return type:

dict[str, str]

sat(proj: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Additive_Cost_Sqrt_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Bases: AdditiveSatisfaction

Additive cost square root satisfaction. It is equal to the sum over the approved and selected projects of the square root of their costs. It can be applied to all ballot format supporting the in operator.

Parameters:
get_project_sat(project: Project) → int | float | mpq#

Given a project, computes the corresponding satisfaction. Stores the score after computation to avoid re-computing it.

Parameters:

project (Project) – The instance.

Returns:

The satisfaction of the project.

Return type:

Numeric

preprocessing(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot) → dict#

Preprocessing based on the instance, the profile and the ballot that returns a dictionary of precomputed values. The precomputed_values dictionary is initialised via this method.

Parameters:
Returns:

The precomputed values.

Return type:

dict[str, str]

sat(proj: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Additive_Cost_Log_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Bases: AdditiveSatisfaction

Additive cost log satisfaction. It is equal to the sum over the approved and selected projects of the log of 1 plus the cost of the projects. It can be applied to all ballot format supporting the in operator.

Parameters:
get_project_sat(project: Project) → int | float | mpq#

Given a project, computes the corresponding satisfaction. Stores the score after computation to avoid re-computing it.

Parameters:

project (Project) – The instance.

Returns:

The satisfaction of the project.

Return type:

Numeric

preprocessing(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot) → dict#

Preprocessing based on the instance, the profile and the ballot that returns a dictionary of precomputed values. The precomputed_values dictionary is initialised via this method.

Parameters:
Returns:

The precomputed values.

Return type:

dict[str, str]

sat(proj: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Effort_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot)[source]#

Bases: AdditiveSatisfaction

The effort satisfaction. It is equal to the sum over the selected projects appearing in the ballot of the cost of the project divided by the number of voters who included the project in their ballot. It applies to all ballot types that support the in operator.

Parameters:
get_project_sat(project: Project) → int | float | mpq#

Given a project, computes the corresponding satisfaction. Stores the score after computation to avoid re-computing it.

Parameters:

project (Project) – The instance.

Returns:

The satisfaction of the project.

Return type:

Numeric

preprocessing(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot) → dict#

Preprocessing based on the instance, the profile and the ballot that returns a dictionary of precomputed values. The precomputed_values dictionary is initialised via this method.

Parameters:
Returns:

The precomputed values.

Return type:

dict[str, str]

sat(proj: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Additive_Cardinal_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractCardinalBallot)[source]#

Bases: AdditiveSatisfaction

The additive satisfaction for cardinal ballots. It is equal to the sum over the selected projects appearing in the ballot of the score assigned to the project by the voter. It only applies to cardinal ballots.

Parameters:
get_project_sat(project: Project) → int | float | mpq#

Given a project, computes the corresponding satisfaction. Stores the score after computation to avoid re-computing it.

Parameters:

project (Project) – The instance.

Returns:

The satisfaction of the project.

Return type:

Numeric

preprocessing(instance: Instance, profile: AbstractProfile, ballot: AbstractBallot) → dict#

Preprocessing based on the instance, the profile and the ballot that returns a dictionary of precomputed values. The precomputed_values dictionary is initialised via this method.

Parameters:
Returns:

The precomputed values.

Return type:

dict[str, str]

sat(proj: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Additive_Cardinal_Relative_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractCardinalBallot)[source]#

Bases: AdditiveSatisfaction

The relative additive satisfaction for cardinal ballots. It is equal to the sum over the selected projects appearing in the ballot of the score assigned to the project by the voter, divided by the highest total score achievable by a feasible budget allocation. It only applies to cardinal ballots.

Parameters:
get_project_sat(project: Project) → int | float | mpq#

Given a project, computes the corresponding satisfaction. Stores the score after computation to avoid re-computing it.

Parameters:

project (Project) – The instance.

Returns:

The satisfaction of the project.

Return type:

Numeric

preprocessing(instance: Instance, profile: AbstractProfile, ballot: AbstractCardinalBallot)[source]#

Preprocessing based on the instance, the profile and the ballot that returns a dictionary of precomputed values. The precomputed_values dictionary is initialised via this method.

Parameters:
Returns:

The precomputed values.

Return type:

dict[str, str]

sat(proj: Collection[Project]) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class PositionalSatisfaction(instance: Instance, profile: AbstractProfile, ballot: AbstractOrdinalBallot, positional_func: Callable[[AbstractOrdinalBallot, Project], Numeric], aggregation_func: Callable[[Iterable[Numeric]], Numeric])[source]#

Bases: SatisfactionMeasure

Class representing satisfaction measures that are based on the position of the projects in an ordinal ballot.

Parameters:

  • instance (Instance) – The instance.

  • profile (AbstractProfile) – The profile.

  • ballot (AbstractOrdinalBallot) – The ballot.

  • positional_func (Callable[[AbstractOrdinalBallot, Project], Numeric]) – The positional function mapping ordinal ballots and projects to numbers. That represents the actual satisfaction function.

  • aggregation_func (Callable[[Iterable[Numeric]], Numeric]) – The aggregation function used to aggregate the positional scores for a collection of projects.

instance#

The instance.

Type:

Instance

profile#

The profile.

Type:

AbstractProfile

ballot#

The ballot.

Type:

AbstractOrdinalBallot

positional_func#

The positional function mapping ordinal ballots and projects to numbers. That represents the actual satisfaction function.

Type:

Callable[[AbstractOrdinalBallot, Project], Numeric]

aggregation_func#

The aggregation function used to aggregate the positional scores for a collection of projects.

Type:

Callable[[Iterable[Numeric]], Numeric]

sat(projects: Collection[Project])[source]#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq[source]#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

class Additive_Borda_Sat(instance: Instance, profile: AbstractProfile, ballot: AbstractOrdinalBallot)[source]#

Bases: PositionalSatisfaction

Additive Borda satisfaction. It can only be applied to ordinal ballots. It is equal to the sum of the Borda scores of the selected projects in the ballots. The Borda score is the length of the ballot minus 1 plus the index of the project in the ballot

Parameters:
sat(projects: Collection[Project])#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for the given collection of projects.

Parameters:

projects (Iterable[Project]) – The collection of projects.

Returns:

The corresponding satisfaction

Return type:

Numeric

sat_project(project: Project) → int | float | mpq#

Given the internal attributes of the satisfaction measure (ballot, profile, instance), returns the satisfaction for a single project.

Parameters:

project (Project) – The project.

Returns:

The corresponding satisfaction

Return type:

Numeric

Contents