Iterative Methods¶

The voting methods defined below all follow a similar procedure: iteratively remove “poorly performing” candidates from the profile until there is a “clear winner” in the current stage. The voting methods differ in how they answer the following two questions:

What does it mean for a candidate to “perform poorly”? Different definitions of a poorly performing candidate include the fewest number of first-place votes, the most last-place votes, the least Borda score, etc.
How to break ties when there are more than one candidate that is identified as “poorly performing”? One approach is to remove all candidates that are poorly performing at each round (and if all remaining candidates would be removed, then the remaining candidates are tied for the win). A second approach is to use so-called parallel-universe tiebreaking. On this approach, a candidate A is a winner if there is some poorly perfoming candidate B such that in the profile without B, A is a winner.
What counts as a “clear winner” in the current stage? Possible answers include a candidate with a strict majority of first-place votes, a Condorcet winner, etc.

To illustrate the difference with respect to the first question, consider the voting methods Instant Runoff and Coombs. According to Instant Runoff, a candidate is “poorly performing” if that candidate has the fewest number first-place votes, and according to Coombs, a candidate is “poorly performing” if that candidate has the most last-place votes.

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import instant_runoff, coombs

prof = Profile([[2, 1, 0], [0, 2, 1], [1, 2, 0]], [1, 2, 2])

prof.display()
instant_runoff.display(prof)
coombs.display(prof)

+---+---+---+
| 1 | 2 | 2 |
+---+---+---+
| 2 | 0 | 1 |
| 1 | 2 | 2 |
| 0 | 1 | 0 |
+---+---+---+
Instant Runoff winner is {1}
Coombs winner is {2}

To illustrate the difference with respect to the second question, consider Instant Runoff and Instant Runoff PUT that uses parallel-universe tiebreaking.

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import instant_runoff, instant_runoff_put

prof = Profile([[1, 2, 0], [2, 1, 0], [0, 1, 2]], [1, 1, 1])

prof.display()
instant_runoff.display(prof)
instant_runoff_put.display(prof)

+---+---+---+
| 1 | 1 | 1 |
+---+---+---+
| 1 | 2 | 0 |
| 2 | 1 | 1 |
| 0 | 0 | 2 |
+---+---+---+
Instant Runoff winners are {0, 1, 2}
Instant Runoff PUT winners are {1, 2}

Instant Runoff¶

pref_voting.iterative_methods.instant_runoff(profile, curr_cands=None)[source]¶

If there is a majority winner then that candidate is the winner. If there is no majority winner, then remove all candidates that are ranked first by the fewest number of voters. Continue removing candidates with the fewest number first-place votes until there is a candidate with a majority of first place votes.

Important

If there is more than one candidate with the fewest number of first-place votes, then all such candidates are removed from the profile.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

See also

Instant Runoff is also known as “Ranked Choice”, “Hare”, and “Alternative Vote”.

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import instant_runoff, ranked_choice, alternative_vote, hare

prof = Profile([[2, 1, 0], [0, 2, 1], [1, 2, 0]], [1, 2, 2])

prof.display()
instant_runoff.display(prof)
ranked_choice.display(prof)
alternative_vote.display(prof)
hare.display(prof)

+---+---+---+
| 1 | 2 | 2 |
+---+---+---+
| 2 | 0 | 1 |
| 1 | 2 | 2 |
| 0 | 1 | 0 |
+---+---+---+
Instant Runoff winner is {1}
Ranked Choice winner is {1}
Alternative Vote winner is {1}
Hare winner is {1}

Instant Runoff TB¶

pref_voting.iterative_methods.instant_runoff_tb(profile, curr_cands=None, tie_breaker=None)[source]¶

Instant Runoff (instant_runoff) with tie breaking: If there is more than one candidate with the fewest number of first-place votes, then remove the candidate with lowest in the tie_breaker ranking from the profile.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands
tie_breaker (List[int]) – A list of the candidates in the profile to be used as a tiebreaker.

Returns:

A sorted list of candidates

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import instant_runoff, instant_runoff_tb

prof = Profile([[1, 2, 0], [2, 1, 0], [0, 1, 2]], [1, 1, 1])

prof.display()
print("no tiebreaker")
instant_runoff.display(prof)
print("tie_breaker = [0, 1, 2]")
instant_runoff_tb.display(prof)
print("tie_breaker = [1, 2, 0]")
instant_runoff_tb.display(prof, tie_breaker=[1, 2, 0])

+---+---+---+
| 1 | 1 | 1 |
+---+---+---+
| 1 | 2 | 0 |
| 2 | 1 | 1 |
| 0 | 0 | 2 |
+---+---+---+
no tiebreaker
Instant Runoff winners are {0, 1, 2}
tie_breaker = [0, 1, 2]
Instant Runoff TB winner is {1}
tie_breaker = [1, 2, 0]
Instant Runoff TB winner is {2}

Instant Runoff PUT¶

pref_voting.iterative_methods.instant_runoff_put(profile, curr_cands=None)[source]¶

