Population

class svvamp.Population(preferences_ut=None, preferences_rk=None, log_creation=None, labels_candidates=None)[source]

Create a population with preferences.

Parameters:
  • preferences_ut – 2d array of floats. preferences_ut[v, c] is the utility of candidate c as seen by voter v.
  • preferences_rk – 2d array of integers. preferences_rk[v, k] is the candidate at rank k for voter v.
  • log_creation – Any type (string, list...). Some comments.
  • labels_candidates – List of strings. Names of the candidates.

You may enter preferences_ut, preferences_rk or both to define the preferences of the population.

If you provide preferences_rk only, then preferences_ut is set to the corresponding Borda scores (preferences_borda_rk).

If you provide preferences_ut only, then preferences_rk is naturally derived from utilities. If voter v has a greater utility for candidate c than for candidate d, then she ranks c before d. If voter v attributes the same utility to several candidates, then the first time the attribute preferences_rk is called, a random ranking will be decided for these tied candidates (once and for all).

If you provide both, then SVVAMP checks that they are coherent, in the sense that if v ranks c before d, then she her utility for c must be at least equal to her utility for d. If it is not the case, an error is raised.

preferences_rk will be used for sincere voting when a voting system accepts only strict orders.

In contrast, preferences_ut is always used for manipulation purposes, which means that indifference is taken into account as such to determine the interest in manipulation. If voter v attributes the same utility to candidates w and c, and if w is the sincere winner in an election, then v is not interested in a manipulation for c.

If all voters have a strict order of preference (in the sense of ut), then for functions below having variants with suffix _ut or _rk, the two variants are equivalent.

In some voting systems and in some of the attributes below, we use a process referred as candidate tie-breaking or CTB in SVVAMP. It means that lowest-index candidates are favored. When using CTB, if candidates c and d are tied (for example, in an election using Plurality), then c is favored over d iff c < d.

Implications between majority favorite and Condorcet criteria (cf. corresponding attributes below).

majority_favorite_ut          ==>         majority_favorite_ut_ctb
||              ||                                ||            ||
V               ||                                ||            ||
Resistant Cond. V                                 V             ||
||       majority_favorite_rk ==> majority_favorite_rk_ctb      ||
||                     ||                ||                     ||
V                      ||                ||                     V
Condorcet_ut_abs              ==>             Condorcet_ut_abs_ctb
||      ||             ||                ||            ||       ||
||      V              V                 V             V        ||
V         Condorcet_rk        ==>        Condorcet_rk_ctb       V
Condorcet_ut_rel              ==>             Condorcet_ut_rel_ctb
||
V
Weak Condorcet
||
V
Condorcet-admissible

If all voters have strict orders of preference (in the sense of ut) and if there is an odd number of voters, then:

  • majority_favorite_ut, majority_favorite_rk, majority_favorite_ut_ctb and majority_favorite_rk_ctb are equivalent,
  • Condorcet_ut_abs, Condorcet_ut_abs_ctb, Condorcet_rk, Condorcet_rk_ctb, Condorcet_ut_rel, Condorcet_ut_rel_ctb, Weak Condorcet and Condorcet-admissible are equivalent.
C

Integer (number of candidates).

V

Integer (number of voters).

borda_score_c_rk

1d array of integers. borda_score_c_rk[c] is the total Borda score of candidate c (using preferences_borda_rk, i.e. strict preferences).

borda_score_c_ut

1d array of integers. borda_score_c_ut[c] is the total Borda score of candidate c (using preferences_borda_ut, i.e. weak preferences).

candidates_by_decreasing_borda_score_rk

1d array of integers. candidates_by_decreasing_borda_score_rk[k] is the candidate ranked kth by decreasing Borda score (using borda_score_c_rk, i.e. strict preferences).

For example, candidates_by_decreasing_borda_score_rk[0] is the candidate with highest Borda score (rk).

candidates_by_decreasing_borda_score_ut

1d array of integers. candidates_by_decreasing_borda_score_ut[k] is the candidate ranked kth by decreasing Borda score (using borda_score_c_ut, i.e. weak preferences).

For example, candidates_by_decreasing_borda_score_ut[0] is the candidate with highest Borda score (ut).

condorcet_admissible_candidates

1d array of booleans. condorcet_admissible_candidates[c] is True iff candidate c is Condorcet-admissible, i.e. iff no candidate d has an absolute victory against c (in the sense of matrix_victories_ut_abs).

condorcet_winner_rk

Integer or NaN. Candidate who has only victories in matrix_victories_rk. If there is no such candidate, then NaN.

