Modeling the electoral college as a knapsack problem

In my previous and first post about the electoral college, I tried to show how it is possible to get the necessary 270 votes to win the election in the college and do it winning the popular election in a minority of the states. Now we model the electoral college as a knapsack problem.

My approach was a bit simplistic (heuristic) and now I will show how to model the electoral college as an example of a very well-known problem in mathematical programming: the knapsack problem. In the knapsack problem, you want to fill the knapsack with a few items. Each item has a weight and some value to you, and you want to pack the knapsack with as much value as possible within the weight the knapsack (and your own back!) can hold.

The knapsack problem

The mathematical formulation for the optimization problem is:

max Σv_i*x_i
ST Σw_i*x_i≤W
x_i ∈{0,1}
Where i = items
v_i = values
w_i = weights
W = weight capacity
x_i = 1 if the item is loaded, 0 if it is not

So for example, if you have four items that weigh 10, 20, 25, and 30, the respective values are 5, 10, 20, and 15 and the capacity is 50. Then the best solution is to take items 2 and 3:

The best solution yields a total value of 30 and the knapsack weighs 45, not even reaching the capacity of 50, which is a bit counterintuitive. And this is exactly why mathematical programming provides the best approach

The electoral college equivalent

The exact equivalent to the knapsack problem in the electoral college would be to minimize the number of votes needed to get at least 270 electors. Actually, the exact equivalent is to maximize the number of votes while not reaching 270 votes, but the results are the same:

min Σv_i*x_i
ST Σe_i*x_i ≥ E
x_i ∈{0,1}
Where i = districts
v_i = votes
e_i = electors
E = electoral majority = 270
x_i = 1 if the district is won, 0 if it is not

We can apply this to the 2016 election that (in)famously was won by a candidate that lost the popular vote.

The model for the 2016 election

The model is essentially the same except that there is an extra little complication. Almost all states assign all their electors to the popular vote winner, except for two states. Nebraska and Maine assign 2 electors to the popular vote winner and then 1 elector to the vote winner in each of their house districts. Of course, there is a need to add a restriction: if there is a single winner for all house districts, obviously the same candidate would have won the state vote.

The extra constraints (one for Nebraska and one for Maine) are:

Σx_i ≤ Y_i*n
Y_i*n ≤ Σx_i
Where x_i = same as before, for the house districts in the state
y_i = x_i for the state
n = number of House districts in the state

The constraint ensures that if all the x_i for the house districts are 1 then y_i (the x_i for the state) will be 1 as well. And if y_i is 1 then the x_i for the districts are also 1 The possible solutions for the two districts in Maine and for the state are, then: 0,0,0; 1,0,0; 0,1,0; 1,1,1.

Finally, the population for the state (Nebraska and Maine) is set to 0, only the districts carry their population cost. The extra constraints above make sure the states “incur the population cost” as needed.

Results

The results were more or less as expected. Fortunately, the outcome is not trivial, and sorting the states by votes/electors ratio shows that Alabama is not picked when several states with lower ratios are picked. This is similar to what I first found analyzing the simplistic approach in my previous post when it was more efficient to pick North Carolina before GeorgiaThe results are now different (involve different states) because last time I had used population and now I am using actual votes cast.

It took me a couple of tweaks to get the constraints for Nebraska and Maine to work. I had to realize I was counting their population twice (once for the whole state and a second time for the House district) which was making them much less desirable. Now they are both picked.

These are the “optimal” states (in dark):

The bigger states are not optimal because they get the same 2 electors per their 2 senators as small states do.

For comparison, this was the result of the election:

The file

The Excel file with the data and the Solver model can be found in the downloads section on this site following this link.

Another thing that can be modeled and appears not to have a trivial result (and, given how close the election was in so many states) is how many vote flips would have been needed to change the outcome of the election. We’ll do that next time.

What other questions would be interesting to ask?

Things that I use, like, and am affiliated with:
Google Fi offers great cell phone service in 120 countries, get $20 off using the link. Get discounted phones with service activation and no contract.
Uber and Lyft are offering discount rates on your first rides using the links.
AirBnB where you can be home anywhere in the world; get up to $55 off with the link.
I never spend money before I check Mr Rebates, Raise, Ebates or Honey to get cashbacks, rebates, discounts, coupons or cheaper gift cards.
This blog is hosted at Hostgator