On the representation of informational structures in games

1.   Introduction

Since the concept of information plays an important role in defining strategies in games involving sequential moves (for example, see Kuhn (1953) ^[11] or Osborne and Rubinstein (1994) ^[12] for the classical formulation of an extensive game and Başar and Olsder (1999) ^[3] or Dockner et al, (2000) ^[4] for the formulation of dynamic games), a mathematical model of information in games can be valuable to game theorists. Traditionally, the informational structure of a game is often defined by a partition of decision nodes which are themselves derived from the primitives of the game (for instance a graph theoretical tree in Kuhn's formulation or a binary relation in von Neumann's representation ^[15]). More recently, there have been at least two important developments in the modelling of information in games; the first is due to Kaneko and Kline (2008a, 2008b) ^[5], ^[6], who developed a framework that explicitly models information in terms of sequences of pairs of information pieces and actions, referred to as information protocols, whereas the second is due to von Stengel and Forges (2008) ^[16] who, in a paper on the computational complexity of the extensive-form correlated equilibrium, introduce a "precedence" binary relation that describes the notion of order on information sets. One fundamental difference between these two approaches is that the Kaneko-Kline information protocol is based on a sequence theoretic formulation while that of Stengel and Forges is based on a binary relation which can be regarded a directed graph. In this paper, we ask which of the two formulations is more general and under which conditions they are equivalent. In particular, we ask, given a finite set of information (information sets or information pieces), under which conditions a set of strings of information (of finite or infinite length) can be regarded as mathematically equivalent to some informational digraph (induced by the precedence binary relation). The following example demonstrates that not all sequence theoretic informational structures are equivalent to their induced informational digraphs.

Example 1. Let $X = \left\{ a, b, c, d\right\}$ be a finite set of information (information sets or information pieces) of a given game and let the set of feasible sequences of information derived from the game be given as follows.

From $S$, we can derive a precedence binary relation as follows. For $x, y\in X$, we say that $x < y$ if $x$ precedes $y$ in some sequence $s\in S$. We can then derive the informational digraph as $G = \left(X, < \right)$ so that

The digraph is illustrated as follows.

In order to compare $S$ and $G$, we compare the maximal sequences of $S$ (that is, the set of sequences that are not proper subsequences any sequences in $S$), denoted by $S^{\ast}$, with the set of maximal walks of $G$, denoted by $W^{\ast}$. When the two sets coincide, we say that $S$ and $G$ are equivalent.^① It can be shown that

^①We will develop this notion of equivalence formally in the next section following ^[9] and ^[10].

Since $S^{\ast}\neq$ $W^{\ast}$, we conclude that $S$ is not equivalent to its informational digraph $G$. In this paper, we aim to give the necessary and sufficient conditions for any general informational sequence structure to be equivalent to its informational digraph and the converse, that is, starting from a directional digraph, whether we can find an equivalent informational structure.

An equivalence theorem along the lines of the above was given by Kline and Luckraz (2011) ^[9] who showed that the Information Protocol (IP) formulation of ^[5] is equivalent to some multi- colored digraph if and only if the IP satisfies the strong extension property. However, their equivalence has two limitations. First, since the sequences in a basic IP were restricted to be of finite lengths, informational digraphs that contain cycles were excluded from ^[9]'s equivalence theorem. It has been shown that information cycles can occur even in two-player games that satisfy perfect recall (see ^[16] on page 1012, Figure 6).^② Related to this, is the fact that sequences in some IP that contain repeated information pieces cannot be captured by multi- colored graphs according to ^[9]'s theorems since repeated pieces will induce a cyclical multi-colored digraph which cannot be equivalent to some finite IP. Second, ^[9] considered the multi-graph induced by sequences of pairs of information pieces and actions so that the action components of some sequence in the IP were translated to labels (coloring) assigned to the edges of the digraph. This excluded many well-known class of games, like the simultaneous moves for instance (see Figure 3 on page 108 in ^[9]). Our approach can circumvent both of these limitations as, by allowing the informational sequences to be of length up to $\omega$, where $\omega$ is the smallest ordinal, we are able to capture informational digraphs with cycles. Moreover, as we only consider action-free sequences of information (sets or pieces), our informational digraph is a simple digraph that can include simultaneous moves games.

^②Another well-known example that has informational cycles is the Absent-Minded Driver Game (see ^[13] and ^[1]).