condorcet_winner_rk_ctb

Integer or NaN. Candidate who has only victories in matrix_victories_rk_ctb. If there is no such candidate, then NaN.

condorcet_winner_ut_abs

Integer or NaN. Candidate who has only victories in matrix_victories_ut_abs. If there is no such candidate, then NaN.

condorcet_winner_ut_abs_ctb

Integer or NaN. Candidate who has only victories in matrix_victories_ut_abs_ctb. If there is no such candidate, then NaN.

condorcet_winner_ut_rel

Integer or NaN. Candidate who has only victories in matrix_victories_ut_rel. If there is no such candidate, then NaN.

condorcet_winner_ut_rel_ctb

Integer or NaN. Candidate who has only victories in matrix_victories_ut_rel_ctb. If there is no such candidate, then NaN.

decreasing_borda_scores_rk

1d array of integers. decreasing_borda_scores_rk[k] is the kth Borda score (using borda_score_c_rk, i.e. strict preferences) by decreasing order.

For example, decreasing_borda_scores_rk[0] is the highest Borda score for a candidate (rk).

decreasing_borda_scores_ut

1d array of integers. decreasing_borda_scores_ut[k] is the kth Borda score (using borda_score_c_ut, i.e. weak preferences) by decreasing order.

For example, decreasing_borda_scores_ut[0] is the highest Borda score for a candidate (rk).

demo(log_depth=1)

Demonstrate the methods of Population class.

Parameters:log_depth – Integer from 0 (basic info) to 3 (verbose).
ensure_voters_sorted_by_rk()

Ensure that voters are sorted.

This function sorts voters first by their strict order of preference (their row in preferences_rk), then by their weak order of preference (their row in preferences_borda_ut). Note that two voters having the same strict order may have different weak orders, and vice versa.

This function will be called automatically when creating an election, because it allows to accelerate some algorithms (typically Individual Manipulation).

This function actually performs the sort only when it is called on a Population object for the first time.

exists_condorcet_admissible

Boolean (True iff there is at least one Condorcet-admissible candidate, condorcet_admissible_candidates).

exists_condorcet_order_rk

Boolean. True iff in matrix matrix_victories_rk, there is a candidate with C-1 victories, a candidate with C-2 victories, etc.

exists_condorcet_order_rk_ctb

Boolean. True iff in matrix matrix_victories_rk_ctb, there is a candidate with C-1 victories, a candidate with C-2 victories, etc.

exists_condorcet_order_ut_abs

Boolean. True iff in matrix matrix_victories_ut_abs, there is a candidate with C-1 victories, a candidate with C-2 victories, etc.

exists_condorcet_order_ut_abs_ctb

Boolean. True iff in matrix matrix_victories_ut_abs_ctb, there is a candidate with C-1 victories, a candidate with C-2 victories, etc.

exists_condorcet_order_ut_rel

Boolean. True iff in matrix matrix_victories_ut_rel, there is a candidate with C-1 victories, a candidate with C-2 victories, etc.

exists_condorcet_order_ut_rel_ctb

Boolean. True iff in matrix matrix_victories_ut_rel_ctb, there is a candidate with C-1 victories, a candidate with C-2 victories, etc.

exists_condorcet_winner_rk

Boolean (True iff there is a condorcet_winner_rk).

exists_condorcet_winner_rk_ctb

Boolean (True iff there is a condorcet_winner_rk_ctb).

exists_condorcet_winner_ut_abs

Boolean (True iff there is a condorcet_winner_ut_abs).

exists_condorcet_winner_ut_abs_ctb

Boolean (True iff there is a condorcet_winner_ut_abs_ctb).

exists_condorcet_winner_ut_rel

Boolean (True iff there is a condorcet_winner_ut_rel).

exists_condorcet_winner_ut_rel_ctb

Boolean (True iff there is a condorcet_winner_ut_rel_ctb).

exists_majority_favorite_rk

Boolean (True iff there is a majority_favorite_rk).

exists_majority_favorite_rk_ctb

Boolean (True iff there is a majority_favorite_rk_ctb).

exists_majority_favorite_ut

Boolean (True iff there is a majority_favorite_ut).

exists_majority_favorite_ut_ctb

Boolean (True iff there is a majority_favorite_ut_ctb).

exists_resistant_condorcet_winner

Boolean (True iff there is a resistant_condorcet_winner).

exists_weak_condorcet_winner

Boolean (True iff there is at least one weak Condorcet winner, weak_condorcet_winners).

labels_candidates

List of C strings (names of the candidates).