Instant Runoff (instant_runoff()) with parallel universe tie-breaking (PUT), defined recursively: if there is a candidate with a strict majority of first-place votes, that candidate is the IRV-PUT winner; otherwise a candidate x is an IRV-PUT winner if there is some candidate y with a minimal number of first-place votes such that after removing y from the profile, x is an IRV-PUT winner.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

Warning

This will take a long time on profiles with many candidates having the same plurality scores

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import instant_runoff, instant_runoff_tb, instant_runoff_put

prof = Profile([[1, 2, 0], [2, 1, 0], [0, 1, 2]], [1, 1, 1])

prof.display()
print("no tiebreaker")
instant_runoff.display(prof)
print("tie_breaker = [0, 1, 2]")
instant_runoff_tb.display(prof, tie_breaker=[0, 1, 2])
print("tie_breaker = [0, 2, 1]")
instant_runoff_tb.display(prof, tie_breaker=[0, 2, 1])
print("tie_breaker = [1, 0, 2]")
instant_runoff_tb.display(prof, tie_breaker=[1, 0, 2])
print("tie_breaker = [1, 2, 0]")
instant_runoff_tb.display(prof, tie_breaker=[1, 2, 0])
print("tie_breaker = [2, 0, 1]")
instant_runoff_tb.display(prof, tie_breaker=[2, 0, 1])
print("tie_breaker = [2, 1, 0]")
instant_runoff_tb.display(prof, tie_breaker=[2, 1, 0])
print()
instant_runoff_put.display(prof)

+---+---+---+
| 1 | 1 | 1 |
+---+---+---+
| 1 | 2 | 0 |
| 2 | 1 | 1 |
| 0 | 0 | 2 |
+---+---+---+
no tiebreaker
Instant Runoff winners are {0, 1, 2}
tie_breaker = [0, 1, 2]
Instant Runoff TB winner is {1}
tie_breaker = [0, 2, 1]
Instant Runoff TB winner is {1}
tie_breaker = [1, 0, 2]
Instant Runoff TB winner is {2}
tie_breaker = [1, 2, 0]
Instant Runoff TB winner is {2}
tie_breaker = [2, 0, 1]
Instant Runoff TB winner is {1}
tie_breaker = [2, 1, 0]
Instant Runoff TB winner is {1}

Instant Runoff PUT winners are {1, 2}

Instant Runoff with Explanation¶

pref_voting.iterative_methods.instant_runoff_with_explanation(profile, curr_cands=None)[source]¶

Instant Runoff with an explanation. In addition to the winner(s), return the order in which the candidates are eliminated as a list of lists.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

A list describing the order in which candidates are eliminated

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import instant_runoff, instant_runoff_with_explanation


prof = Profile([[2, 1, 0], [0, 2, 1], [1, 2, 0]], [1, 2, 2])
prof.display()
instant_runoff.display(prof)
ws, exp = instant_runoff_with_explanation(prof)
print(f"winning set: {ws}")
print(f"order of elimination: {exp}")

prof = Profile([[1, 2, 0], [2, 1, 0], [0, 1, 2]], [1, 1, 1])
prof.display()
instant_runoff.display(prof)
ws, exp = instant_runoff_with_explanation(prof)
print(f"winning set: {ws}")
print(f"order of elimination: {exp}")

prof = Profile([[2, 0, 1, 3], [2, 0, 3, 1], [3, 0, 1, 2],  [3, 2, 1, 0], [0, 2, 1, 3]], [1, 1, 1, 1, 1])
prof.display()
instant_runoff.display(prof)
ws, exp = instant_runoff_with_explanation(prof)
print(f"winning set: {ws}")
print(f"order of elimination: {exp}")

+---+---+---+
| 1 | 2 | 2 |
+---+---+---+
| 2 | 0 | 1 |
| 1 | 2 | 2 |
| 0 | 1 | 0 |
+---+---+---+
Instant Runoff winner is {1}
winning set: [1]
order of elimination: [[2]]
+---+---+---+
| 1 | 1 | 1 |
+---+---+---+
| 1 | 2 | 0 |
| 2 | 1 | 1 |
| 0 | 0 | 2 |
+---+---+---+
Instant Runoff winners are {0, 1, 2}
winning set: [0, 1, 2]
order of elimination: [[0, 1, 2]]
+---+---+---+---+---+
| 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+
| 2 | 2 | 3 | 3 | 0 |
| 0 | 0 | 0 | 2 | 2 |
| 1 | 3 | 1 | 1 | 1 |
| 3 | 1 | 2 | 0 | 3 |
+---+---+---+---+---+
Instant Runoff winner is {2}
winning set: [2]
order of elimination: [[1], [0]]

Instant Runoff for Truncated Linear Orders¶

pref_voting.iterative_methods.instant_runoff_for_truncated_linear_orders(profile, curr_cands=None, threshold=None, hide_warnings=True)[source]¶

Instant Runoff for Truncated Linear Orders. Iteratively remove the candidates with the fewest number of first place votes, until there is a candidate with more than the threshold number of first-place votes. If a threshold is not set, then it is strictly more than half of the non-empty ballots.

Parameters:

