Drawing the presidential Election

Finding all the ways the electoral college votes from each state can be added up to give both candidates 269 votes turns out to be really hard. Political pundits always bring up the spectre of a drawn presidential election.

What happens if the US election ends in a draw?

If There’s an Electoral College Tie, Things Will Get Even Crazier Than You May Know

Where both candidates get 269 of the electoral college votes.

The website 270towin calculates 32 practical combinations that could result in a tie and give the probability of one of these occuring given polling data at 0.2%.

The NYtimes here claims there are 5 practical ways a tie could result.

But how many possible drawing combinations are there in total, including implausible ones?

Elections are much closer than the set of all possible wins a candidate could have. Certain states are similar so tend to vote the same way so some divisions are far more likely than others. Also by the median voter theorem two competing parties will be as similar to each other as possible to get as much of the vote as they can. Roughly the Republicans will be as near the center as they can while getting all the right wing votes and the democrats as near the center while getting all the left wing votes.

But how many total ways are there that two candidates can win 50 states and one district? That is as, ColinTheMathmo pointed out, 2^51 as each state can go to either candidate. I want to find the number of allocations in this 2^51 that give each candidate 269 electoral college votes*.

2^51 is a big number. As Matthew Saltzman said the set partition is an NP-Complete problem and a 'Complete enum at 10M/sec, would take 7 years.'

But instead of complete enum we just want to see the cases where both candidates get 269. The code here calculates this. I took some Minizinc code from Hakan Kjellerstrand who pointed out an error in my previous reading of a result that would calculate all the allocations of states that give 269 electoral votes. The code is written in Minizinc as it can calculate all answers in a way GLPK** doesn't. Hakan also kindly pointed out some inefficiencies in my program so I am linking to his code.

Here are some of the many results it output

Alaska California Delaware Florida Idaho Illinois Iowa Maine Michigan Mississippi Montana Nevada 'New York' Ohio Pennsylvania 'South Dakota' Texas Utah 
----------
Alaska California Delaware Florida Idaho Illinois Iowa Maine Michigan Mississippi Montana Nevada 'New York' Ohio Pennsylvania Texas Utah Vermont 
----------
Alaska California Delaware Florida Idaho Illinois Iowa Maine Michigan Mississippi Montana Nevada 'New York' Ohio Pennsylvania Texas Utah Wyoming 
----------
Alaska California Delaware Florida Idaho Illinois Iowa Maine Michigan Mississippi Nevada 'New York' 'North Dakota' Ohio Pennsylvania 'South Dakota' Texas Utah 

My mac is 2.16 gz and has 2 gigs of RAM so it is not a fast machine. Still after three hours of running it ground to a halt. This means I have no answer for you. If I find out how many of the state allocations result in 269 votes I will let you know.

It is interesting that these sorts of difficult NP-Complete problems pop up in real life and getting solutions for them is not always easy.

* Actually Maine and Nebraska can give out votes proportionately so the search space is even larger than this

**Just in case someone can use it here is GLPK code that will work out one answer

/* sets */
set STATES;
set NEED;

/* parameters */
param VotesTable {i in STATES, j in NEED};
param Pop {i in STATES};
param Need {j in NEED};


/* decision variables: x1: alabama, x2: , x3: , x4:  x51: Wyoming*/
      var x {i in STATES} binary >= 0;

/* objective function 
          z: sum{i in STATES} VotesTable[i,j]*x[i];
     
/* Constraints */
s.t. const{j in NEED} : sum{i in STATES} VotesTable[i,j]*x[i] == Need[j];

/* data section */
data;

set STATES :=  Alaska Delaware "District of Columbia" Montana "North Dakota" "South Dakota" Vermont Wyoming Hawaii Idaho Maine "New Hampshire" "Rhode Island" Nebraska Nevada "New Mexico" Utah "West Virginia" Arkansas Kansas Mississippi Connecticut Iowa Oklahoma Oregon Kentucky "South Carolina" Alabama Colorado Louisiana Arizona Maryland Minnesota Wisconsin Indiana Missouri Tennessee Washington Massachusetts Virginia Georgia "New Jersey" "North Carolina" Michigan Ohio Illinois Pennsylvania Florida "New York" Texas California;
set NEED := Votes;

param VotesTable: Votes:=
 Alabama 9
 Alaska 3
 Arizona 11
 Arkansas 6
 California 55
 Colorado 9
 Connecticut 7
 Delaware 3
 "District of Columbia" 3
 Florida 29
 Georgia 16
 Hawaii 4
 Idaho 4
 Illinois 20
 Indiana 11
 Iowa 6
 Kansas 6
 Kentucky 8
 Louisiana 8
 Maine 4
 Maryland 10
 Massachusetts 11
 Michigan 16
 Minnesota 10
 Mississippi 6
 Missouri 10
 Montana 3
 Nebraska 5
 Nevada 6
 "New Hampshire" 4
 "New Jersey" 14
 "New Mexico" 5
 "New York" 29
 "North Carolina" 15
 "North Dakota" 3
 Ohio 18
 Oklahoma 7
 Oregon 7
 Pennsylvania 20
 "Rhode Island" 4
 "South Carolina" 9
 "South Dakota" 3
 Tennessee 11
 Texas 38
 Utah 6
 Vermont 3
 Virginia 13
 Washington 12
 "West Virginia" 5
 Wisconsin 10
 Wyoming 3;

param Need:=
Votes        269;

end;