Borda¶

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

Borda rule.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

Example:

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

Voter v gives (C - 1) points to her top-ranked candidate, (C - 2) to the second, ..., 0 to the last. Ties are broken by natural order on the candidates (lower index wins).

CM(): Deciding CM is NP-complete.

CM_option = 'fast': Zuckerman et al. (2009). This approximation algorithm is polynomial and has a window of error of 1 manipulator.

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

ICM(): Algorithm is polynomial and has a window of error of 1 manipulator.

IM(): Exact in polynomial time.

not_IIA(): Exact in polynomial time.

TM(): Exact in polynomial time.

UM(): Exact in polynomial time.

References:

‘Algorithms for the coalitional manipulation problem’, M. Zuckerman, A. Procaccia and J. Rosenschein, 2009.

‘Unweighted Coalitional Manipulation Under the Borda Rule is NP-Hard’, Nadja Betzler, Rolf Niedermeier and Gerhard Woeginger, 2011.

‘Complexity of and algorithms for the manipulation of Borda, Nanson’s and Baldwin’s voting rules’, Jessica Davies, George Katsirelos, Nina Narodytska, Toby Walsh and Lirong Xia, 2014.

scores¶: 1d array of integers. scores[c] is the total Borda score for candidate c.

w¶

Integer (winning candidate).

Default behavior in superclass ElectionResult:: The candidate with highest value in vector scores is declared the winner. In case of a tie, the tied candidate with lowest index wins.