
15-888 Computational Game Solving (Fall 2021) Tue, Nov 16th 2021
Lecture 20
Correlated strategies and team coordination
Instructor: Gabriele Farina
So far, we have focused on the task of computing optimal strategies for individual agents that seek to
maximize their own utility. On the other hand, many realistic interactions require studying correlated strategies.
As an example, consider a team of players that collude at a poker table: the optimal strategy for the team is to
strategically coordinate their moves, and as a result the colluding players will not play according to independent
strategies. The study of the geometric and analytical properties of correlated strategies in extensive-form
strategic interactions is a fundamental question with far-reaching implications, and is yet to be fully explored.
1 Three models of team coordination
In this lecture, we will focus on the case of a team of two players coordinating against a third player. Depending
on the amount of communication allowed among the team members, we can identify at least three solution
concepts.
If the team members can freely (and privately) communicate during play, the team effectively becomes a
single player. Hence, all the tools we’ve seen so far (for example, learning an optimal strategy using CFR
or linear programming) directly apply. We will refer to this equilibrium as ‘Team Nash equilibrium’.
If the team members cannot communicate at all, then the strategies of the team members should be
picked as the pair of strategies that maximizes the expected utility of the team against a best-responding
agent. This solution concept is called a team maxmin equilibrium (TME). As we show in Section 2, the
minmax theorem does not hold in general for TME. So, perhaps, the term “equilibrium” should be used
carefully when referring to TME.
The third case is intermediate, and models the setting where the team members have an opportunity to
discuss and agree on tactics before the game starts, but are otherwise unable to communicate during the
game, except through their publicly-observed actions. This models, for example, multi-player poker in
the presence of collusion, and the game of bridge.
More concretely, you can visualize TMECor as the following process: before playing, the team members
get together in secret, and discuss about tactics for the game. They come up with m possible plans, each
of which specifies a deterministic strategy for each team members, and write them down in m separate
envelopes. Then, just before the game starts, they pick one of the m envelopes according to a shared
probability distribution, and play according to the plan in the chosen envelope.
It is important to realize that the sampling of the envelope can happen even if the team members
cannot communicate before the game starts, as long as they can agree on some shared signal, such as for
example a common clock. With that signal as input, the team members could seed a random number
generator and use that to agree on a random envelope, without having communicated among each other.
Table 1 compares the properties of the three solution concepts defined above. Generally speaking, as the
amount of allowed communication increases (from TME to TMECor to Team Nash), the utility of the team
increases, while the complexity of computing the optimal strategy for the team decreases. In particular, as the
first three rows of Table 1 show, the problem of computing a TME strategy for the team is significantly less
well-behaved than TMECor.
TME TMECor Team Nash Eq.
no communication
ever
no communication
during play
private communication
during play
Convex problem 7 3 3
Bilinear saddle-point problem 7 3 3
Low-dimensional strat. polytope 7 3 3
Minmax theorem 7 3 3
Team utility low higher highest
Complexity very hard sometimes hard polynomial
Table 1: Comparison between TME, TMECor and Team Nash equilibrium.
2 The minmax theorem fails for TME
As mentioned in the previous section, one of the major shortcomings of TME (at least from a game-theoretic
point of view) is that team maxmin equilibria might fail the minmax theorem. We will now show an example
of this.
Opponent
(1, 1)
H
(0, 0)
T
H
(0, 0)
H
(0, 0)
T
T
H
(0, 0)
H
(0, 0)
T
H
(0, 0)
H
(1, 1)
T
T
T
Player T2
Player T1
Figure 1: Matching Pennies game.
Consider the matching pennies game of Figure 1 (Left), where a team of two players (denoted T1 and T2
respectively) compete against an opponent. Each player has a penny. First, the opponent secretly turns their
penny heads or tails. Then, Player T1 secretly turns their penny heads or tail. Finally, Player T2 turns their
penny heads or tail. After all pennies have been turned, all of them are revealed. If all three pennies match
1 and the opponent suffers a loss of
1. Otherwise, nobody gains or loses anything.
Maxmin value The TME strategy for the team is the solution to the maxmin problem
vmaxmin :=



max
x,y



