Create a population with preferences.

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 k^th 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 k^th 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).

See also

nb_condorcet_admissible, exists_condorcet_admissible, not_exists_condorcet_admissible.

condorcet_winner_rk¶

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

See also

exists_condorcet_winner_rk, not_exists_condorcet_winner_rk.

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.

See also

exists_condorcet_winner_rk_ctb, not_exists_condorcet_winner_rk_ctb.

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.

See also

exists_condorcet_winner_ut_abs, not_exists_condorcet_winner_ut_abs.

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.

See also

exists_condorcet_winner_ut_abs_ctb, not_exists_condorcet_winner_ut_abs_ctb

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.

See also

exists_condorcet_winner_ut_rel, not_exists_condorcet_winner_ut_rel.

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.

See also

exists_condorcet_winner_ut_rel_ctb, not_exists_condorcet_winner_ut_rel_ctb.

decreasing_borda_scores_rk¶

1d array of integers. decreasing_borda_scores_rk[k] is the k^th 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 k^th 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.

See also

not_exists_condorcet_order_rk.

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

not_exists_condorcet_order_rk_ctb.

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

not_exists_condorcet_order_ut_abs.

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

not_exists_condorcet_order_ut_abs_ctb.

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

not_exists_condorcet_order_ut_rel.

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

not_exists_condorcet_order_ut_rel_ctb.

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.

See also

exists_majority_favorite_rk, not_exists_majority_favorite_rk.

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.

See also

exists_majority_favorite_rk_ctb, not_exists_majority_favorite_rk_ctb.

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.

See also

exists_majority_favorite_ut, not_exists_majority_favorite_ut.

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.

See also

exists_majority_favorite_ut_ctb, not_exists_majority_favorite_ut_ctb.

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.

See also

exists_resistant_condorcet_winner, not_exists_resistant_condorcet_winner.

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).

Population with ‘Cubic uniform’ model.

Each coefficient preferences_ut[v, c] is drawn independently and uniformly in the interval [-1, 1].

The ordinal part of this distribution is the Impartial Culture.

Population with ‘Euclidean box’ model.

Let us note n_dim the number of elements in sigma. For each voter and each candidate, a position is independently and uniformly drawn in a rectangular box of dimensions box_dimensions[0],... , box_dimensions[n_dim - 1]. If shift is used, the distribution of positions for candidates is displaced by this vector.

Let d[v, c] denote the Euclidean distance between voter v and candidate c. Then preferences_ut[v, c] = A - d[v, c], where A is such that the average utility is 0 over the whole population.

If ndim = 1, the population is single-peaked.

Population with ‘Gaussian well’ model.

Let us note n_dim the number of elements in sigma. For voter v (resp. each candidate c) and each axis i in range(n_dim), a position x_i[v] (resp. y_i[c]) is independently drawn according to a normal law of mean 0 and variance sigma[i]. If shift is used, the distribution of positions for candidates is displaced by this vector.

Let d[v, c] denote the Euclidean distance between voter v‘s position x[v] and candidate c‘s position y[c]. Then preferences_ut[v, c] = A - d[v, c], where A is such that the average utility is 0 over the whole population.

If ndim = 1, the population is single-peaked.

Population with ‘Ladder’ model.

Each utility preferences_ut[v, c] is drawn independently and equiprobably between n_rungs values that divide the interval [-1, 1] equally. For example, if n_rungs = 21, then values in {-1, -0.9, ..., 1} are used.

The ordinal part of this distribution is not the Impartial Culture. Indeed, weak orders of preference come with non-zero probability. This model is interesting the study the effect of voters’ ties.

Population with ‘Spheroid’ model.

The utility vector of each voter is drawn independently and uniformly on a sphere in \(\mathbb{R}^C\). Then, it is sent on the spheroid that is the image of the sphere by a dilatation of factor stretching in direction [1, ..., 1]. Cf. working paper Durand et al. ‘Geometry on the Utility Sphere’.

The ordinal part of this distribution is the Impartial Culture.

The parameter stretching has only influence on voting systems based on utilities, especially Approval voting.

• stretching = 0: pure Von Neumann-Morgenstern utility, normalized to \(\sum_c u_v(c) = 0\) (spherical model with C-2 dimensions).
• stretching = 1: spherical model with C-1 dimensions.
• stretching = inf: axial/cylindrical model with only two possible values, all-approval [1, ..., 1] and all-reject [-1, ..., -1].

N.B.: This model gives the same probability distribution as a Von Mises-Fisher with concentration = 0.

Population drawn with Von Mises-Fisher distributions on the C-2-sphere

We work on the C-2-sphere: vectors of \(\mathbb{R}^C\) with Euclidean norm equal to 1 and that are orthogonal to [1, ..., 1]. It is a representation of the classical Von Neumann-Morgenstern utility space. Cf. working paper Durand et al. ‘Geometry on the Utility Sphere’.

Before all computations, the poles are projected onto the hyperplane and normalized. So, the only source of concentration for group i is vmf_concentration[i], not the norm of vmf_pole[i]. If pole is None, then each pole is drawn independently and uniformly on the C-2-sphere.

For each voter c, we draw a group i at random, according to vmf_probability (normalized beforehand if necessary). Then, v‘s utility vector is drawn according to a Von Mises-Fisher distribution of pole vmf_pole[i, :] and concentration vmf_concentration[i], using Ulrich’s method modified by Wood.

Once group i is chosen, then up to a normalization constant, the density of probability for a unit vector x is exp(vmf_concentration[i] vmf.pole[i, :].x), where vmf.pole[i, :].x is a dot product.

References:

Ulrich (1984) - Computer Generation of Distributions on the m-Sphere

Wood (1994) - Simulation of the von Mises Fisher distribution

Population drawn with Von Mises-Fisher distributions on the C-1-sphere

For each voter c, we draw a group i at random, according to vmf_probability (normalized beforehand if necessary). Then, v‘s utility vector is drawn according to a Von Mises-Fisher distribution of pole vmf_pole[i, :] and concentration vmf_concentration[i], using Ulrich’s method modified by Wood.

Once group i is chosen, then up to a normalization constant, the density of probability for a unit vector x is exp(vmf_concentration[i] vmf.pole[i, :].x), where vmf.pole[i, :].x is a dot product.

Then, v‘s utility vector is sent onto the spheroid that is the image of the sphere by a dilatation of factor stretching along the direction [1, ..., 1]. For example, if stretching = 1, we stay on the unit sphere of \(\mathbb{R}^C\). Cf. working paper Durand et al. ‘Geometry on the Utility Sphere’.

N.B.: if stretching != 1, it amounts to move the poles. For example, if the pole [1, 0, 0, 0] is given and stretching = 0, then the actual pole will be [0.75, - 0.25, - 0.25, - 0.25] (up to a multiplicative constant).

poles are normalized before being used. So, the only source of concentration for group i is vmf_concentration[i], not the norm of vmf_pole[i]. If vmf_pole is None, then each pole is drawn independently and uniformly on the sphere.

