Multiagent Reasoning

Chapter 1: Normal Form Games

The simplest multiagent setting is a normal form game (also called a matrix game). Everything happens in a single step: agents simultaneously choose actions, then each receives a reward that depends on the joint action.

Formally, a normal form game for i = 1, …, n agents has three components:

We write the joint action as a = (a₁, …, a_n) ∈ A₁ × ··· × A_n. Agent i's goal is to maximize U_i(a), but a depends on all agents' choices simultaneously.

Chapter 2: Response Models

To choose optimally, agent i needs a model of what agent j will do. A response model is a distribution π_j over j's actions. Given π_j, agent i can compute its expected utility for each action a_i:

The simplest model: agent j plays uniformly at random. More sophisticated: level-k reasoning. A level-0 agent plays uniformly. A level-1 agent best-responds to level-0 beliefs. A level-k agent best-responds to a level-(k−1) opponent.

Chapter 3: Dominant Strategy Equilibrium

Sometimes one action is simply better than all others, regardless of what opponents do. This is called a dominant strategy, and it gives the most decisive solution concept.

Action a_i strictly dominates action a'_i if, for every possible joint action of the opponents:

A rational agent never plays a strictly dominated action. This gives us a pruning rule: repeatedly eliminate dominated actions from all agents — iterated elimination of dominated strategies (IEDS). Sometimes this fully solves the game in a unique action profile.

Chapter 4: Nash Equilibrium

Most games have no dominant strategy. We need a solution concept for the general case. The most important concept in game theory is the Nash equilibrium, introduced by John Nash in 1950.

A joint strategy profile (π₁*, …, π_n*) is a Nash equilibrium if no agent can improve their expected utility by unilaterally changing their strategy, given that all other agents play their equilibrium strategy:

In words: at a Nash equilibrium, every agent is already playing a best response to what everyone else is doing. There's no incentive for any single agent to deviate. It's a fixed point of mutual best-response.

Chapter 5: Mixed Strategy Nash

Many games have no pure Nash equilibrium. Matching Pennies is the classic: Agent 1 wins if coins match, Agent 2 wins if they differ. Check any pure profile — one agent always wants to deviate. No pure Nash exists.

The resolution: allow randomization. A mixed strategy π_i ∈ Δ(A_i) is a probability distribution over actions. Nash's theorem guarantees at least one Nash equilibrium in mixed strategies for every finite game.

The key insight for finding mixed Nash: if agent i mixes between two actions, those actions must give equal expected utility. Otherwise, i would deviate to the better one. So agent j's equilibrium mixing is chosen to make agent i indifferent:

python
import numpy as np
from itertools import combinations

def find_mixed_nash_2x2(U1, U2):
    """Find all Nash equilibria for 2x2 game.
    U1, U2: 2x2 numpy arrays. Returns list of (pi1, pi2) tuples."""
    m, n = 2, 2
    equilibria = []

    # Check pure Nash (support size 1x1)
    for r in range(m):
        for c in range(n):
            br1 = U1[r,c] == U1[:,c].max()  # agent 1 BR at col c
            br2 = U2[r,c] == U2[r,:].max()  # agent 2 BR at row r
            if br1 and br2:
                pi1 = np.eye(m)[r]; pi2 = np.eye(n)[c]
                equilibria.append((pi1, pi2))

    # Check fully mixed Nash (support size 2x2)
    # Agent 2 mixes so agent 1 is indifferent: U1[0,:] @ pi2 = U1[1,:] @ pi2
    # => (U1[0,0]-U1[1,0])*p + (U1[0,1]-U1[1,1])*(1-p) = 0
    d1 = (U1[0,0] - U1[1,0]) - (U1[0,1] - U1[1,1])
    if abs(d1) > 1e-10:
        p2 = (U1[1,1] - U1[0,1]) / d1  # pi2(action 0)
        d2 = (U2[0,0] - U2[0,1]) - (U2[1,0] - U2[1,1])
        if abs(d2) > 1e-10:
            p1 = (U2[1,1] - U2[1,0]) / d2  # pi1(action 0)
            if 0 <= p1 <= 1 and 0 <= p2 <= 1:
                equilibria.append((np.array([p1, 1-p1]), np.array([p2, 1-p2])))
    return equilibria

