I was pondering today whether U.S. presidential elections could be quantified in closeness by the smallest number of extra votes the losing candidate would need to add to select states in order to win at least 270 electoral votes, the minimum threshold of victory. This is directly relevant to turnout efforts in 2020.
For example, it's well known that the three closest contests in 2016 that went to Donald Trump -- MI, WI and PA -- were decided by 10,704, 22,748 and 44,292 votes, respectively. They are worth 46 EVs total. Adding one to each margin to prevent a tie, this means it would take a minimum of 77,747 extra voters allotted appropriately to those three states to flip the election, even though this surpasses the 38 electoral votes Clinton would need to take from Trump to win, assuming you discount the 7 faithless electors. There was not a smaller number of extra votes that would have put Clinton ahead by a smaller margin of EVs that still hit the 270 mark.
It's not always so simple. In 2012, Mitt Romney would have needed 64 more electoral votes. But the closest margins are in states with a small number of EVs. (Here's the 2012 and 2016 data as a viewable page or a downloadable csv.) So it stands to reason that it might not be worth him "spending" 39,644 extra votes to win New Hampshire's 4 EVs--the closest contest he lost--when there were bigger prizes.
My first strategy here was to calculate a simple "cost" column that's the needed-votes divided by the electoral payoff. In Romney's case, the lowest cost is 2,562, since he would need 74,310 extra votes in Florida to get 29 more EVs -- the best "deal." Of course, you have to buy in bulk.
Where I'm getting tripped up is balancing the total vote deficit and the cost. Just sorting the total deficit in ascending order of "cost" gets one close, but fails to account for the fact that you don't want to spend any more votes than you need to get as close to 270 as possible. In Romney's case, just eyeballing the data, the combination of NH, NV, FL, CO and OH are good for 66 EVs at a cost of 485,835 extra votes, but these states are not in consecutive order any way you sort the columns, and may not be the optimal solution.
I thought this might be a knapsacking problem, but it's tricky since, to follow the knapsack analogy, you have different sized blocks of different masses and want the lightest knapsack with the smallest overflow. Naturally, one could brute-force it with combinatorial computations, but I'd much prefer an elegant solution.
This is a variant of the knapsacking problem. For every state that the losing candidate lost you can compute how many votes it would have taken to win it (the price) and how many EVs he would have gotten for it (the weight). Now you want to know the cheapest package that 'weighs' at least a given number of EVs. The signs are reversed relative to the standard wikipedia definition (that is we want cheapest above a weight instead of most expensive below a weight) but that shouldn't change much. So using one of the algorithms for knapsack problems is probably your best bet.