Serious games against murderous enemies

Terrorists, drug smugglers and even deadly viruses are bitter enemies. Wise use of game theory may improve dealing with them

Israel Benjamin

For terrorists, Los Angeles International Airport is undoubtedly an attractive target for attack. The airport, known as LAX, is the sixth busiest in the world, and in 2009 about sixty million (!) passengers passed through it. For those who are in charge of the security of the place and the protection of the lives of those at the airport, the need to put in place the best defenses is a daily challenge: it is impossible to guard every point at every moment, both because of budget limitations and because such guarding would create impossible delays and prevent the airport from functioning . On the other hand, any unguarded passage may be used by the terrorists to infiltrate the airport and lead to disaster.

How can you choose the save templates and check points in a way that ensures maximum security? For mathematicians, this is a kind of game: the first move is of the security manager, who chooses the protection plan. The second move is the terrorist's, who decides on the course of his attack, or decides not to attack. Using game theory for life-or-death options may sound strange, but it has a long history, including the considerations that guided the development and production of nuclear weapons during the Cold War.

A.S.A.P. Creative | Carlos A Torres, Shutterstock

When it is better to decide randomly

The "LAX game", as we will refer to it later, has characteristics that distinguish it compared to other games known to mathematicians. It is replayed every day, when for the terrorist organization, one "success" is a victory even if it comes after many losses. In addition, the security manager must assume that the defense pattern is known to the attacker, since he can learn the security methods over a long period of time. This fact rules out fixed patterns: if the defense is always at the same points, it will be easy for the attacker to choose a route that does not pass through those points.

Therefore, when it is impossible to test all car traffic routes into LAX and all walking routes within it, the preferred patterns are random. In this way, the attacker can learn the probabilities of guarding a certain path, but cannot be sure if on the day of the attack this path will indeed be exposed.

It is important to understand that the meaning of random selection is not a coin toss, and it does not free the security manager from the need for thinking and planning. Random patterns determine a probability for each decision, such as "a probability of 0.7 for a police car patrol on road section A; 0.4 probability of inspection by sniffer dogs in area B of the terminal, …”. It is important to choose good templates, but what is a good plan and how can you find it?

Since 2007, the ARMOR software developed to answer these questions has been running at LAX. The name ARMOR, which means "armor" in English, is an acronym for "Assistant for Randomized Monitoring Over Routes". The software was developed by a team of researchers from the University of Southern California with Prof. Sarit Kraus from Bar-Ilan University.1

A.S.A.P. Creative | Yacobchuk Vasyl, Shutterstock

How do you measure success?

To choose the pattern, the software needs information about the possible save points and the expected "profit" for the attacker if he can penetrate through these points. Let's demonstrate this in a simple case: let's assume that the budget allows to maintain at a given moment only two out of three ways of access, ways A, B and C. In this case, there are three options for the defender for the game taking place at that moment: A and B, A and C or B and C. If the attacker has good reasons to prefer penetration through A or B, and the attack options he can reach through point C are more limited, it is tempting to decide to keep only A and B.

This is a bad decision, of course, because the attacker could learn that point C is never protected and may prefer the penetration through this point: although the "profit" from it is lower, the chances of success of the terrorist operation are much higher in this situation. A better decision is a random pattern between the three options: 70% chance to keep A and B, 15% chance to keep A and C and a similar chance for B and C. Therefore, every decision of the attacker involves a real risk for him.

From this it follows that there is a need for a model of the attacker, which includes an assessment of the profit he attributes to each attack path. The profit estimate may change from day to day due to receiving intelligence or events at the airport, such as a visit by an important personality. Also, there are several types of attackers who may find LAX an attractive target, each for their own reasons. Therefore, the software needs a model for each type of attack, and the assessment of the probability of an attack for each type. It is clear that the information in the defender's hands is incomplete, therefore there is no certainty that the probability estimates and profits included in the validity model are accurate. The mathematical tools of game theory make it possible to deal with this problem as well.

When it is not known whether terrorists intended to attack a particular target, it is difficult to assess whether the defense system was able to deter them. However, success can be measured in other ways, including success in curbing different types of crime. By this measure, the math of game theory does work in the real world: In 2009, when the City of Los Angeles awarded the project's developers badges, the LAX police chief noted that the software had contributed to the arrest of illegal gun owners and drug smugglers at the airport.

An attack that does not make sense

Game theory generally assumes that each player acts in the best way for him, that is, in the way that will produce the highest benefit for him. As economists and psychologists have already discovered, this assumption is inaccurate. First, most people find it difficult to accurately calculate the expected benefit of each action, even when the opponent's moves and the probabilities are known to them and even when they have a good understanding of probability theory.

This phenomenon is called "bounded rationality" (bounded rationality) and it leads to the selection of moves that are not optimal, due to a limitation in the ability to calculate (this is not stupidity: for many problems of this type, even supercomputers will not be able to find the optimal action in a reasonable time). Second, humans have difficulty estimating probabilities, and in particular they are prone to the "anchoring" phenomenon, that is, they maintain their initial probability estimates even when information that contradicts the estimate and points to a different probability accumulates.

Finally, even the most rational attacker may know only partial information about the defender's action patterns, even when the defender builds these patterns under the strict assumption that the attacker knows the patterns and the software that creates them. Apparently, the limitations of the attacker's rationality and information improve the defender's chances of success, but it turns out that when the defender ignores these limitations, he may choose the wrong strategy. In the example shown of three access routes, an adversary who ignores the fact that routes A and B are protected is more likely than route C to attack one of the two routes, because they protect higher priority targets for him. If the defender could be sure that this was the attacker's way of thinking, the correct strategy would be to defend only A and B, and success would be guaranteed.

