Teaser 3116: Poll positions
From The Sunday Times, 12th June 2022 [link] [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?
[teaser3116]
Hugh+Casement, 
Frits are discussing. 
GeoffR, and 
Jim Olson are discussing. 
S2T2 
Jim Randell 5:17 pm on 10 June 2022 Permalink |
There are only factorial(4) = 24 different ways to order the candidates, so that gives us an upper bound on the number of voters.
This Python program finds the required points values, and the unique set of votes that leads to it.
It isn’t particularly fast (although it is faster than my first program, which just tried all possible sets of votes). It runs in 251ms.
Run: [ @replit ]
from enigma import (group, subsets, join, unpack, irange, decompose, cproduct, map2str, printf) candidates = "ABCD" # consider possible voting patterns (first, second, third, fourth) # grouped by first choice patterns = group(subsets(candidates, size=len, select="P", fn=join), by=(lambda x: x[0])) # count the number of first choice votes def first(vs, ks): d = dict((k, 0) for k in ks) for v in vs: d[v[0]] += 1 return sorted(d.items(), key=unpack(lambda p, n: n), reverse=1) # eliminate a candidate def eliminate(vs, x): return list(v.replace(x, '', 1) for v in vs) # calculate Borda points def borda(vs, ks): n = len(ks) d = dict((k, 0) for k in ks) for v in votes: for (i, x) in enumerate(v): d[x] += n - i return d # check the remaining puzzle constraints # return Borda points def check(N, votes): # first D is eliminated vs = eliminate(votes, 'D') # count the number of first choices ((p1, n1), (p2, n2), (p3, n3)) = first(vs, "ABC") # there is no majority of first choices, and B is eliminated if 2 * n1 > N or not (n2 > n3 and p3 == 'B'): return # then B is eliminated vs = eliminate(vs, 'B') # count the number of first choices again ((p1, n1), (p2, n2)) = first(vs, "AC") if not (p1 == 'C' and 2 * n1 > N): return # count Borda points pts = borda(votes, candidates) # D and C are equal first, then B, then A if not (pts['D'] == pts['C'] > pts['B'] > pts['A']): return # return Borda points return pts # consider the number of voters [6, 24] for N in irange(6, 24): # consider the number of first choice votes (A does not have a majority) for (A, B, C, D) in decompose(N, 4, increasing=-1, sep=1, min_v=0, max_v=min(6, N // 2)): # choose the votes vs = (subsets(patterns[k], size=n) for (k, n) in zip("ABCD", (A, B, C, D))) for (As, Bs, Cs, Ds) in cproduct(vs): votes = As + Bs + Cs + Ds pts = check(N, votes) if pts: printf("points: {pts}", pts=map2str(pts, arr="=", sep=" ", enc="")) printf("-> {n} votes {votes}", n=len(votes), votes=join(votes, sep=" ", enc="[]")) printf()Solution: The Borda points are: A=33, B=35, C=36, D=36.
There are 14 voters and the votes cast are:
Using “first-past-the=post”, A wins with 5 votes, B has 4, C has 3, D has 2.
Under “alternative vote” the first round is as given above. D is eliminated and his 2 votes are redistributed to give: A=5, B=4, C=5. Again there is no outright winner, so C’s 4 votes are redistributed to give: A=6, C=8, and C wins.
LikeLike
Frits 10:58 am on 11 June 2022 Permalink |
@Jim,
With a little analysis you can halve the run time by choosing a better range of number of voters than [6, 24].
LikeLike
Jim Randell 1:32 pm on 11 June 2022 Permalink |
I went with the smallest possible number of voters: D=0, C=1, B=2, A=3, gives a total of 6 voters.
But in this scenario when D is eliminated there would be no votes to redistribute, so we can move to: D=1, C=2, B=3, A=4, to give a total of 10 voters.
But when D’s votes are redistributed it is enough to knock B into last place, so C needs to gain at least 2 votes to leapfrog B.
So we can increase minimum possible to: D=2, C=3, B=4, A=5, for a total of 14 voters.
Incorporating this into my program brings the run time down to 384ms.
And with a bit more analysis of the alternative vote system we can see that the number of voters is in {14, 15, 17, 18}.
LikeLike
Frits 1:59 pm on 11 June 2022 Permalink |
@Jim,
Yes, [14, 15, 17, 18] is what I had in mind.
LikeLike
Frits 2:05 pm on 11 June 2022 Permalink |
My PuzzlingInPython program also early rejects N=18.
LikeLike
Hugh+Casement 9:48 am on 19 June 2022 Permalink |
I really don’t see the point of optimizing the run time for a program that is run only once.
It takes far longer to write it!
LikeLike
Jim Randell 10:59 pm on 19 June 2022 Permalink |
If possible, I aim for a generic program that runs in under 1s, and if I can get the run time down to 100ms that’s even better (although I still like to keep it generic if possible).
In this case my initial attempt ran in 44s, so I accepted I might have to tune it a little to improve on the run time. It wasn’t very much work, and the program posted above ran in less than 1s. I did do some more tweaking which got the run time down to 74ms, but I didn’t think the extra complication was worth posting.
LikeLike
Hugh+Casement 9:51 am on 20 June 2022 Permalink |
This is not process control, where milliseconds may well matter!
If a program takes many minutes to run (while I go and do something else), I probably find it worth spending a bit of time to try and improve the method or find a different line of attack.
But one has to keep a sense of proportion.
LikeLike