majority_favorite_rk

Integer or NaN. Candidate who has stricly more than V/2 in plurality_scores_rk. If there is no such candidate, then NaN.

majority_favorite_rk_ctb

Integer or NaN. Candidate who has stricly more than V/2 in plurality_scores_rk. Can also be candidate 0 with exactly V/2. If there is no such candidate, then NaN.

majority_favorite_ut

Integer or NaN. Candidate who has stricly more than V/2 in plurality_scores_ut. If there is no such candidate, then NaN.

majority_favorite_ut_ctb

Integer or NaN. Candidate who has stricly more than V/2 in plurality_scores_ut. Can also be candidate 0 with exactly V/2. If there is no such candidate, then NaN.

matrix_duels_rk

2d array of integers. matrix_duels_rk[c, d] is the number of voters who rank candidate c before d (in the sense of preferences_rk). By convention, diagonal coefficients are set to 0.

matrix_duels_ut

2d array of integers. matrix_duels_ut[c, d] is the number of voters who have a strictly greater utility for c than for d. By convention, diagonal coefficients are set to 0.

matrix_victories_rk

2d array of values in {0, 0.5, 1}. Matrix of victories based on matrix_duels_rk.

matrix_victories_rk[c, d] is:

  • 1 iff matrix_duels_rk[c, d] > matrix_duels_rk[d, c], i.e. iff matrix_duels_rk[c, d] > V / 2.
  • 0.5 iff matrix_duels_rk[c, d] = matrix_duels_rk[d, c], i.e. iff matrix_duels_rk[c, d] = V / 2.
  • 0 iff matrix_duels_rk[c, d] < matrix_duels_rk[d, c], i.e. iff matrix_duels_rk[c, d] < V / 2.

By convention, diagonal coefficients are set to 0.

matrix_victories_rk_ctb

2d array of values in {0, 1}. Matrix of victories based on matrix_duels_rk, with tie-breaks on candidates.

matrix_victories_rk_ctb[c, d] is:

  • 1 iff matrix_duels_rk[c, d] > matrix_duels_rk[d, c], or matrix_duels_rk[c, d] = matrix_duels_rk[d, c] and c < d.
  • 0 iff matrix_duels_rk[c, d] < matrix_duels_rk[d, c], or matrix_duels_rk[c, d] = matrix_duels_rk[d, c] and d < c.

By convention, diagonal coefficients are set to 0.

matrix_victories_ut_abs

2d array of values in {0, 0.5, 1}. Matrix of absolute victories based on matrix_duels_ut.

matrix_victories_ut_abs[c, d] is:

  • 1 iff matrix_duels_ut[c, d] > V / 2.
  • 0.5 iff matrix_duels_ut[c, d] = V / 2.
  • 0 iff matrix_duels_ut[c, d] < V / 2.

By convention, diagonal coefficients are set to 0.

matrix_victories_ut_abs_ctb

2d array of values in {0, 1}. Matrix of absolute victories based on matrix_duels_ut, with tie-breaks on candidates.

matrix_victories_ut_abs_ctb[c, d] is:

  • 1 iff matrix_duels_ut[c, d] > V / 2, or matrix_duels_ut[c, d] = V / 2 and c < d.
  • 0 iff matrix_duels_ut[c, d] < V / 2, or matrix_duels_ut[c, d] = V / 2 and d < c.

By convention, diagonal coefficients are set to 0.

matrix_victories_ut_rel

2d array of values in {0, 0.5, 1}. Matrix of relative victories based on matrix_duels_ut.

matrix_victories_ut_rel[c, d] is:

  • 1 iff matrix_duels_ut[c, d] > matrix_duels_ut[d, c].
  • 0.5 iff matrix_duels_ut[c, d] = matrix_duels_ut[d, c].
  • 0 iff matrix_duels_ut[c, d] < matrix_duels_ut[d, c].

By convention, diagonal coefficients are set to 0.

matrix_victories_ut_rel_ctb

2d array of values in {0, 1}. Matrix of relative victories based on matrix_duels_ut, with tie-breaks on candidates.

matrix_victories_ut_rel_ctb[c, d] is:

  • 1 iff matrix_duels_ut[c, d] > matrix_duels_ut[d, c], or matrix_duels_ut[c, d] = matrix_duels_ut[d, c] and c < d.
  • 0 iff matrix_duels_ut[c, d] < matrix_duels_ut[d, c], or matrix_duels_ut[c, d] = matrix_duels_ut[d, c] and d < c.

By convention, diagonal coefficients are set to 0.

