Best response polytopes

Motivating Example: Insider Threat Detection¶

A large organization is conducting a red team exercise to test its internal security against potential insider threats.

A simulated Leaker (the row player) chooses among three methods of exfiltrating sensitive data: USB drive, Personal email, or Cloud storage.

The Defender (the column player) allocates monitoring resources to one of three detection strategies: Endpoint Monitoring, Email Filtering, or Cloud Auditing.

A government regulator observes the system and wants to assess whether current security measures are adequate. It is assumed that both players act optimally, i.e., they adopt strategies that correspond to a Nash equilibrium.

The regulator evaluates the system based on the equilibrium probability of a successful breach. If this exceeds a critical threshold, the regulator will mandate additional investment in security.

Let the row player (Leaker) choose among USB, Email, and Cloud, and let the column player (Defender) choose among Endpoint Monitoring, Email Filtering, and Cloud Auditing.

The Leaker’s payoff matrix (probabilities of successful exfiltration) is:

The Defender’s payoff matrix (probabilities of successful detection) is:

Note that the sum of payoffs in any outcome need not equal 1. This reflects the possibility that the attacker fails to exfiltrate and the defender fails to detect the attempt — for instance, if the file transfer crashes mid-way and no alert is triggered.

This point is also important mathematically: the game is not constant-sum and therefore not equivalent to a zero-sum game. It is also strategically rich: each player has three actions, none of which can be removed through simple rationalisation. This chapter introduces efficient methods for computing Nash equilibria in such settings.

Theory¶

Definition: Best Response Polytopes¶

For a two player game $(M_r, M_c)\in{\mathbb{R}^{m\times n}_{>0}}^2$ the row/column player best response polytope $\mathcal{P}_r$/$\mathcal{P}_c$ is defined by:

The polytope $\mathcal{P}_r$, corresponds to the set of points with an upper bound on the utility of those points when considered as row strategies against which the column player plays.

The polytope $\mathcal{Q}_r$, corresponds to the set of points with an upper bound on the utility of those points when considered as column strategies against which the row player plays.

Example: Best Response Polytopes for the threat detection game¶

Let us construct the best response polytopes for the threat detection game.

Applying the definition (3) we have:

This gives:

The vertices of these two polytopes are:

For $\mathcal{P}_r$:

These are shown in Figure 1.

For $\mathcal{P}_c$:

These are shown in Figure 2.

A vertex of a best response polytope corresponds to a strategy through normalization that ensures the sum corresponds to one.

For example $u_6$ corresponds to a strategy:

Similarly for $u_5$:

Definition: Vertex Labelling¶

A vertex labelling is an assignment of labels to each vertex of a best response polytope, where each label corresponds to a constraint that is binding (i.e., holds with equality) at that vertex.

Each defining inequality of a best response polytope has a game theoretic interpretation when it is a binding inequality for a given vertex.

Example: Vertex labelling for the threat detection game¶

Let us consider the inequalities of $P_r$ and interpret what is implied when the inequality is binding:

Similarly for $Q_r$

We have used $\text{\textcircled{1}}$ through $\text{\textcircled{6}}$ as the labels.

Let us label each of the vertices:

For $v_4=(160/91, 135/91, 0)$:

For $\mathcal{P}_r$:

For $\mathcal{P}_c$:

If a label is present in either vertex then either of the following are true::

• it is indicating that an action is not played (for example label 1 in $\mathcal{P}_r$).
• is is indicating that the same action is a best response to the strategy represented by the vector (for example label 1 in $\mathcal{P}_c$).

Looking at $v_5$ and $u_5$ the union of the labels of these vertices gives the full set of vertices.

This leads to the following definition.

Definition: Fully labelled vertex pair¶

A pair of vertices $(x, y) \in \mathcal{P}_r \times \mathcal{P}_C$ is said to be a fully labelled vertex pair if the union of their labels covers all possible labels:

Such a pair, when normalised (so that the components sum to 1), corresponds to a Nash equilibrium.

Example: Fully labelled vertex pair for the threat detection game¶

As shown in Example: Vertex labelling for the threat detection game:

is a fully labelled vertex pair.

This corresponds to the normalised strategies:

and

which is a Nash equilibrium.

Searching through all pairs of vertices is one approach to identifying Nash equilibria although a more efficient approach will now be discussed.

Definition: Lemke-Howson Algorithm¶

For a nondegenerate 2 player game $(M_r, M_c)\in{\mathbb{R}^{m\times n}_{>0}}^2$ the following algorithm returns a Nash equilibrium:

1. Start at the artificial equilibrium: $(0, 0)$
2. Choose a label to drop.
3. Remove this label from the corresponding vertex by traversing an edge of the corresponding polytope to another vertex.
4. The new vertex will now have a duplicate label in the other polytope. Remove this label from the vertex of the other polytope and traverse an edge of that polytope to another vertex.
5. Repeat step 4 until the pair of vertices is fully labelled.

Example: Application of the Lemke–Howson algorithm for the threat detection game with known vertices and labels¶

