Machinations


Another Application of Game Theory
January 7, 2010, 5:43 pm
Filed under: Uncategorized | Tags: , , ,

Well it took me a trip out to Rome to find out about it, but David Kempe (at WINE) told me about another application of game theory developed in CS that is actually used in the real world.  Milind Tambe at USC has created a system that is currently used for scheduling security activities at the LA airport (and soon Pittsburgh airport) based on game theoretic concepts .  You can read about it here and in more detail in the research papers on Milind’s web page.

The basic idea seems like the following.  They analyze the problem as a Stackleberg game where the airport decides first on a probability distribution over which security activities will be scheduled that day (e.g. at which gates complete searches of luggage will occur, where and when drug sniffing dogs will be deployed, etc.) and then the “bad guys” get to decide on their actions e.g. which areas of the airport they will try to smuggle contraband through.  The goal of the airport security is of course to maximize the probability of catching illegal activity minimize the expected damage of illegal activity.  To do this, there needs to be some unpredictability on the part of the airport since the bad guys get to see the history of security activities.

This is really very cool research – David tells me that after implementing the system, LAX has been able to detect more illegal activity.

Advertisements

2 Comments so far
Leave a comment

A small suggested correction: The goal is not to maximize the probability of catching illegal activity, but to minimize the expected damage of said activity. For instance, since a lot of this work is to guard against terrorist attacks, this means one wants a higher frequency of guarding targets for which an attack would be considered more damaging (e.g., more people, higher visibility, higher economic value, …).

Comment by David Kempe

Thanks for the correction David! I didn’t realize you read this blog.

Comment by Jared




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: