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
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.
9. Michael Shermer, “The Doping Dilemma”, Scientific American Vol298, #4 pp82-89, April 2008
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-24 11:20
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社