References:

Ulrich (1984) - Computer Generation of Distributions on the m-Sphere

Wood (1994) - Simulation of the von Mises Fisher distribution

Population from a file.

If the file name ends with ‘.t.csv’ (t = transposed format): simple table of utilities with candidates declared in the first column and voters declared in the first row.

If the file name ends with ‘.csv’ (but not ‘.t.csv’), candidates must be declared in the first row and voters in the first column.

Otherwise, the file is considered as a PrefLib file. In that case, since information is ordinal only, preferences_ut[v, c] is set to the Borda score (with no vtb) minus (C - 1) / 2. This way, utilities are between - (C - 1) / 2 and (C - 1) / 2.

To each preferences_ut[v, c], a random noise is added which is drawn independently and uniformly in the interval [- relative_noise * amplitude, relative_noise * amplitude], where amplitude is the difference between the lowest and the highest utility.

Another random noise is added, which is drawn independently and uniformly in the interval [-absolute_noise, absolute_noise].

Create a simple election (without manipulation).

This is an ‘abstract’ class. As an end-user, you should always use its subclasses Approval, Plurality, etc.

>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.Approval(pop, approval_comparator='>=')

ballots¶

Ballots cast by the voters.

Default type in superclass ElectionResult:

2d array of integers.

Default behavior in superclass ElectionResult:

ballots[v, k] = preferences_rk[v, k].

candidates_by_scores_best_to_worst¶

1d array of integers. All candidates, sorted from the winner to the last candidate in the result of the election.

Default behavior in superclass ElectionResult:

candidates_by_scores_best_to_worst[k] is the candidate with k^th highest value in scores.

By definition, candidates_by_scores_best_to_worst[0] = w.

demo(log_depth=1)¶

Demonstrate the methods of ElectionResult class. s

param log_depth:
	Integer from 0 (basic info) to 3 (verbose).

mean_utility_w¶

Float. The mean utility for the sincere winner w. Be careful, this makes sense only if interpersonal comparison of utilities makes sense.

options_parameters¶

Display options.

Display a overview of available options, their default values and a minimal indication about what values are allowed for each option. For more details about a specific option, see its documentation.

pop¶

A Population object. The population running the election.

score_w¶

Score of the sincere winner.

Default type in superclass ElectionResult:

Number or 1d array.

Default behavior in superclass ElectionResult:

If scores is a 1d array, then score_w is w‘s numerical score: score_w = scores[w].

If scores is a 2d array, then score_w is w‘s score vector: score_w = scores[:, w].

scores¶

Scores of the candidates in the election.

This function is not implemented in the superclass ElectionResult. See specific documentation for each voting system.

Typical type in most subclasses:

1d or 2d array.

Typical behavior in most subclasses:

If scores is a 1d array, then scores[c] is the numerical score for candidate c.

If scores is a 2d array, then scores[:, c] is the score vector for candidate c.

scores_best_to_worst¶

Scores of the candidates, from the winner to the last candidate of the election.

Default type in superclass ElectionResult:

1d or 2d array.

Default behavior in superclass ElectionResult:

scores_best_to_worst is derived from scores and candidates_by_scores_best_to_worst.

If scores is a 1d array, then so is scores_best_to_worst. It is defined by scores_best_to_worst = scores[candidates_by_scores_best_to_worst]. Then by definition, scores_best_to_worst[0] = score_w.

If scores is a 2d array, then so is scores_best_to_worst. It is defined by scores_best_to_worst = scores[:, candidates_by_scores_best_to_worst]. Then by definition, scores_best_to_worst[:, 0] = score_w.

total_utility_w¶

Float. The total utility for the sincere winner w. Be careful, this makes sense only if interpersonal comparison of utilities makes sense.

w¶

Integer (winning candidate).

Default behavior in superclass ElectionResult:

The candidate with highest value in vector scores is declared the winner. In case of a tie, the tied candidate with lowest index wins.

w_is_condorcet_admissible¶

Boolean. True iff the sincere winner w is Condorcet-admissible. Cf. condorcet_admissible_candidates.

w_is_condorcet_winner_rk¶

Boolean. True iff the sincere winner w is a condorcet_winner_rk.

w_is_condorcet_winner_rk_ctb¶

Boolean. True iff the sincere winner w is a condorcet_winner_rk_ctb.

w_is_condorcet_winner_ut_abs¶

Boolean. True iff the sincere winner w is a condorcet_winner_ut_abs.

w_is_condorcet_winner_ut_abs_ctb¶

Boolean. True iff the sincere winner w is a condorcet_winner_ut_abs_ctb.

w_is_condorcet_winner_ut_rel¶

Boolean. True iff the sincere winner w is a condorcet_winner_ut_rel.

w_is_condorcet_winner_ut_rel_ctb¶

Boolean. True iff the sincere winner w is a condorcet_winner_ut_abs_ctb.

w_is_not_condorcet_admissible¶

Boolean. True iff the sincere winner w is not a Condorcet-admissible candidate (whether some exist or not). Cf. condorcet_admissible_candidates.

w_is_not_condorcet_winner_rk¶

Boolean. True iff the sincere winner w is not a condorcet_winner_rk (whether one exists or not).

w_is_not_condorcet_winner_rk_ctb¶

Boolean. True iff the sincere winner w is not a condorcet_winner_rk_ctb (whether one exists or not).

w_is_not_condorcet_winner_ut_abs¶

Boolean. True iff the sincere winner w is not a condorcet_winner_ut_abs (whether one exists or not).

w_is_not_condorcet_winner_ut_abs_ctb¶

Boolean. True iff the sincere winner w is not a condorcet_winner_ut_abs_ctb (whether one exists or not).

w_is_not_condorcet_winner_ut_rel¶

Boolean. True iff the sincere winner w is not a condorcet_winner_ut_rel (whether one exists or not).

w_is_not_condorcet_winner_ut_rel_ctb¶

Boolean. True iff the sincere winner w is not a condorcet_winner_ut_abs_ctb (whether one exists or not).

w_is_not_resistant_condorcet_winner¶

Boolean. True iff the sincere winner w is not a resistant_condorcet_winner (whether one exists or not).

w_is_not_weak_condorcet_winner¶

Boolean. True iff the sincere winner w is not a Weak Condorcet winner (whether some exist or not). Cf. weak_condorcet_winners.

w_is_resistant_condorcet_winner¶

Boolean. True iff the sincere winner w is a resistant_condorcet_winner.

w_is_weak_condorcet_winner¶

Boolean. True iff the sincere winner w is a Weak Condorcet winner. Cf. weak_condorcet_winners.

w_missed_condorcet_admissible¶

Boolean. True iff the sincere winner w is not a Condorcet-admissible candidate, despite the fact that at least one exists. Cf. condorcet_admissible_candidates.

w_missed_condorcet_winner_rk¶

Boolean. True iff the sincere winner w is not the condorcet_winner_rk, despite the fact that she exists.

