Author: Mohammed Osumah

We’ve seen numerous disease outbreaks occur. The Ebola virus in West Africa, Cholera in Yemen, Hepatitis A in the United States to name a few. The spread of disease, which leads to major outbreaks is a very important and interesting topic. Everyone should make a conscientious effort to be well informed and take appropriate measures to prevent outbreaks .

When reading the title of this blog, one might wonder, How on Earth does game theory relate to disease outbreaks? In a recent article titled, “Game theory can help prevent disease outbreaks”, by authors Istvan Zoltan Kiss and Nicos Georgiou, they showed how game theory can and does play a big role in disease outbreak prevention.

When it comes to decisions about health, what’s best for us individually might not always be the best thing for the whole population, and vice versa. This leads to difficulty for authorities in making decisions to protect the populace. It’s easy to see how game theory ties into this problem.

A good example of this that the article talked about was the approach of having the population take vaccination, as shown in the image above. Vaccines have been proven safe, but they can have short-term negative effects such as, financial cost, pain from injection, a temporary reaction from the immune system. When deciding whether to get vaccinated, one has to weigh up these costs against the benefit of getting vaccinated to protect themselves from the disease. It might seem obvious to accept the costs and get vaccinated, but what if everybody else in the population gets vaccinated? You’d be relatively protected, so not getting vaccinated might appear to be the better choice. The problem with this is that if everyone thought like this then no one will be protected and a major disease outbreak could occur.

How would a best strategy in situations like this be determined? The article brings up the idea of Nash equilibrium. In some cases the optimal strategy for an individual can also be optimal for the population as well. The understanding of Nash equilibrium can help authorities in choosing strategies for disease outbreak prevention.

An example of this would be a situation where people from one area could choose whether to travel to another area affected by the disease or not. If the risk of disease was high because the outbreak was publicised in the news, individuals would logically choose not to travel. This would be beneficial with authorities in their desire for a travel ban to that area affected by the disease. Here, having the severity of the outbreak publicised in the news, helped tourists in implementing a travel ban, because they understood that an optimal strategy for individuals then would be to not travel.

Evidently, game theory can help in making sense of all the factors for finding out when individuals are most likely to act in a way that isn’t beneficial to the group. In response to that, authorities can then implement appropriate measure in order to decrease the chance of a disease outbreak.

References

https://theconversation.com/game-theory-can-help-prevent-disease-outbreaks-102934

https://www.contagionlive.com/news/the-10-biggest-infectious-disease-outbreaks-of-2017

Road networks are essential for transportation in many states, cities, towns, and villages. People travel on roads everyday in order to get to work, to school, to business meetings, to transport their goods, etc. A big problem in road networks is finding shortest paths between various locations. A motivating example of why we want to find shortest paths between various locations in road networks is google maps. Ever tried using google maps to get the fastest direction from your house to school? Google maps tries to find the shortest path that gets you there the fastest.

Shortest path problems are inevitable in road network applications such as city emergency handling and drive guide handling. I am going to look at how to tackle these problems, using graph theory which we learned in lecture to give a representation of the network and an efficient algorithm for finding shortest path from every node to every other node.

A way to tackle these shortest path problems in road networks is to use Dijkstra’s shortest path algorithm. Dijkstra’s Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non negative edge weight, producing a shortest path tree. For example, suppose the vertices of the graph are cities, the edges are direct roads, and the edge weights are driving distances between pairs of cities. Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities.

Dijkstra’s algorithm works as follows.

Step 1: Start at the ending vertex by marking it with a distance of 0, because it’s 0 units from the end. Call this vertex your current vertex, and put a circle around it indicating as such.

Step 2: Identify all of the vertices that are connected to the current vertex with an edge. Calculate their distance to the end by adding the weight of the edge to the mark on the current vertex. Mark each of the vertices with their corresponding distance, but only change a vertex’s mark if it’s less than a previous mark. Each time you mark the starting vertex with a mark, keep track of the path that resulted in that mark.

Step 3: Label the current vertex as visited by putting an X over it. Once a vertex is visited, we won’t look at it again.

Step 4: Of the vertices you just marked, find the one with the smallest mark, and make it your current vertex. Now, you can start again from step 2.

Step 5: Once you’ve labeled the beginning vertex as visited – stop. The distance of the shortest path is the mark of the starting vertex, and the shortest path is the path that resulted in that mark.

Dijkstra’s algorithm provides us with a very efficient way to find shortest path. This algorithm is a very useful practical algorithm for finding shortest paths in road networks. Using graph theory, we can represent these road networks as vertices and edges, with edge weights, which gives us a representation of the networks in which we can use dijkstra’s algorithm to find the shortest path from a vertex to every other vertex.

References

https://zenodo.org/record/3375123#.Xa_N-ChKg2w

https://www.researchgate.net/figure/The-search-space-of-Dijkstras-algorithm-on-a-road-network-for-a-given-source-and_fig2_262319862

https://study.com/academy/lesson/dijkstra-s-algorithm-definition-applications-examples.html