# How Voting Systems Work 6, Exercise 3: how often does lifting the winner make it lose?
# Assumed model: 3000 seeded elections, 9 voters, 3 candidates, each ballot a uniformly random order.
# For each method: lift the winner to first place on 1, 2, ... of the ballots where it is not
# already first (in ballot order). If the winner then loses, that is a monotonicity failure.
import random
from collections import Counter
from itertools import permutations

def plurality(ballots):
    tally = Counter(b[0] for b in ballots)
    return max(sorted(tally), key=tally.get)

def borda(ballots):
    k = len(ballots[0])
    points = {c: 0 for c in sorted(ballots[0])}
    for b in ballots:
        for place, c in enumerate(b):
            points[c] += k - 1 - place
    return max(points, key=points.get)

def irv(ballots):
    alive = set(ballots[0])
    while True:
        tally = Counter({c: 0 for c in alive})
        for b in ballots:
            tally[next(c for c in b if c in alive)] += 1
        top = max(sorted(tally), key=tally.get)
        if tally[top] * 2 > len(ballots) or len(alive) == 1:
            return top
        alive.remove(min(sorted(tally), key=tally.get))

def to_top(ballot, who):
    return (who,) + tuple(c for c in ballot if c != who)

random.seed(6)
names, voters, trials = ("Ana", "Bo", "Cy"), 9, 3000
orders = list(permutations(names))
failures = Counter()
for _ in range(trials):
    ballots = [random.choice(orders) for _ in range(voters)]
    for label, rule in (("plurality", plurality), ("Borda", borda), ("instant-runoff", irv)):
        w = rule(ballots)
        group = [i for i, b in enumerate(ballots) if b[0] != w]
        for r in range(1, len(group) + 1):
            trial = [to_top(b, w) if i in group[:r] else b for i, b in enumerate(ballots)]
            if rule(trial) != w:
                failures[label] += 1
                break
for label in ("plurality", "Borda", "instant-runoff"):
    print(f"{label:<15} monotonicity failures in {failures[label]} of {trials} elections")

# Output when run:
# plurality       monotonicity failures in 0 of 3000 elections
# Borda           monotonicity failures in 0 of 3000 elections
# instant-runoff  monotonicity failures in 48 of 3000 elections