In the highly competitive world of quantitative finance, landing a coveted position at Jane Street as a Quantitative Trader is no easy feat. Candidates are frequently tested on their mathematical prowess, game theory knowledge, and problem-solving skills. One classic area that often appears in interviews is the analysis and solution of two-player zero-sum games. In this comprehensive guide, we will dive deep into the methods for solving such games, understanding mixed strategies, and computing the value of the game — all skills crucial for both interviews and professional trading.

Jane Street Quantitative Trader Interview Question: Solving Two-Player Zero-Sum Games

Table of Contents

• What is a Two-Player Zero-Sum Game?
• Understanding the Payoff Matrix
• Pure vs. Mixed Strategies
• How to Compute Optimal Mixed Strategies
• Step-by-Step Example: Solving a Two-Player Zero-Sum Game
• Linear Programming Approach
• Python Implementation
• Conclusion

What is a Two-Player Zero-Sum Game?

A two-player zero-sum game is a strategic scenario involving two players where one player's gain is exactly the other player's loss. In other words, the sum of the outcomes for both players is always zero. These games are fundamental in game theory, financial modeling, and are a staple in quantitative trading interviews.

Formally, if Player A and Player B are the two players, and if Player A gains $x$, then Player B loses $x$, so the total sum is zero:

$$ \text{Player A's gain} + \text{Player B's loss} = 0 $$

Real-world examples include poker, certain trading scenarios, and competitive bidding situations.

Understanding the Payoff Matrix

The payoff matrix is the foundation of any two-player zero-sum game. It represents all possible outcomes depending on the choices made by both players.

Let us denote the payoff matrix as $A$, where $a_{ij}$ is the payoff to Player 1 (the row player) when Player 1 chooses row $i$ and Player 2 (the column player) chooses column $j$.

For a game with $m$ strategies for Player 1 and $n$ strategies for Player 2, the payoff matrix $A$ is of size $m \times n$.

Each entry $a_{ij}$ indicates the gain for Player 1 (and loss for Player 2) when the respective strategies are played.

Pure vs. Mixed Strategies

Pure Strategies

A pure strategy is when a player always chooses the same move. For example, always choosing Row 1.

Mixed Strategies

A mixed strategy involves randomly selecting among available options according to a probability distribution. Mixed strategies are crucial when no single pure strategy dominates, allowing players to minimize their maximum possible loss (minimax) or maximize their minimum possible gain (maximin).

If Player 1 uses a mixed strategy $x = (x_1, x_2, ..., x_m)$ where $x_i$ is the probability of choosing Row $i$, and Player 2 uses $y = (y_1, y_2, ..., y_n)$, then the expected payoff to Player 1 is:

$$ \text{Expected Payoff} = x^T A y $$

How to Compute Optimal Mixed Strategies

To solve a two-player zero-sum game, we want to find the optimal mixed strategies for both players and the value of the game (expected payoff under optimal play).

Key Concepts

• Value of the Game ($V$): The expected payoff to Player 1 when both players play optimally.
• Minimax Theorem: In zero-sum games, the maximum of the minimum payoffs equals the minimum of the maximum payoffs:
  $$ \max_x \min_y x^T A y = \min_y \max_x x^T A y = V $$
• Linear Programming: Finding optimal strategies can be formulated and solved as a linear program (LP).

Solving Small Games by Inspection

In some cases, you can solve the game by directly analyzing the matrix (especially $2 \times 2$ matrices). For larger matrices, LP is used.

Step-by-Step Example: Solving a Two-Player Zero-Sum Game

Interview-Style Example Question

Suppose you are given the following payoff matrix:

Find the optimal mixed strategies for both players and the value of the game.

Step 1: Identify Dominant Strategies

Check if either player has a dominant strategy (one which always gives a better outcome, regardless of the opponent’s choice).

For Player 1:

• Row 1: If Col 1 is chosen, payoff is 2. If Col 2 is chosen, payoff is -1.
• Row 2: If Col 1 is chosen, payoff is -3. If Col 2 is chosen, payoff is 4.

There's no row that dominates the other in all columns, so no pure strategy is dominant.

Step 2: Set Up Mixed Strategies

Let Player 1 randomize between Row 1 and Row 2 with probabilities $p$ and $1-p$ respectively. Let Player 2 randomize between Col 1 and Col 2 with probabilities $q$ and $1-q$ respectively.

Player 1's Expected Payoff

The expected payoff to Player 1 if Player 2 chooses Col 1:

$$ E_1 = 2p + (-3)(1-p) = 2p -3 + 3p = 5p - 3 $$

If Player 2 chooses Col 2:

$$ E_2 = (-1)p + 4(1-p) = -p + 4 - 4p = -5p + 4 $$

Player 1's Optimal Strategy

Player 2 will pick the column that minimizes Player 1's expected payoff. Player 1 wants to maximize the minimum expected payoff:

$$ \max_p \min\{5p - 3, -5p + 4\} $$

Set $5p - 3 = -5p + 4$ to find the intersection (where both columns yield the same expected value):

$$ 5p - 3 = -5p + 4 $$ $$ 10p = 7 $$ $$ p = 0.7 $$

So Player 1 should play Row 1 with probability 0.7 and Row 2 with 0.3.

Player 2's Expected Loss

Similarly, for Player 2, suppose they play Col 1 with probability $q$, Col 2 with $1 - q$.

The expected loss for Player 2 (gain for Player 1) when Player 1 chooses Row 1:

$$ E_1 = 2q + (-1)(1-q) = 2q -1 + q = 3q - 1 $$

When Player 1 chooses Row 2:

$$ E_2 = -3q + 4(1 - q) = -3q + 4 - 4q = -7q + 4 $$

Player 2 wants to minimize the maximum expected loss:

$$ \min_q \max\{3q - 1, -7q + 4\} $$

Set $3q - 1 = -7q + 4$:

$$ 3q - 1 = -7q + 4 $$ $$ 10q = 5 $$ $$ q = 0.5 $$

So Player 2 should play Col 1 with probability 0.5 and Col 2 with 0.5.

Step 3: Value of the Game

The value is the expected payoff when both play optimally:

$$ V = 5p - 3 = 5(0.7) - 3 = 3.5 - 3 = 0.5 $$

Or using the other equation:

$$ V = -5p + 4 = -5(0.7) + 4 = -3.5 + 4 = 0.5 $$

So, the value of the game is 0.5.

Summary of the Solution

• Player 1: Play Row 1 with probability 0.7, Row 2 with 0.3.
• Player 2: Play Col 1 and Col 2 with probability 0.5 each.
• Value of the game: 0.5 (Player 1's expected gain, Player 2's expected loss).

Linear Programming Approach

For larger matrices, we use linear programming (LP) to find the optimal mixed strategies.

Formulating the Linear Program

Suppose Player 1 wants to maximize their minimum expected payoff $V$:

Let $x_i$ be the probability of playing Row $i$, for $i=1,...,m$. Player 1's strategy is $x = (x_1, ..., x_m)$, with $x_i \geq 0$ and $\sum x_i = 1$.

We want:

$$ \min_{j} \sum_{i=1}^m a_{ij} x_i \geq V $$

for all $j = 1, ..., n$.

So, the LP for Player 1 is:

Maximize:   V
Subject to: ∑_{i=1}^m a_{ij} x_i ≥ V   for all j = 1,...,n
            ∑_{i=1}^m x_i = 1
            x_i ≥ 0 for all i

Similarly, Player 2's LP is:

Minimize:   W
Subject to: ∑_{j=1}^n a_{ij} y_j ≤ W   for all i = 1,...,m
            ∑_{j=1}^n y_j = 1
            y_j ≥ 0 for all j

Example: Our $2 \times 2$ Matrix

Let's solve for Player 1:

• $2x_1 - 3x_2 \geq V$ (if Col 1 is chosen)
• $-x_1 + 4x_2 \geq V$ (if Col 2 is chosen)
• $x_1 + x_2 = 1$
• $x_1, x_2 \geq 0$

