The world’s leading publication for data science, AI, and ML professionals.

Using Dynamic Planning to Help Trump Win the Elections

Dynamic Planning in Python for optimising Election Promotion

Photo by fajarbudi86 on Pixabay
Photo by fajarbudi86 on Pixabay

Disclamation: The 2020 US Election is merely used as background in this article. This story meant to show you such a way of thinking in computer programming. I am NEITHER expressing my viewpoints of politics NOR persuading with any ideas. All the data used in this article is made up from assumption, which does not necessarily reflect the truth in anyway.

Well, at the time I am writing this article, Joe Biden has secured the victory already. I am neither an American nor living in the US, so I won’t comment on this politically, though I think most of the people who are reading my articles might support Biden. How do I know? Just have a look at California 🙂

OK. Now we imagine that we are hired as a member of Trump’s election team. Suppose we have 10 days left before the voting started. Everyone knows that the most important thing is to strive for the swing states. I’m not quite a fan of politics so my knowledge about this is limited, but fortunately, I got the 11 states that are considered as the swing states in the 2020 US Election from Wikipedia.

Let’s just make up the data and put all the states, their number of electoral votes and the number of days that are required to promote in this state together in a dictionary.

states_dict = [
    {'name': 'Maine', 'votes': 5, 'days': 1},
    {'name': 'Nevada', 'votes': 6, 'days': 1},
    {'name': 'Minnesota', 'votes': 10, 'days': 2},
    {'name': 'New Hampshire', 'votes': 4, 'days': 1},
    {'name': 'Michigan', 'votes': 16, 'days': 3},
    {'name': 'Pennsylvania', 'votes': 20, 'days': 4},
    {'name': 'Wisconsin', 'votes': 10, 'days': 2},
    {'name': 'Florida', 'votes': 29, 'days': 5},
    {'name': 'Arizona', 'votes': 11, 'days': 2},
    {'name': 'North Carolina', 'votes': 15, 'days': 3},
    {'name': 'Georgia', 'votes': 16, 'days': 3},
]

The assumption is that if we spend the number of days in the corresponding state, we will win the state.

The problem is how many electoral votes maximum that Trump can get in the last 10 days? So, if we add up these votes with all the red states, we would be able to estimate how many electoral votes Trump would have finally.

There are several ways to solve the problem. The most intuitive way is probably the recursive function. However, it is definitely not the best solution.

In this article, I’ll provide both the recursive solution and the dynamic planning solution. An explanation will be given to illustrate why dynamic planning is more advanced than the former.

The Recursive Solution

Photo by tkirkgoz on Pixabay
Photo by tkirkgoz on Pixabay

The idea of the recursive solution is relatively simple. That is, for every state, we have two options – go or not go.

Therefore, the function will be about

Getting the maximum electoral votes from the rest of the states in the rest of days

If we choose to go to to this state, we will get the electoral votes + the maximum electoral votes from the rest of the states in the rest of days. Otherwise, we should just return the maximum electoral votes from the rest of the states in the rest of the days.

Here is the code:

Just in case gist doesn’t work well sometimes, I also post the code in plain as follows:

def max_vote_recursive(states, days_left, index):
    # Terminating conditions
    if len(states) == 0 or index >= len(states) or days_left <= 0:
        return 0
# If we have enough days, go to this state
    votes_if_go = 0
    if states[index]['days'] <= days_left:
        votes_if_go = states[index]['votes'] + max_vote_recursive(states, days_left - states[index]['days'], index + 1)
# If we don't go to this state
    votes_if_not_go = max_vote_recursive(states, days_left, index + 1)
    return max(votes_if_go, votes_if_not_go)

If we run the function as max_vote_recursive(states_dict, 10, 0), we should get the result is 56 electoral votes.

Why did I say that this recursive function is not efficient enough? I can show you intuitively.

What I did is changing the last return statement return max(votes_if_go, votes_if_not_go) to the following snippet.

if votes_if_go > votes_if_not_go:
        print(f'There are {days_left} days left. We should go to {states[index]["name"]}')
        return votes_if_go
    else:
        print(f'There are {days_left} days left. We should not go to {states[index]["name"]}')
        return votes_if_not_go

Therefore, every step of the recursion will have an output for how many days are left and what is the current state. After the change, by running the function again, we will have a lot of output logs as follows.

There are 2 days left. We should not go to Georgia
There are 2 days left. We should not go to North Carolina
There are 2 days left. We should go to Arizona
There are 2 days left. We should not go to Florida
There are 2 days left. We should not go to Wisconsin
There are 2 days left. We should not go to Pennsylvania
There are 1 days left. We should not go to Georgia
There are 1 days left. We should not go to North Carolina
There are 1 days left. We should not go to Arizona
There are 1 days left. We should not go to Florida
There are 1 days left. We should not go to Wisconsin
There are 1 days left. We should not go to Georgia
There are 1 days left. We should not go to North Carolina
...

Please note that in these initial few rows, we can already find a duplicated output There are 1 days left. We should not go to Georgia. What I did then is to put the output into an array and then count how many duplicated output there are. The sorted results are as follows:

('There are 1 days left. We should not go to Georgia', 74),
('There are 2 days left. We should not go to Georgia', 63),
('There are 3 days left. We should go to Georgia', 51),
('There are 1 days left. We should not go to North Carolina', 45),
('There are 2 days left. We should not go to North Carolina', 41),
('There are 4 days left. We should go to Georgia', 40),
('There are 3 days left. We should not go to North Carolina', 35),
('There are 4 days left. We should not go to North Carolina', 29),
('There are 5 days left. We should go to Georgia', 28),
('There are 1 days left. We should not go to Arizona', 24),
('There are 2 days left. We should go to Arizona', 23),
('There are 5 days left. We should not go to North Carolina', 22),
('There are 3 days left. We should not go to Arizona', 21),
('There are 6 days left. We should go to Georgia', 19),
('There are 4 days left. We should not go to Arizona', 18),
('There are 3 days left. We should not go to Florida', 16),
('There are 6 days left. We should go to North Carolina', 16),
('There are 2 days left. We should not go to Florida', 15),
('There are 4 days left. We should not go to Florida', 15),
('There are 5 days left. We should go to Arizona', 14),
('There are 1 days left. We should not go to Florida', 13),
('There are 5 days left. We should go to Florida', 13),
('There are 7 days left. We should go to Georgia', 12),
('There are 6 days left. We should not go to Arizona', 11),
('There are 6 days left. We should not go to Florida', 11),
('There are 7 days left. We should go to North Carolina', 11),
...

Please be aware that more rows are truncated, but it is still very obvious that some of the "sub-problems" are repeated many times. For example, the sub-problem below is "calculated" 74 times.

We have 1 day left, should/can we go to the Georgia state?

Fortunately, we only have 11 swing states. If this kind of problem is transferred to another domain, we may have a huge number of nodes. The drawback of the recursive function, which is repeatedly calculating the sub-problems, might make the problem unsolvable with reasonable hardware resources.

The Dynamic Planning Solution

Photo by stevepb on Pixabay
Photo by stevepb on Pixabay

You may already be aware that the recursive function is actually a "top-down" solution. On the contrary, Dynamic Planning refers to the way of solving the problem in a "bottom-up" structure. It has the following characteristics:

  • The problem to be solved must be divided into sub-problems.
  • During the bottom-up inference, we must make sure that every step (sub-problem) is the optimised globally under its given condition(s).

Let’s have a look at the code first.

In case the gist has troubles to be loaded, here is the plain code. Please copy-paste it to your text editor for pretty indentation.

def max_vote_dynamic_planning(states, total_days):
    dp_matrix = [[0 for days_left in range(total_days + 1)] for index in range(len(states) + 1)]
for index in range(1, len(states) + 1):
        for days_left in range(1, total_days + 1):
            if states[index-1]['days'] <= days_left:  # If we have enough days left
                votes_if_go = dp_matrix[index-1][days_left - states[index-1]['days']] + states[index-1]['votes']
                votes_if_not_go = dp_matrix[index-1][days_left]
                # Save the maximum votes into cache
                dp_matrix[index][days_left] = max(votes_if_go, votes_if_not_go)
            else:  # We don't have any days left
                dp_matrix[index][days_left] = dp_matrix[index-1][days_left]

    return dp_matrix[-1][-1]
