Back in the early fifties, RAND Corporation in California was a hotbed for military and other basic research. One researcher at RAND  by the name of Rufus Isaacs was studying the problem of pursuit and evasion. He single handedly invented the theory of Differential Games which by hindsight can be viewed as a two person zero-sum game with the game tree (i.e., the extensive form as defined in my blog “what is MGT? (#4) ) given as  differential equations of motion. But Isaacs apparently has a difficult personality and was in constant quarrels/disputes with other (he claimed that Bellman stole the idea of dynamic programming from him).   Nor did he pay much attention to the then extant literature in main stream game theory. This can be gleamed from the references of his own book [1]. Otherwise he could have gone much further in his research. As a result, his pioneer work was largely unknown for quite sometime. In the early sixties, when optimal control theory was hot due to the Cold War and aerospace race with USSR, I was lucky to be present at the creation and participated in the boom. Aerial dogfight between two aircraft again became a topic of interesting research. While doing that I discovered Isaac’s work. Looking at it from the viewpoint of two sided control theory, I was able to discover the only closed form solution for a class of general TPZS differential games [2,3]. In the process, I was also able to demonstrate that the engineering solution of “proportional navigation” for aerospace guidance and control was actually a special case of this general optimal pursuit-evasion differential game and that it is the optimal feedback control law [2]. This work heralded in a wave of differential game research by control theorist. Further taking advantage of main stream game theoretical concepts (as described in my four earlier blog articles on the subject),

http://www.sciencenet.cn/blog/user_content.aspx?id=21735

http://www.sciencenet.cn/blog/user_content.aspx?id=21210

http://www.sciencenet.cn/blog/user_content.aspx?id=20337

http://www.sciencenet.cn/blog/user_content.aspx?id=17894

I was able to extend differential games to the nonzero sum and many person case [4]. This occupied my full time effort for five to six years (1964-1970).

 

In the seventies, the problem of incentive design became fashionable. This addresses the problem of governance where an authority would like to design laws or mechanisms to induce self-interested people to behave in ways that also address the common good, e.g., to tell the truth or to behave for the public good in their own self-interest.  Capitalism in its pure form is one theoretical example. This form of mechanism design gained additional popularity more recently in e-commerce (see below) and represented a trend in the development of mathematical game theory.

 

In 1968, Hans Witsenhausen at Bell Telephone labs proposed an extremely simple and perhaps the simplest (from the control theory viewpoint) two person cooperative differential game in extensive form or two person dynamic team theory [5]. This is really the first direct attack on the information structure (who knows what when) issue in games of extensive form. What he showed is that even this apparently simple problem is extremely hard because the two players have different, dynamic, and non-inclusive information (“Dynamic”  in the sense that the order in which players act is important and the later acting  player does not know everything the earlier player knows.) This paper led to my interest in information structure problems in game and team theory which is really a totally cooperative game of many players emphasizing the role of information structures. I spend essentially the decade of the Seventies working on this and again was lucky to be able to devise the only general solution to a class of dynamic team theoretic problems [8]. (Note to young researchers: This is another illustration of the advantages of doing research in new areas vs. working within an established problem framework: see my blog article on “how to do Research?” http://www.sciencenet.cn/blog/user_content.aspx?id=2224 )

Forty years later in 2008, there will be a special session devoted to this famous Witsenhausen problem at the annual IEEE Conference on Decision and Control, Cancun, Mexico, December 2008 [6, 7].  This is because the fundamental computational difficulty remain unresolved

However, the advent of personal computers beginning in the Eighties changed the problem domain for extensive games. “Information” becomes widely available via the Internet, Google, and Wikipedia and almost costless. Many of the problem difficulties and assumption for information structure disappeared. New problems in e-commerce, auctions, and incentives can be addressed because players in many cases have access to the same information. You may say that the playing field of information has been leveled. Design  of real world workable incentive mechanism become possible. A joint research field of Computer Science and Economics was created.  I would not be surprised that a future Nobel prize will come out of this area.

 

In summary, what is mathematical game theory? It has three models

1. Games in extensive form – This is the most detailed model for a game. Differential games is a special case where control theorists attempted to get actual quantitative solutions. Current interest in e-commerce represents another attempt by computer scientist to solve economic games in extensive form. This is the direction MGT seems to be developing.
2. Games in strategic form – This model introduces various qualitative concepts fundamental to explaining human and economic behavior
3. Games in characteristic form – This model emphasizes the issue of coalition formation and bargaining among many players

And what has the theory done for our understanding of human and economic behavior? MGT on the whole is a rigorous attempt to describe and make precise insights of these interactions. For example, the recent problems of doping and cheating in international sports such as cycling can be explained and their inevitability demonstrated using game theoretic concepts we described here [9]. However, actual quantitative solution of real world games are far and few in between because of the tremendous mathematical and computational difficulties involved. But at least we now understand as to why they are difficult and computer science technology may present new opportunities and problems.

 

Game problems and related issue have been a significant part of the 46 years of my research career.  I welcome the opportunity to give a popularized account of the subject to ScienceNet readers.  To the extent I fall short of my original goal, my apologies for wasting your time.

 

1.      Isaacs, Rufus. Differential Games, John Wiley and Sons, 1965.

2. Y.C. Ho, S. Baron, and A.E.l Bryson, “Differential Games and Optimal Pursuit-Evasion Strategies”  IEEE Trans. on Automatic Control , Vol. 10, No. 4, Oct. 1965, pp 385-389.
3. Y.C. Ho and A. Starr,  “Nonzero Sum Differential Games”, J of Opt. Th. and Applications, Vol. 3, # 3, March 1969, 184-206
4. Y. C. Ho and G.J. Olsder, “Differential Games:  Concepts and Applications”, Proc. of Yale-ONR Conference on Models of Conflict , Nov. 1979;  Chapter in Mathematics of Conflict , M. Shubik (Ed), North Holland, 1983, pp 127-186.
5. Witsenhausen HS,  “A counterexample in stochastic optimum control”. SIAM Journal on Control  6(1):131-147. 1968
6. Lee JT, Lau EL, and Ho YC ,“The Witsenhausen counterexample: A hierarchical search approach for nonconvex optimization problems”. IEEE Transactions on Automatic Control  46(3):382-397, 2001.
7. Y.C. Ho, “Review of the Witsenhausen Problem”, Proc. of the 2008 IEEE CDC, Mexico, 2008 to appear
8. Y.C. Ho, “Team Decision Theory and Information Structures” Proc. of IEEE , Vol. 68, No. 6, June 1980, pp 644-654.

     9. Michael Shermer, “The Doping Dilemma”, Scientific American Vol298, #4 pp82-89, April 2008

转载本文请联系原作者获取授权，同时请注明本文来自何毓琦科学网博客。
链接地址：https://blog.sciencenet.cn/blog-1565-21891.html

上一篇：What is Mathematical Game Theory ?( #4) –Many person game theory
下一篇：National Public Radio (NPR) on China