Converting spacetime games to the extensive form

General principle

A spacetime game, with or without perfect information, corresponds to decisions made in flat Minkowski spacetime.

Decisions connected, directly or indirectly, by directed arrows occur in an order that all observers agrees with. This is called timelike separation.

Decisions that are not connected by a directed path will occur in an order that is observer-dependent (if they can occur together).

Let us go back to a previous example:

In order to talk about the six nodes in this game, let us give us names, A, B, X, Y, W, and Z.

In this game, A and B are not connected by any arrow (spacelike separation). This means that some observers will see Alice make her decision A before Bob makes his decision B, and some observers will see Bob make his decision B before Alice makes her decision A.

On the other hand, A has a directed arrow to X (timelike separation). It means that A occurs before X no matter what.

A more subtle case is X and Y: they will never occur together because it is either-or depending on Alice's previous decision. We call this haplike-separated, i.e., they always occur in parallel worlds. If we ignored the edge labels, they would "seem" spacelike-separated according to the DAG, but this is irrelevant because they never jointly occur.

Linearization of a Directed Acyclic Graph

In other words, the directed arrows enforce an order on some pairs of decisions, but not on some others. Thus, if we try to build a list of the six decisions (A, B, X, Y, W, Z) under the constraint enforced by the arrows (A before X, A before Y, B before W, B before Z) there are a not small, but limited number of possibilities. A few examples (not exhaustive):

Some possible orders
AXYBWZ
BWZAXY
ABXYWZ
BAXYWZ

Such lists are called linearizations of the DAG. Each list corresponds to an order that some observer could actually witness under the constraints of the DAG.

If we swap haplike-separated decisions (like X and Y, or like W and Z), this is considered to be the same linearization because they never jointly occur anyway. So AXYBWZ would be the same as AYXBWZ or AXYBZW or AYXBZW.

The conversion algorithm

Now, for each one of these linearizations, it is possible to build a game in extensive form with imperfect information that corresponds to the linearization and that is semantically equivalent to the original spacetime game. This is done recursively by starting with the first decision in the list and putting it at the top of the three.

Then the second decision in the list goes below.

Timelike-separated decisions

If it is timelike separated from the first, then it is put below the action that activates it and not below the other actions. The other actions might get children later in the process, or point to a final outcome if this is not the case.

For example, these are two decisions that are timelike-separated:

And this is the equivalent extensive form structure. We write below each outcome which leaf nodes of the spacetime game are reached.

In this particular case the spacetime form is similar to the extensive form. This is in fact always the case when there is only timelike separation and no spacelike separation between two decisions.

Spacelike-separated decisions

If it is spacelike separated from the first, then it is duplicated and put below every action and all the duplicates are connected with dashed lines.

For example, these are two decisions that are spacelike-separated:

And this is the equivalent extensive form structure if the left decision appears first in the linearization. We write below each outcome which leaf nodes of the spacetime game are reached.

If we had instead had the right decision first (top layer), and then the left one (bottom layer) we would have obtained this extensive form instead:

Then we traverse the list, adding layer by layer. For each decision, we add nodes at the bottom below all the activating paths and connect them with dashed lines. Then we conclude by adding outcome leaf nodes to all the outgoing edges without child nodes.

Drive-through: a more complex example

Let us take this other example of spacetime game.

We take the linearization yellow/orange/red/blue/green/brown (top down then left to right).

We start with yellow at the top level of the extensive form:

Then we proceed to orange, which is spacelike-separated, so we add it to both edges and connected with a dashed line, like so:

Now we proceed to red, which connects to the x side because this is the precondition:

And now blue, whih connects to the y side. Since there is room, we can put it on the same layer as red for a symmetrical visual. This happens for haplike-separated decisions, such as red and blue:

Next comes green, which connects to the paths with w, there are four of them:

And finally, brown, to the paths with z, also four of them. Since there is room, we put it on the same layer as green:

Finally, we add the outcomes to every edge with no destination node. We have labeled the outcomes with the active subset of leaf nodes from the spacetime form:

As you can see, the leaf nodes of the extensive form exactly correspond to the outcomes of the spacetime game (subsets of activated leaf nodes of the DAG in the spacetime form). Likewise, the information sets (colors) exactly correspond to the information sets of the spacetime game (in this case, the spacetime game had six singleton information sets).