Kemeny

class svvamp.Kemeny(population, **kwargs)[source]

Kemeny method.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

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 superclass Election.

ICM(): Exact in polynomial time (once the sincere winner is computed).

IM(): Non-polynomial or non-exact algorithms from superclass Election.

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 by C.

UM(): Non-polynomial or non-exact algorithms from superclass Election.

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, with C for the winner and 1 for the last candidate in Kemeny optimal order.

w

Integer (winning candidate).