Winning an election with 22% of the popular vote
A presidential candidate could be elected with as a little as 21.8% of the popular vote by getting just over 50% of the votes in DC and each of 39 small states. This is true even when everyone votes and there are only two candidates. In other words, a candidate could lose with 78.2% of the popular vote by getting just under 50% in small states and 100% in large states.
The optimal set of states to take (the one that lets a candidate win with the smallest popular vote) is not the N states with the smallest population. It's also not the N states with the smallest value for (population/electors), which would be optimal if you could get exactly 270 electoral votes that way.
The optimal solution happens to get exactly 270 electoral votes. In this solution, the winner takes DC, the 37 smallest states, the 39th smallest state, and the 40th smallest state. (The winner takes Alabama, Alaska, Arizona, Arkansas, Colorado, Connecticut, Delaware, DC, Hawaii, Idaho, Indiana, Iowa, Kansas, Kentucky, Louisiana, Maine, Maryland, Minnesota, Mississippi, Missouri, Montana, Nebraska, Nevada, New Hampshire, New Mexico, North Carolina, North Dakota, Oklahoma, Oregon, Rhode Island, South Carolina, South Dakota, Tennessee, Utah, Vermont, Virginia, Washington, West Virginia, Wisconsin, and Wyoming.)
Read on for my assumptions and algorithm.
Assumptions
I made two simplifying assumptions. First, I assumed that the entire population of each state can vote. Second, I assumed that all states were winner-take-all. Maine and Nebraska are not, but I think I can justify this assumption: it would be "wasteful" to take one congressional district of Maine without taking the other districts and at-large votes.
I used apportionment data from the 2000 census for populations and numbers of electoral votes. The 2000 census controls electoral vote apportionment for 2004 and 2008. Since that data didn't include the population of DC, I got the population of DC from another source, which was also connected to the 2000 census but which used different criteria to determine whether a person counted as part of the population of a state.
Algorithm
To come up with an algorithm to solve the problem, I first thought about how the Electoral College problem would generalize:
- Instance: populations[], electors[], goal. (Population needed to win each state, electoral college vote of each state, number of electoral votes I need to win.)
- Solution: W, a set of states. (States that I win.)
- Constraint: (sum over W of electors[]) >= g. (I win the election.)
- Objective: minimize (sum over W of populations[]). (I win the election with the minimum popuplar vote.)
I noticed that the problem looked similar to Subset Sum, an NP-complete problem, so I thought about possible exponential-time algorithms:
- Brute force, trying every possible W. This would take 251 for 50 states plus DC.
- Backtracking (adding states to W until goal is reached). This would take at least 237, since you can have the 37 smallest states and still need more electoral votes to win.
- Backtracking, taking advantage of the fact that several states have the same number of electoral votes. Sort the states by electoral votes and then by population. If we didn't add Wyoming (smallest state with exactly 3 electoral votes), we won't add any other states with exactly 3 electoral votes. Significantly faster than simple backtracking; might be fast enough.
I looked up Subset Sum in Garey and Johnson to see which exponential-time algorithm they recommended for Subset Sum. To my surprise, I found a fast dynamic programming algorithm. The algorithm is "pseudo-polynomial" -- its running time is a polynomial in the size of the input and the integer values represented by the input. The algorithm is only exponential because an integer can be represented using a number of bits equal to a log of its value. If the numbers are small, the dynamic programming algorithm is fast.
Once this algorithm is modified to apply to the Electoral College problem, it computes a two-dimensional table containing the minimum population needed for every exactly j electoral votes using only the first i states. Each cell of the table can be computed quickly by considering two cases, either the candidate wins state i, getting eleci electoral votes for popi/2, or doesn't: minpopi,j = min(minpopi-1,j-eleci + popi/2, minpopi-1,j). The algorithm runs in O(states * electors) time. It is nice that the running time depends on the numbers of electors, not the populations.
I implemented the dynamic programming algorithm in ugly JavaScript. The JavaScript requires the print() function provided by my minimal JavaScript environment. On my computer, it takes about 3 seconds in IE or 1 second in Firefox.
Related work
After getting the answer of 21.8%, I searched Google for variations on "22% of the popular vote" and found several people who had have made similar calculations (some using approximate greedy algorithms, some using correct dynamic programming algorithms, all with different input data).
November 1st, 2004 at 9:29 am
What is so wrong with that? If you carry 39 states, maybe you should win because the other canidiate obviously was appealing only to voters in the other eleven states.
November 1st, 2004 at 9:50 am
The point of having an electoral college (in addition to not trusting the voters, which no longer holds) is to make sure the opinions of big states can’t dominate over the opinions of little states in elections. In this highly improbable scenario, that’s certainly what’s happening. Whether the union is so partitioned that it’s necessary to have this barrier in place is debatable. Given that the only two elections where the winner lost the popular vote but won the electoral vote both had highly disputed endings (and dubious, depending on which side of the aisle you’re asking), I think I’d lean more towards nixing it.
Note that given 50% turnout (which is roughly typical for the last few elections, I believe) in each state, that means only 11% of the country needs to support a candidate to elect him. (Of course, in this permutation of the situation the loser’s supporters would have pretty much only themselves to blame.)
November 1st, 2004 at 9:51 am
the incredible part is that americans can still vote for bush, a lier, with ties with the Bin Laden family …
http://www.bushnews.com/bushcarlyle.htm
http://www.bushnews.com/bushmoney.htm
November 1st, 2004 at 1:52 pm
This came about from a conversation Jesse and I had in IRC about the fact that a person can win the Presidency by winning only the 13 largest states. While I’m somewhat surprised the minimal number is that much below 25%, this is obviously a theoretical solution only. With population not evenly distributed, it’s (practically speaking) easier to take most of the large states and a few small states to reach 270. John Kerry currently holds California (and the west coast) and New York (and the north east), Bush holds Texas and the plains states, and some of the Atlantic southeast. They’re battling for the balance of the top tier prizes (PA, Ohio, Michigan, Florida), and the smaller states that are toss ups (upper midwest, a few southwest states) to fill out their card. This gives them specific regions to target, as opposed to a wide array of land area and population centers to cover, as they would trying to battle for the lowest 38 or states. :)
November 1st, 2004 at 2:22 pm
Oklahoma or some other state that starts with an “O” is also doing a Maine-like system (divvy up all the Representative (x) electoral votes between the districts that create each Representative and let the two remaining Senator votes do whatever they want [# of electoral votes = House + Senate congressmen]; Senate votes are winner-take-all so that the candidates still campaign in Maine) starting this year. Nebraska does a 100% proportional vote (if 75% vote Kerry, 75% of the electors vote Kerry) because they’re weird.
Mod self +1000 uber-informational.
November 1st, 2004 at 3:11 pm
How does Nebraska’s proportional vote work, especially when there are more than two candidates?
November 1st, 2004 at 3:26 pm
If there wasn’t 100% turnout, then Candidate X could win with < 1% of the popular vote. A simple example: 49 states vote 100% for Candidate X, but only one person voted per state. The other state is 100% for candidate Y, with 100% turnout. Popular vote: 49 for candidate X, entire population of a state for Candidate Y.
November 1st, 2004 at 6:27 pm
hao2lian: It isn’t Oklahoma that is considering splitting up there Electoral votes. The only state I know of that is considering it is Colorado. According to the article below, they would split their electoral votes depending on the popular vote percentage.
Nebraska and Maine have systems where whomever gets the popular vote get 2 electoral votes, and then whomever gets the popular vote in each House district gets 1 vote for that district. This has not actually lead to split state vote yet.
http://www.msnbc.msn.com/id/6106804/
http://www.google.com/search?hl=en&lr=&q=colorado+split+electoral+college+vote&btnG=Search
November 2nd, 2004 at 8:15 pm
Good mathematical analysis – thought you might get a chuckle out of the halloween lights/webcam site where there was voting for Bush, Kerry, … or the HULK … looks like the Big Green Guy is going to win that one – see:
http://www.komar.org/cgi-bin/halloween_webcam
November 2nd, 2004 at 9:46 pm
You’ve exaggerated the system’s flaw, but it is no doubt real and unpleasant. Perhaps it’s time for a more novel approach!
http://www.cowbiscuit.com/cb.cgi?page=articles&aid=25
November 3rd, 2004 at 8:57 am
(Continuing with the assumption of 100% voter turnout, and valid data on the number of eligible voters in each state is used for the population values)
If you look at it from the other direction, examining how many popular votes can be received by a candidate while still losing the election, it becomes the 0-1 Knapsack problem:
Start, as you did, by assuming that the loser receives 100% of the vote in the states he wins and 50%-1 of the vote in states he loses. With a bit of proving I’m not prepared to work through, I believe it can be shown that the solution that maximizes the total number of votes for the loser is the solution which maximizes the population of those states where the loser won.
The task then becomes selecting the set of states for the loser to win; as in the Knapsack problem, the losing candidate seeks to maximize the number of popular votes (value) received while the total number electoral votes (sum of weights) cannot exceed 269.
The population of each state is its “value”, while the corresponding number of electoral votes is its “weight”.
States giving divided electoral votes could mess things up a bit, because of the possible rounding issues involved in selecting which candidate gets how many electoral votes. I really don’t know enough about how that division works (or, really anything about how it works) to determine how it would affect the overall solution. My guess is that for Nebraska-like-systems, it could be incorporated by dividing the state into single-EV portions, each with an equal proportion of the state’s population.
The 0-1 Knapsack problem has a dynamic programming solution that is, iirc, essentially the same as what you describe above, but (to me) this approach to characterizing the problem seems to reach that solution more directly.
November 8th, 2004 at 4:09 am
Hey, Jesse, I did this same thing last month using 2000’s turnout and this year’s electoral vote numbers. Your math and explanation is more detailed, but we came to pretty much the same result.
http://plutor.org/blog/2004/10/14/08.19.24/
November 1st, 2004 at 7:33 am
right or left?
Cheney ripped on Kerry today because Kerry apparently took a poll to gauge the American public’s reaction to the new Osama Bin Laden tape. Or, in other words: “Kerry chose to consult his electors, the American public, rather than acting…
November 1st, 2004 at 4:22 pm
Picking the President
I read a post over at Jesse Ruderman’s blog on how he calculated that one could win the Presidential election…