w_missed_condorcet_winner_rk_ctb¶

Boolean. True iff the sincere winner w is not the condorcet_winner_rk_ctb, despite the fact that she exists.

w_missed_condorcet_winner_ut_abs¶

Boolean. True iff the sincere winner w is not the condorcet_winner_ut_abs, despite the fact that she exists.

w_missed_condorcet_winner_ut_abs_ctb¶

Boolean. True iff the sincere winner w is not the condorcet_winner_ut_abs_ctb, despite the fact that she exists.

w_missed_condorcet_winner_ut_rel¶

Boolean. True iff the sincere winner w is not the condorcet_winner_ut_rel, despite the fact that she exists.

w_missed_condorcet_winner_ut_rel_ctb¶

Boolean. True iff the sincere winner w is not the condorcet_winner_ut_abs_ctb, despite the fact that she exists.

w_missed_resistant_condorcet_winner¶

Boolean. True iff the sincere winner w is not the resistant_condorcet_winner, despite the fact that she exists.

w_missed_weak_condorcet_winner¶

Boolean. True iff the sincere winner w is not a Weak Condorcet winner, despite the fact that at least one exists. Cf. weak_condorcet_winners.

Create an election with possibilities of manipulation.

Inherits functions from superclass ElectionResult.

This is an ‘abstract’ class. As an end-user, you should always use its subclasses Approval, Plurality, etc.

>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.IRV(pop, CM_option='exact')

This class and its subclasses are suitable for voting systems that are deterministic and anonymous (treating all voters equally). As a consequence, they are not neutral (because they need to break ties in totally symmetric situations). As of now, SVVAMP does not support other kinds of voting systems.

Ties in a voter’s utilities

When a sincere voter v must provide a strict order in a specific voting system, she uses preferences_rk[v, :] (which breaks possible ties in her utilities).

In contrast, to know if a voter v wants to manipulate for a candidate c against w, we always use her utilities preferences_ut[v, :]. If she attributes the same utility to w and c, she is not interested in this manipulation.

Some ordinal voting systems in SVVAMP may be adapted to accept weak orders of preferences as ballots. This is future work.

Ties in the result of an election

The voting system itself may need to break ties, for example if candidates c and d have the same score in a score-based system. The standard tie-breaking in SVVAMP, referred to as Candidate Tie-Breaking (CTB), consists of breaking ties by lowest index: c is favored over d if c < d. This tie-breaking rule is used for example in ‘A note on manipulability of large voting schemes’ (Peleg, 1979). Future voting systems implemented as a subclass of Election may use another tie-breaking rule.

Options for manipulation

Attributes allow to choose the algorithm used to compute different kinds of manipulation: CM_option, ICM_option, IM_option, TM_option and UM_option.

To know what options are accepted for a given voting system, use options_parameters.

import svvamp
pop = svvamp.PopulationSpheroid(V=100, C=5)
election = svvamp.IRV(pop, CM_option='exact')
print(election.CM())
print(election.options_parameters)
election.CM_option = 'fast'
print(election.CM())

Here is a non-exhaustive list of typical values for these options.

• 'exact': Exact algorithm. Can always decide manipulation: it answers True or False. Other algorithms may also answer numpy.nan, which is the SVVAMP convention meaning that the algorithm was not able to decide. For a given voting system, if the exact algorithm runs in polynomial time, then it is the only accepted option.
• 'slow': Non-polynomial algorithm, but not exact. For voting systems accepting this option, it is however faster than ‘exact’ (in a little-o sense) and more precise than ‘fast’.
• 'fast': Polynomial algorithm, not exact. If the exact algorithm runs in polynomial time, this option is not available.
• 'lazy': Perform only some preliminary checks. Run in polynomial time (unless deciding the winner of the election is not polynomial, like for Kemeny). Like other non-exact algorithms, it can decide manipulation to True, False or return numpy.nan (undecided).

For a given voting system, the default option is the most precise algorithm running in polynomial time.

Option for Independence of Irrelevant Alternatives (IIA)

The default algorithm for not_IIA first performs some preliminary checks based on the known properties of the voting system under study. For example, if it meets the Condorcet criterion, then the algorithm exploits if. If it meets the majority favorite criterion (see below) and if w is a majority favorite, then it decides IIA immediately.

If the preliminary checks do not allow to decide, the default algorithm then uses brute force to test subsets of candidates including the sincere winner w. This can be non-polynomial or non-exact, depending on the attribute IIA_subset_maximum_size.

Implication diagram between criteria

Cf. corresponding attributes below for the definition of these criteria. See working paper, Durand et al. (2014): ‘Condorcet Criterion and Reduction in Coalitional Manipulability’.

Condorcet_c_ut_rel_ctb            ==>            Condorcet_c_ut_rel
||             Condorcet_c_rk_ctb ==>      Condorcet_c_rk       ||
||           ||        ||                   ||         ||       ||
V            V         ||                   ||         V        V
Condorcet_c_ut_abs_ctb            ==>            Condorcet_c_ut_abs
||                     ||                   ||                  ||
||                     V                    V                   ||
||     majority_favorite_c_rk_ctb ==> majority_favorite_c_rk    ||
||            ||                                  ||            ||
V             V                                   V             V
majority_favorite_c_ut_ctb        ==>        majority_favorite_ut_c
||                                                              ||
V                                                               V
IgnMC_c_ctb                       ==>                       IgnMC_c
||                                                              ||
V                                                               V
InfMC_c_ctb                       ==>                       InfMC_c

CM()¶

Coalition Manipulation.

Returns:	(is_CM, log_CM).

Cf. CM_full().

CM_c(c)¶

Coalition Manipulation, focus on one candidate.

Parameters:	c – Integer (candidate).
Returns:	(candidates_CM[c], log_CM).

Cf. CM_full().

CM_c_with_bounds(c)¶

Coalition Manipulation, focus on one candidate, with bounds.

Parameters:	c – Integer (candidate).
Returns:	(candidates_CM[c], log_CM, necessary_coalition_size_CM[c], sufficient_coalition_size_CM[c]).

Cf. CM_full().

CM_full()¶

Coalition Manipulation, full mode.

We say that a situation is Coalitionaly Manipulable (CM) for c != w iff voters who prefer c to w can cast ballots so that c is elected (while other voters still vote sincerely).

Internally, to decide the problem, SVVAMP studies the following question. When considering the sub-population of voters who do not prefer c to w (sincere voters), what is the minimal number \(x_c\) of c-manipulators needed to perform CM? For all voting system currently implemented in SVVAMP, it means that CM is possible iff there are \(x_c\) voters or more who prefer c to w. (A sufficient condition on the voting system is that, if a population elects c, then an additional voter may always cast a ballot so that c stays elected)

For information only, the result of SVVAMP’s computations about \(x_c\) is given in outputs necessary_coalition_size_CM and sufficient_coalition_size_CM (cf. below). By definition, we have necessary_coalition_size_CM[c] \(\leq x_c \leq\) sufficient_coalition_size_CM[c].