max_vote_dynamic_planning(states_dict, 10)

The matrix is then calculated as follows, and the maximum electoral votes we can get is the last value – 56.

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5],
 [0, 6, 11, 11, 11, 11, 11, 11, 11, 11, 11],
 [0, 6, 11, 16, 21, 21, 21, 21, 21, 21, 21],
 [0, 6, 11, 16, 21, 25, 25, 25, 25, 25, 25],
 [0, 6, 11, 16, 22, 27, 32, 37, 41, 41, 41],
 [0, 6, 11, 16, 22, 27, 32, 37, 42, 47, 52],
 [0, 6, 11, 16, 22, 27, 32, 37, 42, 47, 52],
 [0, 6, 11, 16, 22, 29, 35, 40, 45, 51, 56],
 [0, 6, 11, 17, 22, 29, 35, 40, 46, 51, 56],
 [0, 6, 11, 17, 22, 29, 35, 40, 46, 51, 56],
 [0, 6, 11, 17, 22, 29, 35, 40, 46, 51, 56]]

Here, the idea is as follows:

  • Initialising a 2-D matrix that uses the number of states as the rows and the number of days as the column.
  • Starting from the first state (index = 1) and the days left is 1.
  • If we go to the current state, we should add up the electoral votes of this state with the maximum votes we can get with the days left. The days left should be the current days left minus the days we need for promotion in the current state.

For this point, let’s suppose that we are calculating the second state, Nevada, and there are 2 days left (see dp_matrix[2][2]). If we choose to go to Nevada, we will get 6 electoral votes, but we will use 1 day to get them. So, we have 1 day left. Because we have 1 day left, the maximum votes we can get from the previous state Maine is 5. Therefore, the optimised result for this step is 11 votes.

  • If we choose not to go to the current state, then we should just use the maximum votes we have already optimised for the previous states.

Are you confusing? 🙂 Let me give you an example of how Dynamic Planning could know that when we should NOT go to the state.

Suppose we’re calculating for Minnesota, and there are 2 days left (dp_matrix[3][2]). If we choose to go to Minnesota, we will get 10 votes. However, after that, we will have 2–2=0 days left. On the other hand, if we choose not to go to Minnesota, we still have 2 days left, and the maximum votes we can get from the previous two states are 11.

Therefore, as the for loop going, for every single loop, we can make sure that it is the optimised up to now. That’s also why you can see that the matrix is sorted both horizontally and vertically. Hence, the global optimised number should be at the right bottom corner, that is 56.

A Simple Comparison

Photo by Free-Photos on Pixabay
Photo by Free-Photos on Pixabay

I should not just talk about how efficient Dynamic Planning is. Let me show some evidence instead.

Here is the elapsed time for the recursive function.

And here is the one for Dynamic Planning solution.

In this particular case, Dynamic Planning is about 10 times faster. If we have a problem having more nodes and possibilities, the difference gonna be huge.

Summary

Photo by cocoparisienne on Pixabay
Photo by cocoparisienne on Pixabay

In this article, I have made up a problem that to optimise the Election Promotion within a limited number of days. We can solve the problem using recursive functions very easily, but it turns out that it is not efficient because there are too many sub-problems that have been calculated multiple times.

Instead of using the "top-down" method (recursive), Dynamic Planning that solves problems using the "bottom-up" method. It starts from the smallest sub-problem and makes sure every step gives the optimised result under the current conditions, so the next step will be built on top of the current one. Therefore, it doesn’t have repeated calculations and the algorithm complexity is much smaller.

In the given problem, it has shown it Dynamic Planning solution is 10x faster than the recursive function solution.

A Little Joke

Photo by www_slon_pics on Pixabay
Photo by www_slon_pics on Pixabay

When you tell Trump that we can use 10 days to get 56 electoral votes, he seems to be pretty happy.

And he ask you: "OK. Then, what’s our itinerary? Which are the states we should go to."

You: "Well, I didn’t have that information at the moment. Let me tweak my code…"

Trump: "No. Let me do that. Trust me. No one knows Python better than me!"

🙂

Join Medium with my referral link – Christopher Tao

If you feel my articles are helpful, please consider joining Medium Membership to support me and thousands of other writers! (Click the link above)


Related Articles