• a player mixes before playing the game but then remains loyal to the selected pure strategy.
behavioral strategy in Extensive-Form Games
a behavioral strategy is more in tune with the dynamic nature of the extensive-form game. When using such a strategy, a player mixes among his actions whenever he is called to play.
Normal-Form Representation of Extensive-Form Games
• Any extensive-form game can be transformed into a normal-form game by using the set of pure strategies of the extensive form (see definition 7.4) as the set of pure strategies in the normal form, and the set of payoff functions is derived from how combinations of pure strategies result in the selection of terminal nodes. • Therefore the normal-form representation of an extensive form will suffice to find all the Nash equilibria of the game.
Mixed versus Behavioral Strategies in Extensive-Form Games
• Definition 7.5 A mixed strategy for player i is a probability distribution over his pure strategies si∈ Si .
Mixed versus Behavioral Strategies
Given a mixed strategy , a behavior strategy can be construct by the sum of the probability that reaching the action in the information set. Given a behavior strategy, a mixed strategy can be found by inverse the above process.
Pure Strategies in Extensive-Form Games
• Definition 7.4 A pure strategy for player i is a mapping si :Hi→Ai that assigns an action si(hi) ∈ Ai(hi) for every information set hi ∈ Hi . We denote by Si the set of all pure-strategy mappings si∈ Si . • The strategy defines actions that are conditional on his information about where he is in the game.
The Absent-Minded Driver
• Piccione and Rubinstein (1997)
Define a “planning” mixed strategy of the player as a probability p that he will exit at any exit he passes His expected payoff from this strategy is 0p + 4p(1−p) + 1(1− p)2 =−3p2 + 2p + 1, which is maximized at p = 1/3 At an intersection,he knows that with some probability q he is at Exit 1, and with some probability (1− q) he is at exit 2.The driver’s payoff for choosing to exit with probability p is now, at the intersection, q*4p(1− p) + 1(1− p) 2++ (1− q)*4p + 1(1− p)+, which is equivalent to the planning problem only when q = 1
Mixed versus Behavioral Strategies
• The first is, given a mixed (not behavioral) strategy, can we find a behavioral strategy that leads to the same outcomes? • given a behavioral strategy, can we find a mixed strategy that leads to the same outcomes?
Normal-Form Representation of Extensive-Form Games
• Furthermoreunique normal form that represents it, which is not true for the reverse transformation (see the following remark).
• We defined games of complete as the situation in which each player i knows the action set and the payoff function of each and every player j ∈ N, and this itself is common knowledge. • Definition 7.3 A game of complete information in which every information set is a singleton and there are no moves of Nature is called a game of perfect information. • A game in which some information sets contain several nodes or in which there are moves of Nature is called a game of imperfect information.
• In a game of (complete but) imperfect information some players do not know where they are because some information sets include more than one node. • This happens, for example, every time they move without knowing what some players have chosen previously, • Games of imperfect information are also useful to capture the uncertainty a player may have about acts of Nature.
Example : battle of sexes game.
• This is the sequential version battle of sexes game.
F F Player 1 O Player 2 O (6,8) Palyer 2 O F
(8,6)
(0,0) (0,0)
game of imperfect information
exogenous uncertainty or endogenous uncertainty
A card game
Strategies and Nash Equilibrium
• Pure Strategies in Extensive-Form Games • A pure strategy for player i is a complete plan of play that describes which pure action player i will choose at each of his information sets. • Let Hi be the collection of all information sets at which player i plays, and let hi ∈ Hi be one of i’s information sets. Let Ai(hi) be the actions that player i can take at hi , and let Ai be the set of all actions of player i, Ai=∪hi∈Hi Ai(hi)
A game of perfect recall
• Definition 7.7 A game of perfect recall is one in which no player ever forgets information that he previously knew. • a game of perfect recall is one in which, if a player is called upon to move more than once in a game, then he must remember the moves that he chose in his previous information sets. • Practically all of the analysis in game theory, and in applications of game theory to the social sciences, assumes perfect recall, as will we in this text. • For the class of perfect-recall games, Kuhn (1953) proved that mixed and behavioral strategies are equivalent, in the sense that given strategies of i’s opponents, the same distribution over outcomes can be generated by either a mixed or a behavioral strategy of player i.