When CM_option = 'exact', the exactness concerns the CM decision problems (boolean results below), not the numerical evaluation of \(x_c\). It means that for all boolean answers below, SVVAMP will not answer numpy.nan ( undecided). But it is possible that necessary_coalition_size_CM[c] < sufficient_coalition_size_CM[c].

Returns:	(is_CM, log_CM, candidates_CM, necessary_coalition_size_CM, sufficient_coalition_size_CM).

is_CM: Boolean (or numpy.nan). True if a CM is possible, False otherwise. If the algorithm cannot decide, then numpy.nan.

log_CM: String. Parameters used to compute CM.

candidates_CM: 1d array of booleans (or numpy.nan). candidates_CM[c] is True if CM for candidate c is possible, False otherwise. If the algorithm cannot decide, then numpy.nan. For the sincere winner w, we have by convention candidates_CM[w] = False.

necessary_coalition_size_CM: Integer. necessary_coalition_size_CM[c] is the lower bound found by the algorithm for \(x_c\). For the sincere winner w, we have by convention necessary_coalition_size_CM[w] = 0.

sufficient_coalition_size_CM: Integer or numpy.inf. sufficient_coalition_size_CM[c] is the upper bound found by the algorithm for \(x_c\). For the sincere winner w, we have by convention sufficient_coalition_size_CM[w] = 0.

See also

CM(), CM_c(), CM_c_with_bounds(), CM_with_candidates().

CM_option¶

String. Option used to compute CM() and related methods.

To know what options are accepted for a given voting system, use options_parameters.

CM_with_candidates()¶

Coalition Manipulation, with candidates.

Returns:	(is_CM, log_CM, candidates_CM).

Cf. CM_full().

ICM()¶

Ignorant-Coalition Manipulation.

Returns:	(is_ICM, log_ICM).

Cf. ICM_full().

ICM_c(c)¶

Ignorant-Coalition Manipulation, focus on one candidate.

Parameters:	c – Integer (candidate).
Returns:	(candidates_ICM[c], log_ICM).

Cf. ICM_full().

ICM_c_with_bounds(c)¶

Ignorant-Coalition Manipulation, focus on one candidate, with bounds.

Parameters:	c – Integer (candidate).
Returns:	(candidates_ICM[c], log_ICM, necessary_coalition_size_ICM[c], sufficient_coalition_size_ICM[c]).

Cf. ICM_full().

ICM_full()¶

Ignorant-Coalition Manipulation, full mode.

We say that a situation is Ignorant-Coalition Manipulable (ICM) for c != w iff voters who prefer c to w can cast ballots so that, whatever the other voters do, c is elected, .

Internally, to decide the problem, SVVAMP studies the following question. When considering the sub-population of voters who do not prefer c to w (sincere voters), what is the minimal number \(x_c\) of c-manipulators needed to perform ICM? For all voting system currently implemented in SVVAMP, it means that ICM is possible iff there are \(x_c\) voters or more who prefer c to w.

For information only, the result of SVVAMP’s computations about \(x_c\) is given in outputs necessary_coalition_size_ICM and sufficient_coalition_size_ICM (cf. below). By definition, we have necessary_coalition_size_ICM[c] \(\leq x_c \leq\) sufficient_coalition_size_ICM[c].

When ICM_option = 'exact', the exactness concerns the ICM decision problems (boolean results below), not the numerical evaluation of \(x_c\). It means that for all boolean answers below, SVVAMP will not answer numpy.nan ( undecided). But it is possible that necessary_coalition_size_ICM[c] < sufficient_coalition_size_ICM[c].

Returns:	(is_ICM, log_ICM, candidates_ICM, necessary_coalition_size_ICM, sufficient_coalition_size_ICM).

is_ICM: Boolean (or numpy.nan). True if a ICM is possible, False otherwise. If the algorithm cannot decide, then numpy.nan.

log_ICM: String. Parameters used to compute ICM.

candidates_ICM: 1d array of booleans (or numpy.nan). candidates_ICM[c] is True if ICM for candidate c is possible, False otherwise. If the algorithm cannot decide, then numpy.nan. For the sincere winner w, we have by convention candidates_ICM[w] = False.

necessary_coalition_size_ICM: Integer. necessary_coalition_size_ICM[c] is the lower bound found by the algorithm for \(x_c\). For the sincere winner w, we have by convention necessary_coalition_size_ICM[w] = 0.

sufficient_coalition_size_ICM: Integer or numpy.inf. sufficient_coalition_size_ICM[c] is the upper bound found by the algorithm for \(x_c\). For the sincere winner w, we have by convention sufficient_coalition_size_ICM[w] = 0.

See also

ICM(), ICM_c(), ICM_c_with_bounds(), ICM_with_candidates().

ICM_option¶

String. Option used to compute ICM() and related methods.

To know what options are accepted for a given voting system, use options_parameters.

ICM_with_candidates()¶

Ignorant-Coalition Manipulation, with candidates.

Returns:	(is_ICM, log_ICM, candidates_ICM).

Cf. ICM_full().

IIA_subset_maximum_size¶

Integer or numpy.inf. Maximum size of any subset of candidates that is used to compute not_IIA() (and related methods). For a given voting system, this attribute has no effect if there is an exact algorithm running in polynomial time implemented in SVVAMP.

IM()¶

Individual manipulation.

Returns:	(is_IM, log_IM).

Cf. IM_full().

IM_c(c)¶

Individual manipulation, focus on one candidate.

Parameters:	c – Integer (candidate).
Returns:	(candidates_IM[c], log_IM).

Cf. IM_full().

IM_c_with_voters(c)¶

Individual manipulation, focus on one candidate, with details.

Parameters:	c – Integer (candidate).
Returns:	(candidates_IM[c], log_IM, v_IM_for_c[:, c]).

Cf. IM_full().

IM_full()¶

Individual manipulation, full mode.

Voter v can and wants to manipulate for candidate c iff:

• v strictly prefers c to w (in the sense of preferences_ut).
• And by changing her vote, she can make c win instead of w.

Returns:	(is_IM, log_IM, candidates_IM, voters_IM, v_IM_for_c).

is_IM: Boolean. True if there exists a voter who can and wants to manipulate, False otherwise. If the algorithm cannot decide, then numpy.nan.

log_IM: String. Parameters used to compute IM.

candidates_IM: 1d array of booleans (or numpy.nan). candidates_IM[c] is True if there exists a voter who can manipulate for candidate c, False otherwise. If the algorithm cannot decide, then numpy.nan. For the sincere winner w, we have by convention candidates_IM[w] = False.

voters_IM: 1d array of booleans (or numpy.nan). voters_IM[v] is True if voter v can and wants to manipulate for at least one candidate, False otherwise. If the algorithm cannot decide, then numpy.nan.

