何毓琦的个人博客分享 http://blog.sciencenet.cn/u/何毓琦 哈佛(1961-2001) 清华(2001-date)

博文

Security and Game Theory 精选

已有 10698 次阅读 2012-11-4 05:04 |系统分类:海外观察

(For new reader and those who request 好友请求, please read my 公告栏 first)

I recently went to a talk with the above title by Professor Milind Tambe of the University of Southern California. It is an impressive presentation of how simple conceptual idea plus interesting applied mathematics can be used to solve very real life engineering problem and with demonstrable superior results. For me the talk contains several important lessons for all applied scientists/engineers in academia that are worth repeating and emphasizing.

First what is the problem? In a major city such as Los Angles, there are inviting targets for the terrorists to attack (recall the World Trade Center in New York City).The Homeland Security Agency of the US wants to protect such targets by setting up checkpoints along various routes to the target. However, resources are always limited and cannot cover all contingencies. Problem: how and where to establish the checkpoints. Note terrorist have all the time in the world. They can always find the weakest point of your defense and exploit such knowledge in launching their attack. Thus, it is clear that any deterministic plan of checkpoints are almost useless. Random strategy must be used. But this leads to the second question: what kind of randomized strategy should be used knowing full well the terrorists will take advantage of any weakness in the strategy, e.g., a random strategy assigning resources uniformly to all checkpoints is not optimal since the terrorist will simply choose to attack the checkpoint(s) that will results in maximal payoff. To find the optimal random strategy is known as solving a Stackelberg game.

But this conceptual idea is well known in game theory for several decades. I myself have worked and published five papers on this concept some quarter a century ago (note 1). However, like most authors, I was simply interested in adding to the concept and methodology of the literature and did not pay much attention to application; nor were there many pressing applications at that time.

In addition, it is well known in game theory that a straightforward application of game concepts to any real world problem will results in computational burden orders of magnitude beyond what will be practical or possible. That is known as the “SCALE UPissue in practical applications. Thus game theory was used primarily as a tool to gain qualitative insight.

Other examples of “games against terrorists” are

1.      Assignment of limited number of air marshals to various national and international flight every day,

2.      Routes and schedules for patrolling the Boston harbor by the limited number of coast guard boats,

3.      You can imagine many other possibilities

Faced with these pressing real problems and the computational difficulties of solving real world Stackelberg games, the author proceeds to tackle (i.e., to simplify and reduce the needed computations without throwing away the essence of the problem) the mathematical issues behind the problem with a view to simplify and reduce the necessary computation to that can be done in minutes on a laptop in field operations. This is the academic contribution of the author to the literature on game theory, i.e., resolve the computational difficulties using or inventing advanced mathematical tools.

But this is not all. To actually put such solution to use, you must convince the authorities to deploy and implement the solution vs. what they have been doing. To do this, you must somehow demonstrate in a convincing way that your result will produce measurable improvement. Finally, to cap your achievement, the agency and your peers will recognize you by giving you unsolicited awards for what you have done. Real engineering is not complete until this final step.

All this you can find in a book Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned by Milind Tambe Cambridge University Press, 2012).

All aspiring applied mathematics and engineering scholars take notice (note 2).

Note 1. (“Credibility in Stackelberg Games” (with P. Luh and Y. P. Zheng) Systems and Control Letters , 5, 1984, pp 165-168. And “Aspects of Stackelberg Game Problem” (with G.J. Olsder) 1981 IFAC World Congress Proceedings ,  Pergamon Press 1982, Vols. 1 and 2. And “Stochastic Stackelberg Games:  Nonnested Multistage Multiagent Incentive Problem” (with T.S. Chang) IEEE Trans. on Auto. Control , Vol. AC-28, No. 4, April 1983, pp 477-488. And “Incentive Problems:  A Class of Stochastic Stackelberg Closed-loop Dynamic Games” (with T.S. Chang) System Control and Letters , Vol. 1, No. 1, July 1981, pp 16-21. And “Information Structure, Stackelberg Games, and Incentive Controllability” (with P. Luh and R. Muralidharan) IEEE Trans. on Automatic Control , Vol. AC-26, No. 2, April 1981, pp 454-460.)

Note 2. Lest some reader accusing me of either “sour grapes” or “ talking without personal experience” in this connection, I am proud to say that I also had my real engineering experience with three patents to prove it during my life time.

Finally, for those reader who have real interests in game theory, here is an exercise for you. CAN YOU EXPLAIN THE STACKELBERG GAME CONCEPT IN TERM OF MY BLOG ARTICLE FOUR YEARS AGO WITH A TWO DIMENSIONAL GRAPHICAL EXAMPLE?  http://blog.sciencenet.cn/home.php?mod=space&uid=1565&do=blog&id=17894 

s

http://blog.sciencenet.cn/blog-1565-629054.html

上一篇:Harvard's Financial Profile
下一篇:An Experiment with Tablet PC as a teaching tool
收藏 分享 举报

10 徐大海 李本先 陈冬生 马建敏 曹聪 刘文礼 李天成 马磊 zaimingyu guoyanghuawu

该博文允许注册用户评论 请点击登录 评论 (8 个评论)

数据加载中...

Archiver|手机版|小黑屋|科学网 ( 京ICP备14006957 )

GMT+8, 2017-9-19 23:16

Powered by ScienceNet.cn

Copyright © 2007-2017 中国科学报社

返回顶部