Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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