Sunday Times Teaser 3116 – Poll Positions

by BRG on June 10, 2022

by Nick MacKinnon

Published Sunday June 12 2022 (link)

In an election for golf-club president, voters ranked all four candidates, with no voters agreeing on the rankings. Three election methods were considered.

Under First-past-the-post, since the first-preferences order was A, B, C, D, the president would have been A.

Under Alternative Vote, since A had no majority of first preferences, D was eliminated, with his 2nd and 3rd preferences becoming 1st or 2nd preferences for others. There was still no majority of 1st preferences, and B was eliminated, with his 2nd preferences becoming 1st preferences for others. C now had a majority of 1st preferences, and would have been president.

Under a Borda points system, candidates were given 4, 3, 2, or 1 points for each 1st, 2nd, 3rd or 4th preference respectively. D and C were equal on points, followed by B then A.

How many Borda points did each candidate receive?

From → Uncategorized

2 Comments Leave one →

Brian Gladman permalink


from itertools import combinations, permutations

# Analysis (by Frits): C overtakes B when D's votes are
# transferred to others; hence D has at least two votes
# with C, B and A minima being 3, 4 and  5 respectively

# return the alternative vote results for 
# candidates in <cs> and votes in <vs>
def av_result(vs, cs):
  c2v = dict((c, 0) for c in cs)
  for v in vs:
    c2v[v[0]] += 1
  return sorted(((v, c) for c, v in c2v.items()), reverse=True)

# possible voter preferences grouped by first past the post winners
orders = {c:[] for c in 'ABCD'}
for p in permutations('ABCD'):
  orders[p[0]].append(''.join(p))

# the possible numbers of 'first past the post' votes for A
for na in range(5, len(orders['A']) + 1):
  # and the possible combinations for A's first preference votes 
  for ca in combinations(orders['A'], na):
    
    # the possible numbers of 'first past the post' votes for B
    for nb in range(4, na):
      # and the possible combinations for B's first preference votes 
      for cb in combinations(orders['B'], nb):
        
        # the possible numbers of 'first past the post' votes for C
        for nc in range(3, nb):
          # and the possible combinations for C's first preference votes 
          for cc in combinations(orders['C'], nc):
            
            # the possible numbers of 'first past the post' votes for D
            for nd in range(2, nc):
              # and the possible combinations for D's first preference votes 
              for cd in combinations(orders['D'], nd):
                
                # A does not have an overall majority
                nv = sum((na, nb, nc, nd))
                if 2 * na > nv:
                  continue
                votes = ca + cb + cc + cd
  
                # promote D's votes and check there is still no overall majority
                av1 = tuple(v.replace('D', '') for v in votes)
                (fv, f), (sv, s), (tv, t) = av_result(av1, "ABC")
                #  there is no overall majority and B is eliminated
                if 2 * fv > nv or sv <= tv or t != 'B': 
                  continue
                                
                # promote B's votes and check that C now has an overall majority
                av2 = tuple(v.replace('B', '') for v in av1)
                (fv, f), (sv, s) = av_result(av2, "AC")
                if f != 'C' or 2 * fv <= nv:
                  continue

                # calculate the Borda points
                cnts = {}
                for vote in votes:
                  for c, v in zip(vote, (4, 3, 2, 1)):
                    cnts[c] = cnts.get(c, 0) + v

                if cnts['A'] < cnts['B'] < cnts['C'] == cnts['D']:
                  nv = na + nb + nc + nd
                  print(f"Borda points: {cnts}, {nv} votes:\n{' '.join(votes)}")

from itertools import combinations, permutations

# Analysis (by Frits): C overtakes B when D's votes are

# transferred to others; hence D has at least two votes

# with C, B and A minima being 3, 4 and 5 respectively

# return the alternative vote results for

# candidates in <cs> and votes in <vs>

def av_result(vs, cs):

c2v = dict((c, 0) for c in cs)

for v in vs:

c2v[v[0]] += 1

return sorted(((v, c) for c, v in c2v.items()), reverse=True)

# possible voter preferences grouped by first past the post winners

orders = {c:[] for c in 'ABCD'}

