class svvamp.RuleExhaustiveBallot(**kwargs)[source]#

Exhaustive Ballot.

Options#

>>> RuleExhaustiveBallot.print_options_parameters()
cm_option: ['fast', 'exact']. Default: 'fast'.
fast_algo: ['c_minus_max', 'minus_max', 'hardest_first']. Default: 'c_minus_max'.
icm_option: ['exact']. Default: 'exact'.
iia_subset_maximum_size: is_number. Default: 2.
im_option: ['lazy', 'exact']. Default: 'lazy'.
tm_option: ['exact']. Default: 'exact'.
um_option: ['fast', 'exact']. Default: 'fast'.

Notes

At each round, voters vote for one non-eliminated candidate. The candidate with least votes is eliminated. Then the next round is held. Unlike RuleIRV, 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.

  • is_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^{n_c}\)) adapted from Walsh, 2010.

  • is_icm_(): Exact in polynomial time.

  • is_im_():

    • im_option = 'lazy': Lazy algorithm from superclass Rule.

    • im_option = 'exact': Non-polynomial algorithm (\(2^{n_c}\)) adapted from Walsh, 2010.

  • is_iia(): Non-polynomial or non-exact algorithms from superclass Rule.

  • is_tm_(): Exact in polynomial time.

  • is_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^{n_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.

Examples

>>> profile = Profile(preferences_ut=[
...     [ 0. , -0.5, -1. ],
...     [ 1. , -1. ,  0.5],
...     [ 0.5,  0.5, -0.5],
...     [ 0.5,  0. ,  1. ],
...     [-1. , -1. ,  1. ],
... ], preferences_rk=[
...     [0, 1, 2],
...     [0, 2, 1],
...     [1, 0, 2],
...     [2, 0, 1],
...     [2, 1, 0],
... ])
>>> rule = RuleExhaustiveBallot()(profile)
>>> rule.demo_results_(log_depth=0)  

************************
*                      *
*   Election Results   *
*                      *
************************

***************
*   Results   *
***************
profile_.preferences_ut (reminder) =
[[ 0.  -0.5 -1. ]
 [ 1.  -1.   0.5]
 [ 0.5  0.5 -0.5]
 [ 0.5  0.   1. ]
 [-1.  -1.   1. ]]
profile_.preferences_rk (reminder) =
[[0 1 2]
 [0 2 1]
 [1 0 2]
 [2 0 1]
 [2 1 0]]
ballots =
[[0 0]
 [0 0]
 [1 0]
 [2 2]
 [2 2]]
scores =
[[ 2.  1.  2.]
 [ 3. nan  2.]]
candidates_by_scores_best_to_worst
[0 2 1]
scores_best_to_worst
[[ 2.  2.  1.]
 [ 3.  2. nan]]
w = 0
score_w = [2. 3.]
total_utility_w = 1.0

*********************************
*   Condorcet efficiency (rk)   *
*********************************
w (reminder) = 0

condorcet_winner_rk_ctb = 0
w_is_condorcet_winner_rk_ctb = True
w_is_not_condorcet_winner_rk_ctb = False
w_missed_condorcet_winner_rk_ctb = False

condorcet_winner_rk = 0
w_is_condorcet_winner_rk = True
w_is_not_condorcet_winner_rk = False
w_missed_condorcet_winner_rk = False

***************************************
*   Condorcet efficiency (relative)   *
***************************************
w (reminder) = 0

condorcet_winner_ut_rel_ctb = 0
w_is_condorcet_winner_ut_rel_ctb = True
w_is_not_condorcet_winner_ut_rel_ctb = False
w_missed_condorcet_winner_ut_rel_ctb = False

condorcet_winner_ut_rel = 0
w_is_condorcet_winner_ut_rel = True
w_is_not_condorcet_winner_ut_rel = False
w_missed_condorcet_winner_ut_rel = False

***************************************
*   Condorcet efficiency (absolute)   *
***************************************
w (reminder) = 0

condorcet_admissible_candidates =
[ True False False]
w_is_condorcet_admissible = True
w_is_not_condorcet_admissible = False
w_missed_condorcet_admissible = False

weak_condorcet_winners =
[ True False False]
w_is_weak_condorcet_winner = True
w_is_not_weak_condorcet_winner = False
w_missed_weak_condorcet_winner = False

condorcet_winner_ut_abs_ctb = 0
w_is_condorcet_winner_ut_abs_ctb = True
w_is_not_condorcet_winner_ut_abs_ctb = False
w_missed_condorcet_winner_ut_abs_ctb = False

condorcet_winner_ut_abs = 0
w_is_condorcet_winner_ut_abs = True
w_is_not_condorcet_winner_ut_abs = False
w_missed_condorcet_winner_ut_abs = False

resistant_condorcet_winner = nan
w_is_resistant_condorcet_winner = False
w_is_not_resistant_condorcet_winner = True
w_missed_resistant_condorcet_winner = False
>>> rule.demo_manipulation_(log_depth=0)  

*****************************
*                           *
*   Election Manipulation   *
*                           *
*****************************

*********************************************
*   Basic properties of the voting system   *
*********************************************
with_two_candidates_reduces_to_plurality =  True
is_based_on_rk =  True
is_based_on_ut_minus1_1 =  False
meets_iia =  False

****************************************************
*   Manipulation properties of the voting system   *
****************************************************
Condorcet_c_ut_rel_ctb (False)     ==>     Condorcet_c_ut_rel (False)
 ||                                                               ||
 ||     Condorcet_c_rk_ctb (False) ==> Condorcet_c_rk (False)     ||
 ||           ||               ||       ||             ||         ||
 V            V                ||       ||             V          V
Condorcet_c_ut_abs_ctb (False)     ==>     Condorcet_ut_abs_c (False)
 ||                            ||       ||                        ||
 ||                            V        V                         ||
 ||       maj_fav_c_rk_ctb (True)  ==> maj_fav_c_rk (True)        ||
 ||           ||                                       ||         ||
 V            V                                        V          V
majority_favorite_c_ut_ctb (True)  ==> majority_favorite_c_ut (True)
 ||                                                               ||
 V                                                                V
IgnMC_c_ctb (True)                 ==>                IgnMC_c (True)
 ||                                                               ||
 V                                                                V
InfMC_c_ctb (True)                 ==>                InfMC_c (True)

*****************************************************
*   Independence of Irrelevant Alternatives (IIA)   *
*****************************************************
w (reminder) = 0
is_iia = True
log_iia: iia_subset_maximum_size = 2.0
example_winner_iia = nan
example_subset_iia = nan

**********************
*   c-Manipulators   *
**********************
w (reminder) = 0
preferences_ut (reminder) =
[[ 0.  -0.5 -1. ]
 [ 1.  -1.   0.5]
 [ 0.5  0.5 -0.5]
 [ 0.5  0.   1. ]
 [-1.  -1.   1. ]]
v_wants_to_help_c =
[[False False False]
 [False False False]
 [False False False]
 [False False  True]
 [False False  True]]

************************************
*   Individual Manipulation (IM)   *
************************************
is_im = nan
log_im: im_option = lazy
candidates_im =
[ 0.  0. nan]

*********************************
*   Trivial Manipulation (TM)   *
*********************************
is_tm = False
log_tm: tm_option = exact
candidates_tm =
[0. 0. 0.]

********************************
*   Unison Manipulation (UM)   *
********************************
is_um = nan
log_um: um_option = fast, fast_algo = c_minus_max
candidates_um =
[ 0.  0. nan]

*********************************************
*   Ignorant-Coalition Manipulation (ICM)   *
*********************************************
is_icm = False
log_icm: icm_option = exact
candidates_icm =
[0. 0. 0.]
necessary_coalition_size_icm =
[0. 6. 4.]
sufficient_coalition_size_icm =
[0. 6. 4.]

***********************************
*   Coalition Manipulation (CM)   *
***********************************
is_cm = nan
log_cm: cm_option = fast, fast_algo = c_minus_max, icm_option = exact, tm_option = exact
candidates_cm =
[ 0.  0. nan]
necessary_coalition_size_cm =
[0. 0. 2.]
sufficient_coalition_size_cm =
[0. 2. 4.]
property ballots_#

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

property candidates_by_scores_best_to_worst_#

1d array of integers. candidates_by_scores_best_to_worst is the list of all candidates in the reverse order of their elimination.

property elimination_path_#

1d array of integers. Same as candidates_by_scores_best_to_worst, but in the reverse order.

Examples

>>> profile = Profile(preferences_rk=[
...     [0, 1, 2],
...     [0, 2, 1],
...     [0, 2, 1],
...     [0, 2, 1],
...     [2, 0, 1],
... ])
>>> rule = RuleExhaustiveBallot()(profile)
>>> rule.elimination_path_
array([1, 2, 0])
property margins_#

2d array. margins_[r, c] is the number of votes that c must lose to be eliminated at round r (all other things being equal). The candidate who is eliminated at round r is the only one for which margins_[r, c] = 0.

For eliminated candidates, margins_[r, c] = numpy.nan.

Examples

>>> profile = Profile(preferences_rk=[
...     [0, 1, 2],
...     [0, 2, 1],
...     [0, 2, 1],
...     [0, 2, 1],
...     [2, 0, 1],
... ])
>>> rule = RuleExhaustiveBallot()(profile)
>>> rule.margins_
array([[ 5.,  0.,  1.],
       [ 4., nan,  0.]])
property scores_#

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

For eliminated candidates, scores[r, c] = numpy.nan. In contrast, scores[r, c] = 0 means that c is present at round r but no voter votes for c.

property w_#

Integer (winning candidate).

Default behavior: the candidate with highest value in vector scores_ is declared the winner. In case of a tie, the tied candidate with lowest index wins.