Al Roth recently recounted an amusing story about a seminar where he gave a talk on market design. His talk was followed by a talk by Ariel Rubinstein, who argued (as he often does) that game theory is not useful. When asked about Roth’s work, Rubinstein reportedly answered: “Oh, Al’s stuff is useful alright. But it’s not game theory.”
I guess the answer to the question “is game theory useful” depends on how you define “game theory”, and how you define “useful” (fortunately the word “is” is clear). Rubinstein has a point though. Take kidney exchange for example. Arguably the most useful results, which inform deployed applications that are saving lives, deal with efficient exchanges and algorithms for computing them. In contrast, game theoretic results are more speculative at the moment.
Nevertheless, I do think that game theory is useful. A recent line of work on security games, which is most associated with Milind Tambe’s group at USC, is a case in point (which seems to provide a counterexample to the specifics of Rubinstein’s argument). Strangely enough, it seems that this line of work is not yet well-known outside the AI community. (I realized this last week when, during AAMAS, I bumped into a group of prominent theory guys who accidentally wandered into the conference while trying to escape an EC workshop. Reeling from culture shock, they wanted to know what this AAMAS thing was anyway, and what all those AI people were doing. Security games is one of the hottest topics in AAMAS in recent years, so it came up.) Anyway, IMHO work on security games is one of the few examples of research coming out of algorithmic economics that is directly making the world a better place (kidney exchange is another example), so it deserves some discussion.
To understand security games one must know a bit about Stackelberg games. A Stackelberg game typically has two players, a leader and a follower. The leader commits to a strategy, and the follower selects a best response. For example, consider the following game.
The only (mixed) Nash equilibrium is (up,left). However, by committing to down, the row player can get the column player to play right, thereby increasing his own payoff from 1 to 2. An even higher payoff of 2.5 can be guaranteed by committing to a mixed strategy that plays down with probability slightly greater than 0.5. The computation of optimal strategies to commit to was first explored in an EC’06 paper by Conitzer and Sandholm.
Now, suppose you are in charge of airport security. You must decide how to deploy patrols, where to point security cameras, etc. Potential attackers can observe your (possibly randomized) policy and respond accordingly (by choosing which targets to attack). Therefore, you are playing a (Bayesian) Stackelberg game where you are the leader, and the attacker is the follower. The main technical challenge is the computation of good strategies for the leader despite the huge strategy space, and the solutions, published in scores of AAAI/IJCAI/AAMAS papers, tend to rely on heuristic mixed integer programming techniques. Amazingly, these algorithms now run security for LA International Airport (LAX), the federal air marshals, and the coast guard!
Should we be worried? I was, initially. After all, game theory doesn’t really work, does it? I was able to dig up a 2007 Newsweek story, which I read at the time. Here is a scary quote:
Now all airport security officials have to do is press a button labeled RANDOMIZE, and they can throw a sort of digital cloak of invisibility over where they place the cops’ antiterror checkpoints on any given day.
Wow, RANDOMIZE; truly futuristic technology! One can only hope that the relevant security experts and decision makers have a better grasp of the details of the game-theoretic approach and the assumptions that are being made. In any case, I gathered from Tambe that the above security forces have their ways of reliably comparing methods, and the game theoretic methods outperformed their previously used methods.
But wait, to compute an optimal strategy to commit to we need to see the game; where do the payoffs come from? Apparently there is a vast literature on risk analysis, and there are people whose job it is to come up with these numbers. Hold on, can the attacker actually observe the defender’s strategy? Air Marshals for example typically work undercover; should the air marshals identify themselves to potential terrorists to justify the Stackelberg model?!
These seem like reasonable concerns, but the experience of the last few years shows that the approach works and the issues are solvable. If that doesn’t count as both “game theory” and “useful”, I don’t know what does.