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: Complexity of Equilibrium Computation
PPAD-completeness and the limits of exact algorithms.
L6: Practical Equilibrium Computation
Lemke–Howson, support enumeration, and approximation.
Programming assignment
PA2: Learning in Repeated Games · Due October 19 at 11:59 PM CDT