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

博文

What is Mathematical Game Theory ?( #4) –Many person game theory 精选

已有 5754 次阅读 2008-4-15 13:46

What is Mathematical Game Theory ?( #4) –Many person game theory
 
There are three different models of GAMES. First we have what is known as Games in Extensive Form. It is simply a details description of the rules of a game. For example, in the simple game of Tic-Tac-Toe you start with a single node with nine branches leading away from it. This represents the nine possible moves of the first player. Each of the branches leads you to another node with eight braches going out. This represents the move of the second player after the first player moved. The process continues alternatively until a win-or-loss outcome is determined. Other more complicated rules and the issue of incomplete information can all be taken care of via constraints on more complicated tree structure. Reader can quickly see that such model are completely impractical except for the simplest and non-interesting games. The next level of game model is called the Strategic Form (or Normal form) of a Game. In the two person case, it is conceptually what we have been describing in the past three articles
and the related article
However, to justify the use of the word “strategic” we need to carefully define what we mean by a “strategy”. In the example I used in the three articles above, chosen a strategy simply means the choice of the value of a parameter, θ . However we can considerably generalize what we mean by a strategy. Earlier in another article
I defined what I mean by a ”strategy”. It is worth repeating it here:
" . . . .Speaking colloquially, a strategy is nothing but a recipe (like a cooking recipe) for making certain decision or taking certain actions under certain circumstances, e.g., if it rains then I won't go out. Here °rain" is the circumstance and the decision is °not to go out". More technically, we have input x which are the input information representing the situation the decision maker (DM) finds himself or herself in. Then depending on x, the DM choose the output decision or action y, i.e. mathematically, y=f(x) where the function f represents the strategy. Thus, the strategy is a recipe of choosing what under which circumstances and when (mathematically, it is a mapping from the information domain x to the action domain y). For example, if there are three possible circumstancesx = [ rain, cloudy, shine] and two possible actions y=[ go, don't go], then there will be y^x (2^3=8) possible strategies. They are exhaustively: f1=always go no matter what, f2=go only when it is rain or cloudy otherwise don't go, f3=go when it is rain or shine, otherwise don't go, f4=go only when it rains otherwise don't, f5=go when it is cloudy or shine but don't go otherwise, f6=go only when cloudy don't otherwise, f7=go only when it is shine, otherwise don't f8=don't go no matter what. (note: if 0=go, and 1=don't go, we are simply enumerating from 000 thru 111 in binary fashion when spelling out the eight strategies.) 
 
Note “strategy” is sometimes referred to a “decision rule” or “feedback control law” or “adaptive algorithm” or “learning algorithm” and a host of other names depending on the application or disciplinary area. But nothing can be more general than the definition of mapping all available input information into output decision choices. Specifying a strategy tell a player how to play the game under all
circumstances and at all times. In the two player situation if each player picks out a strategy, then we can in principle play out the game and determine the payoff for each player. If there are randomness in the game, then we can in principle evaluate the expected payoffs for each player. In other words, J11, θ 2) and J2 1, θ 2) define a TPNZSG in strategic form when we interpret the search space as the space of all admissible strategies. Using the strategic form description of a game suppress all the details of a Game in extensive form and distills out the essence of conflicts, cooperation, and competition as we have illustrated in the previous three articles. When  is finite and discrete, we have the more familiar matrix form of a game in the two person case.
 
Now when there are more than two players, conceptually nothing new emerges except more dimensions so long we are in the non-cooperative case. Similarly in the totally cooperative case in which all players combine to behave as one super player, all the concepts we introduced apply. However, in between these two extreme a new possibility presents itself, namely, a few but not all of the players can form a Coalition to play against the rest of the players. In such cases, the number of outcomes of a game multiplies rapidly since the number of possible coalitions among n players increases rapidly. We must resort of a third model of game specification – the Characteristic function form of a game. Suppose there are n players and mn players forms a coalition. Then the characteristic function of the m players is the payoff the m players can guarantee themselves as a group regardless what the other n-m players do, i.e.,
Max{m}Min{n-m}{J1+ . . .+Jm}
To get this value we need to solve a two person zero sum game (TPZSG) between two super players, {1, 2, . . .m} as one group and the other group {m+1, . . . , n}. When we do this for all possible coalitions we have succeeded in specifying the characteristic function of the game. Again we can only do this in principle, to do this in practice even for the simplest kind of games is often infeasible. Note in this model even the strategic essence and concepts of a game as described previously are suppressed. We are only concentrating on the idea of “coalition” – what a subgroup of players can gain if they behave together for their common good.
Note characteristic functions satisfy some obvious properties. For example, If we divide a group of players into two subgroups, the sum of the characteristic functions of the two subgroup cannot be larger than the characteristic function of the whole group. However, having the characteristic functions of a game still leave at least one question unresolved, namely how to divide the payoff among the members of a coalition. Clearly, no player is going to accept any division of payoff that is less than what he can guarantee himself, i.e., the value of his own characteristic function. Also, the sum of the individual payoffs must equal to the value of the grand coalition where everyone cooperates together. This leads to the concept of a Core of a game. But unfortunately, many perfectly reasonable game has no core. Thus, other division or payoff to individual players have been devised. Shapley value is another scheme which measures the bargaining power of any player and suggests payoffs accordingly. The list goes on . . .
This very brief exposure to many person games amply illustrates both the conceptual complexity and computational difficulty of mathematical game theory. Even under the big assumption of rationality and ignoring psychological/emotional considerations, at present the theory is at best a partial, qualitative, and imperfect model to explain human behavior. I am sure thoughtful readers can think of all kinds of objections and criticisms not only about my rather inadequate description so far but also about what the theory did not succeed in covering. On the other hand, the theory with the insight it provides does offer a rigorous and rational basis for debate, discussion, and deepening our understanding. As a result, three Nobel prizes on economics have been given on the subject in recent years.
 





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

上一篇:China: Challenges and Changes – A forum sponsored by the Harvard Kennedy School
下一篇:What is Mathematical Game Theory ?( #5) – Finale, summing up, and my own view
收藏 分享 举报

0

发表评论 评论 (2 个评论)

数据加载中...

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

GMT+8, 2017-9-24 02:19

Powered by ScienceNet.cn

Copyright © 2007-2017 中国科学报社

返回顶部