for p in permutations('ABCD'):

orders[p[0]].append(''.join(p))

# the possible numbers of 'first past the post' votes for A

for na in range(5, len(orders['A']) + 1):

# and the possible combinations for A's first preference votes

for ca in combinations(orders['A'], na):

# the possible numbers of 'first past the post' votes for B

for nb in range(4, na):

# and the possible combinations for B's first preference votes

for cb in combinations(orders['B'], nb):

# the possible numbers of 'first past the post' votes for C

for nc in range(3, nb):

# and the possible combinations for C's first preference votes

for cc in combinations(orders['C'], nc):

# the possible numbers of 'first past the post' votes for D

for nd in range(2, nc):

# and the possible combinations for D's first preference votes

for cd in combinations(orders['D'], nd):

# A does not have an overall majority

nv = sum((na, nb, nc, nd))

if 2 * na > nv:

continue

votes = ca + cb + cc + cd

# promote D's votes and check there is still no overall majority

av1 = tuple(v.replace('D', '') for v in votes)

(fv, f), (sv, s), (tv, t) = av_result(av1, "ABC")

# there is no overall majority and B is eliminated

if 2 * fv > nv or sv <= tv or t != 'B':

continue

# promote B's votes and check that C now has an overall majority

av2 = tuple(v.replace('B', '') for v in av1)

(fv, f), (sv, s) = av_result(av2, "AC")

if f != 'C' or 2 * fv <= nv:

continue

# calculate the Borda points

cnts = {}

for vote in votes:

for c, v in zip(vote, (4, 3, 2, 1)):

cnts[c] = cnts.get(c, 0) + v

if cnts['A'] < cnts['B'] < cnts['C'] == cnts['D']:

nv = na + nb + nc + nd

print(f"Borda points: {cnts}, {nv} votes:\n{' '.join(votes)}")

Frits permalink

With more analysis. The program has an internal runtime of 10ms.


from itertools import combinations, permutations, product

# possible 'alternative vote' preferences grouped by
# 'first past the post' winners
orders = {c:[] for c in 'ABCD'}
for p in permutations('ABCD'):
  orders[p[0]].append(''.join(p))

# D must have been chosen first at least twice
for N in range(14, 19):
  # calculate number of wins
  (nA, nB, nC, nD) = (6 - i if (N > 14 + i) else 5 - i for i in range(4))

  # round 1:  distribute nD wins to A, B and C so r1C > r1B
  if not (nC + nD > nB): continue

  # make sure C wins from B after first elimination
  if nD == 2:
    D = [['DCAB', 'DCBA']]
    r1A = nA
    r1B = nB
    r1C = nC + 2
  else:    # nD == 3
    # C has to win at least an extra 2 times after first elimination
    # so DCAB and DCBA must be present but not DBAC and DBCA
    # the third entry must be either DABC or DACB (so a win for A)
    D = [['DCAB', 'DCBA', 'DABC'], ['DCAB', 'DCBA', 'DACB']]
    r1A = nA + 1
    r1B = nB
    r1C = nC + 2

  # C has to win in round 1
  if not r1C > r1B:
    continue

  # C must be able to win in round 2
  if r1A >= r1C + 2:
    continue

  # round 2:  distribute nB wins to A and C so r2C > r2A
  # we can distribute a maximum of 3 wins from B to C,
  # 3 wins for C from BCAD, BCDA and BDCA
  # as nB >= 4 we have to distribute exactly 3 wins from B to C

  # C must be able to win in round 2
  if r1A + (nB - 3) >= r1C + 3:
    continue

  if nC == 5:
    # we have to distribute 3 wins to C and 2 to A
    # 3 wins for C from BCAD, BCDA and BDCA
    # 2 wins for A from BACD, BADC or BDAC
    B = [['BCAD', 'BCDA', 'BDCA', 'BACD', 'BADC'],
         ['BCAD', 'BCDA', 'BDCA', 'BACD', 'BDAC'],
         ['BCAD', 'BCDA', 'BDCA', 'BADC', 'BDAC']]
    # C must win in round 2
    if r1C < r1A:
      continue
  else:   # nC == 4
    # we have to distribute 3 wins to C and 1 to A
    # 3 wins for C from BCAD, BCDA and BDCA
    # 1 win for A from BACD, BADC or BDAC
    B = [['BCAD', 'BCDA', 'BDCA', 'BACD'],
         ['BCAD', 'BCDA', 'BDCA', 'BADC'],
         ['BCAD', 'BCDA', 'BDCA', 'BDAC']]

  # try all combinations
  for p in product(D, B, combinations(orders["A"], nA),
                   combinations(orders["C"], nC)):
    cnts = {"A": 0, "B": 0, "C": 0, "D": 0}
    votes = [x for g in p for x in g]

    for vote in votes:
      for l, v in zip(vote, (4, 3, 2, 1)):
        cnts[l] += v

    if not cnts["D"] == cnts["C"] > cnts["B"] > cnts["A"]:
      continue

    print(f"Borda points: {cnts}, number of voters: {N}\n"
          f"votes: {' '.join(sorted(votes))}")

