Applying Game Theory to Beat the Bad Guys

November 6, 2007

Security officials at Los Angeles International Airport (LAX) are experimenting with a computer system that they hope will make life even more difficult for criminals and other undesirable visitors than it is now. Developed at the University of Southern California (USC), the system makes it harder for outside observers to find any patterns or regularities in LAX security routines.

The software package, called ARMOR, tracks all airport resources, schedules, and relevant information — flight schedules, number of security officers, K9 units, security-shift changes, and so on — to set up secure coverage of LAX that appears completely unpredictable to outsiders.

The system is the result of a simple observation about airport security that USC doctoral student Praveen Paruchuri made in his 2007 thesis. He noted that, for security, "the police have to commit to a policy, while their adversaries may observe and exploit the policy committed to." Paruchuri's thesis is titled "Keeping the Adversary Guessing: Agent Security by Policy Randomization." It builds upon the mathematical business strategy called the Bayesian Stackelberg game, which is the basis of the experimental security system at LAX.

Realizing that the scheme boiled down to optimization problems and their solutions, Paruchuri made use of artificial intelligence techniques whereby computer programs play individual, cooperative roles in problem solving to come up with an improved algorithm for solving such problems. He was assisted by computer scientist Sarit Kraus, of Bar-Ilan University in Ramat Gan, Israel, and systems engineer Fernando Ordoñez of USC, who was instrumental in first formulating and then efficiently solving Bayesian Stackelberg games.

Source: University of Southern California, Oct. 1, 2007.