v_IM_for_c: 2d array of booleans. v_IM_for_c[v, c] is True if voter v can manipulate for candidate c, False otherwise. If the algorithm cannot decide, then numpy.nan. For the sincere winner w, we have by convention v_IM_for_c[v, w] = False.

See also

IM(), IM_c(), IM_c_with_voters(), IM_v(), IM_v_with_candidates(), IM_with_candidates(), IM_with_voters().

IM_option¶

String. Option used to compute IM() and related methods.

To know what options are accepted for a given voting system, use options_parameters.

IM_v(v)¶

Individual manipulation, focus on one voter.

Parameters:	v – Integer (voter).
Returns:	(voters_IM[v], log_IM).

Cf. IM_full().

IM_v_with_candidates(v)¶

Individual manipulation, focus on one voter, with details.

Parameters:	v – Integer (voter).
Returns:	(voters_IM[v], log_IM, v_IM_for_c[v, :]).

Cf. IM_full().

IM_with_candidates()¶

Individual manipulation, focus on candidates.

Returns:	(is_IM, log_IM, candidates_IM).

Cf. IM_full().

IM_with_voters()¶

Individual manipulation, focus on voters.

Returns:	(is_IM, log_IM, voters_IM).

Cf. IM_full().

TM()¶

Trivial manipulation.

Returns:	(is_TM, log_TM).

Cf. TM_with_candidates().

TM_c(c)¶

Trivial manipulation, focus on one candidate.

Parameters:	c – Integer (candidate).
Returns:	(candidates_TM[c], log_TM).

Cf. TM_with_candidates().

TM_option¶

String. Option used to compute TM() and related methods.

To know what options are accepted for a given voting system, use options_parameters.

TM_with_candidates()¶

Trivial manipulation, full mode.

For ordinal voting systems, we call trivial manipulation for candidate c against w the fact of putting c on top (compromising), w at bottom (burying), while keeping a sincere order on other candidates.

For cardinal voting systems, we call trivial manipulation for c (against w) the fact of putting the maximum grade for c and the minimum grade for other candidates.

In both cases, the intuitive idea is the following: if I want to make c win and I only know that candidate w is ‘dangerous’ (but I know nothing else), then trivial manipulation is my ‘best’ strategy.

We say that a situation is trivially manipulable for c (implicitly: by coalition) iff, when all voters preferring c to the sincere winner w use trivial manipulation, candidate c wins.

Returns:	(is_TM, log_TM, candidates_TM).

is_TM: Boolean (or numpy.nan). True if TM is possible, False otherwise. If the algorithm cannot decide, then numpy.nan (but as of now, this value is never used for TM).

log_TM: String. Parameters used to compute TM.

candidates_TM: 1d array of booleans (or numpy.nan). candidates_TM[c] is True if a TM for candidate c is possible, False otherwise. If the algorithm cannot decide, then numpy.nan (but as of now, this value is not never for TM). For the sincere winner w, we have by convention candidates_TM[w] = False.

See also

TM(), TM_c().

UM()¶

Unison manipulation.

Returns:	(is_UM, log_UM).

Cf. UM_with_candidates().

UM_c(c)¶

Unison manipulation, focus on one candidate.

Parameters:	c – Integer (candidate).
Returns:	(candidates_UM[c], log_UM).

Cf. UM_with_candidates().

UM_option¶

String. Option used to compute UM() and related methods.

To know what options are accepted for a given voting system, use options_parameters.

UM_with_candidates()¶

Unison manipulation, full mode.

We say that a situation is unison-manipulable for a candidate c != w iff all voters who prefer c to the sincere winner w can cast the same ballot so that c is elected (while other voters still vote sincerely).

Returns:	(is_UM, log_UM, candidates_UM).

is_UM: Boolean (or numpy.nan). True if UM is possible, False otherwise. If the algorithm cannot decide, then numpy.nan.

log_UM: String. Parameters used to compute UM.

candidates_UM: 1d array of booleans (or numpy.nan). candidates_UM[c] is True if UM for candidate c is possible, False otherwise. If the algorithm cannot decide, then numpy.nan. For the sincere winner w, we have by convention candidates_UM[w] = False.

See also

UM(), UM_c().

c_has_supporters¶

1d array of booleans. c_has_supporters[c] is True iff at least one voter prefers candidate c to the sincere winner w.

demo(log_depth=1)¶

Demonstrate the methods of Election class.

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

is_based_on_rk¶

Boolean. True iff this voting system is based only on strict rankings (no cardinal information, indifference not allowed).

is_based_on_ut_minus1_1¶

Boolean. True iff:

• This voting system is based only on utilities (not rankings, i.e. does not depend on how voters break ties in their own preferences),
• And for a c-manipulator (IM or CM), it is optimal to pretend that c has utility 1 and other candidates have utility -1.

log_CM¶

String. Parameters used to compute CM() and related methods.

log_ICM¶

String. Parameters used to compute ICM() and related methods.

log_IIA¶

String. Parameters used to compute not_IIA() and related methods.

log_IM¶

String. Parameters used to compute IM() and related methods.

log_TM¶

String. Parameters used to compute TM() and related methods.

log_UM¶

String. Parameters used to compute UM() and related methods.

losing_candidates¶

1d of Integers. List of losing candidates, in an arbitrary order.

This attribute is mostly for SVVAMP developers. It is used in manipulation algorithms.

meets_Condorcet_c_rk¶

Boolean. True iff the voting system meets the Condorcet criterion (rk). I.e. if a candidate is a condorcet_winner_rk, then she wins.

Is implied by: meets_Condorcet_c_rk_ctb.

Implies: meets_Condorcet_c_ut_abs, meets_majority_favorite_c_rk.

meets_Condorcet_c_rk_ctb¶

Boolean. True iff the voting system meets the ‘Condorcet criterion (rk) with ctb’. I.e.: if a candidate is a condorcet_winner_rk_ctb, she wins.

Implies: meets_Condorcet_c_rk, meets_Condorcet_c_ut_abs_ctb, meets_majority_favorite_c_rk_ctb.

meets_Condorcet_c_ut_abs¶

Boolean. True iff the voting system meets the absolute Condorcet criterion. I.e. if a candidate is a condorcet_winner_ut_abs, then she wins.

Is implied by: meets_Condorcet_c_rk, meets_Condorcet_c_ut_rel, meets_Condorcet_c_ut_abs_ctb.

Implies: meets_majority_favorite_c_ut.

meets_Condorcet_c_ut_abs_ctb¶

Boolean. True iff the voting system meets the ‘absolute Condorcet criterion with ctb’. I.e.: if a candidate is a condorcet_winner_ut_abs_ctb, she wins.

Is implied by: meets_Condorcet_c_rk_ctb, meets_Condorcet_c_ut_rel_ctb.

Implies: meets_Condorcet_c_ut_abs, meets_majority_favorite_c_ut_ctb.

meets_Condorcet_c_ut_rel¶

Boolean. True iff the voting system meets the relative Condorcet criterion. I.e. if a candidate is a condorcet_winner_ut_rel, then she wins.

