Rain Talk: Security Games

Vincent Conitzer --- who, as Ashish pointed out, is a PolyCS person of AI, Theory and Economics --- talked at the RAIN seminar a few weeks ago. I am familiar with Milind Tambe's work at USC on game theory + physical security. What is remarkable about that work is that it breaks beyond academia and they have been phenomenally successful in getting their solutions deployed in airports for screening, flights for scheduling air marshals, coast guard inspections and so on. I have always been keen on hearing the research issues involved behind theses achievements and Vincent precisely addressed that and did a great job.

In particular, he focused on security games and asked: what equilibrium should one select? How does one model temporal/information structure? What are suitable structures for utility functions? And, do algorithms scale? Security strategies can be observed by intruders and thus this setting can be formalized as a commitment game where one party goes first and commits to a strategy and the other picks a strategy after observing the commitment. Commitment can be to pure or mixed (stackelberg games) strategies and can be viewed as extensive-form games (finite or infinite resp). Vincent described how the optimal mixed strategy can be determined via a set of LPs, and this has nice properties (agrees with Nash in zero-sum, leader has at least as good a payoff as Nash, no equilibrium selection problems, etc). Then Vincent reviewed concepts of correlated equilibria and the associated LP. After that the talk focused on LP for optimal correlated strategy to commit. He also went through several examples of security and resource allocation games, discussed compact LP issues, and so on.

For finale, Vincent had a great slide, pointing out where CS was pushing the boundaries of game theory. It is an amoeba with many protusions. I say, invite Vincent to give a talk, ask him to show you.