- class svvamp.RuleKemeny(**kwargs)[source]
Kemeny method.
Options
>>> RuleKemeny.print_options_parameters() cm_option: ['lazy', 'exact']. Default: 'lazy'. icm_option: ['exact']. Default: 'exact'. iia_subset_maximum_size: is_number. Default: 2. im_option: ['lazy', 'exact']. Default: 'lazy'. tm_option: ['lazy', 'exact']. Default: 'exact'. um_option: ['lazy', 'exact']. Default: 'lazy'.
Notes
We find the order on candidates whose total Kendall tau distance to the voters is minimal. The top element of this order is declared the winner. In case several orders are optimal, the first one by lexicographic order is given. This implies that if several winners are possible, the one with lowest index is declared the winner.
For this voting system, even deciding the sincere winner is NP-hard.
is_cm_(): Non-polynomial or non-exact algorithms from superclassRule.is_icm_(): Exact in polynomial time (once the sincere winner is computed).is_im_(): Non-polynomial or non-exact algorithms from superclassRule.is_iia_(): Exact in polynomial time (once the sincere winner is computed).is_tm_(): Exact in the time needed to decide the winner of one election, multiplied byn_c.is_um_(): Non-polynomial or non-exact algorithms from superclassRule.
References
‘Mathematics without numbers’, J. G. Kemeny, 1959.
‘A Consistent Extension of Condorcet’s Election Principle’, H. P. Young and A. Levenglick, 1978.
‘On the approximability of Dodgson and Young elections’, Ioannis Caragiannis et al., 2009.
‘Comparing and aggregating partial orders with Kendall tau distances’, Franz J. Brandenburg, Andreas Gleißner and Andreas Hofmeier, 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 = RuleKemeny()(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 = [2 0 1] candidates_by_scores_best_to_worst [0 2 1] scores_best_to_worst [2 1 0] w = 0 score_w = 2 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 = 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 = lazy 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 = lazy, um_option = lazy, icm_option = exact, 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. This is an optimal Kemeny order.
In case several orders are optimal, the first one by lexicographic order is given. This implies that if several winners are possible, the one with lowest index is declared the winner.
- property scores_
1d array of integers. By convention, scores are integers from 1 to
n_c, withn_cfor the winner and 1 for the last candidate in Kemeny optimal order.