In another study within the framework of ARMOR, these complexities were examined through more sophisticated algorithms. To test the success of the algorithm in this case, which refers to human cognitive limitations, an experiment against human "attackers" was necessary. For this purpose, participants were recruited in an experiment based on a computer game. In the game they were required to steal treasure from pirates by choosing a door through which they would enter, hoping that at that moment there would not be a pirate guarding that door. The participants were given the opportunity to watch the pirates and see which doors they guarded for several "rounds" before being required to choose the door through which they would try to enter in the next round. Thus, the experiment made it possible to examine the effect of the availability of information (the higher the number of observed rounds, the more accurate the probability estimate can be) on the attacker's strategy, and to examine the success of defense strategies against different attackers. In these experiments it was found that the algorithms that also considered the limitations of the attacker achieved better success against the human participants.

A.S.A.P. Creative | Sebastian Kaulitzki, Shutterstock

A brain game against a virus

Doctors who choose treatment against the HIV virus, which causes AIDS, are also playing a game against a murderous opponent. As we know, this virus undergoes rapid mutations, therefore even when a combination ("cocktail") of drugs is found that inhibits the progression of the disease, eventually one of the mutations will lead to the creation of a virus against which none of the drugs in the cocktail are effective. When this happens, the attending physician must find another combination.

To find an effective combination, it is possible to use the decoding of the genetic code of the virus collected from the patient's blood. International organizations are collecting information on the mutations found in the virus, and on the protection each mutation may give the virus against different drugs. This information appears in "mutation tables". There are also "expert systems" - artificial intelligence systems that save the need to manually consult the tables in search of a drug combination suitable for the new mutation. The software produces recommendations for combining drugs, when it also takes into account complex rules and interactions between different mutations (for example, when two mutations, at two different sites in the viral genome, do not in themselves constitute protection against a drug, but the appearance of both mutations together makes the same drug ineffective).

One of the problems with the mutation table method is the need for a human assessment performed by doctors, each of whom has access to information on only a small portion of all patients. In the article "Chasing the AIDS virus", published in March 2010 by a group of researchers from the Max Planck Institute in Germany, methods from the field of computational biology are described for learning the relationship between the genotype (the sequence of nucleotides that constitutes the genetic code of the virus) and the phenotype (the behavior of the virus, expressed in this context) in its resistance to drugs).

Computerized learning shortens the learning process and bases it on a comprehensive scan of large databases. She even managed to locate in the collected information mutations leading to drug resistance that had not been identified before.

The escape route

A successful drug combination is one that succeeds in inhibiting the strain of the virus currently residing in the patient's body; But this requirement is not enough: the virus will undergo many mutations. Most of the mutations will reduce the virus' ability to harm or its resistance to drugs, but there will also be mutations that will give it a higher resistance. As the principles of natural selection predict, the epidemics in which these mutations appeared will multiply until they are the main strain of the virus in that patient, and a new combination of drugs will be required to deal with that new strain.

For reasons whose biological basis is not well understood, not all series of mutations are equally probable. It is possible to identify "escape paths" - series of mutations that appear with a significant probability, and in the end the virus develops resistance to the treatment. The researchers describe probabilistic learning methods that allow them to tap the escape routes from the databases where the decoding of the genetic code of viruses as they appeared in tens of thousands of patients are collected, with the clinical information on the success of various drugs in these patients. Learning would be much easier if longitudinal data were available, meaning the genetic code of viruses collected at different times from the same patient, but such information is rare. Therefore, the researchers required advanced mathematical methods to deduce the "preferred" mutation series from "cross-sectional" data - the details of the genetic code of viruses collected from different patients.

Once those "escape paths" are known, and the probability for the virus's "choice" in each such series of mutations, it is possible to examine the proposed treatments not only according to their effectiveness against the current strain of the virus but against the virus's next "moves". The words "choice" and "moves" appear in quotation marks because the virus obviously does not think or plan, but the random mutations filtered through the process of natural selection play a similar role. Also in this "game", as in the "LAX game", the doctor chooses the first step in a way that will reduce as much as possible the expected success for each step chosen by the attacker.

With the help of this information, it is possible to test proposed drug combinations and evaluate how effective each of them is against the current strain and against the strains that this strain is likely to reach through the common mutations. The authors of the article report that the use of "treatment optimization" in this method may reduce the number of ineffective treatments from 24% to less than 15%, and that today the clinics that treat two-thirds of the AIDS patients in Germany use the software developed as part of this project.

Other studies also use game theory to adjust treatment regimens for AIDS patients. One of the newest among them is an article published by researchers from the University of Tennessee a few months ago, in which the course of the disease is represented as a game between the virus and a "coalition" consisting of the immune system and the drug treatment. This study showed that there is an equilibrium state (that is, a state in which neither side has an advantage in changing their strategy) in which the T cells of the immune system continue to survive.

Playing seriously

The main contribution of game theory, despite its name, is in areas that are not perceived as a game, including economics, war, negotiations, effective use of frequencies (see: "The game of interference: how to choose communication frequencies", "Galileo" 139) and more. Even when the opposing "player" does not share the preferences or values ​​that guide the defending player, is not necessarily rational even by his own standards, and does not wish to accept any rules of the game, there are still tools in game theory, artificial intelligence and mathematics that allow choosing the best moves Most to protect us from such murderous actors. These tools have already proven their effectiveness in practical tests, and they are branching out into other uses: for example, the group that developed ARMOR also developed software for placing agents in civilian clothes that protect international flights from hijacking, and this software has been in practical testing since October 2009.

1. Prof. Sharit Kraus is the recipient of the AMT Award - Art, Science, Culture - in the field of exact sciences for 2010, with Prof. David Harel from the Weizmann Institute of Science.

Israel Binyamini works at ClickSoftware developing advanced optimization methods.