MIT 14 123 - Preliminary Notions in Game Theory

Unformatted text preview:

Chapter 7 P r elim inary N otio n s in Ga me Theory I assume that y ou recall the basic solution concepts, namely Nash Equilibrium, Ba yesian Nash Equilibr ium, Subga m e-Perfect Equilibrium, and P erfect Bayesian Nash Equilib-rium, from 14.122 v ery w ell. In the next two lectures, I will summar ize some other important solution concepts in G a m e T heory, nam ely R ation a lizability, Correlated E q ui-librium, and Sequential Equilibrium, and illustrate them in some applications. The notes in this c hap ter describe the prelim inar y notions that y o u must know already and the notation that will be used in the course. The games can be represented in two forms: 1. The norm al (strategic) form, 2. The extensive form. I first describe these representations illustrate ho w one ca n go from one representation to the other. 7.1 Norm al form Definition 15 (Normal form) A n n-player game is any list G =(S1,...,Sn; u1,...,un), where, for each i ∈ N = {1,...,n}, Si is the set of all strategies that are available to 6162 CHAPTER 7. PRELIMINARY NOTIONS IN GAME THEORY player i,and ui : S1 × ... × Sn → R is player i’s von Neuman n-Morgenstern utility function. Notice that a player’s utility depends not only on his o w n strategy but also on the strategies played by other pla yers. Moreover, each p lay er i tries to m a xim ize the expected value of ui (where the expected values are computed with respect to his ow n beliefs); in other w ords, ui is a von Neum an n-M o rgen stern utility function. We will sa y that play er i is rational iff he triestomaximizethe expected valueof ui (given his beliefs). It is also assumed that it is common knowledge that the play ers are N = {1,...,n}, that the set of strategies available to eac h player i is Si,and that each i tries to max imize expected value of ui given his beliefs. Wh en there are only two pla yers, we can represent the (normal form) game b y a bimatrix (i.e., by two ma t rices): 1\2 1,14,1 3,2left right up 0,2 do wn Here, Pla yer 1 has strategies up and dow n , and Pla yer 2 has the strategies left and righ t. In eac h bo x the firstnumberis Player1’s payoff and the second one is Pla yer 2’s (e.g., u1 (up,left)=0, u2 (up,left)=2.) I will use the following notational conventio n throughout the course. G iven an y list X1,...,Xn of sets with generic elements x1,...,xn, I will • write X = X1 ×···×Xn and designate x =(x1,...,xn) as the generic element, write X−i =Qj=i Xj and designate x−i =(x1,...,xi−1,xi+1,...,xn) as the generic • 6elemen t for any i,and • write (xi0,x−i)=(x1,...,xi−1,x0i,xi+1,...,xn). For example, • S = S1 ×···×Sn is the set of strateg y profiles s =(s1,...,sn), • S−i is the set of strategy profiles s−i =(s1,...,si−1,si+1,...,sn) other than player i,and7.2. EX T E N SIV E FORM 63 • (s0i,s−i)=(s1,...,si−1,s0i,si+1,...,sn) is the strategy profile in w h ich i plays si0and the others play s−i. 7.2 Extensiv e form The exten sive form contains all the information about a game explicitly, by defining who mo ves when, what eac h pla yer kno ws when he mo ves, what moves are ava ilable to him, and where each move leads to, etc. In contr ast, these are implicitly incorporated in strategies in the normal form. (In a w ay, the normal form is a ‘summ a ry’ representation.) We first introduce some formalisms. Definition 16 A tree is a directed graph (i.e. a set of nodes with directed edges that connect some of the nodes) such that 1. there is an initial node, for which there is no incoming edge; 2. for every other node, there is one incom ing edge; 3. every node is connecte d to the initial no de by a unique p ath. Definition 17 The nodes that are not followed by another node are c a lled terminal. The other nodes are c alle d non-term inal. Definition 18 (Extensive form)A Game consists of a set of players, a tree, an allocation of non-terminal nodes of the tr ee to the players, an informational partition of the non-termin al nodes, and payoffs for each player at each terminal node. The set of players includes the agents taking part in the game. How ever, in many games there is room for c hance, e.g. the thro w of dice in backgammon or the card draws in poker. More broadly, we need to consider “c han ce” whenever there is uncertaint y about some relevant fact. To represent these possibilities we in troduce a fictional player: Nature. There is no payoff for Nature at end nodes, and ev ery time a node is allocated to Nature, a prob ability distribution o ver the branches that follow needs to be specified, e.g., Tail with probabilit y of 1/2 and Head with proba bility of 1/2. An informatio n set is a collection of points (nodes) {n1,...,nk} suc h that64 CHAPTER 7. PRELIMINARY NOTIONS IN GAME THEORY 1. the same player i is to move at eac h of these nodes; 2. the same mov es are a vailable at each of these nodes. Here the player i, who is to mov e at the informatio n set, is assumed to be unab le to distinguish between the points in the information set, but able to distinguish between the poin ts outside the information set from those in it. For instance, consider the game in Figure 7.1. Here, Play er 2 kno ws that Play er 1 has taken action T or B and not action X; but Pla yer 2 cannot know for sure wheth er 1 has taken T or B. The same game is depicted in Figu re 7.2 slightly differen tly. 1 BT x 2 L R RL Figure 7.1: 1 x T B 2 L R L R Figure 7.2: An inform a tion partition is an allocation of each n on-term ina l node of the tree to an information set; the starting node must be "alone".7.3. STRATEG IES 65 To sum up: at any node, we know: which player is to move, which moves are available to the play er, and which information set contain s the node, summ arizing the pla yer’s information at the node. Of course, if t wo nodes are in the same inform ation set, the a vailable mov es in these nodes m ust be the same, for otherwise the play er could disting uish th e nodes by the a vailable c h oice s. A ga in, all these are a ssum ed to be common kno wledge. For instanc e, in the game in Figu re 7.1, player 1 knows that, if player 1 takes X, pla y er 2 will kno w this, but if he takes T or B, play er 2 will not …


View Full Document

MIT 14 123 - Preliminary Notions in Game Theory

Download Preliminary Notions in Game Theory
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Preliminary Notions in Game Theory and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Preliminary Notions in Game Theory 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?