2
$\begingroup$

I am a bit confused by the following statement from the Game Tree wikipedia page:

the complete tree is the same tree as that obtained from the extensive-form game representation

A game tree consists of nodes that represent different states of the game and how different actions can lead to different states. As far as I understand, the extensive form representation of a game consists of nodes that do not represent states, rather they indicate which player should make the decision at that node.

Furthermore, it is known that there may be more than one extensive form game representing the same strategic interaction. I don't believe the same is true for a game tree.

Can anyone clear up my confusion?

$\endgroup$
  • $\begingroup$ The wikipedia page you linked (en.wikipedia.org/wiki/Extensive-form_game) indicates that some authors view the extensive form as being the same as the game tree. $\endgroup$ – quasi Mar 3 '18 at 2:47
  • $\begingroup$ @quasi Yes, I noticed that. I am wondering if this equivalence is appropriate. It does not seem like they are equivalent representations to me. $\endgroup$ – jonem Mar 3 '18 at 3:00
  • $\begingroup$ When you say that the nodes in the extensive form "don't represent states", do you have a reference for that? $\endgroup$ – quasi Mar 3 '18 at 3:05
  • $\begingroup$ @quasi In games with actions that have probabilistic effects, the action itself cannot characterize the state (for example, where I take action $a$ in state $s$ and I end up at state $s'$ with probability $0.5$ or state $s''$ with probability $0.5$). $\endgroup$ – jonem Mar 3 '18 at 3:08
  • $\begingroup$ The state at a given node consists of all the information known to the player who is at that node, including probabilistic effects, and their associated probabilities. $\endgroup$ – quasi Mar 3 '18 at 3:29
0
$\begingroup$

In game theory proper, a game tree is an informal way of referring to an extensive form game; just like the name "William" is also colloquially referred to as "Bill". The fact that the word Bill may also refer a draft of law in a different context is neither here nor there. Note that in the Wikipedia article for "Game Tree", the first line says:

For game tree as it is used in game theory (not combinatorial game theory), see Extensive-form game.

This suggests that the term game tree may have different meanings outside game theory. The example game trees shown in that article are also not what game theorists would consider as proper extensive form games.


Extensive form games do capture different "states", although not with the nodes, but with the edges/branches. Probabilistic effects are represented by introducing a player called Chance who randomly chooses from a set of actions that represent the possible states after that node.

For instance, in the following example, Y can choose to shoot at X or Z or into the air, but he will miss the target 40% of the time. This can be modeled by having Chance moving after Y has chosen his target and randomly deciding whether the shot is a hit or a miss.

enter image description here

| cite | improve this answer | |
$\endgroup$

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.