Chapter 6: Correlated Equilibrium

Nash equilibrium assumes agents choose strategies independently. But what if a trusted mediator could send private recommendations to each agent? This leads to a broader concept: the correlated equilibrium, introduced by Robert Aumann in 1974.

A correlated equilibrium is a joint distribution σ(a) over action profiles such that, for each agent i and each action a_i in the support, following the recommendation is a best response given that all other agents also follow their (private, unseen) recommendations:

Note: agent i sees only their own recommendation, not the others'. Given this, following it must be rational. This is the obedience constraint.

Chapter 7: SHOWCASE — Learning to Equilibrium

How do agents reach a Nash equilibrium without a central coordinator? Three algorithms dominate the literature: iterated best response (IBR), fictitious play (FP), and gradient ascent (GA). Each takes a different approach to the same goal: finding the fixed point of mutual best-response.

Chapter 8: Gradient Ascent in Games

Gradient ascent treats each agent's strategy as a continuous parameter and updates it in the direction of increasing expected utility. It's the game-theoretic analog of gradient descent in optimization — except there's no single objective.

Agent i with mixed strategy π_i ∈ Δ(A_i) updates via:

The gradient of U_i with respect to π_i(a_i) is simply the expected utility of playing a_i against the current π_−i — i.e., Q_i(a_i, π_−i). So the update concentrates probability mass on high-utility actions.

The proj_Δ operation projects back onto the probability simplex: clamp negatives to 0, then renormalize. This is the only constraint — the parameter is a valid probability distribution.

python
import numpy as np

def gradient_ascent(U1, U2, alpha=0.02, T=500):
    """Gradient ascent for 2-player general-sum game.
    U1, U2: (m x n) payoff matrices.
    Returns list of (pi1, pi2) pairs (the trajectory)."""
    m, n = U1.shape
    pi1 = np.ones(m) / m   # start uniform
    pi2 = np.ones(n) / n

    history = [(pi1.copy(), pi2.copy())]
    for _ in range(T):
        # Gradient: Q_i(a_i, pi_{-i}) for each action a_i
        g1 = U1 @ pi2   # shape (m,): EU of each of agent 1's actions
        g2 = U2.T @ pi1  # shape (n,): EU of each of agent 2's actions

        pi1 = pi1 + alpha * g1
        pi2 = pi2 + alpha * g2

        # Project onto simplex: clip, renormalize
        pi1 = np.maximum(pi1, 1e-10); pi1 /= pi1.sum()
        pi2 = np.maximum(pi2, 1e-10); pi2 /= pi2.sum()
        history.append((pi1.copy(), pi2.copy()))

    return history

def fictitious_play(U1, U2, T=500):
    """Fictitious play: best-respond to empirical opponent frequency."""
    m, n = U1.shape
    counts1 = np.ones(m)   # Laplace smoothing
    counts2 = np.ones(n)
    history = []
    for t in range(T):
        freq1 = counts1 / counts1.sum()
        freq2 = counts2 / counts2.sum()
        # Best responses
        a1 = np.argmax(U1 @ freq2)
        a2 = np.argmax(U2.T @ freq1)
        counts1[a1] += 1
        counts2[a2] += 1
        history.append((freq1.copy(), freq2.copy()))
    return history

Chapter 9: Connections & Beyond

Normal form games are the foundation, but real-world multiagent problems are sequential, partially observable, and involve many agents. The concepts from this chapter extend in several important directions covered next.

"Nash equilibrium is not a prescription for how to play — it is a description of what rational play must look like if it is to be stable against unilateral deviation."
— Paraphrase, Osborne & Rubinstein, A Course in Game Theory (1994)