Strategies

Pure strategies

The pure strategies of a player are maps from all the information sets played by this player to actions available at these information sets. A pure strategy is like a masterplan that a player can design in advance, so that at any possible configuration of the game, the player can read off their strategy what to do next.

Pure strategies are a Nashian concept. In non-Nashian game theory, pure strategies have no meaning as a non-Nashian strategy is the reaction to a particular game outcome (Stackelberg competition against the past) and only assigns actions to those information sets that are actually active.

Let us come back to this example:

We have two players, Alice playing at A and Alfred playing at X, Y, and Z.

Alice's pure strategies are:

Strategy number ↓/ Information set →	A
1	a
2	b
3	c

Alfred's pure strategies are:

Strategy number ↓/ Information set →	X	Y	Z
1	0	0	0
2	0	0	1
3	0	1	0
4	0	1	1
5	1	0	0
6	1	0	1
7	1	1	0
8	1	1	1

Strategy profiles

If every player chooses a pure strategy for themselves, the combination of all players' pure strategies is called a (pure) strategy profile. It assigns an action to every information set in the game.

Strategy profiles are also a Nashian concept. Non-Nashian game theory is by essence contextual, and only assigns actions to information sets that are active in the same history.

These are the strategy profiles in our example:

Alice's strategy	Alfred's strategy	A	X	Y	Z
1	1	a	0	0	0
1	2	a	0	0	1
1	3	a	0	1	0
1	4	a	0	1	1
1	5	a	1	0	0
1	6	a	1	0	1
1	7	a	1	1	0
1	8	a	1	1	1
2	1	b	0	0	0
2	2	b	0	0	1
2	3	b	0	1	0
2	4	b	0	1	1
2	5	b	1	0	0
2	6	b	1	0	1
2	7	b	1	1	0
2	8	b	1	1	1
3	1	c	0	0	0
3	2	c	0	0	1
3	3	c	0	1	0
3	4	c	0	1	1
3	5	c	1	0	0
3	6	c	1	0	1
3	7	c	1	1	0
3	8	c	1	1	1

Given any (pure) strategy profile, exactly one history and outcome is obtained. However, different (pure) strategy profiles can lead to the same history. Below we extend the list of strategy profiles with the histories and outcomes:

Alice's strategy	Alfred's strategy	A	X	Y	Z	History	Outcome
1	1	a	0	0	0	A=a,X=0,Y=0	Outcome 1
1	2	a	0	0	1	A=a,X=0,Y=0	Outcome 1
1	3	a	0	1	0	A=a,X=0,Y=1	Outcome 2
1	4	a	0	1	1	A=a,X=0,Y=1	Outcome 2
1	5	a	1	0	0	A=a,X=1,Y=0	Outcome 3
1	6	a	1	0	1	A=a,X=1,Y=0	Outcome 3
1	7	a	1	1	0	A=a,X=1,Y=1	Outcome 4
1	8	a	1	1	1	A=a,X=1,Y=1	Outcome 4
2	1	b	0	0	0	A=b,X=0,Z=0	Outcome 5
2	2	b	0	0	1	A=b,X=0,Z=1	Outcome 6
2	3	b	0	1	0	A=b,X=1,Z=0	Outcome 7
2	4	b	0	1	1	A=b,X=1,Z=1	Outcome 8
2	5	b	1	0	0	A=b,X=0,Z=0	Outcome 5
2	6	b	1	0	1	A=b,X=0,Z=1	Outcome 6
2	7	b	1	1	0	A=b,X=1,Z=0	Outcome 7
2	8	b	1	1	1	A=b,X=1,Z=1	Outcome 8
3	1	c	0	0	0	A=c,Y=0,Z=0	Outcome 9
3	2	c	0	0	1	A=c,Y=0,Z=1	Outcome 11
3	3	c	0	1	0	A=c,Y=0,Z=0	Outcome 9
3	4	c	0	1	1	A=c,Y=0,Z=1	Outcome 11
3	5	c	1	0	0	A=c,Y=1,Z=0	Outcome 10
3	6	c	1	0	1	A=c,Y=1,Z=1	Outcome 12
3	7	c	1	1	0	A=c,Y=1,Z=0	Outcome 10
3	8	c	1	1	1	A=c,Y=1,Z=1	Outcome 12

It is the same to build the pure strategies, or the (pure) strategy profiles, from the spacetime game or from any of its extensive forms.

Strategic form of a game

Given a spacetime game, or in a game in extensive form, it is possible to arrange the strategy profiles in the matrix of a game in normal form, with the same players and with the strategies being the original pure strategies.

In each cell, the payoffs are those of the outcome of the history induced by the strategy profile. It is however possible for several cells to correspond to the same history and thus to have the same payoffs.

Continuing with our example, we place Alfred's pure strategies on the rows and Alice's strategies on the columns. We put in the cell the number of the outcome based on the previous section.

Alfred ↓/ Alice →	Strategy 1 (A=a)	Strategy 2 (A=b)	Strategy 3 (A=c)
Strategy 1 (X=0,Y=0,Z=0)	Outcome 1	Outcome 5	Outcome 9
Strategy 2 (X=0,Y=0,Z=1)	Outcome 1	Outcome 6	Outcome 11
Strategy 3 (X=0,Y=1,Z=0)	Outcome 2	Outcome 7	Outcome 9
Strategy 4 (X=0,Y=1,Z=1)	Outcome 2	Outcome 8	Outcome 11
Strategy 5 (X=1,Y=0,Z=0)	Outcome 3	Outcome 5	Outcome 10
Strategy 6 (X=1,Y=0,Z=1)	Outcome 3	Outcome 6	Outcome 12
Strategy 7 (X=1,Y=1,Z=0)	Outcome 4	Outcome 7	Outcome 10
Strategy 8 (X=1,Y=1,Z=1)	Outcome 4	Outcome 8	Outcome 12

