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 candidatec
as seen by voterv
. - preferences_rk – 2d array of integers.
preferences_rk[v, k]
is the candidate at rankk
for voterv
. - 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, thenpreferences_ut
is set to the corresponding Borda scores (preferences_borda_rk
).If you provide
preferences_ut
only, thenpreferences_rk
is naturally derived from utilities. If voterv
has a greater utility for candidatec
than for candidated
, then she ranksc
befored
. If voterv
attributes the same utility to several candidates, then the first time the attributepreferences_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
ranksc
befored
, then she her utility forc
must be at least equal to her utility ford
. 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 voterv
attributes the same utility to candidatesw
andc
, and ifw
is the sincere winner in an election, thenv
is not interested in a manipulation forc
.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
andd
are tied (for example, in an election using Plurality), thenc
is favored overd
iffc < 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
andmajority_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
andCondorcet-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 candidatec
(usingpreferences_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 candidatec
(usingpreferences_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 rankedk
th by decreasing Borda score (usingborda_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 rankedk
th by decreasing Borda score (usingborda_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]
isTrue
iff candidatec
is Condorcet-admissible, i.e. iff no candidated
has an absolute victory againstc
(in the sense ofmatrix_victories_ut_abs
).
-
condorcet_winner_rk
¶ Integer or
NaN
. Candidate who has only victories inmatrix_victories_rk
. If there is no such candidate, thenNaN
.
-
condorcet_winner_rk_ctb
¶ Integer or
NaN
. Candidate who has only victories inmatrix_victories_rk_ctb
. If there is no such candidate, thenNaN
.
-
condorcet_winner_ut_abs
¶ Integer or
NaN
. Candidate who has only victories inmatrix_victories_ut_abs
. If there is no such candidate, thenNaN
.
-
condorcet_winner_ut_abs_ctb
¶ Integer or
NaN
. Candidate who has only victories inmatrix_victories_ut_abs_ctb
. If there is no such candidate, thenNaN
.
-
condorcet_winner_ut_rel
¶ Integer or
NaN
. Candidate who has only victories inmatrix_victories_ut_rel
. If there is no such candidate, thenNaN
.
-
condorcet_winner_ut_rel_ctb
¶ Integer or
NaN
. Candidate who has only victories inmatrix_victories_ut_rel_ctb
. If there is no such candidate, thenNaN
.
-
decreasing_borda_scores_rk
¶ 1d array of integers.
decreasing_borda_scores_rk[k]
is thek
th Borda score (usingborda_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 thek
th Borda score (usingborda_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 inpreferences_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.See also
-
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.See also
-
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.See also
-
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.See also
-
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.See also
-
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.See also
-
exists_condorcet_winner_rk
¶ Boolean (
True
iff there is acondorcet_winner_rk
).
-
exists_condorcet_winner_rk_ctb
¶ Boolean (
True
iff there is acondorcet_winner_rk_ctb
).
-
exists_condorcet_winner_ut_abs
¶ Boolean (
True
iff there is acondorcet_winner_ut_abs
).
-
exists_condorcet_winner_ut_abs_ctb
¶ Boolean (
True
iff there is acondorcet_winner_ut_abs_ctb
).
-
exists_condorcet_winner_ut_rel
¶ Boolean (
True
iff there is acondorcet_winner_ut_rel
).
-
exists_condorcet_winner_ut_rel_ctb
¶ Boolean (
True
iff there is acondorcet_winner_ut_rel_ctb
).
-
exists_majority_favorite_rk
¶ Boolean (
True
iff there is amajority_favorite_rk
).
-
exists_majority_favorite_rk_ctb
¶ Boolean (
True
iff there is amajority_favorite_rk_ctb
).
-
exists_majority_favorite_ut
¶ Boolean (
True
iff there is amajority_favorite_ut
).
-
exists_majority_favorite_ut_ctb
¶ Boolean (
True
iff there is amajority_favorite_ut_ctb
).
-
exists_resistant_condorcet_winner
¶ Boolean (
True
iff there is aresistant_condorcet_winner
).
-
exists_weak_condorcet_winner
¶ Boolean (
True
iff there is at least one weak Condorcet winner,weak_condorcet_winners
).
-
majority_favorite_rk
¶ Integer or
NaN
. Candidate who has stricly more than V/2 inplurality_scores_rk
. If there is no such candidate, thenNaN
.
-
majority_favorite_rk_ctb
¶ Integer or
NaN
. Candidate who has stricly more than V/2 inplurality_scores_rk
. Can also be candidate 0 with exactly V/2. If there is no such candidate, thenNaN
.
-
majority_favorite_ut
¶ Integer or
NaN
. Candidate who has stricly more than V/2 inplurality_scores_ut
. If there is no such candidate, thenNaN
.
-
majority_favorite_ut_ctb
¶ Integer or
NaN
. Candidate who has stricly more than V/2 inplurality_scores_ut
. Can also be candidate 0 with exactly V/2. If there is no such candidate, thenNaN
.
-
matrix_duels_rk
¶ 2d array of integers.
matrix_duels_rk[c, d]
is the number of voters who rank candidatec
befored
(in the sense ofpreferences_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 forc
than ford
. By convention, diagonal coefficients are set to0
.
-
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. iffmatrix_duels_rk[c, d] > V / 2
. - 0.5 iff
matrix_duels_rk[c, d] = matrix_duels_rk[d, c]
, i.e. iffmatrix_duels_rk[c, d] = V / 2
. - 0 iff
matrix_duels_rk[c, d] < matrix_duels_rk[d, c]
, i.e. iffmatrix_duels_rk[c, d] < V / 2
.
By convention, diagonal coefficients are set to 0.
- 1 iff
-
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]
, ormatrix_duels_rk[c, d] = matrix_duels_rk[d, c]
andc < d
. - 0 iff
matrix_duels_rk[c, d] < matrix_duels_rk[d, c]
, ormatrix_duels_rk[c, d] = matrix_duels_rk[d, c]
andd < c
.
By convention, diagonal coefficients are set to 0.
- 1 iff
-
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.
- 1 iff
-
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
, ormatrix_duels_ut[c, d] = V / 2
andc < d
. - 0 iff
matrix_duels_ut[c, d] < V / 2
, ormatrix_duels_ut[c, d] = V / 2
andd < c
.
By convention, diagonal coefficients are set to 0.
- 1 iff
-
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.
- 1 iff
-
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]
, ormatrix_duels_ut[c, d] = matrix_duels_ut[d, c]
andc < d
. - 0 iff
matrix_duels_ut[c, d] < matrix_duels_ut[d, c]
, ormatrix_duels_ut[c, d] = matrix_duels_ut[d, c]
andd < c
.
By convention, diagonal coefficients are set to 0.
- 1 iff
-
mean_utility_c
¶ 1d array of floats.
mean_utility_c[c]
is the mean utility for candidatec
(i.e. the mean ofc
‘s column in matrixpreferences_ut
).
-
mean_utility_max
¶ Float.
mean_utility_max
is the maximum ofmean_utility_c
.
-
mean_utility_mean
¶ Float.
mean_utility_mean
is the mean ofmean_utility_c
.
-
mean_utility_min
¶ Float.
mean_utility_min
is the minimum ofmean_utility_c
.
-
mean_utility_std
¶ Float.
mean_utility_std
is the standard deviation ofmean_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 nocondorcet_winner_rk
).
-
not_exists_condorcet_winner_rk_ctb
¶ Boolean (
True
iff there is nocondorcet_winner_rk_ctb
).
-
not_exists_condorcet_winner_ut_abs
¶ Boolean (
True
iff there is nocondorcet_winner_ut_abs
).
-
not_exists_condorcet_winner_ut_abs_ctb
¶ Boolean (
True
iff there is nocondorcet_winner_ut_abs_ctb
).
-
not_exists_condorcet_winner_ut_rel
¶ Boolean (
True
iff there is nocondorcet_winner_ut_rel
).
-
not_exists_condorcet_winner_ut_rel_ctb
¶ Boolean (
True
iff there is nocondorcet_winner_ut_rel_ctb
).
-
not_exists_majority_favorite_rk
¶ Boolean (
True
iff there is nomajority_favorite_rk
).
-
not_exists_majority_favorite_rk_ctb
¶ Boolean (
True
iff there is nomajority_favorite_rk_ctb
).
-
not_exists_majority_favorite_ut
¶ Boolean (
True
iff there is nomajority_favorite_ut
).
-
not_exists_majority_favorite_ut_ctb
¶ Boolean (
True
iff there is nomajority_favorite_ut_ctb
).
-
not_exists_resistant_condorcet_winner
¶ Boolean (
True
iff there is noresistant_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
, thenlabels_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 ispreferences_ut
[v, indexes]
. Ifnormalize
isTrue
, 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
, thenlabels_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 whomc
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 preferc
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 candidated
such that voterv
ranksc
befored
.So, these Borda scores are between
0
andC - 1
.
-
preferences_borda_ut
¶ 2d array of integers.
preferences_borda_ut[v, c]
gains 1 point for eachd
such thatv
strictly prefersc
tod
(in the sense of utilities), and 0.5 point for eachd
such thatv
is indifferent betweenc
andd
.So, these Borda scores are between
0
andC - 1
.
-
preferences_rk
¶ 2d array of integers.
preferences_rk[v, k]
is the candidate at rankk
for voterv
.For example,
preferences_rk[v, 0]
isv
‘s preferred candidate.
-
preferences_ut
¶ 2d array of floats.
preferences_ut[v, c]
is the utility of candidatec
as seen by voterv
.
-
resistant_condorcet_winner
¶ Integer or
NaN
. Resistant Condorcet Winner. If there is no such candidate, thenNaN
.A Condorcet winner
w
(in the sense ofcondorcet_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:- Do not prefer
c
tow
, - And prefer
w
tod
.
- Do not prefer
-
threshold_c_prevents_w_Condorcet_ut_abs
¶ 2d array of integers. Threshold for
c
-manipulators to preventw
from being a Condorcet winner (in the sense ofcondorcet_winner_ut_abs
).Intuitively, the question is the following: in an election where
w
is the winner, how manyc
-manipulators are needed to preventw
from being a Condorcet winner?We start with the sub-population of \(n_s\) ‘sincere’ voters, i.e. not preferring
c
tow
. The precise question is: how manyc
-manipulators \(n_m\) must we add in order to create a non-victory forw
against some candidated
\(\neq\)w
(possiblyc
herself)?In the following, \(| c > d |\) denotes the number of voters who strictly prefer candidate
c
tod
. 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 candidatec
(i.e. the sum ofc
‘s column in matrixpreferences_ut
).
-
total_utility_max
¶ Float.
total_utility_max
is the maximum oftotal_utility_c
.
-
total_utility_mean
¶ Float.
total_utility_mean
is the mean oftotal_utility_c
.
-
total_utility_min
¶ Float.
total_utility_min
is the minimum oftotal_utility_c
.
-
total_utility_std
¶ Float.
total_utility_std
is the standard deviation oftotal_utility_c
.
-
v_has_same_ordinal_preferences_as_previous_voter
¶ 1d array of booleans.
v_has_same_ordinal_preferences_as_previous_voter[v]
isTrue
iff voterv
has the same preference strict order (row inpreferences_rk
) and the same preference weak order (row inpreferences_borda_ut
) as voterv-1
.By convention, it is
False
for voter0
.
-
weak_condorcet_winners
¶ 1d array of booleans.
weak_condorcet_winners[c]
isTrue
iff candidatec
is a weak Condorcet winner, i.e. iff no candidated
has a relative victory againstc
(in the sense ofmatrix_victories_ut_rel
).
- preferences_ut – 2d array of floats.