Enhancing Decision-Making with Large Language Models through Multi-Agent Fictitious Play

Large language model (LLM)-based multi-agent systems (MAS) have demonstrated great potential in solving tasks with execution complexity, by distributing subtasks across cooperative agents. However, this divide-and-conquer paradigm falls short in mixed-motive environments such as negotiation and competitive markets, where we control only one agent and the others pursue their own payoffs. In these environments, the quality of our strategy depends on how the others respond, so the strategies are mutually dependent and leave no independently solvable subtasks to divide. Reasoning over this dependence within a single LLM call unfolds recursive mutual anticipation, which quickly exceeds the model's capability. Inspired by the classic learning dynamic of Fictitious Play, we propose Multi-Agent Fictitious Play (MAFP), a novel MAS paradigm that converts this recursive anticipation into iterative strategy updates. To obtain a policy for a distinguished agent, MAFP instantiates a simulated agent for all agents. At each iteration, every agent generates a new decision that seeks to maximize its expected utility against other agents' past decisions. After several rounds, MAFP synthesizes a policy from the distinguished agent's history for deployment. Throughout the process, each agent only needs first-order reasoning, as it best responds to a fixed pool of observed decisions. We evaluate MAFP on decision-making tasks that require deciding a strategy for competitive scenarios prior to acting. Across scenarios spanning competitive games and negotiation, MAFP outperforms other multi-round baselines, and retains higher payoff when others adapt against it, validating it as an effective MAS framework for decision-making.