Is implied by: meets_Condorcet_c_ut_rel_ctb.

Implies: meets_Condorcet_c_ut_abs.

meets_Condorcet_c_ut_rel_ctb¶

Boolean. True iff the voting system meets the ‘relative Condorcet criterion with ctb’. I.e.: if a candidate is a condorcet_winner_ut_rel_ctb, she wins.

Implies: meets_Condorcet_c_ut_rel, meets_Condorcet_c_ut_abs_ctb.

meets_IIA¶

Boolean. True iff this voting system meets Independence of Irrelevant Alternatives.

meets_IgnMC_c¶

Boolean. True iff the voting system meets the ignorant majority coalition criterion. I.e. any ignorant coalition of size strictly more than V/2 can make any candidate win. See working paper, Durand et al. (2014): ‘Condorcet Criterion and Reduction in Coalitional Manipulability’.

Ignorant means that they can choose their ballot without knowing what other voters will do.

Is implied by: meets_majority_favorite_c_ut, meets_IgnMC_c_ctb.

Implies: meets_InfMC_c.

meets_IgnMC_c_ctb¶

Boolean. True iff the voting system meets the ‘ignorant majority coalition criterion with ctb’. I.e.:

• It meets_IgnMC_c,
• And any ignorant coalition of size V/2 can make candidate 0 win.

Is implied by: meets_majority_favorite_c_ut_ctb.

Implies: meets_InfMC_c_ctb, meets_IgnMC_c.

meets_InfMC_c¶

Boolean. True iff the voting system meets the informed majority coalition criterion. I.e. any informed coalition of size strictly more than V/2 can make any candidate win. See working paper, Durand et al. (2014): ‘Condorcet Criterion and Reduction in Coalitional Manipulability’.

Informed means that they know other voters’ ballots before choosing their own.

Is implied by: meets_IgnMC_c, meets_InfMC_c_ctb.

meets_InfMC_c_ctb¶

Boolean. True iff the voting system meets the ‘informed majority coalition criterion with ctb’. I.e.:

• It meets_InfMC_c,
• And any informed coalition of size V/2 can make candidate 0 win.

Is implied by: meets_IgnMC_c_ctb.

Implies: meets_InfMC_c.

meets_majority_favorite_c_rk¶

Boolean. True iff the voting system meets the majority favorite criterion (rk). I.e. if strictly more than V/2 voters rank a candidate first (rk), then she wins.

Is implied by: meets_Condorcet_c_rk, meets_majority_favorite_c_rk_ctb.

Implies: _meets_majority_favorite_c_ut.

meets_majority_favorite_c_rk_ctb¶

Boolean. True iff the voting system meets the ‘majority favorite criterion (rk) with ctb’. I.e.:

• It meets_majority_favorite_c_rk,
• And if V/2 voters rank candidate 0 first (rk), she wins.

Is implied by: meets_Condorcet_c_rk_ctb.

Implies: meets_majority_favorite_c_ut_ctb, meets_majority_favorite_c_rk.

meets_majority_favorite_c_ut¶

Boolean. True iff the voting system meets the majority favorite criterion (ut). I.e. if strictly more than V/2 voters strictly prefer a candidate to all others (ut), she wins.

Is implied by: meets_Condorcet_c_ut_abs, meets_majority_favorite_c_ut_ctb, meets_majority_favorite_c_rk.

Implies: meets_IgnMC_c.

meets_majority_favorite_c_ut_ctb¶

Boolean. True iff the voting system meets the ‘majority favorite criterion (ut) with ctb’. I.e.:

• It meets_majority_favorite_c_ut,
• And if V/2 voters strictly prefer candidate 0 to all other candidates, she wins.

Is implied by: meets_Condorcet_c_ut_abs_ctb, meets_majority_favorite_c_rk_ctb.

Implies: meets_IgnMC_c_ctb, meets_majority_favorite_c_ut.

not_IIA()¶

Independence of Irrelevant Alternatives, incomplete mode.

Returns:	(is_not_IIA, log_IIA).

Cf. not_IIA_full() for more details.

not_IIA_full()¶

Independence of Irrelevant Alternatives, complete mode.

Returns:	(is_not_IIA, log_IIA, example_subset_IIA, example_winner_IIA).

is_not_IIA: Boolean. True if there exists a subset of candidates including the sincere winner w, such that if the election is held with this subset of candidates, then w is not the winner anymore. If the algorithm cannot decide, then the result is numpy.nan.

log_IIA: String. Parameters used to compute IIA.

example_subset_IIA: 1d array of booleans. If the election is not IIA, example_subset_IIA provides a subset of candidates breaking IIA. example_subset_IIA[c] is True iff candidate c belongs to the subset. If the election is IIA (or if the algorithm cannot decide), then example_subset_IIA = numpy.nan.

example_winner_IIA: Integer (candidate). If the election is not IIA, example_winner_IIA is the winner corresponding to the counter-example example_subset_IIA. If the election is IIA (or if the algorithm cannot decide), then example_winner_IIA = numpy.nan.

See also

not_IIA().

v_wants_to_help_c¶

2d array of booleans. v_wants_to_help_c[v, c] is True iff voter v strictly prefers candidate c to the sincere winner w. If v attributes the same utility for c and w, then v is not interested.

with_two_candidates_reduces_to_plurality¶

Boolean. True iff, when using this voting system with only two candidates, it amounts to Plurality (with voter and candidate tie-breaking).

Approval voting.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.Approval(pop, approval_comparator='>', approval_threshold=0)

Each voter may vote for any number of candidates. The candidate with most votes is declared the winner. In case of a tie, the tied candidate with lowest index wins.

Default behavior of sincere voters: sincere voter v approves candidate c iff preferences_ut[v, c] > 0. To modify this behavior, use attributes approval_comparator and approval_threshold.

not_IIA(): With our assumptions, Approval voting always meets IIA.

CM(), ICM(), IM(), TM(), UM(): Exact in polynomial time.

References:

‘Approval voting’, Steven Brams and Peter Fishburn. In: American Political Science Review 72 (3 1978), pp. 831–847.

approval_comparator¶

String. Can be '>' (default) or '>='.

When approval_comparator is '>', sincere voter v approves candidates c iff preferences_ut[v, c] > approval_threshold.

When approval_comparator is '>=', previous relation is modified accordingly.

approval_threshold¶

Number (default 0). Utility above which a sincere voter approves a candidate. See also approval_comparator.

ballots¶

2d array of values in {0, 1}. ballots[v, c] = 1 iff voter v votes for candidates c.

See also

approval_comparator, approval_threshold.

scores¶

1d array of integers. scores[c] is the number of voters who vote for candidate c.

w¶

Integer (winning candidate).

Default behavior in superclass ElectionResult:

The candidate with highest value in vector scores is declared the winner. In case of a tie, the tied candidate with lowest index wins.

Baldwin method.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.Baldwin(pop)

