M2: Computing Equilibria
Once you understand what equilibria are, the next question is how to find them. We will explore the computational complexity of equilibrium computation (PPAD-completeness), then study practical algorithms such as Lemke–Howson and support enumeration. For LLM agents, this raises a practical question: when an agent's strategy space is too large for exact computation, what approximation guarantees do we have? PA2 implements regret-minimization over repeated interactions with LLM-generated strategies.
Module preview
Once you understand what equilibria are, the next question is how to find them. We will explore the computational complexity of equilibrium computation (PPAD-completeness), then study practical algorithms such as Lemke–Howson and support enumeration. For LLM agents, this raises a practical question: when an agent's strategy space is too large for exact computation, what approximation guarantees do we have? PA2 implements regret-minimization over repeated interactions with LLM-generated strategies.
Lectures and materials
L5: Computing Equilibria I
Support enumeration, Lemke–Howson, and the complexity of Nash equilibrium computation.
L6: Computing Equilibria II
Complexity of Nash equilibrium computation: PPAD-completeness and implications for LLM agents.
Programming assignment
PA2: Learning in Repeated Games · Due October 19 at 11:59 PM CDT