Equivalences between mathematical representation of games have recently received some attention in game theory. In particular, Streufert (2019) ^[14] gives a formal five-way equivalence among different game structures and thus, provides game theorists with a broad spectrum of alternative game specifications.^③ Our paper differs from this literature as it focuses on the informational aspect of the game and does not consider the entire game structure which often comprises of other components like payoffs, strategy space and equilibria. Our comparison between informational structures boils down to a comparison between two mathematical objects; a set of sequences and its induced digraph. We provide a necessary and sufficient condition under which these two objects are equivalent. We show that the informational sequence structure can be equivalent to digraphs if and only if it is restricted to the class that satisfies the uniform extension property. On the other hand, the space of all informational digraphs can be embedded freely into the space of all informational sequence structures only under some mild technical condition. Our result can be seen as a generalization of ^[9]'s theorem as we allow for the possibility of infinite informational sequences through cycles. The uniform extension condition we propose is more general than the strong extension condition of ^[9] as firstly, it does not include actions in the extension and secondly, it applies to both finite and infinite informational sequences.^④

^③An equivalence between graph games and sequence games was given by Kline and Luckraz (2016) ^[10].

^④Note that the assumption finiteness was often used in some arguments in the proofs of ^[9] results and these arguments cannot be used in our proofs as we do not restrict the sequences to be of finite length.

As observed by ^[9], the equivalence result we propose can help identify classes of games for which informational digraphs can adequately model information. In such cases, these digraphs can be particularly useful to players who have limited understanding and knowledge of the game structure to acquire information throughout the game. This is because graph theory is founded on the local principle of vertices and edges that build the whole graph, while informational sequences are based on an entire set of historical sequences which may be too large for some players to handle. Hence, having a simple digraph representation can make learning about the game more manageable for such players.

The paper is organized as follows. In the next section we introduce the notion of informational sequences. In Section 3, we give the definition of an informational digraph. In Section 4, we propose a notion of equivalence and give the main results of the paper, while Section 5 concludes.

2.   Informational sequence structure

2.1.   Preliminaries

Recall that an information protocol (IP) was given as a triple which comprised of a finite non-empty set of information pieces; a finite non-empty set of actionsand a finite non-empty subset of sequences of pairs of information pieces and actions (see ^[5], ^[6], ^[7] and ^[8]). Because the focus of this paper is on the informational structures of the game, we only focus on sequences of information, which can be tangible pieces as in IPs or abstract sets decision nodes in the sense of ^[11]. We start by giving a formal definition of an informational sequence structure.

Let $X$ be a non-empty finite set of information. We denote a informational sequence structure $S$ by a set of sequences of elements of $X$ of length at most $\omega$, where $\omega$ is the the smallest infinite ordinal, that is, each $s\in S$ is a sequence of elements of $X$ of length $i$, where $i\leq\omega$. Therefore,

We call $\left(X, S\right)$ an informational sequence structure pair. An example of such an $S$ can be found in Example 1. We denote the power set of ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$ by $\Pi$, so that $\Pi$ is the space of all possible informational sequence structures with base set $X$.

2.2.   Subsequence

For sequences $s = \langle q_{i}\rangle _{i = 1}^{n}$ and $t = \langle t_{j}\rangle _{j = 1}^{m}$ in ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$, where $n$ and $m$ can be up to $\omega$, we say that $t$ is a subsequence of $s$, if there exist some strictly increasing function $f:\left\{ 1, .., m\right\} \rightarrow \left\{ 1, .., n\right\}$ satisfying $t_{j} = q_{f(j)}$ for $j = 1, .., m$.^⑤

^⑤Note that the definition implies that $f$ is injective.

When $s^{\prime}$ is a subsequence of $s$, we denote this relation by $s^{^{\prime}}\preceq s$. We say that $s^{\prime\prime}$ is a proper subsequence of $s$ if $s^{\prime\prime}\preceq s$ and $s\nsucceq s^{\prime\prime}$. In this case, we denote the relation by $s^{\prime\prime }\prec s$. In Example 1, $\langle a, d\rangle$ is a proper subsequence of $\langle a, b, d\rangle$.

2.3.   Concatenation

For sequences $p = \langle p_{1}, p_{2}, ...p_{k}\rangle$ and $q = \langle q_{i}\rangle _{i = 1}^{n}$ in ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$, where $k$ is finite and $n$ can be up to $\omega$, we denote by $\left(p; q\right)$ the sequence obtained by concatenating $p$ with $q$. Thus, in Example 1, $\langle a, b, d\rangle = \left(\langle a\rangle; \langle b, d\rangle \right)$. If $p_{k} = q_{1} = x$, we use the convention that

so that $x$ is not repeated at the concatenated part of the sequence. For example if $p = \langle x, y, z\rangle$ and $q = \langle z, u\rangle$, then $\left(p; q\right) = \langle x, y, z, u\rangle$.

2.4.   Cycles

A finite cyclic sequence $s$ in ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$ is a finite sequence of length at least $2$ such that its first term equals to its last term, that is, $s = \langle s_{i}\rangle _{i = 1}^{k}\in$ ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$ is a finite cyclic sequence if $2\leq k < \infty$ and $s_{1} = s_{k}$. We say that $s^{\prime}$ in ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$ is a (proper) subcycle of finite cyclic sequence $s$ if $s^{\prime}$ is itself a finite cyclic sequence and it is a (proper) subsequence of $s$.