mean_utility_c

1d array of floats. mean_utility_c[c] is the mean utility for candidate c (i.e. the mean of c‘s column in matrix preferences_ut).

mean_utility_max

Float. mean_utility_max is the maximum of mean_utility_c.

mean_utility_mean

Float. mean_utility_mean is the mean of mean_utility_c.

mean_utility_min

Float. mean_utility_min is the minimum of mean_utility_c.

mean_utility_std

Float. mean_utility_std is the standard deviation of mean_utility_c.

nb_condorcet_admissible

Integer (number of Condorcet-admissible candidates, condorcet_admissible_candidates).

nb_weak_condorcet_winners

Integer (number of weak Condorcet winners, weak_condorcet_winners).

not_exists_condorcet_admissible

Boolean (True iff there is no Condorcet-admissible candidate, condorcet_admissible_candidates).

not_exists_condorcet_order_rk

Boolean. Cf. exists_condorcet_order_rk.

not_exists_condorcet_order_rk_ctb

Boolean. Cf. exists_condorcet_order_rk_ctb.

not_exists_condorcet_order_ut_abs

Boolean. Cf. exists_condorcet_order_ut_abs.

not_exists_condorcet_order_ut_abs_ctb

Boolean. Cf. exists_condorcet_order_ut_abs_ctb.

not_exists_condorcet_order_ut_rel

Boolean. Cf. exists_condorcet_order_ut_rel.

not_exists_condorcet_order_ut_rel_ctb

Boolean. Cf. exists_condorcet_order_ut_rel_ctb.

not_exists_condorcet_winner_rk

Boolean (True iff there is no condorcet_winner_rk).

not_exists_condorcet_winner_rk_ctb

Boolean (True iff there is no condorcet_winner_rk_ctb).

not_exists_condorcet_winner_ut_abs

Boolean (True iff there is no condorcet_winner_ut_abs).

not_exists_condorcet_winner_ut_abs_ctb

Boolean (True iff there is no condorcet_winner_ut_abs_ctb).

not_exists_condorcet_winner_ut_rel

Boolean (True iff there is no condorcet_winner_ut_rel).

not_exists_condorcet_winner_ut_rel_ctb

Boolean (True iff there is no condorcet_winner_ut_rel_ctb).

not_exists_majority_favorite_rk

Boolean (True iff there is no majority_favorite_rk).

not_exists_majority_favorite_rk_ctb

Boolean (True iff there is no majority_favorite_rk_ctb).

not_exists_majority_favorite_ut

Boolean (True iff there is no majority_favorite_ut).

not_exists_majority_favorite_ut_ctb

Boolean (True iff there is no majority_favorite_ut_ctb).

not_exists_resistant_condorcet_winner

Boolean (True iff there is no resistant_condorcet_winner).

not_exists_weak_condorcet_winner

Boolean (True iff there is no weak Condorcet winner, weak_condorcet_winners).

plot3(indexes=None, normalize=True, use_labels=True)

Plot utilities for 3 candidates (with approval limit).

Parameters:
  • indexes – List of 3 candidates. If None, defaults to [0, 1, 2].
  • normalize – Boolean. Cf. below.
  • use_labels – Boolean. If True, then labels_candidates is used to label the plot. Otherwise, candidates are simply represented by their index.

Each red point of the plot represents a voter v. Its position is preferences_ut[v, indexes]. If normalize is True, then each position is normalized before plotting so that its Euclidean norm is equal to 1.

The equator (in blue) is the set of points \(\mathbf{u}\) such that \(\sum {u_i}^2 = 1\) and \(\sum u_i = 0\), i.e. the unit circle of the plan that is orthogonal to the main diagonal [1, 1, 1].

Other blue circles are the frontiers between the 6 different strict total orders on the candidates.

Cf. working paper by Durand et al., ‘Geometry on the Utility Space’.

plot4(indexes=None, normalize=True, use_labels=True)

Plot utilities for 4 candidates (without approval limit).

Parameters:
  • indexes – List of 4 candidates. If None, defaults to [0, 1, 2, 3].
  • normalize – Boolean. Cf. below.
  • use_labels – Boolean. If True, then labels_candidates is used to label the plot. Otherwise, candidates are simply represented by their index.

Each red point of the plot represents a voter v.

  • preferences_ut[v, indexes] is sent to the hyperplane that is orthogonal to [1, 1, 1, 1] (by orthogonal projection), which discards information related to approval limit and keeps only the relative preferences between candidates.
  • The plot is done in this 3d hyperplane. In practice, we use a mirror symmetry that exchanges [1, 1, 1, 1] and [0, 0, 0, 1]. This way, the image vector is orthogonal to [0, 0, 0, 1] and can be plotted in the first 3 dimensions.
  • If normalize is True, then the image vector is normalized before plotting so that its Euclidean norm is equal to 1.

