Election¶

class svvamp.Election(population, **kwargs)[source]¶

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.

Parameters:	population – A `Population` object. kwargs – additional keyword parameters. See `options_parameters`.
Example:

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

Example:

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.

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.

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.

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