Kemeny¶
-
class
svvamp.
Kemeny
(population, **kwargs)[source]¶ Kemeny method.
Inherits functions and optional parameters from superclasses
ElectionResult
andElection
.Example: >>> import svvamp >>> pop = svvamp.PopulationSpheroid(V=100, C=5) >>> election = svvamp.Kemeny(pop)
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.
CM()
: Non-polynomial or non-exact algorithms from superclassElection
.ICM()
: Exact in polynomial time (once the sincere winner is computed).IM()
: Non-polynomial or non-exact algorithms from superclassElection
.not_IIA()
: Exact in polynomial time (once the sincere winner is computed).TM()
: Exact in the time needed to decide the winner of one election, multiplied byC
.UM()
: Non-polynomial or non-exact algorithms from superclassElection
.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.
-
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.
By definition,
candidates_by_scores_best_to_worst[0]
=w
.
-
scores
¶ 1d array of integers. By convention, scores are integers from 1 to
C
, withC
for the winner and 1 for the last candidate in Kemeny optimal order.
-
w
¶ Integer (winning candidate).
-