profile (ProfileWithTies) – An anonymous profile with no ties in the ballots (note that ProfileWithTies allows for truncated linear orders).
threshold (int, float, optional) – The threshold needed to win the election. If it is not set, then it is strictly more than half of the remaining ballots.
hide_warnings (bool, optional) – Show or hide the warnings when more than one candidate is eliminated in a round.

Returns:

A sorted list of candidates

Note

This is the simultaneous version of instant runoff, not the parallel-universe tiebreaking version. It is intended to be run on profiles with large number of voters in which there is a very low probability of a tie in the fewest number of first place votes. A warning is displayed when more than one candidate is eliminated.

Example:

from pref_voting.profiles_with_ties import ProfileWithTies
from pref_voting.iterative_methods import instant_runoff_for_truncated_linear_orders

prof = ProfileWithTies([{0:1, 1:1},{0:1, 1:2, 2:3, 3:4}, {0:1, 1:3, 2:3}, {3:2}, {0:1}, {0:1}, {}, {}])
prof.display()

tprof, report = prof.truncate_overvotes()
for r, new_r, count in report:
    print(f"{r} --> {new_r}: {count}")
tprof.display()
instant_runoff_for_truncated_linear_orders.display(tprof)

+-----+---+-----+---+---+---+---+---+
|  1  | 1 |  1  | 1 | 1 | 1 | 1 | 1 |
+-----+---+-----+---+---+---+---+---+
| 0 1 | 0 |  0  | 3 | 0 | 0 |   |   |
|     | 1 | 1 2 |   |   |   |   |   |
|     | 2 |     |   |   |   |   |   |
|     | 3 |     |   |   |   |   |   |
+-----+---+-----+---+---+---+---+---+
( 0  1 )  --> : 1
0 ( 1  2 )  --> 0 : 1
+---+---+---+---+---+---+---+---+
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+
|   | 0 | 0 | 3 | 0 | 0 |   |   |
|   | 1 |   |   |   |   |   |   |
|   | 2 |   |   |   |   |   |   |
|   | 3 |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
Instant Runoff winner is {0}

Plurality With Runoff PUT¶

pref_voting.iterative_methods.plurality_with_runoff_put(profile, curr_cands=None)[source]¶

If there is a majority winner then that candidate is the Plurality with Runoff winner. Otherwise hold a runoff between the top two candidates: the candidate with the most first place votes and the candidate with the 2nd most first place votes (or perhaps tied for the most first place votes). In the case of multiple candidates tied for the most or 2nd most first place votes, use parallel-universe tiebreaking: a candidate is a Plurality with Runoff winner if it is a winner in some runoff as described. If the candidates are all tied for the most first place votes, then all candidates are winners.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

Note

Plurality with Runoff is the same as Instant Runoff when there are 3 candidates, but they can give different answers with 4 or more candidates.

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import instant_runoff, plurality_with_runoff_put

prof = Profile([[0, 1, 2, 3], [3, 1, 2, 0], [2, 0, 3, 1], [1, 2, 3, 0], [2, 3, 0, 1], [0, 3, 2, 1]], [2, 1, 2, 2, 1, 2])
prof.display()
instant_runoff.display(prof)
plurality_with_runoff_put.display(prof)

+---+---+---+---+---+---+
| 2 | 1 | 2 | 2 | 1 | 2 |
+---+---+---+---+---+---+
| 0 | 3 | 2 | 1 | 2 | 0 |
| 1 | 1 | 0 | 2 | 3 | 3 |
| 2 | 2 | 3 | 3 | 0 | 2 |
| 3 | 0 | 1 | 0 | 1 | 1 |
+---+---+---+---+---+---+
Instant Runoff winner is {0}
PluralityWRunoff PUT winner is {2}

Benham¶

pref_voting.iterative_methods.benham(profile, curr_cands=None)[source]¶

As long as the profile has no Condorcet winner, eliminate the candidate with the lowest plurality score.

Important

If there is more than one candidate with the fewest number of first-place votes, then all such candidates are removed from the profile.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

See also

Related functions: pref_voting.iterative_methods.benham_put()

Benham TB¶

pref_voting.iterative_methods.benham_tb(profile, curr_cands=None, tie_breaker=None)[source]¶

Benham (benham) with tie breaking: If there is more than one candidate with the fewest number of first-place votes, then remove the candidate with lowest in the tie_breaker ranking from the profile.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands
tie_breaker (List[int]) – A list of the candidates in the profile to be used as a tiebreaker.

Returns:

A sorted list of candidates

Benham PUT¶

pref_voting.iterative_methods.benham_put(profile, curr_cands=None)[source]¶

Benham (benham()) with parallel universe tie-breaking (PUT), defined recursively: if there is a Condorcet winner, that candidate is the Benham-PUT winner; otherwise a candidate x is a Benham-PUT winner if there is some candidate y with minimal plurality score such that after removing y from the profile, x is a Benham-PUT winner.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

Warning

This will take a long time on profiles with many candidates having the same plurality scores.

Bottom-Two-Runoff Instant Runoff¶

pref_voting.iterative_methods.bottom_two_runoff_instant_runoff(profile, curr_cands=None)[source]¶

Find the two candidates with the lowest two plurality scores, remove the one who loses head-to-head to the other, and repeat until a single candidate remains.