Example 2. Let $X = \left\{ a, b, c\right\}$ and let $S$ be given as follows.

All elements of $S$ are finite cyclic sequences. Moreover, $\langle a, a\rangle, \langle b, b\rangle, \langle a, b, c, a\rangle$, $\langle b, a, b\rangle$, $\langle a, c, a\rangle$ and $\langle a, b, a\rangle$ are proper subcycles of $\langle a, b, a, b, c, a\rangle$.

We say that $s$ is an infinite cyclic sequence in ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$ if it is formed by the infinitely repeated concatenation of some finite cyclic sequence, that is, for some finite cyclic sequence $u = \langle u_{i}\rangle _{i = 1}^{k}\in$ ${ \bigcup\nolimits_{i = 1}^{\infty}} X$, where $u_{1} = u_{k} = x$, infinite cyclic sequence $s$ is given as follows.

Note that in an infinite cyclic sequence all terms of the cycle appear an infinite number ($\omega$) of times.

If $s$ is an infinite cyclic sequence derived from the infinitely repeated concatenation of some finite cyclic sequence $u = \langle u_{i} \rangle _{i = 1}^{k}\in$ ${ \bigcup\nolimits_{i = 1}^{\infty}} X$ and $s^{\prime}$ is an infinite cyclic sequence derived from the infinitely repeated concatenation of some finite cyclic sequence $t = \langle t_{j}\rangle _{j = 1}^{l}\in$ ${ \bigcup\nolimits_{i = 1}^{\infty}} X$, then we say that $s^{\prime}$ is a (proper) subcycle of $s$ if $t$ is a (proper) subsequence of $u$.^⑥

^⑥Note that infinite cyclic sequence $s^{\prime}$ is a (proper) subcycle of infinite cyclic sequence $s$ whenever it is a (proper) subsequence of $s$.

Example 3. Let $X = \left\{ a, b, c\right\}$ and let $S$ be given as follows.

All elements of $S$ are infinite cyclic sequences. Moreover, $\langle a, a, ...\rangle$ is derived from finite cyclic sequence $\langle a, a\rangle$ while $\langle a, b, c, a, b, c, ...\rangle$ is derived from finite cyclic sequence $\langle a, b, c, a\rangle$. We also observe that $\langle a, a, ...\rangle$ is a proper subcycle of $\langle a, b, c, a, b, c, a, ...\rangle$ since $\langle a, a\rangle$ is a proper subcycle of $\langle a, b, c, a\rangle$.

2.5.   Infinite sequences

We next give a general representation of an infinite sequence $s$ in ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$. Observe that since $X$ is finite, whenever $s$ is an infinite sequence, it must have some terminal infinite cyclic subsequence.

Formally, we can define any infinite sequence $s$ by the concatenation of sequences $t$ and $v$, so that

where $t$ is some finite sequence in ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$ while $v$ is some infinite cyclic sequence in ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$. Observe that $t$ and $v$ need not be unique and that $t$ is allowed to be the empty sequence.

Example 4. Let $X = \left\{ a, b, c, d\right\}$ and let $S$ be given as follows.

All of the above sequences are infinite sequences of the form $s\equiv\left(t; v\right)$. In the first sequence, $t = \langle a, b, c\rangle$ while $v = \langle d, d, ...\rangle$. In the second sequence $t = \langle d\rangle$ and $v = \langle a, b, c, a, b, c, ...\rangle$, while in the third sequence, $t = \langle a, b, c, a, b\rangle$ while $v = \langle a, d, a, d, ...\rangle$.

2.6.   Maximal sequences