Each voter provides a strict order of preference. The candidate with lowest Borda score is eliminated. Then the new Borda scores are computed. Etc. Ties are broken in favor of lower-index candidates: in case of a tie, the candidate with highest index is eliminated.

Since a Condorcet winner has always a Borda score higher than average, Baldwin method meets the Condorcet criterion.

CM(): Non-polynomial or non-exact algorithms from superclass Election.

ICM(): Exact in polynomial time.

IM(): Deciding IM is NP-complete. Non-polynomial or non-exact algorithms from superclass Election.

not_IIA(): Exact in polynomial time.

TM(): Exact in polynomial time.

UM(): Non-polynomial or non-exact algorithms from superclass Election.

References:

‘Complexity of and algorithms for the manipulation of Borda, Nanson’s and Baldwin’s voting rules’, Jessica Davies, George Katsirelos, Nina Narodytska, Toby Walsh and Lirong Xia, 2014.

candidates_by_scores_best_to_worst¶

1d array of integers. candidates_by_scores_best_to_worst[-r] is the candidate eliminated at elimination round r.

By definition / convention, candidates_by_scores_best_to_worst[0] = w.

scores¶

2d array of integers. scores[r, c] is the Borda score of candidate c at elimination round r.

By convention, if candidate c does not participate to round r, then scores[r, c] = numpy.inf.

w¶

Integer (winning candidate).

Borda rule.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.Borda(pop)

Voter v gives (C - 1) points to her top-ranked candidate, (C - 2) to the second, ..., 0 to the last. Ties are broken by natural order on the candidates (lower index wins).

CM(): Deciding CM is NP-complete.

• CM_option = 'fast': Zuckerman et al. (2009). This approximation algorithm is polynomial and has a window of error of 1 manipulator.
• CM_option = 'exact': Non-polynomial algorithm from superclass Election.

ICM(): Algorithm is polynomial and has a window of error of 1 manipulator.

IM(): Exact in polynomial time.

not_IIA(): Exact in polynomial time.

TM(): Exact in polynomial time.

UM(): Exact in polynomial time.

References:

‘Algorithms for the coalitional manipulation problem’, M. Zuckerman, A. Procaccia and J. Rosenschein, 2009.

‘Unweighted Coalitional Manipulation Under the Borda Rule is NP-Hard’, Nadja Betzler, Rolf Niedermeier and Gerhard Woeginger, 2011.

‘Complexity of and algorithms for the manipulation of Borda, Nanson’s and Baldwin’s voting rules’, Jessica Davies, George Katsirelos, Nina Narodytska, Toby Walsh and Lirong Xia, 2014.

scores¶

1d array of integers. scores[c] is the total Borda score for candidate c.

w¶

Integer (winning candidate).

Default behavior in superclass ElectionResult:

The candidate with highest value in vector scores is declared the winner. In case of a tie, the tied candidate with lowest index wins.

Bucklin method.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.Bucklin(pop)

At counting round r, all voters who rank candidate c in r^th position gives her an additional vote. As soon as at least one candidate has more than V/2 votes (accrued with previous rounds), the candidate with most votes is declared the winner. In case of a tie, the candidate with lowest index wins.

CM(): Exact in polynomial time.

ICM(): Exact in polynomial time.

IM(): Exact in polynomial time.

not_IIA(): Non-polynomial or non-exact algorithms from superclass Election.

TM(): Exact in polynomial time.

UM(): Exact in polynomial time.

References:

‘The Majoritarian Compromise in large societies’, Arkadii Slinko, 2002.

‘Complexity of Unweighted Coalitional Manipulation under Some Common Voting Rules’, Lirong Xia, Michael Zuckerman, Ariel D. Procaccia, Vincent Conitzer and Jeffrey S. Rosenschein, 2009.

candidates_by_scores_best_to_worst¶

1d array of integers. Candidates are sorted according to their scores during the counting round during which at least one candidate reaches majority.

By definition, candidates_by_scores_best_to_worst[0] = w.

scores¶

2d array of integers. scores[r, c] is the accrued score of candidate c at elimination round r. It is the number of voters who rank c between 0^th and r^th rank on their ballot.

For information, ballot are still counted after the round where the decision is made (it is used for manipulation algorithms).

w¶

Integer (winning candidate). When at least one candidate has more than V/2 votes, the candidate with most votes gets elected. In case of a tie, the candidate with highest index wins.

Absolute-Condorcet Instant Runoff Voting.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.CondorcetAbsIRV(pop)

Each voter must provide a weak order, and a strict total order that is coherent with this weak order (i.e., is a tie-breaking of this weak order).

If there is a Condorcet winner (computed with the weak orders, i.e. in the sense of matrix_victories_ut_abs), then she is elected. Otherwise, IRV is used (with the strict total orders).

If sincere preferences are strict total orders, then this voting system is equivalent to CondorcetVtbIRV for sincere voting, but manipulators have more possibilities (they can pretend to have ties in their preferences). In that case especially, it is a more ‘natural’ framework to use CondorcetVtbIRV.

CM():

• CM_option = 'fast': Rely on IRV‘s fast algorithm. Polynomial heuristic. Can prove CM but unable to decide non-CM (except in rare obvious cases).
• CM_option = 'slow': Rely on ExhaustiveBallot‘s exact algorithm. Non-polynomial heuristic (\(2^C\)). Quite efficient to prove CM or non-CM.
• CM_option = 'almost_exact': Rely on IRV‘s exact algorithm. Non-polynomial heuristic (\(C!\)). Very efficient to prove CM or non-CM.
• CM_option = 'exact': Non-polynomial algorithm from superclass Election.

Each algorithm above exploits the faster ones. For example, if CM_option = 'almost_exact', SVVAMP tries the fast algorithm first, then the slow one, then the ‘almost exact’ one. As soon as it reaches a decision, computation stops.

ICM(): Exact in polynomial time.

IM(): Non-polynomial or non-exact algorithms from superclass Election.

not_IIA(): Non-polynomial or non-exact algorithms from superclass Election.

TM(): Exact in polynomial time.

UM(): Non-polynomial or non-exact algorithms from superclass Election.

References:

‘Condorcet criterion, ordinality and reduction of coalitional manipulability’, François Durand, Fabien Mathieu and Ludovic Noirie, working paper, 2014.

candidates_by_scores_best_to_worst¶

1d array of integers. If there is a Condorcet winner, candidates are sorted according to their (scalar) score.

Otherwise, candidates_by_scores_best_to_worst is the list of all candidates in the reverse order of their IRV elimination.

By definition, candidates_by_scores_best_to_worst[0] = w.

scores¶

1d or 2d array.

If there is a Condorcet winner, then scores[c] is the number of victories for c in matrix_victories_ut_abs.

Otherwise, scores[r, c] is defined like in IRV: it is the number of voters who vote for candidate c at round r. For eliminated candidates, scores[r, c] = numpy.nan. At the opposite, scores[r, c] = 0 means that c is present at round r but no voter votes for c.