from itertools import combinations, permutations, product

# possible 'alternative vote' preferences grouped by

# 'first past the post' winners

orders = {c:[] for c in 'ABCD'}

for p in permutations('ABCD'):

orders[p[0]].append(''.join(p))

# D must have been chosen first at least twice

for N in range(14, 19):

# calculate number of wins

(nA, nB, nC, nD) = (6 - i if (N > 14 + i) else 5 - i for i in range(4))

# round 1: distribute nD wins to A, B and C so r1C > r1B

if not (nC + nD > nB): continue

# make sure C wins from B after first elimination

if nD == 2:

D = [['DCAB', 'DCBA']]

r1A = nA

r1B = nB

r1C = nC + 2

else: # nD == 3

# C has to win at least an extra 2 times after first elimination

# so DCAB and DCBA must be present but not DBAC and DBCA

# the third entry must be either DABC or DACB (so a win for A)

D = [['DCAB', 'DCBA', 'DABC'], ['DCAB', 'DCBA', 'DACB']]

r1A = nA + 1

r1B = nB

r1C = nC + 2

# C has to win in round 1

if not r1C > r1B:

continue

# C must be able to win in round 2

if r1A >= r1C + 2:

continue

# round 2: distribute nB wins to A and C so r2C > r2A

# we can distribute a maximum of 3 wins from B to C,

# 3 wins for C from BCAD, BCDA and BDCA

# as nB >= 4 we have to distribute exactly 3 wins from B to C

# C must be able to win in round 2

if r1A + (nB - 3) >= r1C + 3:

continue

if nC == 5:

# we have to distribute 3 wins to C and 2 to A

# 3 wins for C from BCAD, BCDA and BDCA

# 2 wins for A from BACD, BADC or BDAC

B = [['BCAD', 'BCDA', 'BDCA', 'BACD', 'BADC'],

['BCAD', 'BCDA', 'BDCA', 'BACD', 'BDAC'],

['BCAD', 'BCDA', 'BDCA', 'BADC', 'BDAC']]

# C must win in round 2

if r1C < r1A:

continue

else: # nC == 4

# we have to distribute 3 wins to C and 1 to A

# 3 wins for C from BCAD, BCDA and BDCA

# 1 win for A from BACD, BADC or BDAC

B = [['BCAD', 'BCDA', 'BDCA', 'BACD'],

['BCAD', 'BCDA', 'BDCA', 'BADC'],

['BCAD', 'BCDA', 'BDCA', 'BDAC']]

# try all combinations

for p in product(D, B, combinations(orders["A"], nA),

combinations(orders["C"], nC)):

cnts = {"A": 0, "B": 0, "C": 0, "D": 0}

votes = [x for g in p for x in g]

for vote in votes:

for l, v in zip(vote, (4, 3, 2, 1)):

cnts[l] += v

if not cnts["D"] == cnts["C"] > cnts["B"] > cnts["A"]:

continue

print(f"Borda points: {cnts}, number of voters: {N}\n"

f"votes: {' '.join(sorted(votes))}")

Sunday Times Teaser 3116 – Poll Positions

by Nick MacKinnon

Published Sunday June 12 2022 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta