Published on

More on extensive forms

Authors
  • avatar
    Name
    Yunho Kim
    Twitter

Quick review : Extensive form representation

  • Nodes: Where players choose actions - Successor Nodes : Node B is a successor to Node A if there is some path going from A to B. - Immediate Successor : B is an immediate successor to A if there is a branch leading directly from A to B. - Predecessor Nodes : Same idea as successor nodes but moving through the tree backwards.
  • Branches: Specific actions.
  • Labels: Identify nodes or branches.
  • Payoffs: Represent preferences over outcomes.
  • Information sets: Reveal what a player knows when he/she makes a decision.
    • A player’s strategy must give a decision for each of his/her info sets.

Example

tree example
  • Initial Node : a
  • All successors to a : b, c, d, e, f, g, h, i, j, k
  • All immediate successors to a : b, c
  • All predecessor node to f : a, b, d
  • All immediate predecessor node to f : d
  • Information sets :
    • player 1 : {a},{d},{e}\{a\}, \{d\}, \{e\}
    • player 2 : {b,c}\{b, c\}

Tree rules

  • Following are the rules that game tree must obey.
  1. Every node is a successor of the initial node, and the initial node is the only one with this property.
  2. Each node except the initial node has exactly one immediate predecessor. The initial node has no predecessors.
  3. Multiple branches extending from the same node have different action labels.
  4. Each information set contains decision nodes for only one of the players.
  5. All nodes in a given information set must have the same number of immediate successors and they must have the same set of action labels on the branches leading to these successors. (if not, it is trivial that the player can distinguish states. )

Representing infinite action space

continuous action space
  • We can use dotted line to represent simultaneous move games.
continuous action space
  • The Stackelberg game, represented by the graph above, is a variation of cournot game we looked before.
  • The difference here is that it is not simultaneous. Thus the strategy spaces are,

S1=[0,∞)S_1 = [0, \infty) \\ S2={f:[0,∞)→[0,∞)}S_2 = \{ f : [0, \infty) \rightarrow [0, \infty) \}

  • Note that strategy space of player 2 is not positive real number, becuase player 2 can decide with information of player 1's decision.

Perfect Recall

  • Perfect recall is when players remember what they did previously.
  • Following diagram represents an example of imperfect recall. Note that player 1 cannot distinguish two states.
image
  • If every information set is a single node, then the game is of perfect information. (when there are no dashed lines in the extensive form)
  • Otherwise, the game is of imperfect information. (when there is any dashed line in the extensive form)
Discuss on Twitter • View on GitHub