Spacetime games
We have seen in the previous section that games in normal form and games in extensive form are two side of the same coin. Indeed, games in normal form can be converted to an equivalent game in extensive form, but the price to pay is the introduction of imperfect information: the dashed lines.
The reason is that in a game in normal form, an agent is not informed about the other agents' decision. The agents are in different rooms and do not communicate with each other.
This is in contrast with a game in extensive form with perfect information, in which the players are together and play one after each other. Thus, the player who plays second (say, at chess) is informed about the previous move of the other player.
As it turns out, special relativity has names for making this crucial difference: namely, spacelike separation and timelike separation:
To imagine two decisions that are spacelike-separated, imagine them very far away from each other. So far away, that no information can be sent from one to the other. For example, one is made on the Earth and one on Mars, but with just a few seconds of difference (knowing that light takes several minutes to go from Earth to Mars).
And to imagine two decisions that are timelike-separated, imagine that they are taken close enough to each other that there is communication, and one of them unambiguously is made before the other one.
Now, we are able to say that a game in normal form involves spacelike-separation between the players' decisions. And a game in extensive form with perfect information involves timelike-separation between the players' decisions.
We assume that you, the reader, are not familiar with special relativity, but that you may still have heard that space and time are part of the one and same continuum: spacetime, and that time is not absolute.
Thus, in special relativity, events happen "somewhere in spacetime", which you can see as a point "in spacetime". The coordinates in space and time of this point may not be the same depending on who is looking (the observer).
A spacetime game is basically a generalization of games in normal form (only spacelike-separated decisions) and of games in extensive form with perfect information (only timelike-separated decisions), in which decisions are at any points in spacetime. And in the same spacetime game, some pairs of points can be spacelike-separated, some other pairs can be timelike-separated, in the same game. This is what makes spacetime games more general than a game in normal form or than a game in extensive form with perfect information.
Structure of a spacetime game
Formally, a spacetime game is based on a DAG structure. DAG stands for Directed Acyclic Graph. It is a a directed graph in the sense that the edges have a directed arrow, like games in extensive form. And does not have cycles, in the sense that starting from any node and following the edges in their natural direction, one will never reach the original node again: a DAG has a natural "flow". Other names for DAGs depending on the field are: dependency graph, causal dependency graph, etc.
This is what a raw DAG looks like:
A DAG is quite a natural structure in special relativity: if one takes arbitrary points (events) in flat Minkowski spacetime, these points will always form a DAG, whose arrows indicate the order in which pairs of timelike-separated events occur. Typically, we take the transitive reduction of this DAG as the most intuitive, and visually minimalistic, representation. "Transitive reduction" is a fancy word to say that if we have an arrow from A to B and from B to C, then it is unnecessary to also have an arrow from A to C because it is implicit that if B occurs after A and C after B, then C occurs after A. The non-existence of cycles corresponds to the impossibility to time-travel in flat spacetime.
A spacetime game has a few more features on top of this raw DAG:
First, every non-leaf node in the DAG is labeled with a player: Alice, Bob, ... who makes a decision at that node. Leaf nodes are blank and have no associated player.
Second, every edge is labeled with an action: "cooperate", "defect", X, Y, 0, 1, ...
The labels on the outgoing edges from a given node represent all the possible decisions that the player at that node can make. Below, Alice can decide between 0, 1, or 2.
The labels on the incoming edges to a given node represent preconditions for the decision at that node to take place: for each incoming edge, the player at the source of that edge must have made the decision corresponding to the edge label. If this is the case (as a conjunction, that is, for all incoming edges), the decision is active. Otherwise, the decision is inactive. A decision at a node with no incoming edge is always active. Below, Bob's decision is active if the players playing at the three parent nodes chose 0, 1 and 0 respectively.
Here is an example of game structure with three players:
The rewards
Third, a spacetime game associates rewards (economists call them utility) with every outcome of the game. An outcome of the spacetime game is a possible play, and it corresponds to the subset of leaf nodes that are reached under that play.
In the above game, there are only sixteen possible plays (not all 256 subsets are possible) and each one is associated with a reward for each player. For example, this is a possible reward setup (the rewards are arbitrary and completely orthogonal to the game structure):
1
◉︎◯︎◯︎◯︎◉︎◯︎◯︎◯︎
Alice 1, Bob 2, Alfred (the cat) 33
2
◉︎◯︎◯︎◯︎◯︎◉︎◯︎◯︎
Alice 2, Bob 1, Alfred (the cat) 33
3
◉︎◯︎◯︎◯︎◯︎◯︎◉︎◯︎
Alice 3 Bob 4, Alfred (the cat) 31
4
◉︎◯︎◯︎◯︎◯︎◯︎◯︎◉︎
Alice 4, Bob 3, Alfred (the cat) 36
5
◯︎◉︎◯︎◯︎◉︎◯︎◯︎◯︎
Alice 5, Bob 6, Alfred (the cat) 33
6
◯︎◉︎◯︎◯︎◯︎◉︎◯︎◯︎
Alice 6, Bob 5, Alfred (the cat) 37
7
◯︎◉︎◯︎◯︎◯︎◯︎◉︎◯︎
Alice 7, Bob 8, Alfred (the cat) 39
8
◯︎◉︎◯◯◯︎◯︎◯︎◉︎
Alice 8, Bob 7, Alfred (the cat) 35
9
◯︎◯︎◉︎◯︎◉︎◯︎◯︎◯︎
Alice 9, Bob 2, Alfred (the cat) 32
10
◯︎◯︎◉︎◯︎◯︎◉︎◯︎◯︎
Alice 10, Bob 1, Alfred (the cat) 39
11
◯︎◯︎◉︎◯︎◯︎◯︎◉︎◯︎
Alice 11, Bob 4, Alfred (the cat) 33
12
◯︎◯︎◉︎◯︎◯︎◯︎◯︎◉︎
Alice 12, Bob 3, Alfred (the cat) 31
13
◯︎◯︎◯︎◉︎◉︎◯︎◯︎◯︎
Alice 13, Bob 6, Alfred (the cat) 39
14
◯︎◯︎◯︎◉︎◯︎◉︎◯︎◯︎
Alice 14, Bob 5, Alfred (the cat) 35
15
◯︎◯︎◯︎◉︎◯︎◯︎◉︎◯︎
Alice 15, Bob 7 Alfred (the cat) 34
16
◯︎◯︎◯︎◉︎◯︎◯︎◯︎◉︎
Alice 16, Bob 8, Alfred (the cat) 33
Spacetime games with imperfect information
The gaves shown above are spacetime games with perfect information, because there are no dashed lines between nodes. Each node represents a decision and the player at that node is fully informed about past decisions.
It is also possible for a spacetime game to have imperfect information, and this is similar to what we explained before for games in extensive form. An example is shown below: here there are seven nodes, but they are in four groups. Each group corresponds to one decision, and is called an information set. For example, the cat reasoning on the information set comprising the first and third nodes on the second row, which are connected with a dashed line, is not informed on whether Alice's prior decision was a or c.
This game has twelve possible outcomes, shown below with hypothetical rewards.
1
◉︎◯︎◯︎◯︎◯︎◯︎◉︎◯︎◯︎◯︎◯︎◯︎
Alice 1, Alfred (the cat) 33
2
◯︎◉︎◯︎◯︎◯︎◯◉︎◯︎◯︎◯︎◯︎◯︎
Alice 2, Alfred (the cat) 33
3
◉︎◯︎◯︎◯︎◯︎◯︎◯︎◉︎◯︎◯︎◯︎◯︎
Alice 3 Alfred (the cat) 31
4
◯︎◉︎◯︎◯︎◯︎◯◯︎◉︎◯︎◯︎◯︎◯︎
Alice 4, Alfred (the cat) 36
5
◯︎◯︎◉︎◯︎◯︎◯◯︎◯︎◯︎◯︎◉︎◯︎
Alice 5, Alfred (the cat) 33
6
◯︎◯︎◯︎◉︎◯︎◯◯︎◯︎◯︎◯︎◉︎◯︎
Alice 6, Alfred (the cat) 37
7
◯︎◯︎◉︎◯︎◯︎◯◯︎◯︎◯︎◯︎◯︎◉︎
Alice 7, Alfred (the cat) 39
8
◯︎◯︎◯︎◉︎◯︎◯◯︎◯︎◯︎◯︎◯︎◉︎
Alice 8, Alfred (the cat) 35
9
◯︎◯︎◯︎◯︎◉︎◯◯︎◯︎◉︎◯︎◯︎◯︎
Alice 9, Alfred (the cat) 32
10
◯︎◯︎◯︎◯︎◯◉︎◯︎◯︎◉︎◯︎◯︎◯︎
Alice 10, Alfred (the cat) 39
11
◯︎◯︎◯︎◯︎◉︎◯◯︎◯︎◯︎◉︎◯︎◯︎
Alice 11, Alfred (the cat) 33
12
◯︎◯︎◯︎◯︎◯◉︎◯︎◯︎◯︎◉︎◯︎◯︎
Alice 12, Alfred (the cat) 31
In a spacetime game, imperfect information can be used to model non-contextuality, which is an important feature in the study of the foundations of quantum theory.
Last updated