If there is a tie for lowest or second lowest plurality score, consider all head-to-head matches between a candidate with lowest and a candidate with second lowest plurality score, and remove all the losers of the head-to-head matches, unless this would remove all candidates.

Note

BTR-IRV is a Condorcet consistent voting method, i.e., if a Condorcet winner exists, then BTR-IRV will elect the Condorcet winner.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

Bottom-Two-Runoff Instant Runoff PUT¶

pref_voting.iterative_methods.bottom_two_runoff_instant_runoff_put(profile, curr_cands=None)[source]¶

Find the two candidates with the lowest two plurality scores, remove the one who loses head-to-head to the other, and repeat until a single candidate remains. Parallel-universe tiebreaking is used to break ties for lowest or second lowest plurality scores.

Note

BTR-IRV is a Condorcet consistent voting method, i.e., if a Condorcet winner exists, then BTR-IRV will elect the Condorcet winner.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

Tideman’s Alternative¶

pref_voting.iterative_methods.tideman_alternative(vm)[source]¶

Given a voting method vm, returns a voting method that restricts the profile to the set of vm winners, then eliminates all the candidate with the fewest first-place votes, and then repeats until there is only one vm winner. If at some stage all remaining candidates are tied for the fewest number of first-place votes, then all remaining candidates win.

Parameters:: vm (VotingMethod) – A voting method.
Returns:: The Tideman Alternative PUT version of vm.

Tideman’s Alternative PUT¶

pref_voting.iterative_methods.tideman_alternative_put(vm)[source]¶

Given a voting method vm, returns a voting method that restricts the profile to the set of vm winners, then eliminates the candidate with the fewest first-place votes, and then repeats until there is only one vm winner. Parallel-universe tiebreaking is used when there are multiple candidates with the fewest first-place votes.

Parameters:: vm (VotingMethod) – A voting method.
Returns:: The Tideman Alternative PUT version of vm.

Coombs¶

pref_voting.iterative_methods.coombs(profile, curr_cands=None)[source]¶

If there is a majority winner then that candidate is the Coombs winner. If there is no majority winner, then remove all candidates that are ranked last by the greatest number of voters. Continue removing candidates with the most last-place votes until there is a candidate with a majority of first place votes.

Important

If there is more than one candidate with the largest number of last-place votes, then all such candidates are removed from the profile.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

See also

pref_voting.iterative_methods.coombs_with_tb(), pref_voting.iterative_methods.coomb_put(), pref_voting.iterative_methods.coombs_with_explanation()

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import instant_runoff, coombs

prof = Profile([[2, 1, 0], [0, 2, 1], [1, 2, 0]], [1, 2, 2])

prof.display()
coombs.display(prof)
instant_runoff.display(prof)

+---+---+---+
| 1 | 2 | 2 |
+---+---+---+
| 2 | 0 | 1 |
| 1 | 2 | 2 |
| 0 | 1 | 0 |
+---+---+---+
Coombs winner is {2}
Instant Runoff winner is {1}

Coombs TB¶

pref_voting.iterative_methods.coombs_tb(profile, curr_cands=None, tie_breaker=None)[source]¶

Coombs with a fixed tie-breaking rule: The tie-breaking rule is any linear order (i.e., list) of the candidates. The default rule is to order the candidates as follows: 0,….,num_cands-1.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands
tie_breaker (List[int]) – A list of the candidates in the profile to be used as a tiebreaker.

Returns:

A sorted list of candidates

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import coombs, coombs_tb

prof = Profile([[2, 0, 1], [0, 2, 1], [1, 0, 2], [2, 1, 0], [0, 1, 2]], [1, 1, 1, 2, 1])
prof.display()
print("no tiebreaker")
coombs.display(prof)
print("tie_breaker = [0, 1, 2]")
coombs_tb.display(prof)
print("tie_breaker = [2, 1, 0]")
coombs_tb.display(prof, tie_breaker=[2, 1, 0])

+---+---+---+---+---+
| 1 | 1 | 1 | 2 | 1 |
+---+---+---+---+---+
| 2 | 0 | 1 | 2 | 0 |
| 0 | 2 | 0 | 1 | 1 |
| 1 | 1 | 2 | 0 | 2 |
+---+---+---+---+---+
no tiebreaker
Coombs winners are {0, 1, 2}
tie_breaker = [0, 1, 2]
Coombs TB winner is {2}
tie_breaker = [2, 1, 0]
Coombs TB winner is {0}

Coombs PUT¶

pref_voting.iterative_methods.coombs_put(profile, curr_cands=None)[source]¶

Coombs with parallel universe tie-breaking (PUT), defined recursively: if there is a candidate with a strict majority of first-place votes, that candidate is the Coombs-PUT winner; otherwise a candidate x is a Coombs-PUT winner if there is some candidate y with a maximal number of last-place votes such that after removing y from the profile, x is a Coombs-PUT winner.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

Warning

This will take a long time on profiles with many candidates having the same number of last-place votes.

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import coombs, coombs_tb, coombs_put

prof = Profile([[2, 0, 1], [1, 0, 2], [0, 1, 2]], [2, 1, 1])

