ExhaustiveBallot

class svvamp.ExhaustiveBallot(population, freeze_options=False, **kwargs)[source]

Exhaustive Ballot.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

Example:
>>> import svvamp
>>> pop = svvamp.PopulationSpheroid(V=100, C=5)
>>> election = svvamp.ExhaustiveBallot(pop)

At each round, voters vote for one non-eliminated candidate. The candidate with least votes is eliminated. Then the next round is held. Unlike IRV, voters actually vote at each round. This does not change anything for sincere voting, but offers a bit more possibilities for the manipulators. In case of a tie, the candidate with highest index is eliminated.

CM():

  • CM_option = 'fast': Polynomial heuristic. Can prove CM but unable to decide non-CM (except in rare obvious cases).
  • CM_option = 'exact': Non-polynomial algorithm (\(2^C\)) adapted from Walsh, 2010.

ICM(): Exact in polynomial time.

IM():

  • IM_option = 'lazy': Lazy algorithm from superclass Election.
  • IM_option = 'exact': Non-polynomial algorithm (\(2^C\)) adapted from Walsh, 2010.

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

TM(): Exact in polynomial time.

UM():

  • UM_option = 'fast': Polynomial heuristic. Can prove UM but unable to decide non-UM (except in rare obvious cases).
  • UM_option = 'exact': Non-polynomial algorithm (\(2^C\)) adapted from Walsh, 2010.

References:

‘Single transferable vote resists strategic voting’, John J. Bartholdi and James B. Orlin, 1991.

‘On The Complexity of Manipulating Elections’, Tom Coleman and Vanessa Teague, 2007.

‘Manipulability of Single Transferable Vote’, Toby Walsh, 2010.

ballots

2d array of integers. ballots[v, r] is the candidate for which voter v votes at round r.

candidates_by_scores_best_to_worst

1d array of integers. candidates_by_scores_best_to_worst is the list of all candidates in the reverse order of their elimination.

By definition, candidates_by_scores_best_to_worst[0] = w.

elimination_path

1d array of integers. Same as candidates_by_scores_best_to_worst, but in the reverse order.

margins

2d array. margins[r, c] is the number of votes that c must lose to be eliminated at round r (all other things being equal). The candidate who is eliminated at round r is the only one for which margins[r, c] = 0.

For eliminated candidates, margins[r, c] = numpy.nan.

scores

2d array. scores[r, c] is the number of voters who vote for candidate c at round r.

For eliminated candidates, scores[r, c] = numpy.nan. At the opposite, scores[r, c] = 0 means that c is present at round r but no voter votes for c.

w

Integer (winning candidate).