4
$\begingroup$

I am trying to clarify my understanding of the difference between nature nodes and chance nodes in extensive form games. Specifically, on the implication of equilibrium computation.


Current understanding

Nature nodes determine fundamental properties of one's private knowledge (termed a type) before the game begins whereas chance nodes model some random outcomes during play of the game.


From the literature...

Myerson's "Game Theory" text describes chance nodes (pp. 39) as follows:

If the event is determined by chance, then we give the node a label "0" (zero). That is, a nonterminal node with label "0" is a chance node, where the next branch in the path of play would be determined by some random mechanism, according to probabilities that are shown on the branches that follow the chance node.

Myerson doesn't ever use the terminology "nature nodes", instead he calls them historical chance nodes (pp. 67) which are used to define types:

...we should admit the possibility that a player may have some private information already at the first point in time when he begins to plan his moves in the game. The initial private information that a player has at this point in time is called the type of the player.

Games with incomplete information can be modeled in extensive form by using a historical chance node to describe the random determination of the players' types.

So at this point, it seems to me that all nature nodes are chance nodes, but there can be some (internal) chance nodes in the game tree that are not nature nodes (or as Myerson puts them "historical chance nodes").

This agrees with Fudenberg & Tirole in their description of nature's selection of types; see the second page of Fudenberg & Tirole's 1991 paper:

We focus on multi-period games with observed actions, where the players move simultaneously in each period, and each period’s play is revealed before the next period begins. The only asymmetry of information in these games is that each player knows his own “type” (Harsanyi [6]), which is chosen by nature at the start of play and revealed only to him; each player’s payoff function depends on his type and possibly on the other players’ types as well. This class of games includes many applications to economics, such as bargaining, reputation and predation games.

Immediately following the above text, Fudenberg & Tirole state that the definition of PBE requires that types are independent:

We begin by developing a definition of “PBE for games with independent types.”

I don't believe that Fudenberg & Tirole study games with chance nodes (at least the concept does not appear in their 1991 paper).


Questions

My main concerns relate to the appropriateness of PBE when the game has chance nodes. Specifically, consider a game that includes a nature node which specifies player's types (independently) before the game begins, as well as chance nodes that determine the outcome of random events during the game.

If the outcome of these chance nodes were private information to one player, wouldn't it be possible to model these random events (chance nodes) as nature nodes at the beginning of the game?

If so, since the definition of PBE requires that types are independent, is it true that in any game that has nature nodes (dictating type) as well as chance nodes (describing any other randomness in the problem) that the probability distribution of the outcomes of a chance node must be independent of player's types?

In summary, the distinction between nature and chance nodes doesn't seem to abide by strict rules. I would hope for a more formal delineation in the literature between chance nodes and nature nodes (or at least the different kinds of uncertainty that would make one model one random event with a nature node, versus another random event with a chance node). It seems that one can model the same game in many different ways (by choosing which events are dictated by nature at the beginning of the game, and which events are dictated by chance) which, by the assumption of independent types in the definition of PBE, seems to require some additional assumptions on the nature of the probability distributions of the chance nodes. My concern is that I haven't seen any such assumptions on chance nodes in the literature. It would be helpful to see a game in which there are chance nodes whose outcomes are type dependent.


TL;DR: Do the probability distributions for the outcome of chance nodes need to be type independent?

$\endgroup$
3
$\begingroup$

Thanks to Kuhn's theorem, there is no need to distinguish what you call Nature and Chance moves on a game tree. If randomization happens at multiple information sets throughout a game tree, it is without loss of generality to assume that it occurs only once at the beginning of the tree.

We can think of randomization that occurs at multiple information sets throughout a game tree --- including at the initial node (what you call Nature node) as well as subsequent information sets (what you call Chance nodes) --- as behavioral strategies of a single player, call it Player 0. Kuhn's theorem says that every behavioral strategy is generated by some mixed strategy. Therefore, any such "multi-stage" randomization can be equivalently represented as a single randomization at the initial node by Player 0 using the said mixed strategy.

For more reference, see

  • Kuhn, Harold W. (1953) “Extensive Games and the Problem of Information,” in Contributions to the Theory of Games, eds. Harold W. Kuhn and A. Tucker, Vol. 2, Princeton University Press, p.193–216.
  • Myerson, Roger B. (1991) Game Theory: Analysis of Conflict, Harvard University Press, p.154-163.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the answer, Herr! So I suppose that means that when the probabilities of chance nodes depend on some player's (private) type, it means we are dealing with a case of dependent/correlated types? $\endgroup$ – jonem Aug 19 '19 at 18:12
  • $\begingroup$ @jonem: Yes, I believe so. Type independence is not a prerequisite for PBE. Sections 5 and 6 of Fudenberg and Tirole (1991) are about correlated types. $\endgroup$ – Herr K. Aug 19 '19 at 20:58
  • $\begingroup$ Thanks! Yes, I saw those sections but had a bit of a hard time following, I will continue reading. Do you know of any examples (either online or in the literature) that compute PBE for games with correlated types? $\endgroup$ – jonem Aug 19 '19 at 23:33
  • $\begingroup$ @jonem: The typical examples usually involve one player observing a private type while the other has only one type. If you can solve a game of this form, solving for games with correlated type distribution should not be too difficult. It may worth a separate question if you have a specific game in mind. $\endgroup$ – Herr K. Aug 20 '19 at 16:18
  • $\begingroup$ @jonem: If correlated types are a prominent feature of the game you want to analyze, you may also want to check out the notion of Bayes correlated equilibrium, a relatively new theoretical development in relation to robust mechanism design. $\endgroup$ – Herr K. Aug 20 '19 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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