Milind Tambe.on game theory in security applications

||Conversations

Milind Tambe.portraitMilind Tambe.是Helen N.和Emmett H. Jones在工程中教授南加利福尼亚大学(USC). He is a fellow ofAaai.(Association for Advancement of Artificial Intelligence) andACM.(Association for Computing Machinery), as well as recipient of the ACM/SIGARTAutonomous Agents Research Award,Christopher Columbus Fellowship Foundation Homeland security award, theINFORMS Wagner prize for excellence in Operations Research Practice, theRist Prize of the Military Operations Research Society,IBM Faculty Award,Okawa Foundation Faculty Research Award, RoboCup scientific challenge award,USC Associates Award for Creativity in ResearchandUSC Viterbi School of Engineering use-inspired research award.

Prof. Tambe has contributed several foundational papers in agents and multiagent systems; this includes areas of multiagent teamwork, distributed constraint optimization (DCOP) and security games. For this research, he has received the “influential paper award“从国际代理和基金会Multiagent Systems (IFAAMAS), as well as with his research group, best paper awards at a number of premier Artificial Intelligence Conferences and workshops; these have included multiple best paper awards at the International Conference on Autonomous Agents and Multiagent Systems and International Conference on Intelligent Virtual Agents.

In addition, the “security games” framework and algorithms pioneered by Prof. Tambe and his research group are now deployed for real-world use by several agencies including the US Coast Guard, the US Federal Air Marshals service, the Transportation Security Administration, LAX Police and the LA Sheriff’s Department for security scheduling at a variety of US ports, airports and transportation infrastructure. This research has led to him and his students receiving the US Coast Guard Meritorious Team Commendation from the Commandant, US Coast Guard First District’s Operational Excellence Award, Certificate of Appreciation from the US Federal Air Marshals Service and special commendation given by the Los Angeles World Airports police from the city of Los Angeles. For his teaching and service, Prof. Tambe has received the USC Steven B. Sample Teaching and Mentoring award and the ACM recognition of service award. Recently, he co-foundedarmorway., a company focused on risk mitigation and security resource optimization, where he serves on the board of directors. Prof. Tambe received his Ph.D. from the School of Computer Science at Carnegie Mellon University.

Luke Muehlhauser: InTambe等。(2013), you and your co-authors give an overview of game theory in security applications, saying:

博弈论是适合对抗reasoning for security resource allocation and scheduling problems. Casting the problem as a Bayesian Stackelberg game, we have developed new algorithms for efficiently solving such games to provide randomized patrolling or inspection strategies.

You then give many examples of game-theoretic algorithms used for security at airports, borders, etc.

有证据表明,引入of these systems has improved the security of the airports, borders, etc. relative to whatever security processes they were using before?


Milind Tambe.: This is an important and wonderful question. There is a long answer to this question that compiles all of our evidence (this is actually abook章节)。我将尝试在此处提供更短的答案,并将尝试向我们的出版物提供指针,这些出版物汇编本证据。

