The 2020 US Presidential Election Race as an OBDD

Stefan Szeider, Algorithms and Complexity Group, TU Wien

Whether one of the candidates reaches at least 270 electoral votes is determined by the states (or districts) he wins. For instance, who wins Texas (TX) receives its 38 electoral votes.

We can represent the candidates' race to reach 270 electoral votes by an Ordered Binary Decision Diagram (OBDD), a prominent data structure used in Computer Science for various purposes. Don Knuth called OBDDS in a 2009 lecture to be
"one of the really fundamental data structures that came out in the last 25 years."

We start with OBDDs that are created before the election took place. Here we have many unknown variables, so the OBDD is large. After the election, when votes are counted and state after state becomes decided, the OBDD becomes smaller and smaller.

Pre-Election Analysis

 

Below we see an OBDD that represents the data from before the election. It is read from top to bottom, starting at the top node labeled (TX), representing Texas. If Trump wins Texas, we leave (TX) via the red line; if Biden wins Texas, we leave (TX) via the blue line. We continue this way until we have reached one of the boxes at the bottom: [BIDEN wins] or [TRUMP wins]. Here we consider the 11  states TX, FL, PA, OH, GA, NC, AZ, IA, NV, ME2, NE2, which are labeled "toss-up" by the meta-poll from the Financial Times (morning of November 3, 2020).


Biden 252 vs Trump 125 (AK, AL, AR, AZ, CA, CA, CO, CO, CT, CT, DC, DC, DE, DE, FL, GA, HI, HI, IA, ID, IL, IL, IN, KS, KY, LA, MA, MA, MD, MD, ME, ME, ME1, ME1, ME2, MI, MI, MN, MN, MO, MS, MT, NC, ND, NE, NE1, NE2, NE3, NH, NH, NJ, NJ, NM, NM, NV, NY, NY, OH, OK, OR, OR, PA, RI, RI, SC, SD, TN, TX, UT, VA, VA, VT, VT, WA, WA, WI, WI, WV, WY)

For instance, a possible red path to victory for Trump is (TX)—(FL)—(PA)—(OH)—(GA)—(NC)—(AZ)—[TRUMP wins]

If we consider the same red path (TX)—(FL)—(PA)—(OH)—(GA)—(NC)—(AZ), but Biden wins Arizona and Nevada, we can continue in blue (AZ)—(NV)—[BIDEN wins or tie].

We need to break ties (269:269 votes) in one or the other way. Above, we break ties in favor of Biden, below is a corresponding OBDD where we break ties in favour of Trump. The OBDD below shows that (TX)—(FL)—(PA)—(OH)—(GA)—(NC)—(AZ)—(NV)—[BIDEN wins] is indeed a win for Biden and not a tie.

The OBDD becomes more interesting (and quite complicated) when we add more states to the equation. Below, we add to the toss-up states also the Biden-leaning states MI and MN, and the Trump-leaning states AK and MO (click on the image to zoom in).


Biden 226 vs Trump 112 (AK, AL, AR, AZ, CA, CA, CO, CO, CT, CT, DC, DC, DE, DE, FL, GA, HI, HI, IA, ID, IL, IL, IN, KS, KY, LA, MA, MA, MD, MD, ME, ME, ME1, ME1, ME2, MI, MN, MO, MS, MT, NC, ND, NE, NE1, NE2, NE3, NH, NH, NJ, NJ, NM, NM, NV, NY, NY, OH, OK, OR, OR, PA, RI, RI, SC, SD, TN, TX, UT, VA, VA, VT, VT, WA, WA, WI, WI, WV, WY)

 

Here is the even larger (and opaque)  OBDD with 23 battleground states TX, FL, PA, OH, GA, MI, NC, IN, AZ, WI, MO, MN, CO, SC, NV, IA, UT, KS, NH, AK, MT, ME2, and NE2. There are 2^23=8,388,608 possible outcomes for the individual battleground states.  In Computer Science terminology, the OBDD represents a Boolean function on 23 variables. The size of an OBDD strongly depends on the chosen ordering of the variables. We order the variables (representing states) decreasingly in the number of electoral votes.

 


Biden 203 vs Trump 77 (AK, AL, AR, AZ, CA, CA, CO, CT, CT, DC, DC, DE, DE, FL, GA, HI, HI, IA, ID, IL, IL, IN, KS, KY, LA, MA, MA, MD, MD, ME, ME, ME1, ME1, ME2, MI, MN, MO, MS, MT, NC, ND, NE, NE1, NE2, NE3, NH, NJ, NJ, NM, NM, NV, NY, NY, OH, OK, OR, OR, PA, RI, RI, SC, SD, TN, TX, UT, VA, VA, VT, VT, WA, WA, WI, WV, WY)

 

When state results are known at election night, more and more states will move to the solid category, which will make the OBDD simpler. We will post updates here; stay tuned.

 

