SPOON: Strategy-based Prompt Optimization for Multi-Agent LLM Games

LLM agents can collaborate, negotiate, and compete in multi-agent settings where each player’s success depends on the actions of others. While multi-agent games provide a useful formalization of these settings, improving LLM agents’ performance in these games often relies on reinforcement learning, requiring access to model parameters and costly training across many optimization iterations. To address this, we propose SPOON, a strategy-based prompt optimizer that represents each player’s strategy as explicit rules written in text and refines them without updating model weights. Our strategic abstractions compress many game histories into shared states, allowing one rule update to improve behavior across multiple situations. Explicit strategies enable our method to examine how both players’ rules interact and guide structured best-response search, directly improving each player’s strategy in response to another as they co-evolve across optimization iterations. Across 19 existing benchmarks spanning classical multi-agent games, practical multi-agent applications, and an extension to prompt optimization for single-agent tasks, our method improves optimization efficiency and held-out performance compared with training-based and prompt optimization baselines.