As you note, we are fortunate that many of our game-theoretic algorithms for security resource optimization (via optimal scheduling, allocation) have jumped out of our lab and are now deployed for real use in many applications. As we write papers about these deployed applications, evidence showing the benefits of these algorithms is definitely an important issue that is necessary for us to answer. Unlike our more “mainstream” papers, where we can run 1000s of careful simulations under controlled conditions, we cannot conduct such experiments in the real world with our deployed applications. Nor can we provide a proof of 100% security – there is no such thing. So what can we do? In our evidence gathering, we have focused on the question of: are we better off with our tools based on computational game theory than what was being done previously, which was typically relying on human schedulers or a simple dice roll for security scheduling (simple dice roll is often the other “automation” that is used or offered as an alternative to our methods). Now within my area of Artificial Intelligence, that AI programs can beat humans at complex scheduling tasks is not controversial; but regardless we have used the following methods to provide evidence that our game-theoretic algorithms indeed perform better. These methods range from simulations to actual field tests.

  1. 仿真(包括使用“机器学习”攻击者):我们提供安全计划的模拟,例如,基于人类调度员使用的技术将我们的方法与早期方法的方法进行比较。我们拥有一台基于机器学习的攻击者,他们学习任何模式,然后选择攻击受保护的设施。游戏定理调度员被视为在提供更高水平的保护方面表现更好(Pita et al. 2008;Jain et al. 2010).
  2. 实验室的人体对手:我们已经致力于大量的人类主题和安全专家(保安官员),使他们通过随机安全计划,其中一些是我们的算法产生的计划,其中一些是基线方法进行比较。通过通过我们的安全时间表成功侵入他们收集的奖励来支付人类受试者;我们的游戏定理调度员再次表现得更好(Pita et al. 2009).
  3. 实际安全计划之前和之后:对于某些安全应用程序,我们有关于如何通过人类(部署算法之前的调度的数据以及如何在部署我们的算法后生成计划。对于安全机构感兴趣的措施,例如,在时间表中的可预测性,我们可以比较实际的人类生成的时间表VS我们的算法计划。同样,通过避免可预测性,可以看到游戏理论调度仪显着更好地表现更好,但确保更重要的目标被更高的巡逻频率覆盖。这些数据已发布(Shieh等人。2012年).
  4. “Adversary” teams simulate attack: In some cases, security agencies have deployed adversary perspective teams or “mock attacker teams” that will attempt to conduct surveillance to plan attacks; this is done before and after our algorithms have been deployed to check which security deployments worked better. This was done by the US Coast Guard indicating that the game-theoretic scheduler provided higher levels of deterrence (Shieh等人。2012年).
  5. 实时比较:人类vs算法:这是我们在洛杉矶的地铁列车上跑了一项测试。对于巡逻计划的一天,我们提供了试图安排90名巡逻队的人类调度人员对自动化游戏定理调度程序进行的人力调度员的头脑比较。然后,外部评估员提供了这些巡逻的评估;评估员不知道谁生成了每个计划。结果表明,虽然人类调度员也需要大量努力,即使是生成一个时间表(差不多的日子),外部评估人员也会评估更高的游戏定理调度员(具有统计学意义)。(Delle Fave et al. 2014a,delle fave等人。在考虑中)。
  6. Actual data from deployment: This is another test run on the metro trains in LA. We had a comparison of game-theoretic scheduler vs an alternative (in this case a uniform random scheduler augmented with real time human intelligence) to check fare evaders. In 21 days of patrols, the game-theoretic scheduler led to significantly higher numbers of fare evaders captured than the alternative. (Delle Fave et al. 2014a,Delle Fave et al. 2014b).
  7. Domain expert evaluation (internal and external): There have been of course significant numbers of evaluations done by domain experts comparing their own scheduling method with game theoretic schedulers and repeatedly the game theoretic schedulers have come out ahead. The fact that our software is now in use for several years at several different important airports, ports, air-traffic, and so on, is an indicator to us that the domain experts must consider this software of some value.

所有这些证据表明,安全资源优化的游戏理论方法明显优于竞争对手,即人类调度员或简单随机化。人类被认为是可预测的模式;事实上,这是一个极其复杂的对抗性调度/规划/分配任务,人类必须推理大量可能的时间表(实际上也是更多的),并且对于人类来说是耗时和非常困难的。似乎我们应该让这种复杂的任务交给软件,让人类专注于实际提供安全性的更重要的任务。


Luke: Diana Spearsmentioned你教导了一个关于“人工智能和科幻小说”的课程,其中包括关于你的“亚马夫人类的研究”一节。亚博体育官网是这个2007年教学大纲still a pretty accurate outline of the course? What work on “Asimovian multiagents” do you discuss? She mentionedSchurr et al. (2006); is there any other work on that topic you’ve done?


Milind: The last iteration of “Understanding intelligent agents via science fiction” was taught in 2010. Here is thesyllabus for it.

本课程与我的前博士生,Emma Bowring教授联合开发,现在是太平洋大学的副教授,真的是她的想法,而她仍然是USC的学生。我们写了关于本课程的(Bowring & Tambe 2009).

While we did use Asimov’s short stories extensively, the goal here is to really introduce core concepts in agents and multiagent systems, as can be seen from the syllabus. So the focus is more on using these stories, Star Trek clips, and other science fiction as a motivation to introduce core concepts in AI/Agents and Multiagent systems, starting from Markov Decision Problems (MDPs), POMDPs, Game theory, agent modeling and so on.

While you are right that we have done some follow up work based on Diana’s original paper and earlier paper byWeld & Etzioni (1994)and that is a fascinating thread of research, but that isn’t the focus of this course. This is more of an undergraduate course introducing students to key concepts. Towards the end of the course we get into abstract ideas on agent design where students may use some of the ideas advocated in these “Asimovian agents”, which is great.

We haven’t pursued that research direction beyond that paper and an earlier one (Pynadath and Tambe 2001).

It would be a great idea to push that direction more though.


Luke: InTambe等。(2013)您可以在安全应用程序中确定游戏理论的亚博体育官网开放研究问题,例如可扩展性和稳健性。如果他们可以康复,您认亚博体育官网为这一领域的开放研究问题会有最大的实际影响吗?


Milind: Both scalability and robustness are important. Scale-up is important because we want to solve large-scale games. For example, even if we leave aside complex scheduling constraints and just think of the abstract assignment problem of security agencies such as Federal Air Marshals Service of assigning say 20 defenders to 1000 flights, that is 1000-choose-20. These problems become so large that we cant fit games in the normal form in memory and must somehow find an optimal defender strategy without explicitly representing the game in memory. On the other hand, we wish to handle robustness because of the many uncertainties in the game. There is uncertainty related to adversary’s surveillance (how much surveillance is actually going on), uncertainty about adversary’s payoffs, capabilities, and so on. When we combine the two requirements of solving large-scale games and handling uncertainty, then the problem becomes even more complex. These remain critical challenges for us to address.

There are however many other major research challenges that are open. Significant effort has been focused on modeling adversary bounded rationality. This exciting research at the intersection of algorithmic and behavioral game theory is a major area of research in security games. Furthermore, our recent work focused on protecting wildlife and fisheries (Yang et al. 2014;Haskell等人。2014年)带来与机器学习相关的挑战。具体而言,我们现在有与偷猎者的动作和动作有关的数据。该数据可用于创建更好的偷猎者模型。另一个区域是偏好引出。如果与域的许多方面有关的显着不确定性,并减少这种不确定性会努力,然后我们首先关注哪些功能以减少不确定性?我们最近在Aaai'2014的论文(nguyen等人。2014年)将我们的初始推动力提供给该地区。

In short, while we have made significant progress, not just in my group, but as the “security games community,” there is a lot more that still needs to be done.


Luke:谢谢,Milind!