class svvamp.RuleMaximin(**kwargs)[source]

Maximin method.

Options

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

Notes

Candidate c’s score is the minimum of the row matrix_duels_rk[c, :] (except the diagonal term), i.e. the result of candidate c for her worst duel. The candidate with highest score is declared the winner. In case of a tie, the candidate with lowest index wins.

This method meets the Condorcet criterion.

  • is_cm_(): Deciding CM is NP-complete, even for 2 manipulators.

    • cm_option = 'faster': Zuckerman et al. (2011) (cf. below). The difference with option fast is that, if CM is proven possible or impossible, we optimize the bounds only based on UM, and not on CM. Hence this option is as precise as fast to compute is_cm_, but less precise for the bounds necessary_coalition_size_cm_ and sufficient_coalition_size_cm_.

    • cm_option = 'fast': Zuckerman et al. (2011). This approximation algorithm is polynomial and has a multiplicative factor of error of 5/3 on the number of manipulators needed.

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

  • is_icm_(): Exact in polynomial time.

  • is_im_(): Exact in polynomial time.

  • is_iia_(): Exact in polynomial time.

  • is_tm_(): Exact in polynomial time.

  • is_um_(): Exact in polynomial time.

References

‘Complexity of Unweighted Coalitional Manipulation under Some Common Voting Rules’, Lirong Xia et al., 2009.

‘An algorithm for the coalitional manipulation problem under Maximin’, Michael Zuckerman, Omer Lev and Jeffrey S. Rosenschein, 2011.

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 = RuleMaximin()(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 =
[3 2 2]
candidates_by_scores_best_to_worst
[0 1 2]
scores_best_to_worst
[3 2 2]
w = 0
score_w = 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 = False
log_im: im_option = exact
candidates_im =
[0. 0. 0.]

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

********************************
*   Unison Manipulation (UM)   *
********************************
is_um = False
log_um: um_option = exact
candidates_um =
[0. 0. 0.]

*********************************************
*   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 = False
log_cm: cm_option = fast, um_option = exact, tm_option = exact
candidates_cm =
[0. 0. 0.]
necessary_coalition_size_cm =
[0. 2. 3.]
sufficient_coalition_size_cm =
[0. 2. 3.]
property scores_

1d array of integers. scores[c] is the minimum of the row matrix_duels_rk[c, :] (except the diagonal term), i.e. the result of candidate c for her worst duel.

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.