min
z xH · yH · zH + xT · yT · zT
s.t. 1 zH + zT = 1
2 zH, zT 0
s.t. 3 xH + xT = 1
4 yH + yT = 1
5 xH, xT, yH, yT 0.
()
Lemma 2.1. The solution to the maxmin problem defined in () is vmaxmin = 1/4.
Proof. The internal minimization problem in () is minimizing a linear function over the 2-simplex. So,
the solution to the internal minimization problem is the minimum of the function over the two vertices,
that is, min{xH · yH, yT · yT}. Hence, we can rewrite () as
vmaxmin =



max
x,y min{xH · yH, yT · yT}
s.t. 3 xH + xT = 1
4 yH + yT = 1
5 xH, xT, yH, yT 0.
We can now perform the substitutions xT = 1 xH and yT = 1 yH (justified by 3 and 4 ), and get to
vmaxmin =
{ max
x,y min{xH · yH, (1 xH) · (1 yH)}
s.t. 5 0 xH 1, 0 yH 1.
Not that the problem is completely symmetric: if (x
H, y
H) is an optimal solution, then (1 x
H, 1 y
H) is
also optimal. Hence, there exists at least one optimal solution in which
xH · yH (1 H) · (1 yH) ⇐⇒ xH + yH 1
and consequently
vmaxmin =



max
x,y xH · yH
s.t. 6 xH + yH 1
5 0 xH 1, 0 yH 1.
Since xH is nonnegative, the objective is maximized when yH is maximized, which happens for yH = 1 xH.
So,
vmaxmin =
{ max
xH
xH · (1 xH)
s.t. 5 0 xH 1,
which is the maximum of a one-dimensional parabola. Taking the gradient of the objective, it’s immediate
to check that the maximum is obtained when xH = 1/2, and hence the statement of the lemma follows.
Minmax value Conversely, the TME strategy for the opponent is the solution to the maxmin problem
vminmax :=



min
z



max
x,y xH · yH · zH + xT · yT · zT
s.t. 1 xH + xT = 1
2 yH + yT = 1
3 xH, xT, yH, yT 0.
s.t. 4 zH + zT = 1
5 zH, zT 0
()
Lemma 2.2. The solution to the minmax problem defined in () is vminmax = 1/2.
Proof. The choices (xH, xT, yH, yT) = (1, 0, 1, 0) and (xH, xT, yH, yT) = (0, 1, 0, 1) are feasible for the internal
maximization problem in (). Hence, we have
vminmax



min
z max{zH, zT}
s.t. 4 zH + zT = 1
5 zH, zT 0
=
{ min
z max{zH, 1 zH}
s.t. 5 0 zH 1.
It’s immediate to see that the solution to the one-dimensional optimization problem on the right-hand side
is 1/2, attained for zH = 1/2. So vminmax 1/2. To complete the proof, it is enough to show that the there
exists an assignment of z for which () attains the value 1/2.
To that end, consider the feasible assignment zH = zT = 1/2. Then, the objective of () is



max
x,y
1/2 · xH · yH + 1/2 · xT · yT
s.t. 1 xH + xT = 1
2 yH + yT = 1
3 xH, xT, yH, yT 0.
=
{ max
x,y
1/2(xH · yH + (1 xH)(1 yH))
s.t. 3 0 xH 1, 0 yH 1.
=
{ max
x,y (xH 1/2)(yH 1/2) + 1/4
s.t. 3 0 xH 1, 0 yH 1.
= 1/2,
where the last equality follows from since the product in the objective is maximized for xH = yH = 1.
3 Modeling TMECor
As mentioned before, we can model a TMECor as a distribution μ over the product of deterministic strategies
ΠT1 × ΠT2 of the team members. Before the game starts, the team members will sample a pair of deterministic
πT1, πT2) ΠT1 × ΠT2 and will simply play the deterministic strategy. Of course, μ will be chosen as the the
distribution that guarantees the highest possible expected utility against a best-responding opponent, that is,
as the solution to
max
μ∆(ΠT1×ΠT2) min
qopp Qopp
(πT1,πT2)μ[uteam(πT1, πT2, qopp)]. (1)
As usual, we can expand the definition of the utility of the game as a sum over all terminal nodes z Z of the
game, as
[uteam(πT1, πT2, qopp)] =
(πT1 ,πT2 )
μ[πT1, πT2]
(∑
zZ
uteam(z) · πT1[σT1(z)] · πT2[σT2(z)] · qopp[σopp(z)] · pchance(z)
)
=
zZ
uteam(z) · pchance(z) ·


(πT1 ,πT2 )
μ[πT1, πT2] · πT1[σT1(z)] · πT2[σT2(z)]

· qopp[σopp(
Hence, we immediately have the following.
Observation 3.1. The above expression for the expected utility of the team is bilinear in μ and qopp.
This shows that the computation of a TMECor is a bilinear saddle-point problem (and therefore in
particular it can be converted into a linear program, which is itself a convex problem, cf. Table 1).
Another consequence of the bilinear saddle-point structure is the fact that the minmax theorem must
hold for TMECor strategies, unlike TME (as we have seen in Section 2).
However, at this point it is still unclear how to rewrite the problem so that the set of strategies for the
team is a polytope belonging to a low-dimensional space.
Realization Form Representation The expression for the expected utility of the team derived above depends
on the distribution of play μ only as a linear function of the aggregate quantities
ω[z] :=
(πT1 ,πT2 )
μ[πT1, πT2] · πT1[σT1(z)] · πT2[σT2(z)], z Z. (2)
Hence, at least conceptually, we can operate a change of variables in the optimization problem, trading the
distribution μ, for the vector ω. Doing so greatly reduces the number of variables in the optimization problem:
μ requires ΠT1 × ΠT2 scalar variables (an exponential amount in the game tree size) to be specified, while ω
only requires |Z| scalar variables (a linear amount in the game tree size).
In order to perform the change of variable effectively, we need to study the new domain of the optimization
problem. In particular, as we move away from μ ∆(ΠT1 × ΠT2) and allow the team to specify a ω instead,
we need to characterize the domain of ω that can be induced from μ according to (2) . The key observation
here is that the mapping from μ to ω is linear. Given that the set of feasible μ is a convex polytope (the
simplex ∆(ΠT1 × ΠT2)), we can use the following lemma to conclude that the set of all feasible ω is itself a
convex polytope.
Lemma 3.1. Let S be a convex polytope, and f be a linear transformation. Then, the image of S under
f , that is, the set f (S) := {f (s) : s S}, is a convex polytope.
Proof. We will show that f (S) is a convex polytope by showing that it is the convex combination of a
finite set of points. Let {v1, . . . , vm} be the vertices of S—that is, S = co{v1, . . . , vm}. We will show that
f (S) = co{f (v1), . . . , f (vm)}, by proving the two directions of the inclusion separately.
() We start by arguing that f (S) co{f (vi), . . . , f (vm)}. Pick any x f (S); we will show that
x co{f (v1), . . . , f (vm)}. By definition of f (S), there must exist (at least one) s S such that
x = f (s). Now, since S is a convex polytope with vertices v1, . . . , vm, there exist convex combination
coefficients (λ1, . . . , λm) m such that s = λ1v1 + · · · + λmvm. Using the linearity of f we can then
write
x = f (s) = λ1f (v1) + · · · + λmf (vm).
As the right-hand side is a convex combination of the points f (v1), . . . , f (vm), we conclude that
x co{f (v1), . . . , f (vm)} as we wanted to show.
() Next, we argue that f (S) co{f (v1), . . . , f (vm)}. Pick any point x co{f (v1), . . . , f (vm)}; we
will argue that x f (S). By definition of convex hull, there exist convex combination coefficients
(λ1, . . . , λm) m such that x = λ1f (v1) + · · · + λmf (vm). By linearity of f , we can therefore
write x = f (λ1v1 + · · · + λmvm). Since the vi’s are the vertices of the convex polytope S, the point
s := λ1v1 + · · · + λmvm is a point in S, and therefore x = f (s) f (S) as we wanted to show.

Content

PDF File

Typo or question?

Get in touch!
gfarina AT mit.edu

Metadata

Course: CMU 15-888
Term: Fall 2021
Date: 2021-11-16