prof.display()
print("no tiebreaker")
coombs.display(prof)
print("tie_breaker = [0, 1, 2]")
coombs_tb.display(prof, tie_breaker=[0, 1, 2])
print("tie_breaker = [0, 2, 1]")
coombs_tb.display(prof, tie_breaker=[0, 2, 1])
print("tie_breaker = [1, 0, 2]")
coombs_tb.display(prof, tie_breaker=[1, 0, 2])
print("tie_breaker = [1, 2, 0]")
coombs_tb.display(prof, tie_breaker=[1, 2, 0])
print("tie_breaker = [2, 0, 1]")
coombs_tb.display(prof, tie_breaker=[2, 0, 1])
print("tie_breaker = [2, 1, 0]")
coombs_tb.display(prof, tie_breaker=[2, 1, 0])
print()
coombs_put.display(prof)

+---+---+---+
| 2 | 1 | 1 |
+---+---+---+
| 2 | 1 | 0 |
| 0 | 0 | 1 |
| 1 | 2 | 2 |
+---+---+---+
no tiebreaker
Coombs winner is {0}
tie_breaker = [0, 1, 2]
Coombs TB winner is {2}
tie_breaker = [0, 2, 1]
Coombs TB winner is {0}
tie_breaker = [1, 0, 2]
Coombs TB winner is {2}
tie_breaker = [1, 2, 0]
Coombs TB winner is {0}
tie_breaker = [2, 0, 1]
Coombs TB winner is {0}
tie_breaker = [2, 1, 0]
Coombs TB winner is {0}

Coombs PUT winners are {0, 2}

Coombs with Explanation¶

pref_voting.iterative_methods.coombs_with_explanation(profile, curr_cands=None)[source]¶

Coombs with an explanation. In addition to the winner(s), return the order in which the candidates are eliminated as a list of lists.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

A list describing the order in which candidates are eliminated

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import coombs, coombs_with_explanation


prof = Profile([[2, 1, 0], [0, 2, 1], [1, 2, 0]], [1, 2, 2])
prof.display()
coombs.display(prof)
ws, exp = coombs_with_explanation(prof)
print(f"winning set: {ws}")
print(f"order of elimination: {exp}")

prof = Profile([[1, 0, 3, 2], [2, 3, 1, 0], [2, 0, 3, 1], [1, 2, 3, 0]], [1, 1, 1, 1])
prof.display()
coombs.display(prof)
ws, exp = coombs_with_explanation(prof)
print(f"winning set: {ws}")
print(f"order of elimination: {exp}")

+---+---+---+
| 1 | 2 | 2 |
+---+---+---+
| 2 | 0 | 1 |
| 1 | 2 | 2 |
| 0 | 1 | 0 |
+---+---+---+
Coombs winner is {2}
winning set: [2]
order of elimination: [[0]]
+---+---+---+---+
| 1 | 1 | 1 | 1 |
+---+---+---+---+
| 1 | 2 | 2 | 1 |
| 0 | 3 | 0 | 2 |
| 3 | 1 | 3 | 3 |
| 2 | 0 | 1 | 0 |
+---+---+---+---+
Coombs winner is {2}
winning set: [2]
order of elimination: [[0], [1]]

Baldwin¶

pref_voting.iterative_methods.baldwin(profile, curr_cands=None)[source]¶

Iteratively remove all candidates with the lowest Borda score until a single candidate remains. If, at any stage, all candidates have the same Borda score, then all (remaining) candidates are winners.

Note

Baldwin is a Condorcet consistent voting method, i.e., if a Condorcet winner exists, then Baldwin will elect the Condorcet winner.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

See also

pref_voting.iterative_methods.baldwin_with_tb(), pref_voting.iterative_methods.baldwin(), pref_voting.iterative_methods.baldwin_with_explanation()

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import baldwin

prof = Profile([[1, 0, 2, 3], [3, 1, 0, 2], [2, 0, 3, 1]], [2, 1, 1])

prof.display()
baldwin.display(prof)

+---+---+---+
| 2 | 1 | 1 |
+---+---+---+
| 1 | 3 | 2 |
| 0 | 1 | 0 |
| 2 | 0 | 3 |
| 3 | 2 | 1 |
+---+---+---+
Baldwin winner is {1}

Baldwin TB¶

pref_voting.iterative_methods.baldwin_tb(profile, curr_cands=None, tie_breaker=None)[source]¶

Baldwin with a fixed tie-breaking rule: The tie-breaking rule is any linear order (i.e., list) of the candidates. The default rule is to order the candidates as follows: 0,….,num_cands-1.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands
tie_breaker (List[int]) – A list of the candidates in the profile to be used as a tiebreaker.

Returns:

A sorted list of candidates

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import baldwin, baldwin_tb

prof = Profile([[0, 2, 1, 3], [1, 3, 0, 2], [2, 3, 0, 1]], [1, 1, 1])
prof.display()
print("no tiebreaker")
baldwin.display(prof)
print("tie_breaker = [0, 1, 2, 3]")
baldwin_tb.display(prof)
print("tie_breaker = [2, 1, 0, 3]")
baldwin_tb.display(prof, tie_breaker=[2, 1, 0, 3])