Update 1 at November 4, 4am ET

New data from the the Financial Times (also Associated Press) suggests a 238 (Biden) vs 213 (Trump) intermediate result. Here is the updated OBDD:

 


Biden 238 vs Trump 213 (AK, AL, AR, AZ, AZ, CA, CA, CO, CO, CT, CT, DC, DC, DE, DE, FL, GA, HI, HI, IA, ID, IL, IL, IN, KS, KY, LA, MA, MA, MD, MD, ME, ME, ME1, ME1, ME2, MI, MN, MN, MO, MS, MT, NC, ND, NE, NE1, NE2, NE3, NE3, NH, NH, NJ, NJ, NM, NM, NV, NY, NY, OH, OK, OR, OR, PA, RI, RI, SC, SD, TN, TX, UT, VA, VA, VT, VT, WA, WA, WI, WV, WY)

 

Update 2 at November 4, 3pm ET

The Financial Times/Associated Press projects 248 (Biden) vs 214 (Trump). See here for an explanation why a certain state is "called" (considered to be won by a candidate).

Here is the OBDD:


Biden 248 vs Trump 214 (AK, AL, AR, AZ, AZ, CA, CA, CO, CO, CT, CT, DC, DC, DE, DE, FL, GA, HI, HI, IA, ID, IL, IL, IN, KS, KY, LA, MA, MA, MD, MD, ME, ME, ME1, ME1, ME2, MI, MN, MN, MO, MS, MT, NC, ND, NE, NE1, NE2, NE3, NE3, NH, NH, NJ, NJ, NM, NM, NV, NY, NY, OH, OK, OR, OR, PA, RI, RI, SC, SD, TN, TX, UT, VA, VA, VT, VT, WA, WA, WI, WI, WV, WY)

 

Interestingly, there is still the theoretical possibility of a 269:269 tie. In the following OBDD, this possibility is made explicit. In the meantime, it was reported that Michigan is won by Biden. We see that excludes that possibility of a tie.

 

 

CNN projects 237 (Biden) vs 213 (Trump), here is the OBDD:


Biden 237 vs Trump 213 (AK, AL, AR, AZ, CA, CA, CO, CO, CT, CT, DC, DC, DE, DE, FL, GA, HI, HI, IA, ID, IL, IL, IN, KS, KY, LA, MA, MA, MD, MD, ME, ME, ME1, ME1, ME2, MI, MN, MN, MO, MS, MT, NC, ND, NE, NE1, NE2, NE3, NE3, NH, NH, NJ, NJ, NM, NM, NV, NY, NY, OH, OK, OR, OR, PA, RI, RI, SC, SD, TN, TX, UT, VA, VA, VT, VT, WA, WA, WI, WI, WV, WY)

 

Update 3 at November 5, 3pm ET

The Financial Times/Associated Press projects 264 (Biden) vs 214 (Trump), and CNN projects 253 vs 213. Here are the corresponding OBDDs.


Left: AP projection with Biden 264 vs Trump 214 (AK, AL, AR, AZ, AZ, CA, CA, CO, CO, CT, CT, DC, DC, DE, DE, FL, GA, HI, HI, IA, ID, IL, IL, IN, KS, KY, LA, MA, MA, MD, MD, ME, ME, ME1, ME1, ME2, MI, MI, MN, MN, MO, MS, MT, NC, ND, NE, NE1, NE2, NE3, NE3, NH, NH, NJ, NJ, NM, NM, NV, NY, NY, OH, OK, OR, OR, PA, RI, RI, SC, SD, TN, TX, UT, VA, VA, VT, VT, WA, WA, WI, WI, WV, WY)

Right: CNN projection with Biden 253 vs Trump 213 (AK, AL, AR, AZ, CA, CA, CO, CO, CT, CT, DC, DC, DE, DE, FL, GA, HI, HI, IA, ID, IL, IL, IN, KS, KY, LA, MA, MA, MD, MD, ME, ME, ME1, ME1, ME2, MI, MI, MN, MN, MO, MS, MT, NC, ND, NE, NE1, NE2, NE3, NE3, NH, NH, NJ, NJ, NM, NM, NV, NY, NY, OH, OK, OR, OR, PA, RI, RI, SC, SD, TN, TX, UT, VA, VA, VT, VT, WA, WA, WI, WI, WV, WY).

 

The FT/AP projection excludes the possibility for tie, but the CNN projection admits tie situations (Biden wins only GA, or Biden wins only NC and ME2). Here is an OBDD with three terminal nodes that makes the possibility of a tie explicit.

 

Update 4 at November 7

Several networks, including CNN project that Biden wins Pensilvania (PA), which makes him, with very high probability, the elected winner.

 

 

The author thanks Vaidyanathan P.R. for his help with the OBDD computation. The use of all media posted here is permitted as long as credit is given to the author.