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.
1,1 | 3,0 |
0,0 | 2,1 |
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.
Thank you for your post. I am also aware of this work on security games and kidney exchange. However, being still a student, and having a CS background, I am not still convinced that game theory can be easily applied in practice. I am only aware of some real applications of game theory, such as auctions (always tuned by experts to make up for the wrong assumptions or realistic constraints).
My main question is: what is the predictive power of game theory in real settings?
I would hope to see more and more applications coming out, Otherwise, I do not understand why do game theory for the sake of game theory (i.e. no value to the society).
It would be nice to see more applications, but basic research has value to society even if it doesn’t have immediate applications.
Speaking as an outsider there seems to be too much focus on single event games, when in real life the more common case is when games are played over and over.
In fact, both your Stackelberg games example and the anon comment above illustrate this wonderfully. Stackelberg games illustrate what can happen if play is repeated, while contract/radio spectrum bidding auctions are one of the few examples where the game happens so infrequently that it can be modeled nicely with classical “play a single game and its over” game theory,
Regarding the work on Security Games, there should first be an objective benchmark as to how to evaluate its performance. Since you don’t expect terrorist attacks to occur every month (or even a year), how are you going to compare the algorithm from some other arbitrary benchmark?
Moreover, how do you claim to know the utility values of the attacker for different targets, and how sensitive is the algorithm with regard to these exact values of the utilities?
Both questions (evaluation and robustness/sensitiveness) are great questions! It is always difficult to evaluate the effectiveness/performance of deployed systems (it is even harder to do so on security applications). On the one hand, we cannot switch security on/off for controlled experiments since terrorists won’t cooperate. On the other hand, we cannot show that we are “safe” after deploying the game theoretic systems since there is no 100% security. The objective is to show that we are now better off than previous approaches. Different evaluation approaches were tried including simulations, human subject experiments, comparing actual security schedules before vs after, security expert (e.g., FBI) evaluation, “adversary” team (i.e., red team) evaluation, supportive data from deployment, etc.
For the deployed application, all the payoff values come from the users who often have a risk analyst team that looked at the targets and assigned corresponding values for each one. The types of factors taken into consideration for generating these values include economic damage and injury/loss of life. To address the concern of robustness/sensitiveness, different types of robustness analysis on different types of uncertainties have been tried, including payoff values (as you mentioned), adversary decision (bounded rationality), adversary surveillance, adversary capabilities, adversary execution errors, etc.
Clearly, there is much more to do about evaluation and robustness analysis.
For those of you not familiar with this line of work, you can check the tutorial at UAI’11 (http://videolectures.net/uai2011_tambe_kiekintveld_game/) and Milind’s book (http://www.amazon.com/Security-Game-Theory-Algorithms-Deployed/dp/1107096421) published last year. You can also go to the project webpage (http://teamcore.usc.edu/projects/security/) for more resources.
I would like to add on to Bo’s point. Clearly, as Bo pointed out, security and robustness are very important questions that we focus on when developing and deploying these algorithms / applications. Furthermore, again as Bo said, the right question to ask is that are we better off than before (and not whether we are 100% safe). The objective of this research is to make the best use of the already available limited no. of resources, and we have successfully shown that we have improved security without any additional cost to the end user (security agencies) and with reduced burden on the officers.
Having said that, and keeping all the difficulties that Bo has pointed out above, I want to explicitly list out the 6-pronged approach that we have used for evaluation:
1. Models and simulations: We have compared the strategies generated by our algorithms against other randomization (uniform/weighted) /robust strategies in simulation. We have also compared them against our models of the strategies that the police officers were likely using. All these experiments show that our algorithms yield better strategies. This is also expected because of the mathematical rigor and proofs associated with our algorithms.
2. Experiments with human subjects: We have designed games simulating the security scenario faced the LAX police. These games have been played by USC students at our lab as well as by hundreds of netizens on Amazon Turk. Here, we give the human subjects controlled observations after they simulate an attack. These results have shown two things: (i) our Stackelberg strategies are better than naive strategies computed otherwise; (ii) better performance can be achieved against human subjects by exploiting their cognitive biases and “bounded rationality”. We have done so by borrowing insights from behavioral game theory and psychological literature.
3. Comparison of security schedules used prior to the use of our systems and after: Data is security sensitive in most domains, but for the domains that we have this data, we have been able to show that the schedules generated by our system are less exploitable.
4. Expert evaluation: While we are not privy to the exact procedures used by some security agencies in conducting their internal evaluations, we have been assured that our system was adopted only after extensive trials and evaluation. We have been subsequently awarded by letters of commendation by City of Los Angeles (LAX Police), FAMS, Coast Guard with mention of our system in Congressional committee hearings. Furthermore, the continued use of our systems even after many years alludes to the fact that our systems are appreciated by the end users. Additionally, while a human was generating schedules previously, our systems have significantly reduced cognitive burden while overcoming possible bounded rationality and biases of human schedules.
5. Red team tests: Some security agencies have conducted “Red Team Exercises” where they send some undercover officers to attack targets. These red team tests have also reported that our strategies have made the targets harder to attack.
6. Actual before and after data: While this is NON-scientific, before and after data, where ever available, has shown that our strategies have been more effective in terms of catching more threats.
With all this in mind, security and robustness are still open questions and we continue to look for ways: theoretical and experimental, computational and behavioral, simulated and real-world to address these questions better.
Please feel free to visit our webpage (http://teamcore.usc.edu) for more questions.
I love how Dawkins uses basic game theory to explain animal behavior and specialization in “The Selfish Gene”. That means “useful” enough for me
Thanks for an enlightening post! Wouldn’t you say that Stackelberg games are yet another valid criticism of the solution concept of Nash equilibrium?
I am a big fan of game theory and of Ariel Rubinstein’s approach, though I’m an expert on neither so please correct my misconceptions. I am wondering if there is confusion here between being useful and being used. So while game theory is being used in very important real-life applications, does it prove that it is making positive impact?
This seems to be related to the question of the first anonymous commentator about the predictive power of game theory. I am fond of one of Rubinstein’s “informal experiments” arguing that game-theory is mainly predictive of the behavior of those who studied game-theory, and they are worth off due to this behavior (again, apologies for any possible misunderstanding on my part). In addition, I like his theme of pointing out the ideological aspects of game theory and economics, and I admire his criticism of those who are promoting an ideology at the pretense of science. But I guess that I am getting way off tracks here …
Interesting points.
I don’t think of Stackelberg as a criticism of Nash, rather as a solution concept that makes additional assumptions (similarly to correlated eq., which assumes a correlation device). In the game of chicken, for example, the ability to commit to “dare” has been interpreted as the option to break off your wheel and wave it out the window…
For a partial answer to the second point, see Bo An’s reply to one of the comments above, in which he describes the various ways security forces evaluate the game-theoretic approach, including “adversary team” evaluation. I would say that, at least in this case, game theory is not only being used but is actually useful, i.e., it has been convincingly demonstrated that the approach has a positive impact compared to the previous approach (even though the “adversaries” are presumably not game theorists). Nevertheless, one cannot necessarily rule out the possibility that a different principled approach based on optimization (and of course RANDOMIZATION) would do even better.
To add on Omer’s point, game-theory is *used* all the time. Social and economic policies are often based on theories from microeconomics, which in turn has many game-theoretic considerations.
Are those theories really *useful*? some people get rich, others get broke. Sometimes countries flourish, sometimes markets collapse.
As a past security-officer, I can think of at least one reason why such algorithms improve security regardles of whether the theory works.
Security involves many rutine and even boring activities. Guards often “cut-corners”, take the easier route more often, etc. Moreover, even when the gurad is trying to randomize his action he can never do it properly. In other words, even if the head of security devised the optimal strategy, it will not be carried out.
On the other hand, guards and supervisers will be more reluctant to diverge from what “the computer says”.
Why isn’t there a report on EC?
Thanks for the nice post, Ariel! For this audience, the talk that I gave on this topic at the 2011 Innovations in Algorithmic Game Theory workshop might also be useful: http://www.youtube.com/watch?v=ZCd6G458fJM
I work in the computer security industry working on a companies internal “red team” that looks for holes internally, recommends mitigations, and supports incident responders. I’ve found Game theory concepts so useful I actually recommended that several of the incident responders take a course in it in their annual review.
in particular handling reported, but not yet publicly disclosed vulnerabilities lends it self well to basic game theory…(analyzing what the reporter wants, and what we can give)
additionally when reviewing the many options of where to harden our products architecturally, we frequently play out what the attacker(follower) response would be to each to understand how much of a permanent barier the hardening provides.
theres also a classic annecdote about the playstation 3 and homebrew computing(linux) vs.piracy, and playstation 3 being immune to piracy as long as it allowed homebrew computing (the linux folks being the uber hackers… by letting them in, the barriers to piracy held as the platform didn’t attract much uber-hacker attention, but once sony decided to revoke easy linux access for homebrew computing, the uber-hackers suddenly had a challenge and broke into the system in such a way that enabled piracy as well)… there’s an interesting lesson in incentives in there… somewhere… I think.
Hi Ariel,
Being a co-author of the initial series of kidney exchange papers in economics, I could not resist responding to your interesting post. I absolutely agree with you that our most significant contributions on kidney exchange have little to do with game theory and more with optimization, efficiency, and broadly non-strategic aspects of market design. In that sense kidney exchange is not the best application to promote the usefulness of game theory. (That said, initial research on kidney exchange is very much inspired by a few papers on cooperative game theory and mechanism design.)
Another line of research that I have been fortunate to be involved in is my research program on school choice, and the influence of game theory on this line of research is much stronger than the influence of game theory on kidney exchange. The only reason we were able to convince Boston Public Schools to replace their matching mechanism is that their old mechanism was very highly manipulable and we were able to offer strategy-proof alternatives. Essentially all of the recent reforms in school choice are driven by strategic considerations, some with our encouragement and others independently by policymakers (for example throughout England). The following paper gives an account of some of these recent developments.
Click to access PathakSonmez-Compare.pdf
In my opinion the influence of game theory has been much more profound for our academic and practical work on school choice than on kidney exchange (which might be better known by the cs community).
I recently gave a semi-general interest talk titled “How Does Matching Theory Improve our Lives?” where one can see several areas where game theory has clearly been very very useful. Here are the slides for this talk.
Click to access MatchingApplications.pdf
Fascinating. As a researcher of security games, I am always looking for domains with real-world successful application of game-theory, and this reference is great.
Good point Tayfun! As you said, the CS community is less involved in school choice, probably because there are no obvious optimization issues (at least ones that I am aware of): computation of two-sided matchings is typically easy, and the setting is static (i.e., there are no dynamically arriving and departing vertices). Itai Ashlagi did recently give a fascinating lecture about resident matching and school choice to an audience that included many talented CS grad students (as part of a mini-course on market design: http://www.cs.cmu.edu/~arielpro/summer/schedule.html#itai), so one can hope we’ll see some more CS-ish research in this space soon!
What about adversarial risk analysis to solve the kind of problems that stackelberg games propose? the bayesian community are developing models that seem to me more accesible for decision makers while robust, and therefore easily implemented in real life. I often find that many subdisciplines talk about the same with different languages and looses focus sometimes.
Perhaps it can be useful to discuss if game theory is useful by comparing the usefulness of Game theory to that of closely related areas like Statistics, Optimization, Theory of Computing, and theoretical economics.
“The computation of optimal strategies to commit to was first explored in an EC’06 paper by Conitzer and Sandholm.”
Security games under the name of “inspection games” have been around for 50 years, when the US Arms Control and Disarmament Agency (ACDA) commissioned game theorists, including many pioneers such as Aumann, Kuhn, Maschler, Selten, to analyze adherence to arms control treaties via game theory. For a survey of inspection games see
R. Avenhaus, B. von Stengel, and S. Zamir (2002), Inspection games. Chapter 51, Handbook of Game Theory, Vol. 3, eds. R. J. Aumann and S. Hart, North-Holland, Amsterdam, 1947-1987.
The role of commitment was pointed out already in this paper, 40 years before the above reference in EC’06:
M. Maschler (1966), A price leadership method for solving the inspector’s non-constantsum game. Naval Research Logistics Quarterly 13, 11–33.
In fact, our EC’06 paper didn’t say anything about inspection or security
games at all. It was Milind Tambe’s group who started the security games
line of work having come across our EC paper. They initially focused on
developing reasonably scalable MIP algorithms for computing optimal mixed
strategies to commit to in general Bayesian games, a case we had discussed
and shown to be NP-hard, but they managed to scale to their LAX instance
nonetheless (and improved their algorithm further later on).
It is certainly true that many others have analyzed optimal strategies to
commit to. Speaking even more broadly, one might say that this includes
all of mechanism design, since the designer typically gets to commit to the
mechanism in the first move. (And of course there is good old Stackelberg
competition itself…) I think Ariel’s remark is to be interpreted as
referring to the general algorithmic/computational complexity study of
computing optimal strategies to commit to, i.e., given an arbitrary
normal-form / Bayesian / … game with … players, can we compute an
optimal strategy to commit to in polynomial time? Is it NP-hard? Can we
compute approximately optimal solutions efficiently? Etc.
Maschler’s paper focuses primarily on a specific inspection game with two
utilities alpha and beta (though he does analyze the more general solution
concept in Theorem 3.1). Certainly, though, it is true that when we
consider the more recent literature on security games, Maschler’s paper and
others were well ahead of their time!
Bernhard, you’re making a good point, but as Vince said my statement is true if you put the emphasis on the word “computation” (at least from the computational complexity viewpoint). We should give more credit though to these early papers.