w¶

Integer (winning candidate).

Condorcet with sum of defeats.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.CondorcetSumDefeats(pop)

An elementary move consists of reversing a voter’s preference about a pair of candidate (c, d) (without demanding that her whole relation of preference stays transitive). The score for candidate c is minus the number of elementary moves needed so that c becomes a Condorcet winner.

It is the same principle as Dodgson’s method, but without looking for a transitive profile.

In practice:

In particular, for V odd:

CM(): Non-polynomial or non-exact algorithms from superclass Election.

ICM(): Algorithm from superclass Election. It is polynomial and has a window of error of 1 manipulator.

IM(): Non-polynomial or non-exact algorithms from superclass Election.

not_IIA(): Non-polynomial or non-exact algorithms from superclass Election. If IIA_subset_maximum_size = 2, it runs in polynomial time and is exact up to ties (which can occur only if V is even).

TM(): Exact in polynomial time.

UM(): Non-polynomial or non-exact algorithms from superclass Election.

scores¶

1d array of integers.

\[\texttt{scores}[c] = - \sum_{c \text{ does not beat } d}\left( \left\lfloor\frac{V}{2}\right\rfloor + 1 - \texttt{matrix_duels_rk}[c, d] \right)\]

w¶

Integer (winning candidate).

Default behavior in superclass ElectionResult:

The candidate with highest value in vector scores is declared the winner. In case of a tie, the tied candidate with lowest index wins.

Condorcet Instant Runoff Voting

Inherits functions and optional parameters from superclasses ElectionResult and Election.

>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.CondorcetVtbIRV(pop)

Each voter must provide a strict total order. If there is a Condorcet winner (in the sense of matrix_victories_rk), then she is elected. Otherwise, IRV is used.

If sincere preferences are strict total orders, then this voting system is equivalent to CondorcetAbsIRV for sincere voting, but manipulators have less possibilities (they are forced to provide strict total orders).

CM():

• CM_option = 'fast': Rely on IRV‘s fast algorithm. Polynomial heuristic. Can prove CM but unable to decide non-CM (except in rare obvious cases).
• CM_option = 'slow': Rely on ExhaustiveBallot‘s exact algorithm. Non-polynomial heuristic (\(2^C\)). Quite efficient to prove CM or non-CM.
• CM_option = 'almost_exact': Rely on IRV‘s exact algorithm. Non-polynomial heuristic (\(C!\)). Very efficient to prove CM or non-CM.
• CM_option = 'exact': Non-polynomial algorithm from superclass Election.

Each algorithm above exploits the faster ones. For example, if CM_option = 'almost_exact', SVVAMP tries the fast algorithm first, then the slow one, then the ‘almost exact’ one. As soon as it reaches a decision, computation stops.

ICM(): Exact in polynomial time.

IM(): Non-polynomial or non-exact algorithms from superclass Election.

not_IIA(): Non-polynomial or non-exact algorithms from superclass Election. If IIA_subset_maximum_size = 2, it runs in polynomial time and is exact up to ties (which can occur only if V is even).

TM(): Exact in polynomial time.

UM(): Non-polynomial or non-exact algorithms from superclass Election.

References:

‘Condorcet criterion, ordinality and reduction of coalitional manipulability’, François Durand, Fabien Mathieu and Ludovic Noirie, working paper, 2014.

candidates_by_scores_best_to_worst¶

1d array of integers.

If there is a Condorcet winner, candidates are sorted according to their (scalar) score.

Otherwise, candidates_by_scores_best_to_worst is the list of all candidates in the reverse order of their IRV elimination.

By definition, candidates_by_scores_best_to_worst[0] = w.

scores¶

1d or 2d array.

If there is a Condorcet winner, then scores[c] is the number of victories for c in matrix_duels_rk.

Otherwise, scores[r, c] is defined like in IRV: it is the number of voters who vote for candidate c at round r. For eliminated candidates, scores[r, c] = numpy.nan. At the opposite, scores[r, c] = 0 means that c is present at round r but no voter votes for c.

w¶

Integer (winning candidate).

Coombs method.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.Coombs(pop)

The candidate who is ranked last by most voters is eliminated. Then we iterate. Ties are broken in favor of lower-index candidates: in case of a tie, the tied candidate with highest index is eliminated.

CM():

• CM_option = 'fast': Polynomial heuristic. Can prove CM but unable to decide non-CM (except in rare obvious cases).
• CM_option = 'exact': Non-polynomial (\(C!\)).

ICM(): Exact in polynomial time.

IM():

• IM_option = 'fast': Polynomial heuristic. Can prove CM but unable to decide non-IM (except in rare obvious cases).
• IM_option = 'exact': Non-polynomial (\(C!\)).

not_IIA(): Non-polynomial or non-exact algorithms from superclass Election.

TM(): Exact in polynomial time.

UM(): For this voting system, UM and CM are equivalent. For this reason, UM_option and CM_option are linked to each other: modifying one modifies the other accordingly.

References:

‘On The Complexity of Manipulating Elections’, Tom Coleman and Vanessa Teague, 2007.

candidates_by_scores_best_to_worst¶

1d array of integers. Candidates are sorted according to their order of elimination.

By definition / convention, candidates_by_scores_best_to_worst[0] = w.

scores¶

2d array of integers. scores[r, c] is minus the number of voters who vote against candidate c at elimination round r.

w¶

Integer (winning candidate).

Exhaustive Ballot.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.ExhaustiveBallot(pop)

At each round, voters vote for one non-eliminated candidate. The candidate with least votes is eliminated. Then the next round is held. Unlike IRV, voters actually vote at each round. This does not change anything for sincere voting, but offers a bit more possibilities for the manipulators. In case of a tie, the candidate with highest index is eliminated.

CM():

• CM_option = 'fast': Polynomial heuristic. Can prove CM but unable to decide non-CM (except in rare obvious cases).
• CM_option = 'exact': Non-polynomial algorithm (\(2^C\)) adapted from Walsh, 2010.

ICM(): Exact in polynomial time.

IM():

• IM_option = 'lazy': Lazy algorithm from superclass Election.
• IM_option = 'exact': Non-polynomial algorithm (\(2^C\)) adapted from Walsh, 2010.

not_IIA(): Non-polynomial or non-exact algorithms from superclass Election.

TM(): Exact in polynomial time.

UM():

• UM_option = 'fast': Polynomial heuristic. Can prove UM but unable to decide non-UM (except in rare obvious cases).
• UM_option = 'exact': Non-polynomial algorithm (\(2^C\)) adapted from Walsh, 2010.

References:

‘Single transferable vote resists strategic voting’, John J. Bartholdi and James B. Orlin, 1991.

‘On The Complexity of Manipulating Elections’, Tom Coleman and Vanessa Teague, 2007.

‘Manipulability of Single Transferable Vote’, Toby Walsh, 2010.

ballots¶

2d array of integers. ballots[v, r] is the candidate for which voter v votes at round r.