In the 1940s, mathematician Jon von Neumann and economist Oskar Morgenstern developed game theory, a technique used to analyse complex situations. Much like the centuries-old chess game, game theory abides by the principles whereby your moves are directly affected by that of your opponent.

At the recent World Expo 2020 in Dubai, SMU Assistant Professor of Computer Science Arunesh Sinha shed light on the importance of game theory in analysing modern-day situations during his presentation, Real World Decision Making using Game Theory.

For example, real-world security problems may be considered a “game” dependent on the behaviour of involved parties, albeit with much higher stakes. The greater the game's complexity, the more effort is required to reason and decide the best strategic move. As such, computer science and machine learning now play a critical role in game theory, as the analyses of most real-world games are beyond human capabilities.

From video games to the game of life

Prof Sinha first developed an interest in gaming strategies when he played popular strategy games such as Age of Empires as a student. Such games require players to strategise against opponents and lead their armies to victory.

"When I started my PhD, I was dazzled by how strategy games and mathematics come together," recalls Prof Sinha, who is also a Lee Kong Chian Fellow at SMU.

“Similarly, you can use your intuition from game playing and a little bit of math to design security allocation schemes for real-world problems.”

In the 1940s, mathematicians began researching optimal strategies to win games. These studies formed the foundation for game theory as we know it today. Since the theoretical framework was coined, mathematicians, economists, and computer scientists have applied it to real-world situations, such as modelling economic scenarios, computational interactions, and consumer pricing strategies.

Game Theory in Public Safety

In 2007, Professor Millind Tambe and his students from the University of Southern California (the former is now at Harvard University) applied game theory concepts to public safety in an experiment. They used the Los Angeles Airport and its checkpoints as the stage and patrol teams and criminals as the players.

In this scenario, there are eight checkpoints but only three patrol teams. The challenge lies in the fact that the patrol teams and criminals cannot reason about their opponents’ next move. Using game theory, Prof Tambe and his students accounted for all possible factors to develop the best strategy — patrolling three randomly chosen checkpoints daily. With this strategy, the adversaries cannot predict which checkpoint is unmanned. The lack of predictability increases their chances of failure and may even dissuade them from committing crimes  at all.

Countries have since adopted the game theory model derived by Prof Tambe across the globe in public safety and security practices. The US, for instance, applies the concept of game theory in their airport security measures as well as in patrolling different ports in the country. Singapore also uses the game theory model for its coastguard security and Civil Defense Force.

Protecting big game with game theory

National parks, forests, jungles, and other areas home to wildlife can also benefit from the game theory model to combat illegal practices like poaching. In this scenario, the wildlife reserve serves as the stage, the park rangers are the defenders, and the poachers are the adversaries.

The World Wide Fund for Nature (WWF) has been utilising software that integrates Prof Tambe’s game theory model in its daily operations. It works by dividing an area into different sections and recommends random parts of the map to patrol. The random selection of patrol areas may throw off adversaries, but the model needs to consider areas that need priority protection. To address this concern, the game theory model needs value estimates.

Value estimates suggest that certain areas are more valuable than others, thus making them more susceptible to attack. However, this solution also comes with a limitation — players only know the value estimates of their side.

So how do you calculate accurate value estimates of adversaries? According to Prof Sinha, “in practice, this is done by a team of domain experts who perform some sort of risk estimation to estimate these values, which is the adversaries' perception of how valuable each target is."

If data is available, machine learning algorithm systems may harness data from past attacks to estimate values of the adversary and predict the next move of the attacker. Then, armed with analytics on attack probabilities, the defenders can better strategise against their adversaries.

With value estimates, computer software can create algorithms to solve these games by finding the optimal strategies for the defenders. However, even with the advancement of the game theory model and corresponding computer software, real-world application faces further challenges. For example, there may be thousands of places to defend in specific real-life scenarios, and processing estimates for such large areas can take hours, even on supercomputers.

Today, artificial intelligence combines game theory and machine learning to make rational and optimal decisions in real-world security games. Playing these games can help save lives and property and prevent endangered species' extinction, creating a safer world for all.