Blue lines are the frontiers between the 24 different strict total orders on the candidates (‘permutohedron’).

Cf. working paper by Durand et al., ‘Geometry on the Utility Space’.

plurality_scores_rk

1d array of booleans. plurality_scores_rk[c] is the number of voters for whom c is the top-ranked candidate (with voter tie-breaking).

plurality_scores_ut

1d array of booleans. plurality_scores_ut[c] is the number of voters who strictly prefer c to all other candidates.

If a voter has several candidates with maximal utility, then none of them receives any point.

preferences_borda_rk

2d array of integers. preferences_borda_rk[v, c] gains 1 point for each candidate d such that voter v ranks c before d.

So, these Borda scores are between 0 and C - 1.

preferences_borda_ut

2d array of integers. preferences_borda_ut[v, c] gains 1 point for each d such that v strictly prefers c to d (in the sense of utilities), and 0.5 point for each d such that v is indifferent between c and d.

So, these Borda scores are between 0 and C - 1.

preferences_rk

2d array of integers. preferences_rk[v, k] is the candidate at rank k for voter v.

For example, preferences_rk[v, 0] is v‘s preferred candidate.

preferences_ut

2d array of floats. preferences_ut[v, c] is the utility of candidate c as seen by voter v.

resistant_condorcet_winner

Integer or NaN. Resistant Condorcet Winner. If there is no such candidate, then NaN.

A Condorcet winner w (in the sense of condorcet_winner_ut_abs) is resistant iff in any Condorcet voting system (in the same sense), the profile is not manipulable (cf. Durand et al., working paper 2014). This is equivalent to say that for any pair (c, d) of other distinct candidates, there is a strict majority of voters who simultaneously:

  1. Do not prefer c to w,
  2. And prefer w to d.
threshold_c_prevents_w_Condorcet_ut_abs

2d array of integers. Threshold for c-manipulators to prevent w from being a Condorcet winner (in the sense of condorcet_winner_ut_abs).

Intuitively, the question is the following: in an election where w is the winner, how many c-manipulators are needed to prevent w from being a Condorcet winner?

We start with the sub-population of \(n_s\) ‘sincere’ voters, i.e. not preferring c to w. The precise question is: how many c-manipulators \(n_m\) must we add in order to create a non-victory for w against some candidate d \(\neq\) w (possibly c herself)?

In the following, \(| c > d |\) denotes the number of voters who strictly prefer candidate c to d. We need:

\[\begin{split}| \text{sincere voters for whom } w > d | \leq \frac{n_s + n_m}{2}.\end{split}\]

I.e.:

\[\begin{split}| \text{non } c > w \text{ and } w > d | \leq \frac{| \text{non } c > w | + n_m}{2}.\end{split}\]

I.e.:

\[\begin{split}n_m \geq 2 \cdot | \text{non } c > w \text{ and } w > d | - | \text{non } c > w |.\end{split}\]

One candidate d is enough, so:

threshold_c_prevents_w_Condorcet_ut_abs[c, w] \(= 2 \cdot \min_{d \neq w} |w \geq c \text{ and } w > d| - |w \geq c|\).

If this result is negative, it means that even without c-manipulators, w is not a Condorcet winner. In that case, threshold is set to 0 instead.

total_utility_c

1d array of floats. total_utility_c[c] is the total utility for candidate c (i.e. the sum of c‘s column in matrix preferences_ut).

total_utility_max

Float. total_utility_max is the maximum of total_utility_c.

total_utility_mean

Float. total_utility_mean is the mean of total_utility_c.

total_utility_min

Float. total_utility_min is the minimum of total_utility_c.

total_utility_std

Float. total_utility_std is the standard deviation of total_utility_c.

v_has_same_ordinal_preferences_as_previous_voter

1d array of booleans. v_has_same_ordinal_preferences_as_previous_voter[v] is True iff voter v has the same preference strict order (row in preferences_rk) and the same preference weak order (row in preferences_borda_ut) as voter v-1.

By convention, it is False for voter 0.

weak_condorcet_winners

1d array of booleans. weak_condorcet_winners[c] is True iff candidate c is a weak Condorcet winner, i.e. iff no candidate d has a relative victory against c (in the sense of matrix_victories_ut_rel).