1
$\begingroup$

I'm writing a paper and I need to define what a perfect-information game in extensive form is. My paper includes material from Game Theory and Reinforcement Learning. Since the notation of both fields is different, I changed that definition a bit, but I don't know if this is correct.

A (finite) perfect-information game (in extensive form) is a tuple $G = (\mathcal{N}, \mathcal{A}, \mathcal{H}, \mathcal{Z}, \chi, \rho, \sigma, u)$, where:

  • $\mathcal{N}$ is a set of $n$ players;

  • $\mathcal{A}$ is a (single) set of actions;

  • $\mathcal{H}$ is a set of nonterminal choice nodes;

  • $\mathcal{Z}$ is a set of terminal nodes, disjoint from $\mathcal{H}$;

  • $\chi : \mathcal{H} \mapsto 2^A$ is the action function, which assigns to each choice node a set of possible actions;

  • $\rho : \mathcal{H} \mapsto \mathcal{N} $ is the player function, which assigns to each nonterminal node a player $i \in \mathcal{N}$ who chooses an action at that node;

  • $\sigma : \mathcal{H} \times \mathcal{A} \mapsto \mathcal{H} \cup \mathcal{Z}$ is the successor function, which 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$; and

  • $u = (u_1,\dots,u_n)$, where $u_i : Z \mapsto \mathbb{R}$ is a real-valued utility function for player $i$ on the terminal nodes $Z$.

In Reinforcement Learning the set of all states is $\mathcal{S}$, the set of actions $\mathcal{A}$ and the successor function $\mathcal{A(s)}$.

I wanted to know if it makes sense to change the Game Theory definition to:

  • $\mathcal{N(\cdot)}$ for the player function.
  • $\mathcal{A(\cdot)}$ for the successor function.
  • $\mathcal{S^T}$ for the set of terminal nodes/states.
  • $\mathcal{S^N}$ for the set of nonterminal nodes/states.

Any ideas? Suggestions?

Thanks in advance!

$\endgroup$
2
$\begingroup$

There plainly exists no universally agreed on definition of an extensive form game. In the most popular approach due to Kuhn, the game tree is simply a connected graph without cycles and a distinguished node as the origin. Osborne and Rubinstein treat the game tree as a set of finite and infite sequences of actions. In the tradition of von Neumann and Morgenstern, Alós-Ferrer and Ritzberger treat the game tree as a family of sets of outcomes.

General extensive forms can become very complicated because one has to account for information, but perfect information games are usually simple enough that you can optimize notation and definitions to make your arguments and proofs read nicely.

| 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.