Schulze¶

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

Schulze method.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

Example:

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

scores[c, d] is equal to the width of the widest path from candidate c to candidate d in the capacited graph defined by matrix_duels_rk. We say that c is better than d if scores[c, d] > scores[d, c]. Candidate c is a potential winner if no candidate d is better than c.

Among the potential winners, the candidate with lowest index is declared the winner.

Note

In the original Schulze method, ties are broken at random. However, this feature is not supported by SVVAMP because it leads to difficulties for the definition of manipulation itself (and all the more for its implementation).

CM():

CM_option = 'fast': Gaspers et al. (2013). This algorithm is polynomial and has a window of error of 1 manipulator (due to the tie-breaking rule).

CM_option = 'exact': Non-polynomial algorithm from superclass Election.

ICM(): Exact in polynomial time.

IM():

IM_option = 'fast': Gaspers et al. (2013). This algorithm is polynomial and may not be able to decide IM (due to the tie-breaking rule).

IM_option = 'exact': Non-polynomial algorithm from superclass Election.

not_IIA(): Exact in polynomial time.

TM(): Exact in polynomial time.

UM():

UM_option = 'fast': Gaspers et al. (2013). This algorithm is polynomial and has a window of error of 1 manipulator (due to the tie-breaking rule).

UM_option = 'exact': Non-polynomial algorithm from superclass Election.

References:

‘A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method ‘, Markus Schulze, 2011.

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

‘Manipulation and Control Complexity of Schulze Voting’, Curtis Menton and Preetjot Singh, 2012.

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

‘Coalitional Manipulation for Schulze’s Rule’, Serge Gaspers, Thomas Kalinowski, Nina Narodytska and Toby Walsh, 2013.

candidates_by_scores_best_to_worst¶

1d array of integers. candidates_by_scores_best_to_worst[k] is the k^th candidate by number of Schulze-victories, i.e. the number of candidates d such that c is better than d.

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 the width of the widest path from c to d.

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 width of the widest path from the k^th best candidate of the election to the j^th.

w¶: Integer (winning candidate).