We already solved this above and found $x_1 = 0.7$, $x_2 = 0.3$, $V = 0.5$.

Python Implementation

In practice, especially in interviews or quant roles, you may be asked to implement the solution programmatically. Here’s how you can solve a two-player zero-sum game using Python's scipy.optimize.linprog for Player 1.

import numpy as np
from scipy.optimize import lin```python
import numpy as np
from scipy.optimize import linprog

# Define the payoff matrix for Player 1 (row player)
A = np.array([
    [2, -1],
    [-3, 4]
])

# Since linprog performs minimization, we need to convert the maximization problem.
# We'll solve for Player 1's optimal strategy.

# Number of strategies
num_rows, num_cols = A.shape

# The variables are x_1, x_2, ..., x_m, V (probabilities & value of the game)
# We'll maximize V, but linprog minimizes, so maximize V ↔ minimize -V

# Build the constraints: For each column j: sum_{i} a_{ij} x_i >= V
# Move V to the left: sum_{i} a_{ij} x_i - V >= 0
# Or, -sum_{i} a_{ij} x_i + V <= 0

c = [0]*num_rows + [-1]  # Coefficients for [x_1, x_2, ..., x_m, V]; we minimize -V

A_ub = []
b_ub = []

for j in range(num_cols):
    constraint = [-A[i, j] for i in range(num_rows)] + [1]
    A_ub.append(constraint)
    b_ub.append(0)

# Add the equality constraint: sum x_i = 1
A_eq = [[1]*num_rows + [0]]
b_eq = [1]

# Variable bounds: x_i >= 0, V free (let's bound V for numerical stability)
bounds = [(0, 1)]*num_rows + [(None, None)]

# Solve the linear program
result = linprog(
    c=c,
    A_ub=A_ub,
    b_ub=b_ub,
    A_eq=A_eq,
    b_eq=b_eq,
    bounds=bounds,
    method='highs'
)

if result.success:
    strategy = result.x[:num_rows]
    value = result.x[-1]
    print("Optimal mixed strategy for Player 1 (row player):", strategy)
    print("Value of the game:", value)
else:
    print("Linear program did not converge.")
```

Output:


Optimal mixed strategy for Player 1 (row player): [0.7 0.3]
Value of the game: 0.5



This matches our hand-calculated solution: Player 1 should play Row 1 with probability 0.7 and Row 2 with 0.3, and the value of the game is 0.5.


Generalization for Any Payoff Matrix

The above approach can easily be extended to any two-player zero-sum game. For Player 2, you can transpose the matrix and repeat the process, or derive the dual linear program.




Conclusion

Solving two-player zero-sum games is a core skill for anyone aspiring to be a Jane Street Quantitative Trader or to work in quantitative finance in general. Understanding the concepts of payoff matrices, pure vs. mixed strategies, and the minimax theorem is crucial. For small games, hand calculations suffice; for larger or more complex games, linear programming is the tool of choice.



In summary:

  

    Understand the payoff matrix: Know what each entry means and who benefits.
  
  

    Check for dominant strategies: Simplifies the problem if they exist.
  
  

    Set up mixed strategies: Assign probabilities to each strategy.
  
  

    Apply the minimax theorem: Find the strategy that maximizes your minimum guaranteed payoff.
  
  

    Use linear programming for larger games: Automate the computation of optimal strategies and the value of the game.
  




Mastering these steps will not only help you ace quantitative trading interviews at Jane Street or similar firms, but will also strengthen your analytical and problem-solving skills for real-world trading and beyond.



For further reading, consider exploring advanced topics like Nash equilibria in non-zero-sum games, multi-player games, and repeated game strategies, all of which build on the foundational knowledge of two-player zero-sum games.




Related Resources

  
Wikipedia: Zero-sum game
  
Wikipedia: Minimax
  
scipy.optimize.linprog Documentation
  
MIT OCW: Zero-Sum Games Lecture



Good luck with your Jane Street Quantitative Trader interview!