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

Schulze method.

Options#

>>> RuleSchulze.print_options_parameters()
cm_option: ['fast', 'exact']. Default: 'fast'.
icm_option: ['exact']. Default: 'exact'.
iia_subset_maximum_size: is_number. Default: 2.
im_option: ['fast', 'exact']. Default: 'fast'.
tm_option: ['exact']. Default: 'exact'.
um_option: ['fast', 'exact']. Default: 'fast'.

Notes

scores_[c, d] is equal to the width of the widest path from candidate c to candidate d in the capacited graph defined by matrix_duels_rk. We say that c is better than d if scores_[c, d] > scores_[d, c]. Candidate c is a potential winner if no candidate d is better than c.

Among the potential winners, the candidate with lowest index is declared the winner.

Note

In the original Schulze method, ties are broken at random. However, this feature is not supported by SVVAMP because it leads to difficulties for the definition of manipulation itself (and all the more for its implementation).

  • is_cm_():

    • cm_option = 'fast': Gaspers et al. (2013). This algorithm is polynomial and has a window of error of 1 manipulator (due to the tie-breaking rule).

    • cm_option = 'exact': Non-polynomial algorithm from superclass Rule.

  • is_icm_(): Exact in polynomial time.

  • is_im_():

    • im_option = 'fast': Gaspers et al. (2013). This algorithm is polynomial and may not be able to decide IM (due to the tie-breaking rule).

    • im_option = 'exact': Non-polynomial algorithm from superclass Rule.

  • not_iia(): Exact in polynomial time.

  • is_tm_(): Exact in polynomial time.

  • is_um_():

    • um_option = 'fast': Gaspers et al. (2013). This algorithm is polynomial and has a window of error of 1 manipulator (due to the tie-breaking rule).

    • um_option = 'exact': Non-polynomial algorithm from superclass Rule.

References

‘A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method ‘, Markus Schulze, 2011.

‘Schulze and Ranked-Pairs Voting are Fixed-Parameter Tractable to Bribe, Manipulate, and Control’, Lane A. Hemaspaandra, Rahman Lavaee and Curtis Menton, 2012.

‘Manipulation and Control Complexity of Schulze Voting’, Curtis Menton and Preetjot Singh, 2012.

‘A Complexity-of-Strategic-Behavior Comparison between Schulze’s Rule and Ranked Pairs’, David Parkes and Lirong Xia, 2012.

‘Coalitional Manipulation for Schulze’s Rule’, Serge Gaspers, Thomas Kalinowski, Nina Narodytska and Toby Walsh, 2013.

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 = RuleSchulze()(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 1 2]
 [0 2 1]
 [1 0 2]
 [2 0 1]
 [2 1 0]]
scores =
[[0 3 3]
 [2 0 2]
 [2 3 0]]
candidates_by_scores_best_to_worst
[0 2 1]
scores_best_to_worst
[[0 3 3]
 [2 0 3]
 [2 2 0]]
w = 0
score_w = [0 3 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 (True)  ==> Condorcet_c_rk (True)      ||
 ||           ||               ||       ||             ||         ||
 V            V                ||       ||             V          V
Condorcet_c_ut_abs_ctb (True)      ==>     Condorcet_ut_abs_c (True)
 ||                            ||       ||                        ||
 ||                            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 = fast
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
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, tm_option = exact
candidates_cm =
[ 0.  0. nan]
necessary_coalition_size_cm =
[0. 1. 2.]
sufficient_coalition_size_cm =
[0. 2. 3.]
property candidates_by_scores_best_to_worst_#

1d array of integers. candidates_by_scores_best_to_worst_[k] is the k-th candidate by number of Schulze-victories, i.e. the number of candidates d such that c is better than d.

property score_w_#

score_w_ = scores_[w_, :].

Type:

1d array. score_w_ is w_’s score vector

property scores_#

2d array of integers. scores[c, d] is equal to the width of the widest path from c to d.

Note

Unlike for most other voting systems, scores matrix must be read in rows, in order to comply with our convention for the matrix of duels: c’s score vector is scores[c, :].

property scores_best_to_worst_#

2d array. scores_best_to_worst is the scores of the candidates, from the winner to the last candidate of the election.

scores_best_to_worst[k, j] is the width of the widest path from the k-th best candidate of the election to the j-th.

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.