1Lecture Notes for Economics 200C: Games and InformationVincent Crawford, revised March 2000; do not reproduce except for personal use1. IntroductionMWG 217-233; Kreps 355-384; Varian 259-265; McMillan 3-41Robert Gibbons, "An Introduction to Applicable Game Theory," Journal of EconomicPerspectives (Winter 1997), 127-149 (or you can substitute his book)Noncooperative game theory tries to explain outcomes (including cooperation) from thebasic data of the situation, in contrast to cooperative game theory, which assumesunlimited communication and cooperation and tries to characterize the limits of the set ofpossible cooperative agreements. In "parlor" games players often have opposedpreferences; such games are called zero-sum. But noncooperative game theory spans theentire range of interactive decision problems from pure conflict to pure cooperation(coordination games); most applications have elements of both.A game is defined by specifying its structure: the players, the "rules" (the order of players'decisions, their feasible decisions at each point, and the information they have whenmaking them); how their decisions jointly determine the outcome of the game; and theirpreferences over possible outcomes. Any uncertainty about the outcome is handled byassigning payoffs (von Neumann-Morgenstern utilities) to the possible outcomes andassuming that players' preferences over uncertain outcomes can be represented byexpected-payoff maximization.Assume game is a complete model of the situation; if not, make it one, e.g. by includingdecision to participate. Assume numbers of players, decisions, and periods are finite, butcan relax as needed.Something is mutual knowledge if all players know it, and common knowledge if all knowit, all know that all know it, and so on. Assume common knowledge of structure (allowsuncertainty with commonly known distributions modeled as "moves by nature"): games ofcomplete information.Can represent a game by its extensive form or game tree. E.g. contracting by ultimatum(MWG uses Matching Pennies, Kreps has abstract examples): Two players, R(ow) andC(olumn); two feasible contracts, X and Y. R proposes X or Y to C, who must eitheraccept (a) or reject (r). If C accepts, the proposed contract is enforced; if C rejects, theoutcome is a third alternative, Z. R prefers Y to X to Z, and C prefers X to Y to Z. R'spreferences are represented by vN-M utility or payoff function u(y)=2, u(x)=1, u(z)=0; andC's preferences by v2(x)=2, v2(y)=1, v2(z)=0.Draw game trees when C can observe R's proposal before deciding whether to accept,and when C cannot. Order of decision nodes has some flexibility, but must respect timingof information flows. Players assumed to have perfect recall of their own past moves andother information; tree must reflect this. Each decision node belongs to an information set,2the nodes the player whose decision it is cannot distinguish (and at which he musttherefore make the same decision). All nodes in an information set must belong to thesame player and have the set of same feasible decisions. Identify each information set bycircling its nodes (MWG) or connecting them with dotted lines (Kreps).A static game has a single stage, at which players make simultaneous decisions, as incontracting with unobservable proposal. A dynamic game has some sequential decisions,as in contracting with observable proposal. A game of perfect information is one in which aplayer making a decision can always observe all previous decisions, so every informationset contains a single decision node, as in contracting with observable proposal. Completedoes not imply perfect information; but if background uncertainty is modeled as "moves bynature," perfect implies complete information.A strategy is a complete contingent plan for playing the game, which specifies a feasibledecision for each of a player's decision nodes in the game and possible information stateswhen he reaches them. (In static games I sometimes say "decision" or "action" instead of"strategy.") A strategy is like a detailed chess textbook, not like a move. A player's feasiblestrategies must be independent of others' strategies (no "wrestle with the other cricket"),and specifying a strategy for each player determines an outcome (or at least a probabilitydistribution over possible outcomes) in the game.In contracting, whether or not C can observe R's proposal, R has two pure strategies,"(propose) X" and "(propose) Y." If C cannot observe R's proposal, C has two purestrategies, "a(ccept)" and "r(eject).". If C can observe R's proposal he can make hisdecision depend on it, and therefore has four pure strategies, "a (if X proposed), a (if Yproposed)", "a, r", "r, a", and "r, r."The above descriptions apply to mixed strategies (randomized choices of pure strategies)as well as pure (unrandomized) strategies. In games with perfect recall mixed strategiesare equivalent to behavior strategies, probability distributions over pure decisions at eachnode (Kuhn's Theorem).A strategy must be a complete contingent plan (even for nodes ruled out by own priordecisions!) so that in dynamic games we can evaluate the consequences of alternativestrategies, to formalize the idea that the predicted strategy choice is optimal. This is asurprising difference from individual decision theory, where zero-probability events can beignored. In games we must pay attention to zero-probability outcomes because they areendogenously determined by players' decisions.Because strategies are complete contingent plans, players must be thought of aschoosing them simultaneously (without observing others') at the start: theory assumesrational foresight, so simultaneous choice of strategies is same as decisions in "real time."A game maps strategy profiles into payoffs; a game form maps profiles into outcomes,without specifying payoffs. The relationship between strategy profiles, outcomes, andpayoffs is often described by the normal form or the payoff matrix or payoff function.3In contracting, without and with observable proposals, the payoff matrices are:ara, aa, rr, ar, rX2100X21210000Y1200Y12001200Contracting withUnobservable ProposalContracting withObservable ProposalIncreasingly game-theoretic examples illustrate some issues that a theory of gamesshould address (see also abstract, mostly normal-form examples at Kreps 389-392).L R Confess Don'tT2212Con-fess-5-5-10-1B2111Don't-1-10-2-2Crusoe "versus" Crusoe Prisoner's DilemmaPush Wait Heads