+---+---+---+
| 1 | 1 | 1 |
+---+---+---+
| 0 | 1 | 2 |
| 2 | 3 | 3 |
| 1 | 0 | 0 |
| 3 | 2 | 1 |
+---+---+---+
no tiebreaker
Baldwin winner is {0}
tie_breaker = [0, 1, 2, 3]
Baldwin TB winner is {2}
tie_breaker = [2, 1, 0, 3]
Baldwin TB winner is {3}

Baldwin PUT¶

pref_voting.iterative_methods.baldwin_put(profile, curr_cands=None)[source]¶

Baldwin with parallel universe tie-breaking (PUT), defined recursively: if there is a single candidate in the profile, that candidate wins; otherwise a candidate x is a Baldwin-PUT winner if there is some candidate y with a minimal Borda score such that after removing y from the profile, x is a Baldwin-PUT winner.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import baldwin, baldwin_tb, baldwin_put

prof = Profile([[1, 2, 0], [0, 1, 2], [2, 0, 1]], [1, 3, 2])

prof.display()
print("no tiebreaker")
baldwin.display(prof)
print("tie_breaker = [0, 1, 2]")
baldwin_tb.display(prof, tie_breaker=[0, 1, 2])
print("tie_breaker = [0, 2, 1]")
baldwin_tb.display(prof, tie_breaker=[0, 2, 1])
print("tie_breaker = [1, 0, 2]")
baldwin_tb.display(prof, tie_breaker=[1, 0, 2])
print("tie_breaker = [1, 2, 0]")
baldwin_tb.display(prof, tie_breaker=[1, 2, 0])
print("tie_breaker = [2, 0, 1]")
baldwin_tb.display(prof, tie_breaker=[2, 0, 1])
print("tie_breaker = [2, 1, 0]")
baldwin_tb.display(prof, tie_breaker=[2, 1, 0])
print()
baldwin_put.display(prof)

+---+---+---+
| 1 | 3 | 2 |
+---+---+---+
| 1 | 0 | 2 |
| 2 | 1 | 0 |
| 0 | 2 | 1 |
+---+---+---+
no tiebreaker
Baldwin winner is {0}
tie_breaker = [0, 1, 2]
Baldwin TB winner is {2}
tie_breaker = [0, 2, 1]
Baldwin TB winner is {0}
tie_breaker = [1, 0, 2]
Baldwin TB winner is {2}
tie_breaker = [1, 2, 0]
Baldwin TB winner is {0}
tie_breaker = [2, 0, 1]
Baldwin TB winner is {0}
tie_breaker = [2, 1, 0]
Baldwin TB winner is {0}

Baldwin PUT winners are {0, 2}

Baldwin with Explanation¶

pref_voting.iterative_methods.baldwin_with_explanation(profile, curr_cands=None)[source]¶

Baldwin with an explanation. In addition to the winner(s), return the order in which the candidates are eliminated as a list of dictionaries specifying the Borda scores in the profile restricted to the candidates that have not been eliminated.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

A list describing for each round, the candidates that are eliminated and the Borda scores of the remaining candidates (in the profile restricted to candidates that have not been eliminated)

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import baldwin, baldwin_with_explanation

prof = Profile([[2, 1, 0], [0, 2, 1], [1, 2, 0]], [1, 2, 2])
prof.display()
baldwin.display(prof)
ws, exp = baldwin_with_explanation(prof)
print(f"winning set: {ws}")
print(f"order of elimination: {exp}")

prof = Profile([[1, 0, 3, 2], [2, 3, 1, 0], [2, 0, 3, 1], [1, 2, 3, 0]], [1, 1, 1, 1])
prof.display()
baldwin.display(prof)
ws, exp = baldwin_with_explanation(prof)
print(f"winning set: {ws}")
print(f"order of elimination: {exp}")

+---+---+---+
| 1 | 2 | 2 |
+---+---+---+
| 2 | 0 | 1 |
| 1 | 2 | 2 |
| 0 | 1 | 0 |
+---+---+---+
Baldwin winner is {2}
winning set: [2]
order of elimination: [[[0], {0: 4, 1: 5, 2: 6}], [[1], {1: 2, 2: 3}]]
+---+---+---+---+
| 1 | 1 | 1 | 1 |
+---+---+---+---+
| 1 | 2 | 2 | 1 |
| 0 | 3 | 0 | 2 |
| 3 | 1 | 3 | 3 |
| 2 | 0 | 1 | 0 |
+---+---+---+---+
Baldwin winners are {1, 2}
winning set: [1, 2]
order of elimination: [[[0], {0: 4, 1: 7, 2: 8, 3: 5}], [[3], {1: 4, 2: 5, 3: 3}], [[1, 2], {1: 2, 2: 2}]]

Nanson¶

Strict Nanson¶

pref_voting.iterative_methods.strict_nanson(profile, curr_cands=None)[source]¶

Iteratively remove all candidates with the Borda score strictly below the average Borda score until one candidate remains. If, at any stage, all candidates have the same Borda score, then all (remaining) candidates are winners.

Note