We will use Figure 1,
Figure 2, as well as
(16) and (17) to move
from vertex to vertex in the threat detection game.

We apply the algorithm as follows:

1. Start at $(v_0, u_0)$ and choose to drop label 1 (an arbitrary choice).
2. Label 1 is not among the labels of $u_0$, so we move from $v_0$ to an adjacent vertex—$v_1$, $v_2$, $v_3$, $v_4$, $v_6$, or $v_7$—that does not carry label 1 but shares other labels with $v_0$. We select $v_1$. This introduces label 6, which must now be dropped in $\mathcal{P}_c$.
3. $(v_1, u_0) \to (v_1, u_2)$: the labels are $\{2, 3, 6\}, \{2, 4, 5\}$. Label 2 must be dropped in $\mathcal{P}_r$.
4. $(v_1, u_2) \to (v_4, u_2)$: the labels are $\{3, 5, 6\}, \{2, 4, 5\}$. Label 5 must be dropped in $\mathcal{P}_c$.
5. $(v_4, u_2) \to (v_4, u_4)$: the labels are $\{3, 5, 6\}, \{2, 3, 4\}$. Label 3 must be dropped in $\mathcal{P}_r$.
6. $(v_4, u_4) \to (v_5, u_4)$: the labels are $\{4, 5, 6\}, \{2, 3, 4\}$. Label 4 must be dropped in $\mathcal{P}_c$.
7. $(v_5, u_4) \to (v_5, u_5)$: the labels are $\{4, 5, 6\}, \{1, 2, 3\}$. This is a fully labelled vertex pair.

After normalisation, this yields the Nash equilibrium computed in
Example: Fully labelled vertex pair for the threat detection game.

This approach, while systematic, is only efficient here because the vertices
have already been computed. In practice, obtaining the vertices of the polytope
can be a time-consuming process. In the next example, we will demonstrate how
the Lemke–Howson algorithm becomes truly efficient through
integer pivoting.

Example: Application of the Lemke-Howson Algorithm for the threat detection game with integer pivoting¶

Using the definition of a tableau the tableaux for a 2 player game $(M_r, M_c)\in{\mathbb{R}^{m\times n}_{>0}}^2$ are given by:

and

In the case of the threat detection game this gives:

and

Let us now reproduce the steps of Example: Application of the Lemke–Howson algorithm for the threat detection game with known vertices and labels: we begin by dropping label 1 which corresponds to the non basic variable 1 of $T_r$. In terms of integer pivoting this is done by pivoting the first column of $T_r$.

As described in Definition: Integer Pivoting we carry out the minimum ratio test:

1. The ratio for the first row: $\frac{7}{1}$
2. The ratio for the second row: $\frac{10}{1}$
3. The ratio for the third row: $\frac{5}{2}$

We pivot on the third row giving:

This tableau has labels/non basic variables $\{2, 3, 6\}$. So we now pivot column 6 in $T_c$. The minimum ratio test:

1. The ratio for the first row: $\frac{9}{5}$
2. The ratio for the second row: $\frac{8}{7}$
3. The ratio for the third row: $\frac{7}{5}$

We pivot on the second row giving:

This tableau has labels $\{2, 4, 5\}$ so we pivot column 2 in $T_r$. The minimum ratio test:

1. The ratio for the first row: $\frac{9/35}{11/105} = 27/11$
2. The ratio for the second row: $\frac{3/10}{91/450} = 135/91$
3. The ratio for the third row: $\frac{5/2}{1/2} = 5/2$

We pivot on the second row giving:

This tableau has labels $\{3, 5, 6\}$ so we pivot column 5 in $T_c$. The minimum ratio test:

1. The ratio for the first row: $\frac{23/72}{127/360} = 115/127$
2. The ratio for the second row: $\frac{8/7}{1} = 8/7$
3. The ratio for the third row: $\frac{9/56}{71/280} = 45/71$

We pivot on the third row giving:

This tableau has labels $\{2, 3, 4\}$ so we pivot column 3 in $T_r$. The minimum ratio test:

1. The ratio for the first row: $\frac{18/875}{4927/283500} = 5832 / 4927$
2. The ratio for the second row: $\frac{135/91}{15/28} = 524/195$
3. The ratio for the third row: $\frac{16/45}{13/180} = 576/65$

We pivot on the first row giving:

This tableau has labels $\{4, 5, 6\}$ so we pivot column 4 in $T_c$. The minimum ratio test:

1. The ratio for the first row: $\frac{7/188}{71/320} = 70/639$
2. The ratio for the second row: $\frac{7/40}{4/5} = 7/32$
3. The ratio for the third row: $\frac{45/71}{-200/71} < 0$

We pivot on the first row giving:

This tableau has labels $\{1, 2, 3\}$ so we have a fully labeled vertex pair.

Setting the non-basic variables to 0 we have the following systems of equations:

and:

Giving: $x = (6580/4927, 4185/4927, 5832/4972)$ and $y = (25/67, 40/67, 28/67)$ which when normalised (20) - (21) gives:

Exercises¶

Exercise: Enumeration of fully labelled vertex pairs¶

