questions on information set definition

Question

The definition of "information set" is An information set is a set of decision nodes, all belonging to the same player, over which that player cannot distinguish. How to understand the part of over which that player cannot distinguish If they are his/her decision node, why he/she cannot distinguish?

Answer 1

The fact that the decision node belong to a player, say $i$, means that at this node, player $i$ is to play.

Consider two variant of the following 2 stage game:

• 1st stage : You start by picking an integer between 0 and 100.
• 2dn stage : Then I must pick a number trying to get as close as possible from the number you chose.

I have 100 decision nodes at the second stage : (chosing an integer between 0 and 100 when you have chosen 0), (chosing an integer between 0 and 100 when you have chosen 1) , ... , (chosing an integer between 0 and 100 when you have chosen 100).

These nodes "belong to me" in the sense that I am the one who has to make a decision at any of them.

Now come the variants.

Variant one

Before choosing an integer between 0 and 100, I do not know which number you picked. Then the information set I "am in" is the set of all the decision nodes : (chosing an integer between 0 and 100 when you have chosen 0), (chosing an integer between 0 and 100 when you have chosen 1) , ... , (chosing an integer between 0 and 100 when you have chosen 100). This is because, not knowing anything about what you have played, I cannot distinguish them, they are strategically identical to me.

Variant two

Before choosing an integer between 0 and 100, I learn that you did not play more than 30. Then the information set I "am in" is the set of all the decision nodes up to 30 : (chosing an integer between 0 and 100 when you have chosen 0), (chosing an integer between 0 and 100 when you have chosen 1) , ... , (chosing an integer between 0 and 100 when you have chosen 30). This is because only knowing that you have not played more than 30, I cannot distinguish these nodes : they are not strategically identical to me. However, I can distinguish them from the other nodes (chosing an integer between 0 and 100 when you have chosen 31), (chosing an integer between 0 and 100 when you have chosen 32) , ... , (chosing an integer between 0 and 100 when you have chosen 100)

Edit following question by OP

This really have to do with the rather tricky way that games in extensive form are formally defined. If you can access it, go check Microeconomic Theory by Mas Collel, Winston and Green on pg 227.

The definition of a game in extensive form includes a finite set of nodes. From your answer, it seems that you suppose that this set of nodes can change. This is not the case. As the game unfolds, the formal definition of the game does not change, and in particular the set of nodes does not vary.

I hope the following section will help you understand this.

A more precise definition of Variant two

I realize that what I had in mind when describing variant two might not be completely clear, so here is a more precise definition of the game.

• First stage : you chose a number between 0 and 100. You could really chose any one of them, and you are not restricted to choosing between 0 and 30 at all.

• Second stage : Whatever you chose, I will learn whether you played less than 30, of more than 30. But I won't get more or less information than that. So formally, the two information sets at stage two are {(choosing ... when you have chosen 0), ... (choosing ... when you have chosen 30)} and {(choosing ... when you have chosen 31), ... (choosing ... when you have chosen 100)}.

  • There are really two information sets here, each containing nodes among which I would not be able to distinguish at stage 2. As to which information set I will eventually end up in at stage two, this will depend on how you play in the first stage. If you play, say 55, this will not make the node below 30 disappear. They will still be part of the definition of the game, but they will be in another information set than the one I will be in. This mean that I can distinguish these nodes from all those who are in my information set.

The example from the wikipedia article on information set provides another good example based on the battle of the sexes:

In this first tree, player 2 does know whether player 1 went to the opera or to the football game

In this second three, player 2 does not know (so the two nodes belong to the same information set, which is represented by the dotted line linking the nodes).