Maximal sequences will be defined with respect to some $S\subseteq { \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$. For finite sequence $s\in S$, we say that sequence $s$ is a maximal sequence in $S$ if it is not the proper subsequence of any $s^{\prime}\in S$.

If $s\equiv\left(t; v\right) \in S$ is an infinite sequence, then we say that $s$ is maximal if all $t$ and $v$ satisfying $s\equiv\left(t; v\right)$, all of the conditions below are satisfied.

(i) There exist no sequence $s^{\prime}\equiv\left(t^{\prime}; v^{\prime }\right) \in S$ such that $t$ is a proper subsequence of $t^{\prime}$ and $v$ is a proper subcycle of $v^{\prime}$.

(ii) There exist no sequence $s^{\prime\prime}\equiv\left(t^{\prime\prime }; v^{\prime^{\prime}}\right) \in S$ such that $t = t^{\prime\prime}$ and $v$ is a proper subcycle of $v^{\prime\prime}$.

(iii) There exist no sequence $s^{\prime\prime\prime}\equiv\left(t^{\prime\prime\prime}; v^{\prime\prime\prime}\right) \in S$ such that $t$ is a proper subsequence of $t^{\prime\prime\prime}$ and $v = v^{\prime\prime\prime }$.

In Example 1, $\langle c, b\rangle$ and $\langle a, b, d\rangle$ are maximal. In Example 2, $\langle a, b, a, b, c, a\rangle$ is maximal. In Example 3, $\langle a, b, c, a, b, c, a, ...\rangle$ is maximal. In Example 4, $\langle d, a, b, c, a, b, c, a, b, c, ...\rangle$ and $\langle a, b, c, a, b, a, d, a, d, ....\rangle$ are maximal. Note the above can rule out many types of infinite sequences as maximal sequences. For example, suppose we have only two sequences in $S$ are $x = \langle d, a, b, c, a, b, c, ...\rangle$ and $y = \langle b, c, a, b, c, a, b, c, ..\rangle = \left(t; v\right)$, where $t = \langle b, c\rangle$ and $v = \langle a, b, c, a, b, c, ...\rangle$. Then, $y$ is not a maximal sequence as for the given choice of $t$ and $v$, we can let $x = \left(t^{\prime}; v^{\prime}\right)$, where $t^{\prime} = \langle d, a, b, c\rangle$ and $v^{\prime} = \langle a, b, c, a, b, c, ...\rangle$ so that $t$ is a proper subsequence of $t^{\prime}$ and $v = v^{\prime}$.

2.7.   Adjacent pairs

For $s = \langle s_{i}\rangle _{i = 1}^{n}\in { \bigcup\nolimits_{i = 1}^{\infty}} X^{i},$where $n$ can be up to $\omega$, we denote $\left(x, y\right)$ as an adjacent pair in $s$ if $x = s_{i}$ and $y = s_{i+1}$ for some $i$th term of sequence $s$. For sequence $s$, denote the set of all adjacent pairs in $s$ by $A(s)$. In Example 1, $\left(a, b\right)$ and $\left(b, d\right)$ are adjacent pairs in $\langle a, b, d\rangle$, while in Example 4, $\left(a, b\right)$, $\left(b, c\right)$, $\left(c, d\right)$ and $\left(d, d\right)$ are adjacent pairs in $\langle a, b, c, d, d, ....\rangle$.

2.8.   Segments

We say that sequence $s^{\prime\prime}$ is a segment of $s\equiv \langle s_{i}\rangle _{i = 1}^{n}\in { \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$, where $n$ can be up to $\omega$, if

(i) either $s^{\prime\prime}$ is of length $> 1$ and is a subsequence of $s$ satisfying the following

(ii) $s^{\prime\prime}$ is of length $1$ and is a subsequence of $s$.

We call $s^{\prime\prime}$ is a proper segment of $s$ whenever $s^{\prime\prime}$ is a segment of $s$ and also a proper subsequenceof $s$.

In Example 4, $\langle d, d, ..\rangle$ is a proper segment of $\langle a, b, c, d, d, ....\rangle$.

For $s = \langle s_{i}\rangle _{i = 1}^{n}\in { \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$, where $n$ can be up to $\omega$, we define an initial segment of $s$ as some segment $t = \langle t_{j}\rangle _{j = 1}^{k}$ of $s$ so that $t$ is of length $k$, where $k\leq n$ and $t_{1} = s_{1}$. If $k < n$, we say that that $t$ is a proper initial segment of $s$.

In Example 1, $\langle a, b\rangle$ is a proper initial segment of $\langle a, b, d\rangle$.

2.9.   Well-ordered sequences

We say that sequence $p\in$ ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$ is a well-ordered sequence relative to set $S$, if $p$ is the initial segment of some maximal sequence in $S$. Denote by $P(S)$ the set of all well ordered sequences relative to the set $S$ and let $A\left(S\right)$ be the set of all adjacent pairs of $P(S)$, that is, $A\left(S\right) = { \bigcup\limits_{s\in P(S)}} A(s)$. Note that $p\in P(S)$ does not imply that $p\in S$.

In Example 1, $S = \left\{ \langle a\rangle, \langle b\rangle, \langle c\rangle, \langle d\rangle, \langle c, b\rangle, \langle a, d\rangle, \langle a, b, d\rangle \right\}$ and

$P(S) = \left\{ \langle a\rangle, \langle c\rangle, \langle c, b\rangle, \langle a, b\rangle, \langle a, b, d\rangle \right\}$. Note that $\langle a, b\rangle \in P(S)$ but not in $S$.

2.10.   Properties of informational sequence structures

Let $s = \langle s_{i}\rangle _{i = 1}^{n}$ denote some sequence in $S\subseteq$ ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i},$where $n$ can be up to $\omega$, and consider the following properties of $S$.

A0 (Completeness) For each $x\in X$, there exist some $\langle s_{i}\rangle _{i = 1}^{n}\in S$, such that $x = s_{i}$ for some $i$.

A1 (Subsequence Closure) If $s\in S$ and $s^{^{\prime}}$ $\preceq$ $s$, then $s^{^{\prime}}\in S$.

A2(Uniform Extension) If $\left(x, y\right) \in A\left(S\right)$, then for all finite $s^{\prime}\equiv\langle s_{i}^{\prime }\rangle _{i = 1}^{n}\in P(S)$ satisfying $s_{n}^{^{\prime}} = x$, we have $\left(s^{\prime}; \langle y\rangle \right) \in P(S)$.^⑦

^⑦Note that uniform extension is parallel to what ^[9] refer to as strong extension in the context of information protocols and multi-colored graphs.

In Example 1, $S$ is complete but not subsequence closed because $\langle a, b\rangle$ and $\langle b, d\rangle$ are not in $S$. To verify that whether it satisfies Uniform Extension, we first note that $P(S) = \left\{ \langle a\rangle, \langle c\rangle, \langle c, b\rangle, \langle a, b\rangle, \langle a, b, d\rangle \right\}$ and $A(S) = \left\{ \left(c, b\right), \left(a, b\right), \left(b, d\right) \right\}$. Then, we observe that Uniform Extension is violated because $\langle c, b\rangle \in P(S)$ and $\left(b, d\right) \in A(S),$but

3.   Informational directed graphs

von Stengel and Forges (2008) ^[16], use a "precedence" binary relation to describe the notion of order on information sets of a given extensive game. Using the digraph induced by such a general binary relation, we consider a model of information that can be represented by a digraph so that the vertices of the graph represent information^⑧ and the edges represent local informational linkages.

^⑧Information could mean some tangible infomation piece as in ^[9] or some abstract set of nodes from a decision tree as in ^[16].

We follow Bang-Jensen & Gutin's (2009) ^[2] definition of a digraph. A digraph $G$ is given by pair $\left(V, E\right)$, where $V$ is a finite set of vertices and $E$ is the set of directed arcs between pairs of vertices. We define the walks of the graph as follows.

Sequence $\langle w_{i}\rangle _{i = 1}^{n}$ in ${ \bigcup\nolimits_{i = 1}^{\infty}} V^{i}$, where $n$ can be up to $\omega$, is called a walk in $G$ if either (i) $w$ is of length $1$ and $w_{1} = v$ for some $v\in V$ or (ii) $w$ is of length $> 1$ and $\left(w_{i}, w_{i+1}\right) \in E$ for each $i$. The concepts of a maximal walk and that of a segment can be defined in the same way as we did for sequences in the previous section. We use the convention that the length of a walk is given by the length of the sequence it defines.^⑨ Let $\Omega$ denote the set of all digraphs with base vertex set $V$. The following property will be useful in establishing our equivalence results.

^⑨Note that in standard graph theory, the length counts the number of edges instead of vertices. As a result, an isolated vertex will be a walk of length $1$ in our formulation while in standard graph theory it would have not been regarded as a walk.

B1 (Transitive Reduction) Every walk in $G$ is a segment of some maximal walk in $G$.

In Example 1, Figure 1, transitive reduction is violated because while $\langle a, d\rangle$ is a walk in $G$, it is not the segment of any maximal walks in $G$.

4.   Equivalences

In this section, we introduce the notion of equivalence between the two informational structures given in the previous sections. At this stage it is important to point out that unlike ^[10] and ^[14] who study equivalences between game forms, we only focus on the equivalence at the informational level and hence, we look for an equivalence between the informational sequence structure of section 2 and the informational digraph of section 3. We give the necessary and sufficient conditions for equivalence to hold.

We fix a base finite non-empty set $X$, and we say that informational sequence structure pair $(X, S)$ is $p$-equivalent to informational digraph $G = \left(X, E\right)$ iff for all sequence $\alpha\in$ ${ \bigcup\nolimits_{i = 1}^{\infty}} X^{i}$

We can now give the main results of the paper. Our first result shows that every $S$ has a $p$-equivalent $G$ if and only if the uniform extension property A2 and the completeness property A0 are satisfied.

Theorem 1. Let $S\in\Pi$ for a given finite set $X$. Then, $S$ satisfies A0 and A2 iff $(X, S)$ has a p-equivalent $G$ with vertex set $X$.

Proof(Only if) Suppose that $S$ satisfies A0 and A2. Then, we construct $G$ as follows. Let $G = \left(X, E\right)$, where $E = A\left(S\right)$, the set of all adjacent pairs of $P(S)$ as defined in Section 2. Since $X$ is finite, $A(S)$ is finite. We need to show that (i) every walk in $G$ is a segment of a maximal sequence of $S$ and that (ii) every segment of a maximal sequence in $S$ is a walk of $G$.

We start with (i). Suppose $\langle w_{m}\rangle _{m = 1}^{i}$, where $i$ can be up to $\omega$, is a walk in $G$. We will show by induction that every walk of length $i\leq\omega$ of $G$ is a segment of some maximal sequence in $S$. For the base case, by A0, we have $w_{1}$ is a component of some sequence in $S$ and hence, it is also a component of some maximal sequence in $S$. This implies that $\langle w_{1}\rangle$ is the segment of some maximal sequence in $S$.

For the inductive hypothesis, we assume that each walk $\langle w_{m}\rangle _{m = 1}^{i}$, of length $i$, where $i < \omega$, is the segment of some maximal sequence in $S$. We need to prove that each walk $\langle w_{m}\rangle _{m = 1}^{i+1}$ of length $i+1$ is the segment of some maximal sequence in $S$. Since $\langle w_{m}\rangle _{m = 1}^{i}$ is the segment of some maximal sequence in $S$, say $s^{\ast}$, there exist some sequence $p$ and $q$ such that $q = \left(p; \langle w_{m}\rangle _{m = 1}^{i}\right)$ such that $q$ is an initial segment of $s^{\ast}$ (note that $p$ could be the empty sequence). Since $\left(w_{i}, w_{i+1}\right)$ is an edge of $G$, it is an adjacent pair in $S$. As a result, by uniform extension A2, we have $\left(q; \langle w_{i+1}\rangle \right) \in P(S)$ and therefore, $\langle w_{m}\rangle _{m = 1}^{i+1}$ is the segment of some maximal sequence in $S$.

We now prove (ii). Let $s\in S$ be a segment of a maximal sequence, say $s^{\ast}$, in $S$. We need to show that $s$ is a walk in $G = \left(X, A(S)\right)$. If $s$ is of length $1$, by the definition of walks $G$, $s$ is a walk of length $1$ in $G$. Next, suppose that the length of $s$ is $> 1$. Then, by the definition of $A(S)$, since $s^{\ast}$ is a maximal sequence and $A(S)$ is the set of all edges of $G$, all adjacent pairs of $s^{\ast}$are edges in $G$ and hence, $s$ is a walk of $G$.

(If) We first prove that every $S$ that has a p-equivalent $G$ must satisfy A0. Since $G = \left(X, A(S)\right)$, by the definition of walks, for each $x\in X$, $\langle x\rangle$ is a walk of length $1$ in $G$. Therefore, by p-equivalence, $\langle x\rangle$ is the segment of some maximal sequence in $S$. Hence, all elements of $X$ are used in $S$.

We next show that A2 is satisfied. We first note that since $G$ is equivalent to $S$, the set of maximal sequences of $S$ coincides with the set of maximal walks of $G$.^⑩ To show that A2 is satisfied, we need to show that for all finite $s^{\prime} \equiv\langle s_{i}^{\prime}\rangle _{i = 1}^{n}\in P(S)$ satisfying $s_{n}^{^{\prime}} = x$ and for all adjacent pairs $\left(x, y\right) \in A(S)$, we have $\left(s^{\prime}; \langle y\rangle \right) \in P(S)$. Since $s^{\prime}\in P(S)$, it must be the initial segment of some maximal sequence $s^ \wedge$ in $S$. Now, since $G$ is equivalent to $S$ and $\left(x, y\right)$ is an edge in $G$, $\langle x, y\rangle$ is a walk of length $2$. Furthermore, by equivalence we have $s^{\prime}$ is a walk in $G$. Then, since $\left(x, y\right)$ is an edge of $G$, we have $\left(s^{\prime}; \langle y\rangle \right)$ is a walk in $G$. By equivalence again, $\left(s^{\prime}; \langle y\rangle \right)$ is a segment of some maximal sequence, say $s^{\ast}$ in $S$.

^⑩Indeed, suppose that $w$ was a maximal walk in $G$ but not a maximal sequence in $S$. Then, by p-equivalence, $w$ would be the proper segment of some maximal sequence $s$ in $S$, which, by p-equivalence again, is a walk in $G$, contradicting the maximality of $w$. On the other hand, suppose that $s$ was a maximal sequence in $S$ but not a maximal walk $G$, then, by p-equivalence, $s$ would be the proper subsequence of some maximal walk $w$ in $G$, but since by p-equivalence again $w$ would be the segment of some maximal sequence in $S$, this would imply that $s$ is the proper segment of some maximal sequence in $S$, which would contradict its maximality.

Now, since the set of maximal sequences of $S$ coincides with the set of maximal walks of $G$, we have both $s^ \wedge$ and $s^{\ast}$ are maximal walks in $G$.

We claim that $\left(s^{\prime}; \langle y\rangle \right)$ is an initial segment of $s^{\ast}$. Suppose not. Then, $s^{\ast}$ has an initial segment $q$ such that $\left(s^{\prime}; \langle y\rangle \right)$ is a proper segment of $q$ and where the last term of $q$ is $y$. Observe that $q$ can be written as $q = \left(r; \langle y\rangle \right)$, where $r$ is the proper initial segment of $q$ that has $x$ as its last term and excludes $y$. Then $s^{\prime}$ must be a proper segment of $r$. Furthermore, maximal sequence $s^ \wedge$ can be written as $s^ \wedge = \left(s^{\prime}; s^{\prime\prime}\right)$, where $s^{\prime\prime}$ is a segment of $s^ \wedge$.

From the above, we can construct the walk $u = \left(r; s^{\prime\prime }\right)$ in $G$. But, since this would imply that $s^ \wedge$ is a proper segment of $u$, the maximality of $s^ \wedge$ would be contradicted. Hence, $\left(s^{\prime}; \langle y\rangle \right)$ must the initial segment of maximal walk $s^{\ast}$ and since the set of maximal walks of $G$ coincides with the set of maximal sequences of $S$, we have $\left(s^{\prime}; \langle y\rangle \right) \in P(S)$. $\square$

Theorem 1 shows that when the class of informational sequence structures is restricted to the class that satisfies A0 and A2, then it can be regarded as equivalent to some informational digraph. Thus, when A0 and A2 are satisfied, a digraph or a binary relation (as in ^[16]) can be used to model any informational structure in games without any loss of generality. While A0 can be regarded as a mild condition, A2 can be strong in some cases. Both Example 1 and Example 4 do not satisfy A2 and are negative examples of the above theorem.

For Example 1, we saw in the last paragraph of Section 2 that the sequence informational structure $S$ does not satisfy uniform extension and hence, by Theorem 1, it cannot have a p-equivalent informational digraph.

To see that the uniform extension is violated in Example 4, recall that

and that $\langle d, a, b, c, a, b, c, a, b, c, ...\rangle$ and $\langle a, b, c, a, b, a, d, a, d, ....\rangle$ are the only two maximal sequences of $S$. Then, we must have $\langle d, a\rangle \in$ $P(S)$ as it is an initial segment of maximal sequence $\langle d, a, b, c, a, b, c, a, b, c, ...\rangle$. Moreover, we observe that $\left(a, d\right)$ is adjacent pair in $A(S)$. Suppose uniform extension (A2) holds. Then, we must have sequence $\langle d, a, d\rangle$ as the initial segment of either $\langle d, a, b, c, a, b, c, a, b, c, ...\rangle$ or $\langle a, b, c, a, b, a, d, a, d, ....\rangle$, which is a contradiction. The next example is a positive example of Theorem 1 where $S$ contain infinite sequences and hence, infinite cyclic sequences.

Example 5. Let $X = \left\{ a, b, c, d, e, f\right\}$ and let $S$ be given as follows.

Note that A0 is satisfied and that $P(S)$ will contain $\langle a, b\rangle$ and all initial segments of $\langle a, c, d, e, f, c, d, e, f, c, ....\rangle$. It can be verified that A2 is satisfied and hence, $S$ has a p-equivalent informational digraph given as follows.

Theorem 1 also shows that for a given base set, the space $\Pi$ can be embedded into the space $\Omega$ if and only if A0 and A2 are satisfied. If one regards A2 as a strong condition, then one can argue that a sequence structure is more general than a digraph structure.

The next theorem starts with an informational digraph and shows that it has p-equivalent informational structure if and only if B1 is satisfied.

Theorem 2. Let $G = \left(V, E\right) \in\Omega$. Then, it has an equivalent informational sequence structure pair $(V, S)$ such that $S$ satisfies A0, A1 and A2 iff $G$ satisfies B1.

Proof (if) We construct $(V, S)$ as follows.

We first need to show that (i) every walk in $G$ is a segment of some maximal sequence of $S$ and (ii) every segment of a maximal sequence in $S$ is a walk of $G$.

We start by showing (i). Since by the construction of $S$ every maximal walk in $G$ is also some maximal sequence of $S$, the result follows from B1.

We next show (ii). Let $q$ be the segment of some maximal sequence in $S$. Then, by the construction of $S$, $q$ is the segment of some maximal walk in $G$, hence, a walk in $G$.

Finally, we show that $(V, S)$ satisfies A0, A1 and A2. A0 follows from the definition of walks which states that for each $v\in V$, $\langle v\rangle$ is a walk of length $1$ and from the construction of $S$, which ensures that the walks of length $1$ in $G$ are sequences of length $1$ in $S$ and hence, all elements are used in the sequences of $S$. Next, we see that A1 follows from the construction of $S$.

Last, we show that A2 is satisfied. To see this we first note that by the construction of $S$, the set of maximal walks in $G$ coincides with the set of maximal sequences in $S$. Suppose that $\left(x, y\right) \in A(S)$. We need to show that for all finite $s^{\prime} = \langle s_{i}^{\prime }\rangle _{i = 1}^{n}\in P(S)$ satisfying $s_{n}^{^{\prime}} = x$, we have $\left(s^{\prime}; \langle y\rangle \right) \in P(S)$. By the construction of $S$, $s^{\prime}$ is an initial segment of some maximal walk in $G$ and since $\left(x, y\right)$ is an adjacent pair, $\langle x, y\rangle$ is the segment of some maximal sequence in $S$. Now, by the construction of $S$, $\langle x, y\rangle$ is a walk (and $\left(x, y\right)$ is an edge) of $G$. Thus, we have $\left(s^{\prime }; \langle y\rangle \right)$ is a walk in $G$ and by B1, it is also the segment of some maximal walk, say $w^{\ast}$, in $G$. Finally, we can use an argument similar to the argument in the last two paragraphs of the proof of Theorem 1 to show that $\left(s^{\prime}; \langle y\rangle \right)$ is the initial segment of a maximal walk in $G$ and therefore, by the construction of $S$, $\left(s^{\prime}; \langle y\rangle \right)$ is in $P(S)$.

(Only if) Suppose by contradiction that $G$ has an equivalent informational sequence structure pair $(V, S)$ such that $S$ satisfies A0, A1 and A2 but $G$ violates B1. Then there exist some walk $w^{\prime}$ which is not the segment of any maximal walk in $G$. But by p-equivalence, $w^{\prime}$ must be the segment of some maximal sequence in $S$. Now, since p-equivalence also implies that the set of maximal walks in $G$ coincides with the set of maximal sequences in $S$, $w^{\prime}$ must be the segment of some maximal walk in $G$, a contradiction. $\square$

Theorem 2 shows that any informational digraph that satisfies B1 can be regarded as equivalent to some informational sequence structure and that the latter will be endowed with A0, A1 and A2. For example, the informational binary relation in ^[16] can be translated to some p-equivalent informational sequence structure without any loss of generality. Observe that informational digraph in Figure 1 of Example 1 is a negative example of the theorem because walk $\langle a, d\rangle$ is not the segment of some maximal walk and thus, B1 is violated. A positive example of the theorem, is the same graph in Figure 1 without edge $\left(a, d\right)$.

Theorem 2 also shows that for a given base set, the space $\Omega$ can be embedded into the space $\Pi$ if and only if B1 is satisfied. Since B1 is a mild technical condition, Theorem 2 also reinforce the idea that the sequence informational structure is more general than the informational digraph structure.

4.1.   Application to information in games

Theorems 1 and 2 and can be valuable in game theory as they provide the necessary and sufficient conditions for the two models of information to be equivalent. When modelling games where players are learning about the game structure and have cognitive limitation, the digraph representation may be easier to use. On the other hand, because A2 excludes some important classes of sequence information structures, informational digraphs can be at times inadequate. A well-known example is the Absent-Minded Driver game discussed by ^[1] and ^[13] which resulted in several debates among game theorists. Our results contribute to the above debate at least from the viewpoint of the informational structure. If some sequence informational structure were used to model information in the absent-minded driver game, then $S$ would only contain two elements of finite length (one of length $1$ and the other of length $2$). On the other hand, if we use the informational digraph representation, we would have a one-vertex graph with loop and thus, this graph would have walks of infinite length. Therefore, the the two structures cannot be p-equivalent. Another way to see this is to observe that $S$ violates A2 and hence, Theorem 1 does not apply.

More generally, one can show that any sequence informational structure which contains only sequences of finite length and where terms in some sequences are repeated a finite number of times cannot be equivalent to some informational digraph. On the other hand, Example 5 shows that there exist sequence informational structures that contain infinite cyclic sequences and that can be represented by some informational digraph as A2 is satisfied. Since ^[9] could not include informational structures of the type encountered in example 5 in their equivalence result, our result can be seen as a generalization of the theorems in ^[9]. Moreover, because we do not restrict actions in A2, we are able to include a broader class of games (including simultaneous moves games) than ^[9] in our results.

5.   Conclusions

We compared two widely used mathematical structures in informational models in games: an informational sequence structure and an informational digraph, where sequences and walks can be of infinite length. We developed a notion of equivalence between the two structures and provided explicit translation methods that map one structure to the other. We found that, starting with a informational sequence structure, the two structures can be regarded as equivalent if and only if some uniform extension property and completeness are satisfied. On the other hand, starting with some informational digraph, we obtained equivalence if and only if some transitive reduction property is satisfied. Since the uniform extension is a fairly stringent condition, we conclude that the sequence structure is more general than the digraph structure.

Our results give the flexibility to researchers modelling games where players have cognitive limitations and limited knowledge about the game structure to have a concise graph theoretical representation of information. Moreover, our theorems generalized some of the results of ^[9] as we relaxed the finite sequence assumption. Finally, we offered a new perspective to some well-known problems in game theory that relate to the modelling of information, like the absent-minded driver problem.

Acknowledgments

I would like to thank the Managing Editor and an anonymous referee for providing useful comments on an earlier version of this paper.

Conflict of interest

The author declares that there are no conflicts of interest.