Strict Nanson is a Condorcet consistent voting method, i.e., if a Condorcet winner exists, then Strict Nanson will elect the Condorcet winner.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import strict_nanson

prof = Profile([[2, 1, 0, 3], [0, 2, 1, 3], [1, 3, 0, 2], [0, 3, 2, 1]], [2, 1, 1, 1])

prof.display()
strict_nanson.display(prof)

+---+---+---+---+
| 2 | 1 | 1 | 1 |
+---+---+---+---+
| 2 | 0 | 1 | 0 |
| 1 | 2 | 3 | 3 |
| 0 | 1 | 0 | 2 |
| 3 | 3 | 2 | 1 |
+---+---+---+---+
Strict Nanson winner is {0}

Strict Nanson with Explanation¶

pref_voting.iterative_methods.strict_nanson_with_explanation(profile, curr_cands=None)[source]¶

Strict Nanson with an explanation. In addition to the winner(s), return the order in which the candidates are eliminated as a list of dictionaries specifying the Borda scores in the profile restricted to the candidates that have not been eliminated and the average Borda score.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

A list describing for each round, the candidates that are eliminated and the Borda scores of the remaining candidates (in the profile restricted to candidates that have not been eliminated)

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import strict_nanson_with_explanation

prof = Profile([[2, 1, 0, 3], [0, 2, 1, 3], [1, 3, 0, 2], [0, 3, 2, 1]], [2, 1, 1, 1])

prof.display()
print(strict_nanson_with_explanation(prof))

+---+---+---+---+
| 2 | 1 | 1 | 1 |
+---+---+---+---+
| 2 | 0 | 1 | 0 |
| 1 | 2 | 3 | 3 |
| 0 | 1 | 0 | 2 |
| 3 | 3 | 2 | 1 |
+---+---+---+---+
([0], [{'avg_borda_score': 7.5, 'elim_cands': [3], 'borda_scores': {0: 9, 1: 8, 2: 9, 3: 4}}, {'avg_borda_score': 5.0, 'elim_cands': [1], 'borda_scores': {0: 5, 1: 4, 2: 6}}, {'avg_borda_score': 2.5, 'elim_cands': [2], 'borda_scores': {0: 3, 2: 2}}])

Weak Nanson¶

pref_voting.iterative_methods.weak_nanson(profile, curr_cands=None)[source]¶

Iteratively remove all candidates with Borda score less than or equal the average Borda score until one candidate remains. If, at any stage, all candidates have the same Borda score, then all (remaining) candidates are winners.

Note

Weak Nanson is a Condorcet consistent voting method, i.e., if a Condorcet winner exists, then Weak Nanson will elect the Condorcet winner.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import weak_nanson

prof = Profile([[2, 1, 0, 3], [0, 2, 1, 3], [1, 3, 0, 2], [0, 3, 2, 1]], [2, 1, 1, 1])

prof.display()
weak_nanson.display(prof)

+---+---+---+---+
| 2 | 1 | 1 | 1 |
+---+---+---+---+
| 2 | 0 | 1 | 0 |
| 1 | 2 | 3 | 3 |
| 0 | 1 | 0 | 2 |
| 3 | 3 | 2 | 1 |
+---+---+---+---+
Weak Nanson winner is {2}

Weak Nanson with Explanation¶

pref_voting.iterative_methods.weak_nanson_with_explanation(profile, curr_cands=None)[source]¶

Weak Nanson with an explanation. In addition to the winner(s), return the order in which the candidates are eliminated as a list of dictionaries specifying the Borda scores in the profile restricted to the candidates that have not been eliminated and the average Borda score.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

A list describing for each round, the candidates that are eliminated and the Borda scores of the remaining candidates (in the profile restricted to candidates that have not been eliminated)

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import weak_nanson_with_explanation

prof = Profile([[2, 1, 0, 3], [0, 2, 1, 3], [1, 3, 0, 2], [0, 3, 2, 1]], [2, 1, 1, 1])

prof.display()
print(weak_nanson_with_explanation(prof))

+---+---+---+---+
| 2 | 1 | 1 | 1 |
+---+---+---+---+
| 2 | 0 | 1 | 0 |
| 1 | 2 | 3 | 3 |
| 0 | 1 | 0 | 2 |
| 3 | 3 | 2 | 1 |
+---+---+---+---+
([2], [{'avg_borda_score': 7.5, 'elim_cands': [3], 'borda_scores': {0: 9, 1: 8, 2: 9, 3: 4}}, {'avg_borda_score': 5.0, 'elim_cands': [0, 1], 'borda_scores': {0: 5, 1: 4, 2: 6}}])

Raynaud¶

pref_voting.iterative_methods.raynaud(edata, curr_cands=None, score_method='margins')[source]¶

Iteratively remove the candidate(s) whose worst loss is biggest, unless all candidates have the same worst loss. See https://electowiki.org/wiki/Raynaud.

Parameters:

edata (Profile, ProfileWithTies, MarginGraph) – Any election data that has a margin method.
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands.
score_method (str, optional) – Options include “margins” (the default), “winning” assigns to each candidate \(c\) the maximum support of a candidate majority preferred to \(c\), and “pairwise_opposition” assigns to each candidate \(c\) the maximum support of any candidate over \(c\). These scores only lead to different results on non-linear profiles.