Imagine, as a thought experiment, if every Chess player had decided in advance what to do for any configuration of the chessboard. Then, at a tournament, every player would bring their pure strategy and one directly reads off the matrix who wins. Of course, the gigantic size of the strategy space makes it unfeasible. And interesting fact: if this were feasible, then there is a theorem of game theory that says that either there is a winning strategy for the white player, or there is a winning strategy for the black player, or there are pat strategies for both players. Tournaments would be more boring than they are today!

Reduced strategic form

Because of the structure of the game, some pure strategies may contain superfluous information. For example, if a player decides in their strategy to play A=a, and B (played by the same player) never gets activated in any history where A=a, then it is superfluous to assign any action to B in the pure strategy as this would not change the outcome of the game no matter what opponents do.

Removing such superfluous assignments is a simplification that is called the reduced strategic form of the game.

The above example cannot be simplified further and is already in its reduced strategy form. We will use another example:

These are Alice's strategies. She plays at A and C:

Strategy number ↓/ Information set →	A	C
1	0	0
2	0	1
3	1	0
4	1	1

And these are Bob's strategies. He plays at B and D:

Strategy number ↓/ Information set →	B	D
1	0	0
2	0	1
3	1	0
4	1	1

This is the strategic form:

Alice / Bob	Strategy 1 (B=0,D=0)	Strategy 2 (B=0,D=1)	Strategy 3 (B=1,D=0)	Strategy 1 (B=1,D=1)
Strategy 1 (A=0,C=0)	Outcome 1 (A=0)	Outcome 1 (A=0)	Outcome 1 (A=0)	Outcome 1 (A=0)
Strategy 2 (A=0,C=1)	Outcome 1 (A=0)	Outcome 1 (A=0)	Outcome 1 (A=0)	Outcome 1 (A=0)
Strategy 3 (A=1,C=0)	Outcome 2 (A=1,B=0)	Outcome 2 (A=1,B=0)	Outcome 3 (A=1,B=1,C=0)	Outcome 3 (A=1,B=1,C=0)
Strategy 4 (A=1,C=1)	Outcome 2 (A=1,B=0)	Outcome 2 (A=1,B=0)	Outcome 4 (A=1,B=1,C=1,D=0)	Outcome 5 (A=1,B=1,C=1,D=1)

A look closer shows that Alice's strategies 1 and 2 are indistinguishable. This is because when A=0, C's value makes no difference because it is never activated. Likewise, Bob's strategies 1 and 2 are indistinguishable. This is because when B=0, D's value makes no difference because it is never activated.

Thus, the strategic form can be reduced to three strategies each:

Alice / Bob	Strategy 1' (B=0)	Strategy 3 (B=1,D=0)	Strategy 4 (B=1,D=1)
Strategy 1' (A=0)	Outcome 1 (A=0)	Outcome 1 (A=0)	Outcome 1 (A=0)
Strategy 3 (A=1,C=0)	Outcome 2 (A=1,B=0)	Outcome 3 (A=1,B=1,C=0)	Outcome 3 (A=1,B=1,C=0)
Strategy 4 (A=1,C=1)	Outcome 2 (A=1,B=0)	Outcome 4 (A=1,B=1,C=1,D=0)	Outcome 5 (A=1,B=1,C=1,D=1)

Mixed strategies

Mixed strategies are probability distributions of pure strategies. For example, with the previous example, a mixed strategy of Alice could be:

Strategy number	Probability	A	C
1'	40%	0
3	10%	1	0
4	50%	1	1

And a mixed strategy of Bob could be:

Strategy number	Probability	B	D
1'	30%	0
3	30%	1	0
4	40%	1	1

Mixed strategies can be combined to give a probability distribution over strategy profiles, and thus, over outcomes and histories.

For example, the two above strategies give the joint probability distribution over the strategy profiles as follows:

Alice / Bob	Strategy 1'	Strategy 3	Strategy 4
Strategy 1'	12%	12%	16%
Strategy 3	3%	3%	4%
Strategy 4	15%	15%	20%

Note that under this scheme, the mixed strategies of the players behave like independent random variables, because the probabilities just multiply. This is a fundamental feature of Nashian game theory: the independence of the choice of strategies embodies free choice. A formulation of free choice commonly found in the quantum foundations literature (e.g., Renner, or Sengupta) is that the choice is statistically independent from anything not in its future light cone. This is exactly the case in a game in normal form: the mixed strategies are not in the future of one another and get chosen separately, spacelike-separated. Thus, the probabilities get multiplied. This bridge between free choice in game theory and free choice in quantum theory is at the core of the deterministic extension theory we are building: it is based on non-Nashian game theory and does not follow this pattern.

We can then infer the probability distribution over the game outcomes obtained with the two chosen mixed strategies, which is a coarse-graining of their joint probability on strategy profiles:

Outcome	Probability	A	B	C	D
1	40% (12+12+16)	0
2	18% (3+15)	1	0
3	7% (3+4)	1	1	0
4	15%	1	1	1	0
5	20%	1	1	1	1