For each of the following games, draw the best response polytopes and identify all fully labelled vertex pairs:

1. $ A =
   $$\begin{pmatrix} 3 & -1 \\ 2 & 7 \end{pmatrix}$$

   (35)
   \qquad B =
   $$\begin{pmatrix} -3 & 1 \\ 1 & -6 \end{pmatrix}$$

   (36)
   $
2. $ A =
   $$\begin{pmatrix} 2 & -1 \\ 1 & 3 \end{pmatrix}$$

   (37)
   \qquad B =
   $$\begin{pmatrix} -2 & 2 \\ 1 & -2 \end{pmatrix}$$

   (38)
   $

Exercise: Lemke-Howson algorithm for 2-by-2 games¶

Using the games from Exercise: Enumeration of fully labelled vertex pairs, apply the Lemke–Howson algorithm to compute a Nash equilibrium in each case. Carry out the algorithm twice: once using the known vertex structure, and once using integer pivoting.

Exercise: Coffee shop rivalry¶

In a busy university district, two independent coffee shops compete for customers. Each can choose to:

• Lower prices to attract bargain-seekers,
• Improve quality by investing in better beans and baristas,
• Advertise aggressively through social media and flyers.

Customers respond differently depending on the overall landscape of offers. The three main customer profiles are:

• Students who are price-sensitive,
• Coffee aficionados who value taste,
• Impulse buyers who respond to advertising.

The payoff matrices, based on estimated profits (row player: Café A, column player: Café B), are:

$ M_r =

\qquad M_c =

$

1. Use the Lemke–Howson algorithm to find a Nash equilibrium. Describe how different choices of dropped label may lead to different paths.
2. Interpret the equilibrium in terms of business strategy: What might the equilibrium suggest about the balance between pricing, quality, and advertising?

Exercise: Odd number of equilibria¶

Assume the game is nondegenerate: each vertex of the best response polytopes has exactly the number of labels required to define it, and no label appears more than once across a vertex pair. Also assume that, when applying the Lemke–Howson algorithm, dropping a label from any fully labelled vertex pair always leads to a distinct fully labelled vertex pair.

Under these assumptions, prove that the number of fully labelled vertex pairs — and hence the number of Nash equilibria — is always odd.

Programming¶

Vertex enumeration with Nashpy¶

Nashpy can be used to generate the polytopes and enumerate all pairs of vertices.

import nashpy as nash
import numpy as np


M_r = np.array([
    [3, 1, 2],
    [2, 4, 1],
    [1, 3, 0]
])

M_c = np.array([
    [2, 3, 1],
    [1, 2, 4],
    [5, 1, 3]
])

game = nash.Game(M_r, M_c)
list(game.vertex_enumeration())

Lemke-Howson with Nashpy¶

Nashpy can be used to carry out the Lemke-Howson algorithm, an efficient way to find a Nash equilibrium.

label_to_drop = 0
game.lemke_howson(initial_dropped_label=label_to_drop)

You can also enumerate all possible dropped labels:

list(game.lemke_howson_enumeration())

Vertex enumeration with Gambit¶

Gambit can be used to enumerate all pairs of vertices:

import pygambit as gbt

game = gbt.Game.from_arrays(M_r, M_c)
gbt.nash.enummixed_solve(game)

Lemke-Howson with Gambit¶

Gambit can be used to carry out the Lemke-Howson algorithm:

gbt.nash.lcp_solve(game)

Notable Research¶

The original paper presenting the Lemke–Howson algorithm for two-player games is Lemke & Howson, 1964. That paper also contains a constructive proof that, in nondegenerate games, the number of Nash equilibria is always odd. The algorithm was later extended to $N$-player games in Wilson, 1971, where the oddness result is also generalised. An alternative proof of the oddness theorem is provided in Harsanyi, 1973 the author of which was awarded the Nobel prize with Nash and Selten in 1994.

The worst-case complexity of the Lemke–Howson algorithm is analysed in Savani & Von Stengel, 2004, which demonstrates that the algorithm may require exponential time on specific inputs. Computing Nash equilibria is a computationally challenging task — this intuitive difficulty is formalised in @chen2006settling, Daskalakis et al., 2009, where the problem is shown to be PPAD-complete, placing it in a class of problems believed not to admit polynomial-time solutions.

Conclusion¶

This chapter introduced the geometric and algorithmic structure underlying Nash equilibrium computation through the lens of best response polytopes. By framing strategy sets as polytopes and interpreting labels as binding constraints, we gain powerful visual and computational tools for equilibrium analysis.

The Lemke–Howson algorithm provides a systematic method for tracing paths through these polytopes to identify fully labelled vertex pairs, which correspond to Nash equilibria. Though simple in low dimensions, this method scales to more complex games using tableau-based pivoting techniques such as integer pivoting.

Understanding the polyhedral structure of best responses not only aids in computational efficiency but also provides conceptual clarity: each equilibrium arises from a delicate balance of incentives, visible in the geometry of the feasible region.

Table 1 summarises the key concepts introduced in this chapter.