Returns:

A sorted list of candidates.

Woodall¶

pref_voting.iterative_methods.woodall(profile, curr_cands=None)[source]¶

If there is a single member of the Smith Set (i.e., a Condorcet winner) then that candidate is the winner. If there the Smith Set contains more than one candidate, then remove all candidates that are ranked first by the fewest number of voters. Continue removing candidates with the fewest number first-place votes until there is a single member of the originally Smith Set remaining.

Important

If there is more than one candidate with the fewest number of first-place votes, then all such candidates are removed from the profile.

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

Iterated Removal of Condorcet Loser¶

pref_voting.iterative_methods.iterated_removal_cl(edata, curr_cands=None)[source]¶

Iteratively remove candidates that are Condorcet losers until there are no Condorcet losers. A candidate \(c\) is a Condorcet loser when every other candidate is majority preferred to \(c\).

Parameters:

edata (Profile, ProfileWithTies, MajorityGraph, MarginGraph) – Any election data that has a condorcet_loser method.
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

Example:

from pref_voting.profiles import Profile
from pref_voting.profiles_with_ties import ProfileWithTies
from pref_voting.iterative_methods import iterated_removal_cl

prof = Profile([[2, 1, 3, 0], [2, 1, 0, 3], [3, 1, 2, 0], [1, 2, 3, 0]], [1, 1, 1, 1])

prof.display()
iterated_removal_cl.display(prof)
iterated_removal_cl.display(prof.majority_graph())
iterated_removal_cl.display(prof.margin_graph())

prof2 = ProfileWithTies([{2:1, 1:1, 3:2, 0:3}, {2:1, 1:2, 0:3, 3:4}, {3:1, 1:2, 2:3, 0:4}, {1:1, 2:2, 3:3, 0:4}], [1, 1, 1, 1])

prof2.display()
iterated_removal_cl.display(prof2)

+---+---+---+---+
| 1 | 1 | 1 | 1 |
+---+---+---+---+
| 2 | 2 | 3 | 1 |
| 1 | 1 | 1 | 2 |
| 3 | 0 | 2 | 3 |
| 0 | 3 | 0 | 0 |
+---+---+---+---+
Iterated Removal Condorcet Loser winners are {1, 2}
Iterated Removal Condorcet Loser winners are {1, 2}
Iterated Removal Condorcet Loser winners are {1, 2}
+-----+---+---+---+
|  1  | 1 | 1 | 1 |
+-----+---+---+---+
| 2 1 | 2 | 3 | 1 |
|  3  | 1 | 1 | 2 |
|  0  | 0 | 2 | 3 |
|     | 3 | 0 | 0 |
+-----+---+---+---+
Iterated Removal Condorcet Loser winner is {1}

Iterated Removal of Condorcet Loser with Explanation¶

pref_voting.iterative_methods.iterated_removal_cl_with_explanation(edata, curr_cands=None)[source]¶

Iterated Removal Condorcet Loser with an explanation. In addition to the winner(s), return the order of elimination, where each candidate in the list is a Condorcet loser in the profile (restricted to the remaining candidates).

Parameters:

edata (Profile, ProfileWithTies, MajorityGraph, MarginGraph) – Any election data that has a condorcet_loser method.
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates

Example:

from pref_voting.profiles import Profile
from pref_voting.iterative_methods import iterated_removal_cl_with_explanation

prof = Profile([[2, 1, 3, 0], [2, 1, 0, 3], [3, 1, 2, 0], [1, 2, 3, 0]], [1, 1, 1, 1])

prof.display()
ws, exp = iterated_removal_cl_with_explanation(prof)
print(f"The winning set is {ws}")
print(f"The order of elimination is {exp}")

+---+---+---+---+
| 1 | 1 | 1 | 1 |
+---+---+---+---+
| 2 | 2 | 3 | 1 |
| 1 | 1 | 1 | 2 |
| 3 | 0 | 2 | 3 |
| 0 | 3 | 0 | 0 |
+---+---+---+---+
The winning set is [1, 2]
The order of elimination is [0, 3]

Knockout Voting¶

pref_voting.iterative_methods.knockout(profile, curr_cands=None)[source]¶

Find the two candidates in curr_cands with the lowest and second lowest Borda scores among any candidates in curr_cands. Then remove from curr_cands whichever one loses to the other in a head-to-head majority comparison. Repeat this process, always using the original Borda score (i.e., the Borda scores calculated with respect to all candidates in the profile, not with respect to curr_cands as for Baldwin and Nanson) until only one candidate remains in curr_cands. Parallel universe tie-breaking (PUT) is used when there are ties in lowest or second lowest Borda scores.

Note

Proposed by Edward B. Foley (with unspecified handling of ties in Borda scores, so PUT is used here as an example).

Parameters:

profile (Profile) – An anonymous profile of linear orders on a set of candidates
curr_cands (List[int], optional) – If set, then find the winners for the profile restricted to the candidates in curr_cands

Returns:

A sorted list of candidates