Microscopic Miniature PFC Results
By jacob (Tue Oct 12, 2004 at 04:56:23 PM EST) (all tags)
A few days ago I asked, in a micro-mini PFC, how small a percentage of the popular vote a candidate could receive and still win the presidency. You rose to the challenge! Thanks for your quick and interesting responses.

Inside: the results!

I got code submissions from tmoertel, TurboThy, TPD, ColPanic, and geekmug.

In one sense, it's obvious how to solve the problem: just try out all the different ways a candidate could win the various states and return the one that requires the least votes. Unfortunately, that's very expensive, requiring evaluating the best of 251 = 2251799813685248 different possibilities, a far bigger space than a program can visit in any reasonable amount of time.

All the submitted programs tried some way around that problem. They fell into a couple different camps: in one corner we had dynamic programming algorithms, and in the other we had greedy algorithms. The greedy algorithms — TurboThy, ColPanic, and geekmug's entries — worked on the principle of buying votes where they're cheapest by computing the states in which winning an electoral vote costs the fewest popular  votes. This is a cheap algorithm, it's easy to understand, and it sounds like it will certainly yield good results.

In the other corner we have dynamic algorithms. The dynamic algorithms — tmoertel's and TPD's entries — work on a clever principle: assuming some ordering of the states (any old ordering will do), the number of votes you need to win X electoral votes is the minimum of (a) half (plus one) of the first state's voters plus the number of votes you need to win X - Y electoral votes where Y is the first state's electoral votes (if you won the first state, presumably by the narrowest possible margin), or (b) the number of votes you need to win X electoral votes in the rest of the states (if you lost the first state without even one vote cast for you in that state). Because of this recurrence relation, you can build a table with 51 columns (one for each position you could be in when traversing the list of states) and 270 rows (one for each different number of electoral votes the candidate could need). If you you fill in the table starting with the smallest cases, you'll have to do only constant work for each cell of the table and thus you can fill in the entire table, including the final square which contains the answer to the original problem, with just 51 * 270 = 13770 calculations.

So who's the winner? Well, this being a mini micro PFC, we'll refrain from ranking entries. But on the question of dynamic programming algorithms versus greedy algorithms: the greedy algorithms were in general much easier to read, but the dynamic programming algorithms performed as well as them1 and were provably optimal. I think if I were programming this for myself, I'd prefer the dynamic-programming method, but the greedy algorithm does very well and has the advantage that it's much easier to explain.

I was very happy with the results and I hope you all had fun with this little programming exercise.

And in case you're wondering: it turns out that to win the presidency of the United States, you can get by with a minimum of about 22.175% of all votes cast. You'd need to win al ak az ar co ct de dc hi id ia ks ky la me md ma mn ms mo mt ne nh nj nm nc nd ok or ri sc sd tn ut vt va wv wi and wy to have this happen.

1: Technically, the dynamic programming algorithms will be O(n*V), where n is the number of states and V is the number of needed electoral votes, whereas the greedy algorithms will be O(n*log n), but in actual elections the magnitude of V will be directly proportional to n and thus its size will be proportional to log n, so the DP algorithms will be O(n*log n) as well.

Microscopic Miniature PFC Results | 10 comments (10 topical, 0 hidden) | Trackback
My asymptotic runtime analysis was off by jacob (3.00 / 0) #1 Tue Oct 12, 2004 at 05:31:59 PM EST
It's true that V's magnitude grows directly with n and its size grows with log n. However, remember that we're constructing a table with a row for every number between 0 and V and filling that table in, so we need to do work directly proportional to V's magnitude, not its size, and the correct running time for the DP algorithms is O(n^2), not O(n*log n). In light of that it seems like the greedy algorithm might be much more attractive for answering this question on very large inputs, especially if a bound on its error could be established.

--

So... by TurboThy (3.00 / 0) #2 Tue Oct 12, 2004 at 06:02:23 PM EST
when we need to do calculations for the Galactic Elections, greedy algorithms are the nom du jour :)
__
Sommerhus til salg, første række til Kattegat.
[ Parent ]

Ah, by ColPanic (3.00 / 0) #9 Wed Oct 13, 2004 at 02:56:52 AM EST
but will the galactic elections use an electoral vote system?

[ Parent ]

Excellent challenge by TPD (3.00 / 0) #3 Tue Oct 12, 2004 at 09:14:16 PM EST
and excellent write up, but my entry doesn't work in the way described. Mind you the code's such a mess and went through enough iterations (sorry about the pages of code), that it's not very intellible (or intelligent).

I might shove a post mortem in here later if I find the time.

why sit, when you can sit and swivel with The Ab-SwivellerTM

oh deah by jacob (6.00 / 1) #4 Tue Oct 12, 2004 at 11:42:44 PM EST
I have to admit that your code was big enough that I read it last and just kind of skimmed it. I saw tables an a recursion and thought "Yep! Another dynamic programming entry!" :)

--

[ Parent ]

I should have probably kept quiet by TPD (3.00 / 0) #5 Wed Oct 13, 2004 at 12:36:03 AM EST
cause a dynamic programming entry would have looked better..

however it is closer to being a modification to the greedy alogorithm... Except it's not really as nice as the greedy algorithm you describe.... but it was something that had occured to me as a solution and I thought I'd see how it would perform.

what it does is order like most other entries in terms of least cost then it recursively goes through trying the states as voted for and against, however anytime it recurses into the against branch (say on a state with 10 votes) it says I could have voted for a good 10 votes state. now say the next state also is a 10 vote state it wont bother checking what would happen if that was voted for.

The thing then gets a bit smarter as if you then vote for a 4 Votes state it marks you as could have voted for a six vote state as well (10 - 4), or if you don't vote for it it say you could have voted for a 14 vote state. As it stands it's less efficient than the greedy algorithm, but I wanted to play with the idea. I never ended up implementing stage 2 which would have detected say not voting for a 6 and another 6 state and then voting for a 7 and 5 state as not being worthwhile (though you can probably see how that would have worked).

why sit, when you can sit and swivel with The Ab-SwivellerTM
[ Parent ]

Sorry Stage 2 was there (I lie) by TPD (3.00 / 0) #6 Wed Oct 13, 2004 at 12:39:38 AM EST
but I should have sized the array higher

why sit, when you can sit and swivel with The Ab-SwivellerTM
[ Parent ]

Is this accurate? by garlic (4.50 / 2) #7 Wed Oct 13, 2004 at 01:30:35 AM EST
Don't NE and ME divide their electoral votes up by the popular vote percentage instead of winner takes all? I know it's easier to program the other way, but if it doesn't reflect the real system, does it really matter what the results are?

No it's not by jacob (3.00 / 0) #8 Wed Oct 13, 2004 at 01:39:14 AM EST
In the coming election Colorado might decide to switch to a proportional-electoral-vote system as well. Also, it's highly unrealistic to expect the same turnout in every state; states with more heated battles tend to get higher turnouts than states where one candidate is a shoe-in. But this is a simpler problem, and the solutions could be pretty easily modified to solve the real question under various conditions. (The completely unrestricted minimum is something like 11 votes total, but this model is at least more realistic than that.)

--

[ Parent ]

Thanks, jacob! by tmoertel (3.00 / 0) #10 Wed Oct 13, 2004 at 08:59:58 AM EST
Thanks for posting and hosting the micro-mini PFC. The topic was germane and fun.

I tip my hat to you, sir.

--
Write Perl code? Check out LectroTest. Write markup-dense XML? Check out PXSL.

Microscopic Miniature PFC Results | 10 comments (10 topical, 0 hidden) | Trackback