IRV

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

Instant-Runoff Voting (IRV). Also known as Single Transferable Voting, Alternative Vote, Hare method.

Inherits functions and optional parameters from superclasses ElectionResult and Election.

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

The candidate who is ranked first by least voters is eliminated. Then we iterate. Ties are broken in favor of lower-index candidates: in case of a tie, the tied candidate with highest index is eliminated.

CM(): Deciding CM is NP-complete.

  • CM_option = 'fast': Polynomial heuristic. Can prove CM but unable to decide non-CM (except in rare obvious cases).
  • CM_option = 'slow': Rely on ExhaustiveBallot‘s exact algorithm. Non-polynomial heuristic (\(2^C\)). Quite efficient to prove CM or non-CM.
  • CM_option = 'exact': Non-polynomial algorithm (\(C!\)) adapted from Walsh, 2010.

ICM(): Exact in polynomial time.

IM(): Deciding IM is NP-complete.

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

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

TM(): Exact in polynomial time.

UM(): Deciding UM is NP-complete.

  • 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 (\(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.

See also

ExhaustiveBallot, IRVDuels, ICRV, CondorcetAbsIRV. CondorcetVtbIRV.

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).