Game theory

A perfect-information game in extensive form is defined by the tuple (N, A, H, Z, \x, \rho, \sigma, u) where

• Players: N is a set of players
• Actions: A is a set of actions
• Choice nodes: H is a set of non-terminal choice nodes
• Action function: \(\chi: H \to 2^A\) assigns to each choice node a set of possible actions
• Player function: \(\rho: H \to N\) assigns to each non-terminal node \(h\) a player \(i \in N\) who chooses an action at \(h\)
• Terminal nodes: \(Z\) is a set of terminal nodes, disjoint from \(H\)
• Successor function: \(\sigma: H \times A \to H \cup Z\) maps a choice node and an action to a new choice node or terminal node such that for all \(h_1, h_2 \in H\) and \(a_1, a_2 \in A\), if \(\sigma(h_1, a_1) = \sigma(h_2, a_2)\) then \(h_1 = h_2\) and \(a_1 = a_2\)
• Choice nodes form a tree: nodes encode history
• Utility function: \(u = (u_1, \ldots, u_n); u_i: Z \to \mathml{R}\) is a utility function for player \(i\) on the terminal nodes \(Z\)