\documentstyle[12pt,epsf] {article} \parskip 10pt % Janaury 15, 1996 %Overheads for chatper 2 of Games and Information, for class. \begin{document} \textheight 10in \begin{Large} \setcounter{page}{36} \begin{center} {\bf Table 2.1 ``Ranked Coordination'' } \begin{tabular}{lllccc} & & &\multicolumn{3}{c}{\bf Jones}\\ & & & $Large$ & & $Small$ \\ & & $Large$ & {\bf 2,2} & $\leftarrow$ & $-1, -1$ \\ & {\bf Smith} & & $\uparrow$ & & $\downarrow$ \\ & & $Small$ & $-1, -1$ & $\rightarrow$ & {\bf 1,1} \\ & & & &\\ \multicolumn{6}{l}{\it Payoffs to: (Smith, Jones)} \end{tabular} \end{center} In ``Follow the Leader I'', Jones's strategy set has four elements, \begin{center} \noindent $ \left\{ \begin{tabular}{l} (If Smith chose {\it Large}, choose {\it Large}; if Smith chose {\it Small}, choose {\it Large}),\\ (If Smith chose {\it Large}, choose {\it Large}; if Smith chose {\it Small}, choose {\it Small}),\\ (If Smith chose {\it Large}, choose {\it Small}; if Smith chose {\it Small}, choose {\it Large}), \\ (If Smith chose {\it Large}, choose {\it Small}; if Smith chose {\it Small}, choose {\it Small})\\ \end{tabular} \right\}$ \end{center} \noindent which we will abbreviate as \begin{center} \noindent $\left\{ \begin{tabular}{l} ({\it L$|$L}, {\it L$|$S}),\\ ({\it L$|$L}, {\it S$|$S}),\\ ({\it S$|$L}, {\it L$|$S}), \\ ({\it S$|$L}, {\it S$|$S}) \\ \end{tabular} \right\}$ \end{center} \begin{center} {\bf Table 2.2 ``Follow-the-Leader I'' } \begin{tabular}{llcccc} & & \multicolumn{4}{c}{\bf Jones}\\ & & $J_1$ & $J_2$ & $J_3$ & $J_4$ \\ & & {\it L$|$L, L$|$S} & {\it L$|$L, S$|$S} & {\it S$|$L, L$|$S} &{\it S$|$L, S$|$S} \\ & $Large$ & {\bf \fbox {2}, \begin{picture}(10,15) \put(0,-2){\dashbox{3}(8,12) {2}} \end{picture}, ($E_1$) } &{\bf \fbox{2}, \begin{picture}(10,15) \put(0,-2){\dashbox{3}(8,12) {2}} \end{picture}, ($E_2$) } & \begin{picture}(10,15) \put(0,-2){\dashbox{3}(16,12) {$-1$}} \end{picture}, $-1$ & $-1, -1$ \\ {\bf Smith} & & & & & \\ & $Small$ & $-1, -1$ & $ 1,\begin{picture}(10,15) \put(0,-2){\dashbox{3}(8,12) {1}} \end{picture}, 1$ & \begin{picture}(10,15) \put(0,-2){\dashbox{3}(16,12) {$-1$}} \end{picture},$ -1 $ & {\bf \fbox{1}, \begin{picture}(10,15) \put(0,-2){\dashbox{3}(8,12) {1}} \end{picture} ($E_3$)} \\ & & & &\\ \multicolumn{6}{l}{\it Payoffs to: (Smith, Jones)} \end{tabular} \end{center} \begin{tabular}{ccc} {\bf Equilibrium} & {\bf Strategies} & {\bf Outcome}\\ $E_1$ &\{{\it Large, (L$|$L) (L$|$S)}\} & Both pick $Large$. \\ $E_2$ & \{{\it Large, (L$|$L, S$|$S)}\} & Both pick $Large$.\\ $E_3$ & \{{\it Small,(S$|$L, S$|$S)}\} & Both pick $Small$. \end{tabular} \newpage \bigskip \noindent {\bf The Extensive Form and the Game Tree} \noindent Two other ways to describe a game are the extensive form and the game tree. First we need to define their building blocks. As you read the definitions, you may wish to refer to Figure 2.1 as an example. \noindent {\it A {\bf node} is a point in the game at which some player or Nature takes an action, or the game ends.} \noindent {\it A {\bf successor} to node X is a node that may occur later in the game if X has been reached. \noindent A {\bf predecessor} to node X is a node that must be reached before X can be reached. \noindent A {\bf starting node} is a node with no predecessors. \noindent An {\bf end node} or {\bf end point} is a node with no successors.} \noindent {\it A {\bf branch} is one action in a player's action set at a particular node.} \noindent {\it A {\bf path} is a sequence of nodes and branches leading from the starting node to an end node.} These concepts can be used to define the extensive form and the game tree. \noindent {\it The {\bf extensive form } is a description of a game consisting of \\ (1) A configuration of nodes and branches running without any closed loops from a single starting node to its end nodes.\\ (2) An indication of which node belongs to which player.\\ (3) The probabilities that Nature uses to choose different branches at its nodes.\\ (4) The information sets into which each player's nodes are divided.\\ (5) The payoffs for each player at each end node.} \bigskip \noindent {\it The {\bf game tree} is the same as the extensive form except that (5) is replaced with \\ (5$'$) The outcomes at each end node.} \newpage \begin{center} {\bf Table 2.4 Information Categories } \begin{tabular}{|ll |} \hline {\bf Information Category} & {\bf Meaning}\\ \hline Perfect & Each information set is a singleton\\ Certain & Nature does not move after any player moves\\ Symmetric & No player has information different from other\\ & players when he moves, or at the end nodes\\ Complete & Nature does not move first, or her initial move\\ & is observed by every player\\ \hline \end{tabular} \end{center} \noindent {\it In a game of {\bf perfect information} each information set is a singleton.} {\it Otherwise the game is one of {\bf imperfect information}}. \bigskip \noindent {\it A game of {\bf certainty} has no moves by Nature after any player moves. Otherwise the game is one of {\bf uncertainty.}} \noindent {\it In a game of {\bf symmetric information}, a player's information set at \\ (1) any node where he chooses an action, or \\ (2) an end node\\ contains at least the same elements as the information sets of every other player. Otherwise the game is one of {\bf asymmetric information.}} \bigskip \noindent {\it In a game of {\bf incomplete information}, Nature moves first and is unobserved by at least one of the players. Otherwise the game is one of {\bf complete information.}} \bigskip \noindent {\bf Poker Examples of Information Classification} \noindent In the game of poker, the players make bets on who will have the best hand of cards in his hand, where a ranking of hands has been pre-established. How would the following rules for behavior before betting be classified? (Answers are in note N2.4) \newpage \noindent \begin{enumerate} \item All cards are dealt face up.\\ \item All cards are dealt face down and a player cannot look even at his own cards before he bets.\\ \item All cards are dealt face down, and a player can look at his own cards.\\ \item All cards are dealt face up, but each player then scoops up his hand and secretly discards one card.\\ \item All cards are dealt face up, the players bet, and then each player receives one more card face up.\\ \item All cards are dealt face down, but then each player scoops up his cards without looking at them and holds them against his forehead so all the {\it other} players can see them (Indian poker). \end{enumerate} \newpage \bigskip \noindent {\bf Updating Beliefs with Bayes's Rule} \noindent When we classify a game's information structure we do not try to decide what a player can deduce from the other players' moves. Player Jones might deduce, upon seeing Smith choose {\it Large,} that Nature has chosen state (A), but we do not draw Jones's information set in Figure 2.7 to take account of that. In drawing the game tree we want to illustrate only the exogenous elements of the game, uncontaminated by the equilibrium concept. But to find the equilibrium we do need to think about how beliefs change over the course of the game. One part of the rules of the game is the collection of {\bf prior beliefs} (or {\bf priors}) held by the different players, beliefs that they update in the course of the game. A player holds prior beliefs concerning the types of the other players, and as he sees them take actions he updates his beliefs under the assumption that they are following equilibrium behavior. The term {\bf Bayesian equilibrium} is used to refer to a Nash equilibrium when players update their beliefs according to Bayes's Rule. Since Bayes's Rule is the natural and standard way to handle imperfect information, the adjective ``Bayesian'' is really optional. But the two step procedure of checking a Nash equilibrium has now become a three-step procedure: \noindent 1. Propose a strategy profile.\\ 2. See what beliefs the strategy profile generates when players update their beliefs in response to each others' moves.\\ 3. Check that given those beliefs and the strategies of the other players, each player is choosing a best response for himself. The rules of the game specify each player's initial beliefs, and Bayes's Rule is the rational way to update beliefs. Suppose, for example, that Jones starts with a particular prior belief, $Prob(Nature \; chose \;(A))$. In ``Follow-the-Leader III'', this equals 0.7. He then observes Smith's move--- $Large$, perhaps. Seeing $Large$ should make Jones update to the {\bf posterior} belief, $Prob ( Nature \; chose \;(A)) |Smith \; chose\; Large)$, where the symbol ``$|$'' denotes ``conditional upon,'' or ``given that.'' Bayes's Rule shows how to revise the prior belief in the light of new information such as Smith's move. It uses two pieces of information: the {\bf likelihood} of seeing Smith choose $Large$ given that Nature chose state of the world (A), $Prob ( Large| (A) )$, and the likelihood of seeing Smith choose $Large$ given that Nature did not choose state (A), $Prob ( Large| (B)\; or\; (C) )$. From these numbers, Smith can calculate $Prob (Smith \; chooses\; Large )$, the {\bf marginal likelihood} of seeing $Large$ as the result of one or another of the possible states of the world that Nature might choose. \begin{equation}\label{e2.1} \begin{array}{ll} Prob (Smith \; chooses\; Large ) &= Prob ( Large| A ) Prob(A) + Prob ( Large| B ) Prob(B) \\ & + Prob ( Large| C ) Prob(C).\\ \end{array} \end{equation} To find his posterior, $Prob ( Nature \; chose \;(A)) |Smith \; chose\; Large)$, Jones uses the the likelihood and his priors. The joint probability of both seeing Smith choose $Large$ and Nature having chosen (A) is \begin{equation}\label{e2.2} Prob(Large,A) = Prob(A|Large)Prob(Large) = Prob(Large|A)Prob(A). \end{equation} Since what Jones is trying to calculate is $Prob(A|Large)$, rewrite the last equation in (2.\ref{e2.2}) as \begin{equation}\label{e2.3} Prob(A|Large) = \frac{ Prob(Large|A)Prob(A)} {Prob (Large)}. \end{equation} Jones needs to calculate his new belief--- his posterior--- using $Prob(Large)$, which he calculates from his original knowledge using (2.\ref{e2.1}). Substituting the expression for $Prob(Large)$ from (2.\ref{e2.1}) into equation (2.\ref{e2.3}) gives the final result, a version of Bayes's Rule. \begin{equation}\label{e2.4} Prob(A|Large) = \frac{Prob(Large|A)Prob(A)} {Prob(Large|A)Prob(A) + Prob(Large|B )Prob(B)+ Prob(Large|C)Prob(C)}. \end{equation} More generally, for Nature's move $x$ and the observed data, \begin{equation}\label{e2.4a} Prob(x|data) = \frac{Prob( data|x)Prob(x)} {Prob(data)} \end{equation} Equation (2.\ref{e2.5}) is a verbal form of Bayes's Rule, which is useful for remembering the terminology, summarized in Table 2.5. \begin{equation}\label{e2.5} ( Posterior \;for\; Nature's \; \;Move) = \frac{ (Likelihood\;of\; Player's \; \;Move) \cdot (Prior \ for\; Nature's \; \;Move)} {(Marginal\; likelihood\; of \; Player's \; \;Move)}. \end{equation} Bayes's Rule is not purely mechanical, but rather the only way to rationally update beliefs. The derivation is worth understanding because Bayes's Rule is hard to memorize, but easy to rederive. \begin{center} {\bf Table 2.5 Bayesian Terminology } \begin{tabular}{|ll|} \hline {\bf Name} & {\bf Meaning} \\ & \\ \hline Likelihood & $Prob(data|event)$\\ Marginal likelihood & $Prob(data) $\\ Conditional Likelihood & $Prob(datum X|datum Y, event)$\\ Prior & $Prob( event)$\\ Posterior & $Prob( event|data)$\\ \hline \end{tabular} \end{center} \bigskip \noindent {\bf Updating Beliefs in ``Follow-the-Leader III''} \noindent Let us now return to the numbers in ``Follow-the-Leader III'' to use the belief-updating rule that was just derived. Jones has a prior belief that the probability of event ``Nature picks state (A)'' is 0.7 and he needs to update that belief on seeing the data ``Smith picks $Large$.'' His prior is $Prob(A) = 0.7$, and we wish to calculate $Prob (A|Large)$. To use Bayes's Rule from equation (2.\ref{e2.4}), we need the values of $Prob (Large|A)$, $Prob (Large|B)$, and $Prob (Large|C)$. These values depend on what Smith does in equilibrium, so Jones's beliefs cannot be calculated independently of the equilibrium. This is the reason for the three-step procedure suggested above, for what the modeller must do is propose an equilibrium and then use it to calculate the beliefs. Afterwards, he must check that the equilibrium strategies are indeed best responses given the beliefs they generate. A candidate for equilibrium in ``Follow-the-Leader III'' is for Smith to choose $Large$ if the state is (A) or (B) and $Small$ if it is (C), and for Jones to respond to $Large$ with $Large$ and to $Small$ with $Small.$ This can be abbreviated as $(L| A , L| B , S| C ; L|L, S|S)$. Let us test that this is an equilibrium, starting with the calculation of $Prob(A|Large)$. If Jones observes $Large,$ he can rule out state (C), but he does not know whether the state is (A) or (B). Bayes's Rule tells him that the posterior probability of state (A) is \begin{equation} \label{e2.7} \begin{array}{ll} Prob(A|Large) & = \frac{(1)(0.7)}{(1)(0.7) + (1)(0.1) + (0)(0.2)}\\ & \\ & = 0.875. \end{array} \end{equation} The posterior probability of state (B) must then be $1-0.875 = 0.125$, which could also be calculated from Bayes's Rule, as follows: \begin{equation} \label{e2.8} \begin{array}{ll} Prob(B|Large) &= \frac{(1)(0.1)}{(1)(0.7) + (1)(0.1) + (0)(0.2)}\\ & \\ & = 0.125. \end{array} \end{equation} Figure 2.8 shows a graphic intuition for Bayes's Rule. The first line shows the total probability of 1 which is the sum of the prior probabilities of states (A), (B), and (C). The second line shows the probabilities, summing to 0.8, which remain after $Large$ is observed and rules out state (C). The third line shows that state (A) represents an amount 0.7 of that probability, a fraction of 0.875. The fourth line shows that state (B) represents an amount 0.1 of that probability, a fraction of 0.125. Jones must use Smith's strategy in the proposed equilibrium to find numbers for $Prob(Large|A)$, $Prob(Large|B)$, and $Prob(Large|C)$. As always in Nash equilibrium, the modeller assumes that the players know which equilibrium strategies are being played out, even though they do not know which particular actions are being chosen. Given that Jones believes that the state is (A) with probability 0.875 and state (B) with probability 0.125, his best response is $Large$, even though he knows that if the state were actually (B) the better response would be $Small$. Given that he observes $Large$, Jones's expected payoff from $Small$ is $-0.625$ ( $= 0.875[-1] + 0.125 [2]$), but from $Large$ it is $ 1.875$ ( $= 0.875[2] + 0.125 [1]$). Thus, the strategy profile $(L| A , L| B , S| C ; L|L, S|S)$ is a perfect Bayesian equilibrium. A similar calculation can be done for $Prob (A|Small)$. Using Bayes's Rule, equation (2.\ref{e2.4}) becomes \begin{equation} \label{e2.6} Prob (A|Small) = \frac{(0)(0.7)}{(0)(0.7) + (0)(0.1) + (1)(0.2)} = 0. \end{equation} Given that he believes the state is (C), Jones's best response to $Small$ is $Small$, which agrees with our proposed equilibrium. The calculations are relatively simple because Smith uses a nonrandom strategy in equilibrium, so, for instance, $Prob(Small|A) =0$ in equation (2.\ref{e2.6}). Consider what happens if Smith uses a random strategy of picking $Large$ with probability 0.2 in state (A), 0.6 in state (B), and 0.3 in state (C) (we will analyze such ``mixed'' strategies in Section 3.1). The equivalent of equation (2.\ref{e2.7}) is \begin{equation} \label{e2.9} Prob(A|Large) = \frac{(0.2)(0.7)}{(0.2)(0.7) + (0.6)(0.1) + (0.3)(0.2)} = 0.54 \;\;(rounded). \end{equation} If he sees $Large$, Jones's best guess is still that Nature chose state (A), even though in state (A) Smith has the smallest probability of choosing $Large$, but Jones's subjective posterior probability, $Pr(A|Large)$, has fallen to 0.54 from his prior of $Pr(A)=0.7$. The last two lines of Figure 2.8 illustrate this case. The second-to-last line shows the total probability of $Large$, which is formed from probabilities in all three states, and sums to 0.26 (=$0.14 + 0.06 + 0.06$). The last line shows the component of that probability arising from state (A), which is amount 0.14 and fraction 0.54 (rounded). \newpage \bigskip \noindent {\bf Regression to the Mean} Regression to the mean is an old statistical idea that has a Bayesian interpretation. Suppose that each student's performance on a test results partly from his ability and partly from random error because of his mood the day of the test. The teacher does not know the individual student's ability, but does know that the average student will score 70 out of 100. If a student scores 40, what should the teacher's estimate of his ability be? It should not be 40. A score of 30 points below the average score could be the result of two things: (1) the student's ability is below average, or (2) the student was in a bad mood the day of the test. Only if mood is completely unimportant should the teacher use 40 as his estimate. More likely, both ability and luck matter to some extent, so the teacher's best guess is that the student has an ability below average but was also unlucky. The estimated ability lies somewhere between 40 and 70, reflecting the influence of both ability and luck. Of the students who score 40 on the test, more than half will score above 40 on the next test. Since the scores of these poorly performing students tend to float up towards the mean of 70, this phenomenon is called ``regression to the mean''. Similarly, students who score 90 on the first test will tend to score less well on the second test. This is ``regression to the mean'' (``towards'' would still more accurate) not ``regression to beyond the mean.'' A low score does indicate low ability, on average, so the predicted score on the second test is still below average. Regression to the mean merely recognizes that both luck and ability are at work. In Bayesian terms, the teacher in this example has a prior mean of 70, and is trying to form a posterior estimate using the prior and one piece of data, the score on the first test. For typical distributions, the posterior mean will lie between the prior mean and the data point, so the posterior mean will be between 40 and 70. In a business context, regression to the mean can be used to explain business conservatism. It is sometimes claimed that businesses pass up profitable investments because they have an excessive fear of risk. Let us suppose that the business is risk neutral, because the risk associated with the project and the uncertainty over its value are non-systematic--- they are risks that a widely held corporation can distribute to where each shareholder's risk is trivial. Suppose that the firm will not spend \$100,000 dollars on an investment with a present value of \$105,000. This is easily explained if the \$105,000 is an estimate and the \$100,000 is cash. If the average value of a new project of this kind is less than \$100,000 --- as is likely to be the case, since profitable projects are not easy to find--- then the best estimate of the value will lie between the measured value of \$105,000 and that average value, unless the staffer who came up with the \$105,000 figure has already adjusted his estimate. Regressing the \$105,000 to the mean may regress it past \$100,000. Put a little differently, if the prior mean is, let us say, \$80,000, and the data point is \$105,000, the posterior may well be less than \$100,000. It is important to keep regression to the mean in mind as an alternative to strategic behavior in explaining odd phenomena. In analyzing test scores, one might try to explain the rise in the scores of poor students by changes in their effort level to try to achieve a target grade in the course with minimum work. In analyzing business decisions, one might try to explain why apparently profitable projects are rejected by the dislike of managers for innovations which would require them to work harder. These explanations might well be valid, but models based on Bayesian updating or regression to the mean might explain the situation just as well, and with fewer hard-to-verify assumptions about the utility functions of the individuals involved. \end{Large} \end{document}