3
$\begingroup$

enter image description here

I'm studying game thoery and i'm on extensive form games. One thing I don't understand in my textbook is the following:

enter image description here

I would like to clarify exactly what does an information set mean by the example I drew in the first picture.

So, by what I understand, red player (second player), has 3 information sets. So, on each information set, he has 2 actions. So in total, he has 6 strategies (not $2\times 2 \times 2 =8$). Would this be right? Did I understand the definition of information set right?

Also, if there was no dotted line, i.e the red player knows what the blue player did, would there be a difference in what is the information set? As in the red player would have 1 information set instead of 3? So this would mean he has 2 strategies.

If someone could clarify these concepts for me that would be great as I have trouble understanding these

$\endgroup$

1 Answer 1

3
$\begingroup$

As a first point, in general, the dotted line indicates that the nodes are in the same information set. So in your example, there is a single information set for the Red player and as such she has 2 actions---since she cannot tell which of the 3 nodes she is in, she cannot condition her action on this information, and therefore must take the same action (either left ($l$) or right ($r$)) irrespective of her position.

If, instead, there was no dotted line, then the Red player would know which action the Blue player had taken: lets call them $L$, $M$, or $R$. Contrary to your understanding, in this situation, the Red player does indeed have 8 strategies. Specifically, she can choose to play $l$ or $r$ conditional on each of the three actions she might observes Blue play: letting $(x,y,z) \in \{l,r\}^{3}$ denote the strategy where Red plays $x \in \{l,r\}$ conditional on $L$, $y \in \{l,r\}$ conditional on $M$, and $z \in \{l,r\}$ conditional on $R$, the 8 strategies are

$$(l,l,l),(l,l,r),(l,r,r),(l,r,l),(r,l,l),(r,l,r),(r,r,r),(r,r,l)$$

To understand more generally what is going on, it might help to think less formally and more philosophically about what an information set is. An information set is a collection of game positions (nodes) that a player cannot distinguish between (you can think of the dotted line as representing this entanglement). Then, if a player cannot distinguish between positions, she certainly cannot choose different actions at different positions, for how would she practically make this happen. So the player makes one choice per info set. If, on the other hand, the player can tell the difference between positions, she has many info sets and thus must make correspondingly many more choices.

The combinatorial explosion in the strategy space comes from the fact that each of these choices can be made independently.1 So changing what the Red player will do after the choice of $L$ by the Blue player yields two strategies for every fixed choice out of the other information sets. When there are more periods of play, this growth becomes very very fast (I remember in grad school calculating the number of strategies in tic-tac-toe to be much larger than the atoms in the observable universe). On the other hand, having many strategies does not make the game necessarily more complicated, as many of the strategies may be identified via symmetry or other heuristics.


1 There is a subtly here that some actions might preclude reaching other information sets: nonetheless, in general a strategy is taken as a choice of action at every information set---including the ones precluded by earlier actions in the same strategy

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.