RankedPairs¶

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

Tideman’s Ranked Pairs.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

Example:

>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.RankedPairs(pop)

In the matrix of duels matrix_duels_rk, victories (and ties) are sorted by decreasing amplitude. If two duels have the same score, we take first the one where the winner has the smallest index; if there is still a choice to make, we take first the duel where the loser has the highest index.

Starting with the largest victory, we build a directed graph whose nodes are the candidates and edges are victories. But if a victory creates a cycle in the graph, it is not validated and the edge is not added.

At the end, we has a transitive connected directed graph, whose adjacency relation is included in the relation of victories (with ties broken), matrix_victories_rk_ctb. The maximal node of this graph (by topological order) is declared the winner.

This method meets the Condorcet criterion.

CM(): Deciding CM is NP-complete. Non-polynomial or non-exact algorithms from superclass Election.

ICM(): Exact in polynomial time.

IM(): Deciding IM is NP-complete. Non-polynomial or non-exact algorithms from superclass Election.

not_IIA(): Exact in polynomial time.

TM(): Exact in polynomial time.

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

References:

‘Independence of clones as a criterion for voting rules’, Nicolaus Tideman, 1987.

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

‘Schulze and Ranked-Pairs Voting are Fixed-Parameter Tractable to Bribe, Manipulate, and Control’, Lane A. Hemaspaandra, Rahman Lavaee and Curtis Menton, 2012.

‘A Complexity-of-Strategic-Behavior Comparison between Schulze’s Rule and Ranked Pairs’, David Parkes and Lirong Xia, 2012.

candidates_by_scores_best_to_worst¶

1d array of integers. candidates_by_scores_best_to_worst[k] is the k^th candidate by topological order on the graph generated by Ranked Pairs.

By definition, candidates_by_scores_best_to_worst[0] = w.

score_w¶: 1d array. score_w is w‘s score vector: score_w = scores[w, :].

scores¶: 2d array of integers. scores[c, d] is equal to matrix_duels_rk[c, d] iff this duel was validated in Ranked Pairs, 0 otherwise.

Note

Unlike for most other voting systems, scores matrix must be read in rows, in order to comply with our convention for the matrix of duels: c‘s score vector is scores[c, :].

scores_best_to_worst¶

2d array. scores_best_to_worst is the scores of the candidates, from the winner to the last candidate of the election.

scores_best_to_worst[k, j] is the score of the k^th best candidate of the election against the j^th. It is the result in matrix_duels_rk if this duels was validated by Ranked Pairs, 0 otherwise.

w¶: Integer (winning candidate).