# -*- coding: utf-8 -*-
"""
Created on 4 dec. 2018, 16:00
Copyright François Durand 2014-2018
fradurand@gmail.com
This file is part of SVVAMP.
SVVAMP is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
SVVAMP is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with SVVAMP. If not, see <http://www.gnu.org/licenses/>.
"""
import numpy as np
from svvamp.rules.rule import Rule
from svvamp.utils.util_cache import cached_property
from svvamp.preferences.profile import Profile
[docs]
class RuleCondorcetSumDefeats(Rule):
"""Condorcet with sum of defeats.
Options
-------
>>> RuleCondorcetSumDefeats.print_options_parameters()
cm_option: ['lazy', 'exact']. Default: 'lazy'.
icm_option: ['lazy']. Default: 'lazy'.
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
-----
An *elementary move* consists of reversing a voter's preference about a pair of candidate ``(c, d)`` (without
demanding that her whole relation of preference stays transitive). The score for candidate ``c`` is minus the
number of *elementary moves* needed so that ``c`` becomes a Condorcet winner. It is the same principle as
Dodgson's method, but without looking for a transitive profile.
In practice:
.. math::
\\texttt{scores}[c] = - \\sum_{c \\text{ does not beat } d}\\left(
\\left\\lfloor\\frac{V}{2}\\right\\rfloor + 1 - \\texttt{matrix_duels_rk}[c, d]
\\right)
In particular, for :attr:`n_v` odd:
.. math::
\\texttt{scores}[c] = - \\sum_{c \\text{ does not beat } d}\\left(
\\left\\lceil\\frac{V}{2}\\right\\rceil - \\texttt{matrix_duels_rk}[c, d]
\\right)
* :meth:`is_cm_`: Non-polynomial or non-exact algorithms from superclass :class:`Rule`.
* :meth:`is_icm_`: Algorithm from superclass :class:`Rule`. It is polynomial and has a window of error of 1
manipulator.
* :meth:`is_im_`: Non-polynomial or non-exact algorithms from superclass :class:`Rule`.
* :meth:`is_iia_`: Non-polynomial or non-exact algorithms from superclass :class:`Rule`. If
:attr:`iia_subset_maximum_size` = 2, it runs in polynomial time and is exact up to ties (which can occur only if
:attr:`n_v` is even).
* :meth:`is_tm_`: Exact in polynomial time.
* :meth:`is_um_`: Non-polynomial or non-exact algorithms from superclass :class:`Rule`.
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 = RuleCondorcetSumDefeats()(profile)
>>> rule.demo_results_(log_depth=0) # doctest: +NORMALIZE_WHITESPACE
<BLANKLINE>
************************
* *
* Election Results *
* *
************************
<BLANKLINE>
***************
* 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. -2. -1.]
candidates_by_scores_best_to_worst
[0 2 1]
scores_best_to_worst
[-0. -1. -2.]
w = 0
score_w = -0.0
total_utility_w = 1.0
<BLANKLINE>
*********************************
* Condorcet efficiency (rk) *
*********************************
w (reminder) = 0
<BLANKLINE>
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
<BLANKLINE>
condorcet_winner_rk = 0
w_is_condorcet_winner_rk = True
w_is_not_condorcet_winner_rk = False
w_missed_condorcet_winner_rk = False
<BLANKLINE>
***************************************
* Condorcet efficiency (relative) *
***************************************
w (reminder) = 0
<BLANKLINE>
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
<BLANKLINE>
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
<BLANKLINE>
***************************************
* Condorcet efficiency (absolute) *
***************************************
w (reminder) = 0
<BLANKLINE>
condorcet_admissible_candidates =
[ True False False]
w_is_condorcet_admissible = True
w_is_not_condorcet_admissible = False
w_missed_condorcet_admissible = False
<BLANKLINE>
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
<BLANKLINE>
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
<BLANKLINE>
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
<BLANKLINE>
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) # doctest: +NORMALIZE_WHITESPACE
<BLANKLINE>
*****************************
* *
* Election Manipulation *
* *
*****************************
<BLANKLINE>
*********************************************
* 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
<BLANKLINE>
****************************************************
* 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 (True) ||
|| || || || || ||
V V || || V V
Condorcet_c_ut_abs_ctb (False) ==> Condorcet_ut_abs_c (True)
|| || || ||
|| V V ||
|| maj_fav_c_rk_ctb (False) ==> maj_fav_c_rk (True) ||
|| || || ||
V V V V
majority_favorite_c_ut_ctb (False) ==> majority_favorite_c_ut (True)
|| ||
V V
IgnMC_c_ctb (False) ==> IgnMC_c (True)
|| ||
V V
InfMC_c_ctb (True) ==> InfMC_c (True)
<BLANKLINE>
*****************************************************
* 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
<BLANKLINE>
**********************
* 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]]
<BLANKLINE>
************************************
* Individual Manipulation (IM) *
************************************
is_im = nan
log_im: im_option = lazy
candidates_im =
[ 0. 0. nan]
<BLANKLINE>
*********************************
* Trivial Manipulation (TM) *
*********************************
is_tm = False
log_tm: tm_option = exact
candidates_tm =
[0. 0. 0.]
<BLANKLINE>
********************************
* Unison Manipulation (UM) *
********************************
is_um = nan
log_um: um_option = lazy
candidates_um =
[ 0. 0. nan]
<BLANKLINE>
*********************************************
* Ignorant-Coalition Manipulation (ICM) *
*********************************************
is_icm = False
log_icm: icm_option = lazy
candidates_icm =
[0. 0. 0.]
necessary_coalition_size_icm =
[0. 6. 4.]
sufficient_coalition_size_icm =
[0. 6. 4.]
<BLANKLINE>
***********************************
* Coalition Manipulation (CM) *
***********************************
is_cm = nan
log_cm: cm_option = lazy, um_option = lazy, tm_option = exact
candidates_cm =
[ 0. 0. nan]
necessary_coalition_size_cm =
[0. 1. 1.]
sufficient_coalition_size_cm =
[0. 2. 3.]
"""
full_name = 'Condorcet Sum Defeats'
abbreviation = 'CSD'
options_parameters = Rule.options_parameters.copy()
def __init__(self, **kwargs):
super().__init__(
with_two_candidates_reduces_to_plurality=True, is_based_on_rk=True,
precheck_icm=False,
log_identity="CONDORCET_SUM_DEFEATS", **kwargs
)
@cached_property
def scores_(self):
"""1d array of integers.
.. math::
\\texttt{scores}[c] = - \\sum_{c \\text{ does not beat } d}\\left(
\\left\\lfloor\\frac{V}{2}\\right\\rfloor + 1 - \\texttt{matrix_duels_rk}[c, d]
\\right)
"""
self.mylog("Compute scores", 1)
scores = np.zeros(self.profile_.n_c)
for c in range(self.profile_.n_c):
scores[c] = - np.sum(np.floor(self.profile_.n_v / 2) + 1
- self.profile_.matrix_duels_rk[c, self.profile_.matrix_victories_rk[:, c] > 0])
return scores
@cached_property
def meets_condorcet_c_rk(self):
return True
@cached_property
def meets_infmc_c_ctb(self):
return True