WINNING RANDOMLY
Randomness : The Core Of Unpredictability
How airport security owes it to randomness
“There’s a lot of randomness in the decisions that people make.”-Daniel Kahneman
Consider a game of chess. There are countless strategies to win a game, some good and some, well, not so good. Nevertheless, there’s one thing all of these have in common, and that is the element of trying to be a step ahead, of being aware of the opponent’s next move. Indeed, more often than not, that ends up being the acute difference between winning and losing in most games.
What if we expand our view beyond this simple concept? What if, in an attempt to take a step ahead, your opponent ends up being farther from your next move than they were before? Taking this further, what if you yourself — let alone your opponent — don’t know your next move? Come to think of it, that’s exactly what makes “The Joker” much more than just another supervillain.
Allow us to introduce you all to chaos, a.k.a randomness, the ultimate form of unpredictability.
The concept of knowing your opponent’s next move becomes even more important in Stackelberg games. Named after German economist Heinrich Freiherr Von Stackelberg, a Stackelberg game is, in simple terms, a type of model in which a player (called the leader) moves first and based upon that, the other players (called the followers) make their moves in a sequential manner. Clearly, being unpredictable plays a key role in victory in such a situation. For example, if the leader’s moves are unpredictable, the followers cannot plan ahead and thus, cannot have a sure shot winning strategy prepared to counter the leader’s move with. They can do nothing but wait for the leader to show his hand and then come up with a strategy on the spot.
One of the major applications of Stackelberg game theory can be found in security systems at places such as airports, sea ports, and basically places where patrolling and security checkpoints are required in multiple positions. This might not be obvious at first sight, so let us walk you through it.
Problem Statement:
Suppose you are the officer in charge at an airport for deciding when and where to deploy patrol cars and checkpoints, given a set of routes that may potentially be passages to threats such as terrorists, for example.
Issues at hand:
You have limited resources to work with and not all the routes can be monitored at once!
How Stackelberg games explain it all:
You are now the “leader” in a Stackelberg game with the criminal as the “follower”. The leader here will make their move, i.e., set up security to prevent an attack from happening and then the follower will make their move, i.e., plan an attack through a route. Any criminal with an eye for spotting patterns can see straight through any kind of a proper security schedule and use it to their advantage.
But, as some of you might have guessed, what we have mentioned above is still not the best way to go about this problem. Here’s why:
Thinking in terms of probability, let’s consider the probability for a route to be monitored on a particular day. Assuming that the choices are completely random, we can assume this to be roughly the same for all routes. This is where practicality departs from the theoretical viewpoint in this problem. The idealistic approach mentioned above would have worked for a symmetric case. What we mean to say is that it would have been an optimal solution had all the routes been of equal importance and equally likely to be attacked. In reality however, there are numerous variables at play that make some routes more probable to be attacked, while some of them are safe enough to not require much attention. To tackle this, the randomization procedure used has to be optimized accordingly so that the more vulnerable routes are picked to be monitored more often than the safer ones.
The security team at Los Angeles International Airport (commonly known as LAX) were in a similar, if not the exact same position, when they called upon game theory to find the smartest solution to this problem. And the answer, as expected, was as simple as it was elegant; be random. Allow us to elaborate. In contrast to a proper schedule for security duties and deployment of guards and patrols on different routes, it’s all random. That is to say that from the perspective of the infiltrators or the criminals, there is no possible way of knowing for sure which routes will be monitored next. And that is all thanks to being random. There just doesn’t exist a “plan” or a pattern for monitoring the routes. They are left with no choice but to wait for the airport security team to make their move and come up with a plan of attack that same day.
After six months of using what’s called the Assistant for Randomized Monitoring Over Routes (ARMOR), the LAX police were extremely confident about their approach to the problem. A few potential threats, like cars carrying weapons, were caught by officers scheduled by ARMOR. It reportedly also made the police seem more present at the airport, and that too, while reducing the work of the people in charge of scheduling and allowing them to do other work instead.
Researchers have, since then, developed sophisticated softwares doing exactly this, just better than how a human would do it. They make use of behavioral game theory, which exploits models based on human behavior to get an idea of how the attackers might be planning their strategies, along with computational game theory, a concept that applies game theoretical ideas to design computer algorithms which iterate through and run calculations on games involving a large number of players and outcomes.
Here’s a look at how ARMOR managed to accomplish what it did and an overview of the algorithms used by it for the same.
For starters, it begins by taking a gain matrix as an input. Here’s how such a gain matrix would look like with just 2 targets and 2 defenders :
The payoff matrix presented here is a simplified model of what the real thing is like. In actuality, its size can go upto 100x100 or maybe even higher. Although as illustrated in the above matrix, situations like a Nash Equilibrium are often very hard to come across in such games as there will almost always exist a better strategy for either the defender or the attacker, given a particular pair of strategies chosen by the two. This is what makes the game even trickier for both the players as there exists no win-win or lose-lose situation in such a game. One player’s win is always a loss for the other and vice versa.
Food for thought: as the defender and the leader in the Stackelberg game, would you consider this a disadvantage or an advantage ? If you think this is a disadvantage, then so can the attacker. Can you somehow use that possibility to your advantage?
Now with the payoff matrix ready with the raw data, the computer needs to process it, like how a human would have done for a simpler matrix. The payoffs need to be combined and compared with all the possible combinations weighing in on the calculations. ARMOR does this by feeding this matrix into a mixed integer program (MIP for short), which is essentially just a program that optimizes the 'reward function' for the defender, or in simpler terms, chooses the best possible approach for the airport security based on, say the number of lives that may be saved by patrolling a certain route, while accounting for the probability of that route being targetted by the attacker.
As can be seen in the working of the MIP, probabilities play a huge role in predicting the behavior and outcomes of Stackelberg games. The most basic example of this is the fact that in the airport situation, the routes with lesser probability of being attacked may be focused on less than the other routes. Another factor worth considering are the 'weights' or the magnitudes of the different outcomes. For example, a crowded terminal or route requires more attention than the other routes. Combining these two factors, as a defender, one would have to find the perfect balance between the probability of a terminal being attacked and the magnitude of damage that an attack on that terminal could cause to come up with an optimal strategy in this game.
Even with this, no computer program or human brain can foresee and control every crook and nanny of the practical implications of such games. Real-life variables and uncertainties toss in a huge number of such factors into the mix, making it a complex problem requiring extensive use of logical reasoning, mathematical analysis, accurate prediction models, and game theoretical algorithms.
Just another day at the office for a fellow game theorist.
REFERENCES:
https://teamcore.seas.harvard.edu/files/teamcore/files/news_2012_07.pdf
