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 UtahMy 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;
4 comments:
The following generating function encodes the number of ways of achieving each total:
(1 + x^3)^8 (1 + x^4)^5 (1 + x^5)^3 (1 + x^6)^6 (1 + x^7)^3 (1 +
x^8)^2 (1 + x^9)^3 (1 + x^10)^4 (1 + x^11)^4 (1 + x^12) (1 +
x^13) (1 + x^14) (1 + x^15) (1 + x^16)^2 (1 + x^18) (1 +
x^20)^2 (1 + x^29)^2 (1 + x^38) (1 + x^55)
In particular, the coefficient of x^269 is 16,976,480,564,070.
That is the right answer Rob but how did you generate that function?
Each factor (1 + x^k) corresponds to a state with k electoral votes. For example, 8 states have 3 electoral votes, yielding (1 + x^3)^8. Similarly, 5 states have 4 electoral votes, yielding (1 + x^4)^5. Imagine multiplying out the whole generating function and collecting like powers of x in this degree-538 polynomial. The coefficient of x^n records the number of ways to obtain a total of exactly n votes. We want n = 269.
That is complete genius Rob. Thanks for posting!
Post a Comment