Paper deep dive

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

Leyang Shen, Yang Zhang, Xiaoyan Zhao, Chun Kai Ling, Tat-Seng Chua

Year: 2026Venue: arXiv preprintArea: cs.CLType: PreprintEmbeddings: 70

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 98%

Last extracted: 6/20/2026, 4:57:47 AM

Summary

The paper introduces Multi-Agent Fictitious Play (MAFP), a novel multi-agent system (MAS) paradigm designed to address 'stance entanglement' in LLM-based decision-making. Unlike traditional MAS that focus on execution complexity through task decomposition, MAFP targets strategic decision-making tasks (like negotiation and competitive games) where stakeholder decisions are mutually dependent. MAFP leverages the game-theoretic principle of fictitious play to transform the recursive mutual-anticipation problem into an iterative process. It uses an aggregation operator to summarize historical policies and a best-response operator to update policies, allowing agents to co-evolve toward a Nash equilibrium. The framework was evaluated across 13 scenarios, demonstrating superior tournament strength and robustness compared to single-round and multi-round baselines.

Entities (8)

Aggregation Operator · operator · 100%Best-Response Operator · operator · 100%Fictitious Play · game-theory-principle · 100%Large Language Model (LLM) · technology · 100%Multi-Agent Fictitious Play (MAFP) · algorithmframework · 100%Multi-Agent System (MAS) · paradigm · 100%Nash Equilibrium · concept · 100%Stance Entanglement · concept · 100%

Relation Signals (5)

Multi-Agent Fictitious Play (MAFP) → addresses → Stance Entanglement

confidence 100% · To address it, we propose Multi-Agent Fictitious Play (MAFP), a novel MAS paradigm that represents stakeholder stances as agents...

Multi-Agent Fictitious Play (MAFP) → isbasedon → Fictitious Play

confidence 100% · Built on the game-theoretic principle of fictitious play, MAFP iteratively updates each agent's decision...

Multi-Agent Fictitious Play (MAFP) → uses → Aggregation Operator

confidence 100% · MAFP introduces two operators: an aggregation operator... and a best-response operator...

Multi-Agent Fictitious Play (MAFP) → uses → Best-Response Operator

confidence 100% · MAFP introduces two operators: an aggregation operator... and a best-response operator...

Multi-Agent Fictitious Play (MAFP) → targets → Large Language Model (LLM)

confidence 90% · Large language model (LLM)-based multi-agent systems (MAS) have demonstrated great potential... To address it, we propose Multi-Agent Fictitious Play (MAFP)...

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract: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 on decision-making tasks that are also prevalent in the real world. These tasks require simultaneous reasoning from the stances of all involved stakeholders whose decisions are mutually dependent and thus cannot be solved in isolation. We characterize this challenge as stance entanglement, a form of decision complexity distinct from execution complexity. To address it, we propose Multi-Agent Fictitious Play (MAFP), a novel MAS paradigm that represents stakeholder stances as agents and formulates decision-making as an equilibrium-seeking process. Built on the game-theoretic principle of fictitious play, MAFP iteratively updates each agent's decision by best responding to the empirical mixture of other agents' past decisions. This enables agents to expose and address one another's weaknesses, progressively improving decision quality and robustness. We evaluate MAFP on challenging decision-making tasks that test the capability of deciding strategies for competitive scenarios prior to acting. MAFP outperforms both single-round and multi-round baselines on two complementary metrics, tournament strength and robustness, demonstrating its effectiveness in addressing stance entanglement.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

69,208 characters extracted from source content.

Expand or collapse full text

Enhancing Decision-Making with Large Language Models through Multi-Agent Fictitious Play Leyang Shen National University of Singapore Singapore lshen@u.nus.edu &Yang Zhang National University of Singapore Singapore zhangy@nus.edu.sg &Xiaoyan Zhao National University of Singapore Singapore xzhao@se.cuhk.edu.hk &Chun Kai Ling National University of Singapore Singapore chunkail@nus.edu.sg &Tat-Seng Chua National University of Singapore Singapore dcscts@nus.edu.sg Corresponding author Abstract 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 on decision-making tasks that are also prevalent in the real world. These tasks require simultaneous reasoning from the stances of all involved stakeholders whose decisions are mutually dependent and thus cannot be solved in isolation. We characterize this challenge as stance entanglement, a form of decision complexity distinct from execution complexity. To address it, we propose Multi-Agent Fictitious Play (MAFP), a novel MAS paradigm that represents stakeholder stances as agents and formulates decision-making as an equilibrium-seeking process. Built on the game-theoretic principle of fictitious play, MAFP iteratively updates each agent’s decision by best responding to the empirical mixture of other agents’ past decisions. This enables agents to expose and address one another’s weaknesses, progressively improving decision quality and robustness. We evaluate MAFP on challenging decision-making tasks that test the capability of deciding strategies for competitive scenarios prior to acting. MAFP outperforms both single-round and multi-round baselines on two complementary metrics, tournament strength and robustness, demonstrating its effectiveness in addressing stance entanglement. 1 Introduction Figure 1: Existing MAS address execution complexity, as in software engineering or research (left), by dividing a task into subtasks across cooperative agents. In contrast, MAFP targets stance entanglement, as in competitive market or strategic games (right), where stakeholders’ decisions are mutually dependent: it decomposes these entangled stances into agents and derives decisions through fictitious play. Large language model (LLM)-based multi-agent systems (MAS) [64, 45] have emerged as a powerful paradigm for solving complex tasks that exceed the capability of a single LLM call [47], with applications in software engineering [12], deep research [56], and scientific discovery [65]. The core of these MAS is divide and conquer [17], where each agent corresponds to a part of the task, accomplishing the task collaboratively. By doing so, MAS reduces the difficulty faced by each individual agent and alleviates the context-window pressure that bottlenecks single-agent reasoning [43], thereby increasing the overall performance. The complexity that existing MAS address is primarily execution complexity: tasks are difficult because their execution requires long reasoning chains [24], broad information coverage [56, 32], or heterogeneous skills [65], thus these burdens can be distributed across cooperative agents, as demonstrated in Fig. 1 (Left). However, many real-world decision-making tasks, like negotiation [5], game [14], and competitive market [3, 61], introduce a different form of complexity, which we call stance entanglement. As shown in Fig. 1 (Right), these tasks are complex because they require simultaneous reasoning from the stances of all stakeholders. The decision of each stakeholder depends on those of others, which in turn depend on it. Thus, different stances are coupled through a mutual-dependence loop and become entangled within a single reasoning trajectory. As the number of stakeholders involved increases, reasoning over entangled stances exceeds the capability of a single LLM call [54, 21]. More importantly, these mutually dependent stances cannot be solved in isolation, resisting standard divide-and-conquer MAS solutions. This motivates us to design a new MAS paradigm for stance disentanglement. To achieve this, we begin by examining what constitutes a good decision. At its core, a good decision maximizes payoff while exhibiting no exploitable weaknesses, meaning that it lies in an equilibrium from which no stakeholder can improve payoff through unilateral deviation. Otherwise, the current decision is suboptimal and either can deviate to obtain a higher payoff or can be exploited when others deviate. This characterization parallels the definition of a Nash equilibrium [37] and motivates us to draw inspiration from how equilibria are solved in game theory. Among methods for equilibrium solving [25, 22, 40], fictitious play [6] offers a solution to disentangle coupled strategic stances: it converts the mutually dependent fixed point solving problem into an iteratively convergent process in which each player simply best responds to the empirical average of others’ past strategies. Moreover, its mechanism is well-suited to LLM-based agents, as it reduces each step to a single-chain prediction that an LLM can naturally produce [21, 34], providing the game-theoretic foundation for our MAS design. Building on this insight, we propose the Multi-Agent Fictitious Play (MAFP) algorithm, which leverages MAS as a simulator and derives decisions through multi-agent co-evolution. Specifically, we decompose stances into agents, each representing a stakeholder. The algorithm proceeds in iterative rounds. Within each round, agents update their decisions by best responding to the empirical mixture of others’ past decisions. By doing so, agents probe one another’s exploitable weaknesses and co-evolve to reduce exploitability and improve payoffs. To realize this in natural-language space, MAFP introduces two operators: an aggregation operator that constructs the empirical mixture of a set of decisions, and a best-response operator that generates a new decision that maximizes utility against others’ decisions. After the final round, the empirical mixture serves as the framework’s output. We evaluate MAFP on decision-making tasks across 13 scenarios, spanning competitive games [14] and negotiation [5]. These tasks require the model to decide the strategy for each scenario before acting by generating an open-ended language policy, a challenging problem due to the vast space of possible strategies. We report two complementary metrics: tournament strength, which measures a method’s average payoff against all candidates being evaluated, and robustness, which captures its worst-case performance against adversaries that actively adapt to exploit it. Experimental results show that MAFP outperforms both single-round and multi-round baselines on both metrics, validating it as a promising MAS framework for decision-making. Our contributions are summarized as follows: • We identify stance entanglement as a new form of complexity lies in real-world decision-making tasks that poses new challenge to the execution complexity addressed by existing MAS. • Inspired by fictitious play from game theory, we propose Multi-Agent Fictitious Play (MAFP), a multi-agent framework that decomposes entangled stances to agents and leverages MAS as a simulator for robust decision finding. • We propose a dual-axis evaluation method for good decisions along two complementary axes: tournament strength and robustness. Experiments across 13 scenarios demonstrate MAFP’s effectiveness. 2 Related Works In this section, we review recent research related to MAFP from two perspectives: how existing LLM-based MAS work and how decision-making tasks are addressed. 2.1 LLM-based Multi-Agent System MAS [30, 26] demonstrates effectiveness on a wide range of complex tasks [56, 12, 35, 50] by having multiple LLM-based agents work collaboratively. These systems target tasks with execution complexity and operate through a divide-and-conquer paradigm. Tasks that demand long execution chains, such as software engineering [12] and deep research [56], are decomposed across role-specialized agents and executed sequentially [38, 20]; those that demand broad information coverage or divergent exploration, such as wide research [32] and multi-agent debate [27], are executed in parallel [13, 46]. Existing research primarily operates within this cooperative paradigm, focusing on how to split and arrange tasks effectively, spanning orchestrator optimization [53, 9, 43] and topology optimization [66, 58, 55]. However, all of these remain within a split-and-aggregate formulation, and fall short on decision-making tasks [14, 7, 3] with interdependent stances. Even multi-agent debate, the line that most directly surfaces competing views, only aggregates independently authored solutions without reducing the reasoning complexity introduced by stance entanglement. In this paper, we address such tasks through multi-agent fictitious play, a new MAS paradigm that decomposes stances into self-interested agents and treats MAS as a simulator for decision finding. 2.2 LLM for Decision Making As LLMs [57, 42, 29] grow more capable, they are increasingly deployed as strategic decision-makers, and a wave of benchmarks evaluates this capability across games [14, 62, 10, 2, 8], negotiation [5, 1, 39], social deduction [18, 4, 28], and competitive market [7, 3, 49, 59]. Existing attempts improve the decision-making capability of LLM through strategic reasoning, performing explicit theory-of-mind [15] (ToM) reasoning at inference time. Their solutions range from one-step perspective-taking on opponents [52, 11], to two-order reasoning that additionally anticipates how others perceive the agent [48], to recursive level-k mutual anticipation that extends ToM to arbitrary depth [63]. What unites these methods is the assumption that an LLM can carry out higher-order belief reasoning within a single inference pass. However, recursive mutual anticipation is a structural weak point of LLMs, which are essentially autoregressive next-token predictors [33, 34]. This limitation is verified empirically by Hi-ToM [54] and FANToM [21], showing that LLM accuracy drops rapidly in higher-order belief reasoning (e.g., “I think that you think”) and exhibits an illusory theory of mind. As the number of stakeholders involved increases in real-world tasks, the breadth and depth of ToM reasoning exceed the capability of a single LLM call. In this work, we propose an MAS solution for decision-making that decomposes stances into agents and derives decisions through multi-agent co-evolution. By doing so, each LLM call reduces to a single-layer logic reasoning, aligning with LLMs’ strengths in conditional prediction. 3 MAFP: Multi-Agent Fictitious Play for Robust Decision Making We propose Multi-Agent Fictitious Play (MAFP), a training-free framework for robust decision making over natural-language policies (Section 3.1). Inspired by fictitious play [6, 36], MAFP addresses the mutual-anticipation dilemma (Section 3.2) with multi-agent co-evolution, in which agents iteratively best respond to each other’s policies and co-evolve toward robust profiles through repeated rounds of update (Section 3.3). We elaborate on the design of MAFP in the following. 3.1 Problem Formulation Decision Making Task. We consider strategic decision-making expressed as a language-policy game. A scenario is specified by a natural-language description D together with a set of stakeholders =1,…,nN=\1,…,n\, where n is the number of stakeholders. Each stakeholder i is characterized by a stance that summarizes its situational profile: ωi=(ri,gi,ci,ρi), _i\;=\;(r_i,\,g_i,\,c_i,\, _i), (1) where the stance ωi _i comprises its role rir_i, goal gig_i, private context and constraints cic_i, and payoff description ρi _i. Each stakeholder i then commits to a textual strategy describing how to take action, which we call a language policy, denoted by πi _i: πi∈Πi, _i\;∈\; _i, (2) where Πi _i is the space of natural-language strategies admissible for stakeholder i. The joint commitment of all stakeholders yields a policy profile, denoted by π: =(π1,…,πn)∈Π=∏i=1nΠi, π\;=\;( _1,…, _n)\;∈\; \;=\; _i=1^n _i, (3) where Π is the joint policy space. Since the utility of a policy profile π inherently depends on the opponents it plays against, we evaluate it in expectation over a reference distribution of opponent profiles. We thus define the utility U()U_P( π) as the expected payoff of π against profiles drawn from a given distribution P. To estimate the utility, each stakeholder’s language policy conditions an identical action model MactM_act that produces actions step by step: ai,t∼Mact(⋅∣st,,ωi,πi),a_i,t\; \;M_act\! (\,· s_t,D, _i, _i\, ), (4) where ai,ta_i,t denotes the action taken by stakeholder i at time step t from state sts_t. The environment manages state transitions according to its own rule-based dynamics, and a full match yields a trajectory τ: τ=(s0,a0,s1,a1,…,sT)∼Env(;)τ=(s_0,a_0,s_1,a_1,…,s_T)\; \;Env\! (D;\, π ) (5) where Env(⋅)Env(·) denotes the environment’s transition dynamics, with each πi _i driving stakeholder i’s actions through MactM_act. From this trajectory, the environment computes a rule-based payoff Ri(τ)R_i(τ) for each stakeholder i. The per-stakeholder utility of policy πi _i against the distribution P is then defined as U(πi)=^∼U(πi,^−i)(πi)=^∼τ∼Env(;πi,^−i)[Ri(τ)],U_P( _i)\;=\;E_ π U_( _i, π_-i)( _i)\;=\;E_ π \;E_τ (D;\, _i, π_-i)\! [R_i(τ) ], (6) where π is a profile sampled from P, ^−i π_-i denotes its components corresponding to stakeholders other than i, and (πi,^−i)( _i, π_-i) is the joint profile in which i plays πi _i while the remaining roles are filled by ^−i π_-i. The overall utility of the policy profile π against P is the average of its per-stakeholder utilities: U()=1n∑i=1nU(πi).U_P( π)\;=\; 1n _i=1^nU_P( _i). (7) Finding Robust Policy is Equilibrium Seeking. In strategic environments, the other stakeholders are themselves goal-driven, and the profile −i π_-i that stakeholder i faces is not fixed: once others observe and infer i’s policy, they adjust toward whatever better serves their own goals. A good policy therefore cannot be obtained by simply maximizing one’s own utility alone; it must also account for the other stakeholders’ goals, staying advantageous even after they deviate toward what better serves them. We formalize this requirement through the notion of unilateral deviation. For a given profile π, the deviation gain available to stakeholder i, denoted by Δi() _i( π), is the utility improvement it can attain by switching to its best alternative policy while the others remain fixed: Δi()=maxπi′∈Πi⁡U(πi′,−i)(πi′)−U(πi,−i)(πi), _i( π)\;=\; _ _i ∈ _iU_( _i , π_-i)( _i )\;-\;U_( _i, π_-i)( _i), (8) where πi′ _i ranges over alternative language policies in Πi _i, and U(πi′,−i)(πi′)=τ∼Env(;πi′,−i)[Ri(τ)]U_( _i , π_-i)( _i )=E_τ (D;\, _i , π_-i)[R_i(τ)] denotes the utility of stakeholder i under the joint profile (πi′,−i)( _i , π_-i); the term U(πi,−i)(πi)U_( _i, π_-i)( _i) is defined analogously. Accordingly, finding a good decision amounts to reaching a profile at which no stakeholder retains any incentive to deviate, i.e., the largest deviation gain equals zero: maxi∈⁡Δi()= 0. _i _i( π)\;=\;0. (9) If Δi()>0 _i( π)>0 for some stakeholder i, then i can improve its utility by deviating to a better policy πi′ _i . More importantly, such a deviation propagates across the profile: under the new profile (πi′,−i)( _i , π_-i), the other stakeholders’ utilities are altered, and their deviation gains Δj _j may also shift. For example, after i switches from πi _i to πi′ _i , some other stakeholder j may see its utility drop while Δj _j simultaneously grows, revealing that πj _j is itself far from optimal and likewise admits further improvement. This mutual interdependence implies that any profile with maxi∈⁡Δi()>0 _i _i( π)>0 is inherently sub-optimal. Conversely, when maxi∈⁡Δi()=0 _i _i( π)=0, no stakeholder can gain by a unilateral deviation; equivalently, π is a Nash equilibrium [37] of the game [31]. Therefore, the task of robust decision making is fundamentally an equilibrium-seeking process. Figure 2: Illustration of MAFP algorithm. Fictitious play in game theory finds equilibrium through an iteratively convergent process in which each player best responds to the empirical average of others’ past actions, here converging to the Nash equilibrium of rock–paper–scissors. Inspired by this, multi-agent fictitious play (MAFP) decomposes stances into agents and finds policies through multi-agent co-evolution: at each round, agents update decisions by best-responding to the empirical mixture of others’ past decisions. 3.2 From Mutual Anticipation to Fictitious Play Mutual Anticipation and Its Recursive Dilemma. Solving an equilibrium is difficult for LLMs because each stakeholder’s optimal policy depends on the others’ policies, which in turn depend on their expectations about us. This mutual anticipation results in a search space explosion: if bib_i denotes the branching factor for each stakeholder and d is the depth of the belief hierarchy, the reasoning tree grows exponentially as (∏i=1nbi)d. ( _i=1^nb_i )^d. (10) Even modest depths make the search intractable, as the policy spaces of language-policy games are vast. We refer this as recursive mutual-anticipation dilemma. Fictitious Play as a Decomposition of the Recursion. Fictitious play [6, 36] in game theory sidesteps this difficulty by spreading the recursion across discrete iterations. As illustrated in Fig. 1, instead of unrolling the belief hierarchy inside a single deliberation, each agent at round t best-responds to the empirical average of opponents’ past policies: πit+1∈arg⁡maxπi∈Πi⁡U(πi,¯−it)(πi),¯−it=(π¯jt)j≠i,π¯jt=Avg(πj0,…,πjt). _i^\,t+1\;∈\; _ _i∈ _iU_( _i,\, π_-i^\,t)( _i), π_-i^\,t\;=\;( π_j^\,t)_j≠ i, π_j^\,t\;=\;Avg( _j^0,…, _j^\,t). (11) where π¯jt π_j^\,t denotes the empirical average of opponent j’s historical policies, and ¯−it π_-i^\,t collects these per-opponent averages into a joint profile. By doing so, the recursive reasoning is replaced by iterative updates. As the iterations proceed, each opponent’s empirical average policy captures how the opponent has adapted to the agent’s previous strategies, so responding to it implicitly accounts for multiple levels of anticipation. This decomposition aligns well with LLMs’ strengths, as each step is a flat reasoning task grounded in observed history. By transforming mutual anticipation into a sequence of best-response updates, fictitious play shifts the problem from “reasoning K levels deep” to “reasoning one level deep, K times”. 3.3 Textual Fictitious Play Based on the principles described above, we now introduce the MAFP algorithm. As illustrated in Fig. 2, MAFP operates entirely in language space through an LLM M: starting from a multi-agent initialization, each round applies an aggregation operator to obtain empirical mixtures and a best-response operator to update policies. After K rounds, MAFP outputs a policy profile that specifies a policy for each stakeholder. Multi-Agent Initialization. Given a decision-making task, MAFP instantiates a multi-agent system in which each agent represents a stakeholder i∈i for fictitious play. Each agent is initialized with a policy πi0 _i^0 and a history set ℋH. The first policy is generated from the scenario description D and the stakeholder’s stance ωi _i, πi0=Minit(,ωi),ℋi0=πi0. _i^0=M_init(D, _i), _i^0=\ _i^0\. (12) Aggregation Operator. At iteration t, each agent best responds based on its belief about how opponents are playing, which is the empirical average of their history (Eq. 11). In language space, we obtain this belief using an aggregation operator AggMAgg_M that prompts LLM to summarize historical policies π¯jt=AggM(ℋjt),∀j∈. π_j^t=Agg_M\! (H_j^t ), ∀\,j . (13) Best-Response Operator. Then, agent i produces a best-response on the obtained empirical-mixture opponent policy set ¯−it=(π¯jt)j≠i π_-i^\,t\;=\;( π_j^\,t)_j≠ i. This is realized through best-response operator BRMBR_M conditioned on the scenario D, the agent’s own stance ωi _i, and the aggregated opponents ¯−it π_-i^t, πit+1=BRM(,ωi,¯−it), _i^t+1=BR_M\! (D,\, _i,\, π_-i^t ), (14) and the result is appended to the history, ℋit+1=ℋit∪πit+1H_i^t+1=H_i^t∪\ _i^t+1\. Final Per-stakeholder Policy. After K rounds, we take the empirical mixture of all policies generated by each agent as its final policy, which captures the adaptations it accumulated in response to every weakness that other agents exploited across the rounds. Concretely, we use the same aggregation operator AggMAgg_M to aggregate each stakeholder’s history into one executable policy: πiout=AggM(ℋiK), _i^out=Agg_M\! (H_i^K ), (15) which is the final policy for stance i. MAFP returns the policy profile with policies for all stances out=(π1out,…,πnout) π^out=( _1^out,\,…,\, _n^out). The full procedure is presented in Algorithm 1. Algorithm 1 Multi-Agent Fictitious Play over Language Policies 0: Scenario D, stances ωii=1n\ _i\_i=1^n, frozen LLM M, iterations K 0: Final policy profile out π^out 1: for each stakeholder i∈i do 2: Initialize πi0=Minit(,ωi) _i^0=M_init(D, _i) and ℋi0=πi0H_i^0=\ _i^0\ 3: end for 4: for t=0t=0 to K−1K-1 do 5: for each stakeholder j∈j in parallel do 6: Aggregate empirical mixture: π¯jt=AggM(ℋjt) π_j^t=Agg_M\! (H_j^t ) 7: end for 8: for each stakeholder i∈i in parallel do 9: Best response against ¯−it=π¯jtj≠i π_-i^t=\ π_j^t\_j≠ i: πit+1=BR^M(,ωi,¯−it) _i^t+1= BR_M\! (D, _i, π_-i^t ) 10: Update history: ℋit+1=ℋit∪πit+1H_i^t+1=H_i^t∪\ _i^t+1\ 11: end for 12: end for 13: for each stakeholder i∈i do 14: πiout=AggM(ℋiK) _i^out=Agg_M\! (H_i^K ) 15: end for 16: return out=(π1out,…,πnout) π^out=( _1^out,…, _n^out) 4 Experiments In this section, we conduct experiments to investigate two research questions: RQ1: How does fictitious play improve the performance compared to existing test-time scaling frameworks? RQ2: How does utility improve as the number of rounds increases? 4.1 Experimental Setup Policy Generation Benchmark. We evaluate MAFP on 13 scenarios spanning two strategic decision-making categories: competitive games [14] and natural-language negotiation [5], representing strategic games with clear rules and language-based real-world tasks. The selected scenarios exhibit diversity in characteristics across dimensions, such as whether it is a zero-sum game, static or dynamic, and whether information is complete, to comprehensively reflect the algorithm’s features. Detailed scenario description can be found in Appendix A.1. To isolate the differences between policy profiles, all of which are executed by Qwen3.5-35B-A3B [57] as the action model ℳactM_act (Eq. 4). To ensure the reliability of the results, we play 1616 matches with seat exchange for each pair, averaging the payoff of each scenario. And the full pipeline is run with 8 random seeds and we report seed-averaged means. Metrics. We evaluate each generated policy profile π along two complementary axes, Tournament Strength and Robustness, both measured by the utility U()U_P( π) of Eq. 7 but instantiated with different opponent distributions P. Notably, the two axes correspond to the two ways a policy can violate the equilibrium criterion of Eq. 9: either a higher-utility deviation still exists for it (so it is not strong enough), or it leaves a weakness that an adapting opponent can exploit (so it is not robust enough). A good policy must rule out both. Tournament Strength (TS) instantiates Eq. 7 with =candP\!=\!P_cand, the empirical distribution over the other competing profiles candP_cand in the experiment. TS is estimated using a round-robin schedule, in which profiles engage in pairwise battles. A policy that is beaten by the field admits a stronger response and thus retains a profitable deviation; higher TS therefore means the policy is closer to optimal against the current candidates. Robustness (Rob) measures the extent to which a target policy retains its utility when other players adapt against it: if an adapting opponent can drive the utility down, the policy leaves exploitable weaknesses. Concretely, we calculate the robustness of a profile Rob()Rob( π) by averaging the robustness of each policy within it Rob()≔1n∑i=1nRob(πi).Rob( π) 1n _i=1^nRob( _i). (16) For each policy πi _i, freeze it and let an attacker LLM evolve a counter-profile −i(R) π_-i^(R) over R=10R\!=\!10 rounds, where each round plays 44 matches against πi _i to gather enough evidence. The evolution is achieved by rewriting the policies within the counter-profile based on the collected evidence to maximize their respective utility. Rob(πi)Rob( _i) is then πi _i’s lowest utility against the evolved profile across R rounds, Rob(πi)≔minr∈[R]⁡U(πi,−i(r))(πi).Rob( _i) _r∈[R]\;U_( _i, π_-i^(r))( _i). (17) 4.2 RQ1: MAFP versus Existing Test-Time Scaling Frameworks Table 1: Comparison Results on Tournament Strength. For each scenario, all 9 methods are evaluated by a round-robin tournament, measuring each method’s average utility against the other 8. “Avg.” denotes the mean utility across the 13 scenarios. Best per column in bold. Method TicTac Nim IPD Conn4 Pig BrkThru KuhnPk BlindAuc LiarDice Negot BuySell Ultimat ResExch Avg. Single Round Q3-1.7B 0.616 0.624 0.548 0.509 0.357 0.734 0.505 0.476 0.243 0.600 0.361 0.382 0.496 0.496 Llama-3.1-8B 0.490 0.456 0.526 0.520 0.508 0.458 0.459 0.399 0.258 0.614 0.331 0.365 0.499 0.452 GPT-5-nano 0.383 0.342 0.443 0.421 0.382 0.390 0.406 0.367 0.351 0.590 0.429 0.466 0.494 0.420 Q3.5-35B 0.458 0.601 0.386 0.559 0.493 0.549 0.493 0.384 0.547 0.593 0.413 0.535 0.495 0.500 Multiple Round with Q3.5-35B SR 0.544 0.458 0.347 0.491 0.455 0.461 0.477 0.362 0.544 0.599 0.505 0.464 0.497 0.477 Debate 0.468 0.578 0.385 0.484 0.535 0.513 0.441 0.506 0.490 0.505 0.552 0.486 0.502 0.496 ToM 0.624 0.494 0.385 0.521 0.479 0.575 0.534 0.611 0.550 0.452 0.573 0.559 0.499 0.527 MAFP-Last 0.477 0.375 0.899 0.428 0.469 0.420 0.505 0.630 0.373 0.299 0.553 0.459 0.498 0.491 MAFP 0.531 0.485 0.500 0.537 0.557 0.542 0.583 0.604 0.551 0.504 0.472 0.549 0.508 0.533 Table 2: Comparison Results on Robustness. For each scenario, methods are evaluated by freezing each as the target and letting an attacker evolve a counter-profile over 10 rounds; robustness is the target’s lowest utility across those rounds. “Avg.” denotes the mean robustness across the 13 scenarios. Best per column in bold. Method TicTac Nim IPD Conn4 Pig BrkThru KuhnPk BlindAuc LiarDice Negot BuySell Ultimat ResExch Avg. Single Round Q3-1.7B 0.232 0.477 0.133 0.406 0.174 0.531 0.305 0.348 0.363 0.496 0.234 0.473 0.500 0.359 Llama-3.1-8B 0.227 0.312 0.018 0.434 0.281 0.203 0.246 0.328 0.402 0.467 0.334 0.354 0.500 0.316 GPT-5-nano 0.164 0.078 0.031 0.320 0.281 0.312 0.219 0.234 0.430 0.443 0.447 0.562 0.500 0.309 Q3.5-35B 0.258 0.297 0.031 0.406 0.340 0.266 0.277 0.328 0.531 0.406 0.385 0.584 0.500 0.355 Multiple Round with Q3.5-35B SR 0.328 0.395 0.000 0.359 0.332 0.234 0.273 0.227 0.484 0.438 0.436 0.516 0.498 0.348 Debate 0.229 0.328 0.023 0.434 0.258 0.297 0.266 0.367 0.516 0.398 0.559 0.549 0.502 0.363 ToM 0.307 0.293 0.000 0.391 0.281 0.359 0.328 0.406 0.516 0.293 0.521 0.602 0.504 0.369 MAFP-Last 0.287 0.344 0.469 0.297 0.268 0.234 0.305 0.500 0.477 0.148 0.527 0.502 0.500 0.374 MAFP 0.336 0.340 0.125 0.410 0.449 0.461 0.324 0.469 0.578 0.393 0.477 0.605 0.508 0.421 To evaluate the effectiveness of MAFP, we compare it against a representative set of test-time scaling frameworks. For single-round baselines, we adopt CoT reasoning with four different LLM backbones varying model families and capacity: Qwen3-1.7B, Llama-3.1-8B-Instruct [16], GPT-5-nano [42], and Qwen3.5-35B-A3B [44]. For multi-round baselines, we take the strongest single-round backbone, Qwen3.5-35B-A3B, as the unified backbone for four multi-round frameworks: self-reflection (SR) [41], debate [27], theory-of-mind [52] (ToM), and our MAFP. Implementation details can be found in Appendix A.3. To investigate the contribution of MAFP’s aggregation step, we additionally design an MAFP-Last variant, an ablation that removes aggregation and best responds to the opponent’s latest policy at each round rather than to the empirical mixture of past iterates. All multi-round baselines use a unified 4-round iteration to ensure fair comparison. Across these 9 methods, we calculate Tournament Strength and Robustness metrics, per-scenario results are summarised in Tables 1 and 2. From the results, MAFP achieves the highest TS (0.5330.533) and the highest Rob (0.4210.421) on average against all other candidates. This validates our main claim that multi-agent co-evolution through fictitious play yields decisions that are both strong and robust. Among the multi-round baselines, SR and Debate, despite introducing iterative updates, fail to achieve meaningful improvements over single-round baselines, confirming that iteration alone cannot resolve the recursive mutual-anticipation dilemma. ToM partially addresses this dilemma by incorporating explicit other-agent reasoning, lifting both metrics above all single-round and non-modeling multi-round baselines. However, it still unfolds within a single chain and does not escape the recursive mutual-anticipation process, leaving it behind MAFP especially on robustness (0.369 vs. 0.421). These results validate MAFP’s core design motivation: producing robust policies by replacing single-chain recursive anticipation with iterative best responses to an empirical mixture of historical policies, which distributes anticipation across rounds rather than unfolds it with single-chain reasoning. The aggregation-removed ablation, MAFP-Last, trails MAFP on both metrics. This confirms that best-responding to the empirical mixture instead of the latest policy drives performance gains, which aligns with the classical fictitious play algorithm. Without aggregation, MAFP-Last ’s greedy reaction to the latest iterate captures only the most recent strategic shift and discards the multiple levels of anticipation inherent in the history. While MAFP achieves the highest TS and Rob averages, it does not exhibit consistent dominance across all 13 scenarios. For example, on TS, MAFP falls short on deterministic games with perfect information, including TicTacToe, Nim, ConnectFour, and Breakthrough, where a strong strategy can be found by local, position-by-position backward induction [23], which single-step CoT can already handle well. In contrast, MAFP excels in scenarios with imperfect information, stochastic transitions, or general-sum payoffs, such as Pig, Kuhn Poker, and Liar’s Dice, where no dominant pure strategy exists and a robust policy must hedge against an entire distribution of other players’ behaviors. Another notable exception is the Iterated Prisoner’s Dilemma (IPD), where MAFP-Last beats MAFP by a large margin on both TS and Rob. This is because Prisoner’s Dilemma is dominance-solvable, where Defect strictly dominates Cooperate. As a result, the last-iterate best response quickly collapses to pure defection, an unexploitable Nash strategy. Overall, MAFP excels in complex scenarios with imperfect information, stochastic transitions, or a non-trivial mixed equilibrium structure, suggesting greater potential for real-world tasks. 4.3 RQ2: Convergence Behaviour Across Iterations Dynamics in Policy Generation. Figure 3: Per-iteration quality of policies produced by each iterative method. For each method, we run an internal tournament among its four iterations and report each iteration’s average utility against the other three. The shaded band shows the standard error of the mean. To answer RQ2, we examine the two iterative processes in our paper: the policy-generation process by which each method produces its final profile, and the robustness-measurement process by which an attacker evolves a counter-profile against a frozen target. We conduct per-iteration evaluations to visualize the dynamics of each. Figure 3 reports the per-iteration quality of the five multi-round methods, computed by an internal round-robin tournament among the four policies produced at iterations 1–4 of the same method. The results show that methods without other agent modeling, such as Debate and SR, struggle to benefit from additional iterations: they improve marginally in the first one or two rounds and then plateau or even regress in later rounds. In contrast, methods that explicitly model other stakeholders—ToM, MAFP, and MAFP-Last—achieve meaningful gains across iterations, demonstrating the effectiveness of iterative refinement when policy updates are grounded in reasoning about other stakeholders. This contrast shows that naively switching from one-shot generation to iterative refinement is insufficient. Notably, MAFP and MAFP-Last achieve significantly larger improvements than ToM, validating their advantage in evolution. Dynamics in Robustness Measurement. Figure 4: Target-profile utility under adversarial evolution during robustness evaluation. Each curve shows a method’s per-iteration utility against an evolving attacker, averaged across scenarios. The star marks each method’s worst-case round. Shaded band shows the standard error of the mean. Figure 4 visualizes how the utility of the profile being evaluated evolves as the attacker is updated round-by-round during robustness evaluation. Across all eight methods, utility decays in the early rounds, confirming our premise that an adaptive adversary can read the target’s exposed behavior from past matches and rewrite its own policy to exploit it. For most methods, the lowest utility occurs in rounds 2-4. Subsequent evolution does not cause further declines and often increases the utility due to overfitting. This means our 10-round budget is enough for most methods to estimate the exploitability. Crucially, MAFP’s utility under exploitation exceeds that of other baselines at nearly every iteration. This persistent gap substantiates our claim: the policy profile generated by MAFP is not merely strong on average but harder to exploit, which is the property that matters most for decision making against strategic adversaries in the real world. 5 Conclusion In this work, we focus on enhancing the decision-making capability of LLMs through MAS. In contrast to the execution complexity that existing MAS are designed for, we identify stance entanglement as a different form of complexity introduced by decision-making. Drawing inspiration from fictitious play in game theory, we propose MAFP, a multi-agent framework that decomposes entangled stances to agents and leverages MAS as a simulator to derive the decision. On a 13-scenario benchmark spanning competitive games and negotiation, MAFP attains the highest scores on both tournament strength and robustness among all evaluated baselines, with its advantage most pronounced in scenarios involving imperfect information, stochastic transitions, or mixed-strategy equilibria—precisely the conditions that characterize real-world strategic interaction. 6 Limitations Two limitations point to natural extensions of MAFP. Experimentally, computational constraints confined our evaluation to the scenarios reported above. Our next step is to scale MAFP to richer real-world settings such as commercial decision-making in competitive market [3, 59]. Such environments involve more stakeholders and more intricate strategic structure. We expect MAFP to demonstrate greater advantages through stances decomposition and fictitious play co-evolution. Theoretically, MAFP rests on a clean game-theoretic formulation that opens room for deeper analysis: the convergence rate of language-space fictitious play to equilibrium, which equilibrium it selects when multiple Nash equilibria coexist [19], and how the iterative trajectory can be actively steered toward a desired equilibrium [60] are all high-impact open research problems we leave to future work. References [1] M. F. A. R. D. T. (FAIR)†, A. Bakhtin, N. Brown, E. Dinan, G. Farina, C. Flaherty, D. Fried, A. Goff, J. Gray, H. Hu, et al. (2022) Human-level play in the game of diplomacy by combining language models with strategic reasoning. Science 378 (6624), p. 1067–1074. Cited by: §2.2. [2] E. Akata, L. Schulz, J. Coda-Forno, S. J. Oh, M. Bethge, and E. Schulz (2025) Playing repeated games with large language models. Nature Human Behaviour 9 (7), p. 1380–1390. Cited by: §2.2. [3] A. Backlund and L. Petersson (2025) Vending-bench: a benchmark for long-term coherence of autonomous agents. arXiv preprint arXiv:2502.15840. Cited by: §1, §2.1, §2.2, §6. [4] S. Bailis, J. Friedhoff, and F. Chen (2024) Werewolf arena: a case study in llm evaluation via social deduction. arXiv preprint arXiv:2407.13943. Cited by: §2.2. [5] F. Bianchi, P. J. Chia, M. Yuksekgonul, J. Tagliabue, D. Jurafsky, and J. Zou (2024) How well can llms negotiate? negotiationarena platform and analysis. In International Conference on Machine Learning, p. 3935–3951. Cited by: §A.1, §1, §1, §2.2, §4.1. [6] G. W. Brown (1951) Iterative solution of games by fictitious play. Act. Anal. Prod Allocation 13 (1), p. 374. Cited by: §1, §3.2, §3. [7] J. Chen, S. Yuan, R. Ye, B. P. Majumder, and K. Richardson (2023) Put your money where your mouth is: evaluating strategic planning and execution of llm agents in an auction arena. arXiv preprint arXiv:2310.05746. Cited by: §2.1, §2.2. [8] J. Chen, X. Hu, S. Liu, S. Huang, W. Tu, Z. He, and L. Wen (2024) Llmarena: assessing capabilities of large language models in dynamic multi-agent environments. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 13055–13077. Cited by: §2.2. [9] W. Chen, Y. Su, J. Zuo, C. Yang, C. Yuan, C. Chan, H. Yu, Y. Lu, Y. Hung, C. Qian, et al. (2024) Agentverse: facilitating multi-agent collaboration and exploring emergent behaviors. In International Conference on Learning Representations, Vol. 2024, p. 20094–20136. Cited by: §2.1. [10] A. Costarelli, M. Allen, R. Hauksson, G. Sodunke, S. Hariharan, C. Cheng, W. Li, J. Clymer, and A. Yadav (2024) Gamebench: evaluating strategic reasoning abilities of llm agents. arXiv preprint arXiv:2406.06613. Cited by: §2.2. [11] L. Cross, V. Xiang, A. Bhatia, D. L. Yamins, and N. Haber (2024) Hypothetical minds: scaffolding theory of mind for multi-agent tasks with large language models. arXiv preprint arXiv:2407.07086. Cited by: §2.2. [12] X. Deng, J. Da, E. Pan, Y. Y. He, C. Ide, K. Garg, N. Lauffer, A. Park, N. Pasari, C. Rane, et al. (2025) Swe-bench pro: can ai agents solve long-horizon software engineering tasks?. arXiv preprint arXiv:2509.16941. Cited by: §1, §2.1. [13] Y. Du, S. Li, A. Torralba, J. B. Tenenbaum, and I. Mordatch (2024) Improving factuality and reasoning in language models through multiagent debate. In Forty-first international conference on machine learning, Cited by: §2.1. [14] J. Duan, R. Zhang, J. Diffenderfer, B. Kailkhura, L. Sun, E. Stengel-Eskin, M. Bansal, T. Chen, and K. Xu (2024) Gtbench: uncovering the strategic reasoning capabilities of llms via game-theoretic evaluations. Advances in Neural Information Processing Systems 37, p. 28219–28253. Cited by: §A.1, Appendix C, §1, §1, §2.1, §2.2, §4.1. [15] C. Frith and U. Frith (2005) Theory of mind. Current biology 15 (17), p. R644–R645. Cited by: §2.2. [16] A. Grattafiori, A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Vaughan, et al. (2024) The llama 3 herd of models. arXiv preprint arXiv:2407.21783. Cited by: §4.2. [17] Z. Gu, X. Zhu, Y. Cai, H. Shen, X. Chen, Q. Wang, J. Li, X. Shi, H. Guo, W. Huang, et al. (2025) Agentgroupchat-v2: divide-and-conquer is what llm-based multi-agent system need. arXiv preprint arXiv:2506.15451. Cited by: §1. [18] J. Guo, B. Yang, P. Yoo, B. Y. Lin, Y. Iwasawa, and Y. Matsuo (2023) Suspicion-agent: playing imperfect information games with theory of mind aware gpt-4. arXiv preprint arXiv:2309.17277. Cited by: §2.2. [19] J. C. Harsanyi and R. Selten (1988) A general theory of equilibrium selection in games. MIT Press Books 1. Cited by: §6. [20] S. Hong, M. Zhuge, J. Chen, X. Zheng, Y. Cheng, J. Wang, C. Zhang, S. Yau, Z. Lin, L. Zhou, et al. (2024) MetaGPT: meta programming for a multi-agent collaborative framework. In International Conference on Learning Representations, Vol. 2024, p. 23247–23275. Cited by: §2.1. [21] H. Kim, M. Sclar, X. Zhou, R. Bras, G. Kim, Y. Choi, and M. Sap (2023) FANToM: a benchmark for stress-testing machine theory of mind in interactions. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, p. 14397–14413. Cited by: §1, §1, §2.2. [22] D. Koller, N. Megiddo, and B. von Stengel (1994) Fast algorithms for finding randomized strategies in game trees. In Symposium on the Theory of Computing, Cited by: §1. [23] H. W. Kuhn (1953) Extensive games and the problem of information. Contributions to the Theory of Games 2 (28), p. 193–216. Cited by: §4.2. [24] B. Lei, Y. Zhang, S. Zuo, A. Payani, and C. Ding (2024) Macm: utilizing a multi-agent system for condition mining in solving complex mathematical problems. Advances in Neural Information Processing Systems 37, p. 53418–53437. Cited by: §1. [25] C. E. Lemke and Jr. J. T. Howson (1964) Equilibrium points of bimatrix games. Journal of The Society for Industrial and Applied Mathematics 12, p. 413–423. Cited by: §1. [26] G. Li, H. Hammoud, H. Itani, D. Khizbullin, and B. Ghanem (2023) Camel: communicative agents for" mind" exploration of large language model society. Advances in neural information processing systems 36, p. 51991–52008. Cited by: §2.1. [27] T. Liang, Z. He, W. Jiao, X. Wang, Y. Wang, R. Wang, Y. Yang, S. Shi, and Z. Tu (2024) Encouraging divergent thinking in large language models through multi-agent debate. In Proceedings of the 2024 conference on empirical methods in natural language processing, p. 17889–17904. Cited by: 2nd item, §2.1, §4.2. [28] J. Light, M. Cai, S. Shen, and Z. Hu (2023) Avalonbench: evaluating llms playing the game of avalon. arXiv preprint arXiv:2310.05036. Cited by: §2.2. [29] X. Liu, X. Xia, W. Zhao, M. Zhang, X. Yu, X. Su, S. Yang, S. Ng, and T. Chua (2026) L-mtp: leap multi-token prediction beyond adjacent context for large language models. Advances in Neural Information Processing Systems 38, p. 102569–102600. Cited by: §2.2. [30] Z. Liu, Y. Zhang, P. Li, Y. Liu, and D. Yang (2024) A dynamic llm-powered agent network for task-oriented agent collaboration. In First Conference on Language Modeling, Cited by: §2.1. [31] E. Lockhart, M. Lanctot, J. Pérolat, J. Lespiau, D. Morrill, F. Timbers, and K. Tuyls (2019) Computing approximate equilibria in sequential adversarial games by exploitability descent. arXiv preprint arXiv:1903.05614. Cited by: §3.1. [32] Manus (2025) Introducing wide research. External Links: Link Cited by: §1, §2.1. [33] R. T. McCoy, S. Yao, D. Friedman, M. D. Hardy, and T. L. Griffiths (2024) Embers of autoregression show how large language models are shaped by the problem they are trained to solve. Proceedings of the National Academy of Sciences 121 (41), p. e2322420121. Cited by: §2.2. [34] R. T. McCoy, S. Yao, D. Friedman, M. D. Hardy, and T. L. Griffiths (2024) When a language model is optimized for reasoning, does it still show embers of autoregression? an analysis of openai o1. arXiv preprint arXiv:2410.01792. Cited by: §1, §2.2. [35] M. A. Merrill, A. G. Shaw, N. Carlini, B. Li, H. Raj, I. Bercovich, L. Shi, J. H. Shin, T. Walshe, E. K. Buchanan, J. Shen, G. Ye, H. Lin, J. Poulos, M. Wang, M. Nezhurina, J. Jitsev, D. Lu, O. M. Mastromichalakis, Z. Xu, Z. Chen, Y. Liu, R. Zhang, L. L. Chen, A. Kashyap, J. Uslu, J. Li, J. Wu, M. Yan, S. Bian, V. Sharma, K. Sun, S. Dillmann, A. Anand, A. Lanpouthakoun, B. Koopah, C. Hu, E. K. Guha, G. H. S. Dreiman, J. Zhu, K. Krauth, L. Zhong, N. Muennighoff, R. K. Amanfu, S. Tan, S. Pimpalgaonkar, T. Aggarwal, X. Lin, X. Lan, X. Zhao, Y. Liang, Y. Wang, Z. Wang, C. Zhou, D. Heineman, H. Liu, H. Trivedi, J. Yang, J. Lin, M. Shetty, M. Yang, N. Omi, N. Raoof, S. Li, T. Y. Zhuo, W. Lin, Y. Dai, Y. Wang, W. Chai, S. Zhou, D. Wahdany, Z. She, J. Hu, Z. Dong, Y. Zhu, S. Cui, A. Saiyed, A. Kolbeinsson, J. Hu, C. Rytting, R. Marten, Y. Wang, A. G. Dimakis, A. Konwinski, and L. Schmidt (2026) Terminal-bench: benchmarking agents on hard, realistic tasks in command line interfaces. arXiv preprint arXiv:2601.11868. Cited by: §2.1. [36] D. Monderer and L. S. Shapley (1996) Fictitious play property for games with identical interests. Journal of economic theory 68 (1), p. 258–265. Cited by: §3.2, §3. [37] J. Nash (1951) Non-cooperative games. ANNALS OF MATHEMATICS 54 (2). Cited by: §1, §3.1. [38] C. Qian, W. Liu, H. Liu, N. Chen, Y. Dang, J. Li, C. Yang, W. Chen, Y. Su, X. Cong, et al. (2024) Chatdev: communicative agents for software development. In Proceedings of the 62nd annual meeting of the association for computational linguistics (volume 1: Long papers), p. 15174–15186. Cited by: §2.1. [39] J. Rivera, G. Mukobi, A. Reuel, M. Lamparth, C. Smith, and J. Schneider (2024) Escalation risks from language models in military and diplomatic decision-making. In Proceedings of the 2024 ACM conference on fairness, accountability, and transparency, p. 836–898. Cited by: §2.2. [40] T. Sandholm, A. Gilpin, and V. Conitzer (2005) Mixed-integer programming methods for finding nash equilibria. In AAAI Conference on Artificial Intelligence, Cited by: §1. [41] N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao (2023) Reflexion: language agents with verbal reinforcement learning. Advances in neural information processing systems 36, p. 8634–8652. Cited by: 1st item, §4.2. [42] A. Singh, A. Fry, A. Perelman, A. Tart, A. Ganesh, A. El-Kishky, A. McLaughlin, A. Low, A. Ostrow, A. Ananthram, et al. (2025) Openai gpt-5 system card. arXiv preprint arXiv:2601.03267. Cited by: §2.2, §4.2. [43] K. Team, T. Bai, Y. Bai, Y. Bao, S. Cai, Y. Cao, Y. Charles, H. Che, C. Chen, G. Chen, et al. (2026) Kimi k2. 5: visual agentic intelligence. arXiv preprint arXiv:2602.02276. Cited by: §1, §2.1. [44] Q. Team (2026-02) Qwen3.5: accelerating productivity with native multimodal agents. External Links: Link Cited by: §4.2. [45] K. Tran, D. Dao, M. Nguyen, Q. Pham, B. O’Sullivan, and H. D. Nguyen (2025) Multi-agent collaboration mechanisms: a survey of llms. arXiv preprint arXiv:2501.06322. Cited by: §1. [46] J. Wang, J. Wang, B. Athiwaratkun, C. Zhang, and J. Y. Zou (2025) Mixture-of-agents enhances large language model capabilities. In International Conference on Learning Representations, Vol. 2025, p. 33944–33963. Cited by: §2.1. [47] L. Wang, C. Ma, X. Feng, Z. Zhang, H. Yang, J. Zhang, Z. Chen, J. Tang, X. Chen, Y. Lin, et al. (2024) A survey on large language model based autonomous agents. Frontiers of Computer Science 18 (6), p. 186345. Cited by: §1. [48] S. Wang, C. Liu, Z. Zheng, S. Qi, S. Chen, Q. Yang, A. Zhao, C. Wang, S. Song, and G. Huang (2024) Boosting llm agents with recursive contemplation for effective deception handling. In Findings of the Association for Computational Linguistics: ACL 2024, p. 9909–9953. Cited by: §2.2. [49] Z. Wang and J. Zhang (2025) From bits to boardrooms: a cutting-edge multi-agent llm framework for business excellence. arXiv preprint arXiv:2508.15447. Cited by: §2.2. [50] J. Wei, Z. Sun, S. Papay, S. McKinney, J. Han, I. Fulford, H. W. Chung, A. Passos, W. Fedus, and A. Glaese (2025) BrowseComp: a simple yet challenging benchmark for browsing agents. arXiv preprint arXiv: 2504.12516. Cited by: §2.1. [51] J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou, et al. (2022) Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems 35, p. 24824–24837. Cited by: §A.3. [52] A. Wilf, S. Lee, P. P. Liang, and L. Morency (2024) Think twice: perspective-taking improves large language models’ theory-of-mind capabilities. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 8292–8308. Cited by: §2.2, §4.2. [53] Q. Wu, G. Bansal, J. Zhang, Y. Wu, B. Li, E. Zhu, L. Jiang, X. Zhang, S. Zhang, J. Liu, et al. (2024) Autogen: enabling next-gen llm applications via multi-agent conversations. In First conference on language modeling, Cited by: §2.1. [54] Y. Wu, Y. He, Y. Jia, R. Mihalcea, Y. Chen, and N. Deng (2023) Hi-tom: a benchmark for evaluating higher-order theory of mind reasoning in large language models. In Findings of the Association for Computational Linguistics: EMNLP 2023, p. 10691–10706. Cited by: §1, §2.2. [55] C. Xu, Y. Hu, R. Wang, X. Lin, W. Wang, D. Liu, and F. Feng (2026) TacoMAS: test-time co-evolution of topology and capability in llm-based multi-agent systems. arXiv preprint arXiv:2605.09539. Cited by: §2.1. [56] R. Xu and J. Peng (2025) A comprehensive survey of deep research: systems, methodologies, and applications. arXiv preprint arXiv:2506.12594. Cited by: §1, §1, §2.1. [57] A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, et al. (2025) Qwen3 technical report. arXiv preprint arXiv:2505.09388. Cited by: §2.2, §4.1. [58] Y. Yang, H. Chai, S. Shao, Y. Song, S. Qi, R. Rui, and W. Zhang (2026) Agentnet: decentralized evolutionary coordination for llm-based multi-agent systems. Advances in Neural Information Processing Systems 38, p. 107309–107336. Cited by: §2.1. [59] J. Yun, H. J. Lee, and I. Jeon (2025) QuantEvolve: automating quantitative strategy discovery through multi-agent evolutionary framework. arXiv preprint arXiv:2510.18569. Cited by: §2.2, §6. [60] B. H. Zhang, G. Farina, I. Anagnostides, F. Cacciamani, S. M. McAleer, A. A. Haupt, A. Celli, N. Gatti, V. Conitzer, and T. Sandholm (2023) Steering no-regret learners to a desired equilibrium. arXiv preprint arXiv:2306.05221. Cited by: §6. [61] L. Zhang, J. Wang, J. Wu, and Z. Zhang (2026) RetailBench: evaluating long-horizon autonomous decision-making and strategy stability of llm agents in realistic retail environments. arXiv preprint arXiv:2603.16453. Cited by: §1. [62] Y. Zhang, S. Mao, T. Ge, X. Wang, A. de Wynter, Y. Xia, W. Wu, T. Song, M. Lan, and F. Wei (2024) Llm as a mastermind: a survey of strategic reasoning with large language models. arXiv preprint arXiv:2404.01230. Cited by: §2.2. [63] Y. Zhang, S. Mao, T. Ge, X. Wang, Y. Xia, M. Lan, and F. Wei (2025) K-level reasoning: establishing higher order beliefs in large language models for strategic reasoning. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), p. 7212–7234. Cited by: 3rd item, 3rd item, §2.2. [64] Y. Zhang, R. Sun, Y. Chen, T. Pfister, R. Zhang, and S. Ö. Arık (2024) Chain of agents: large language models collaborating on long-context tasks. Advances in Neural Information Processing Systems 37, p. 132208–132237. Cited by: §1. [65] W. Zhao, C. Wu, Y. Fan, P. Qiu, X. Zhang, Y. Sun, X. Zhou, S. Zhang, Y. Peng, Y. Wang, et al. (2026) An agentic system for rare disease diagnosis with traceable reasoning. Nature, p. 1–10. Cited by: §1, §1. [66] M. Zhuge, W. Wang, L. Kirsch, F. Faccio, D. Khizbullin, and J. Schmidhuber (2024) Gptswarm: language agents as optimizable graphs. In Forty-first International Conference on Machine Learning, Cited by: §2.1. Appendix A Implementation Details A.1 Scenarios We evaluate MAFP across 13 scenarios, comprising 10 strategic games from GTBench [14] and 3 negotiation settings from Negotiation Arena [5]. These scenarios span a broad range of game-theoretic properties to comprehensively reflect the behavior of MAFP across different conditions. They include complete versus incomplete information, deterministic versus probabilistic dynamics, and zero-sum versus general-sum payoffs. We provide a per-scenario description of their rules and characteristics in Table 3. Notably, our task is formulated differently from GTBench and Negotiation Arena, which treat the system being tested as the policy, prompting it to select an action at each step. Instead, we test the capability to generate policies: the tested system produces a natural-language policy specifying how to act before the game begins. Table 3: Scenarios Description. Scenario Description Strategic Games TicTacToe A two-player game on a 3×33× 3 grid; players alternate marking squares, and the first to align three marks horizontally, vertically, or diagonally wins. Connect Four Players alternately drop tokens into a 6×76× 7 vertically suspended grid; the first to form a line of four wins. Breakthrough An abstract strategy game played on a 3×83× 8 board; pieces move one space straight or diagonally forward and may capture diagonally. The first player to reach the opponent’s home row wins. Nim Players alternately remove matches from one of four piles (initial sizes 1,3,5,71,3,5,7); a player must remove at least one match from a single pile, and the player forced to take the last match loses. Iterated Prisoner’s Dilemma (IPD) Two players repeatedly choose between Silent and Testify; per-round payoffs follow the classic Prisoner’s Dilemma matrix and accumulate over rounds. Pig A turn-based dice game in which a player repeatedly rolls a single die, accumulating points until they choose to stop or roll a 11 (losing the turn’s gains); the first to reach the target score wins. Kuhn Poker A two-player imperfect-information poker variant with a three-card deck (King, Queen, Jack); players alternately Bet or Pass, and the showdown awards the pot to the higher card. Blind Auction Players simultaneously submit sealed bids for an item with private valuations; the higher bidder wins and pays their bid. Liar’s Dice A two-player game with private dice; players alternately bid increasing quantity-or-value combinations, or challenge the previous bid. The losing side of a challenge loses a die. Negotiation Two players divide a pool of three item types with private value vectors, alternating between proposal turns and utterance turns; payoff is the total value of items each player ultimately receives. Negotiations BuySell A buyer with a private valuation and a seller with a private cost negotiate the price of a single item over multiple rounds; per-player surplus is the gap between the agreed price and the respective private value, with rejection zeroing both players. Ultimatum A proposer offers a split of a fixed pot, and a responder either accepts (both receive the proposed shares) or rejects (both receive zero). Resource Exchange. Two players hold different bundles of resources with asymmetric private values and negotiate trades over multiple rounds to maximize their own utility. A.2 Payoff Definition All 13 scenarios are reduced to a single chess-style outcome o∈0,0.5,1o∈\0,0.5,1\ per match (seat-0’s score; seat-11’s is 1−o1-o), so that the reported win-rate is the simple mean of o across matches. The reduction is identical for all scenarios within two structural groups, plus a universal illegal-move override. Whenever a player emits a parse-failure or rule-illegal action, that player forfeits and the match is recorded as a loss for them, irrespective of any in-game scoring (o=0o=0 if seat 0 forfeits, o=1o=1 if seat 11 does). This rule dominates every other rule below. The 10 strategic game scenarios each emit a canonical winner field w∈P0,P1,⊥w∈\P_0,P_1, \, where ⊥ denotes “no winner” (board filled without a line, equal cumulative scores, or turn-limit reached without resolution, depending on the game). The outcome is o= 1[w=P0]+12 1[w=⊥].o\;=\;1[w=P_0]+ 12\,1[w= ]. (18) The internal mechanism that produces w varies between sub-groups but the conversion to o does not. Board-completion games (TicTacToe, Connect Four, Breakthrough, Nim) decide w from a terminal board pattern, with ⊥ reachable when the board fills without one. Score-aggregation games (IPD, Pig, Kuhn Poker, Blind Auction, Liar’s Dice, Negotiation) decide w by comparing accumulated scores at game end—cumulative IPD payoff, points-to-target for Pig, pot size for Kuhn Poker, value-minus-bid difference for Blind Auction, last-with-chips for Liar’s Dice, and value totals from accepted deals for Negotiation—with ⊥ reached when totals tie exactly. For consistency across scenarios, we reduce the continuous payoffs of the 3 Negotiation Arena scenarios to discrete win/loss/draw outcomes by comparing the relative magnitudes of the two players’ payoffs. Concretely, these scenarios each produce continuous per-player payoffs (p0,p1)(p_0,p_1), namely the value retained after the deal, with rejection zeroing both players. We collapse to the same discrete outcome via the sign-of-difference: o= 1[p0−p1>ε]+12 1[|p0−p1|≤ε],ε=10−6.o\;=\;1[p_0-p_1> ]+ 12\,1[ p_0-p_1 ≤ ], =10^-6. (19) A.3 Baselines We compare MAFP against seven baselines drawn from two families: four single-round Chain-of-Thought policy authors that differ only in the authoring model, and three multi-round language-policy generators that share the same Qwen3.5-35B-A3B authoring backbone but differ in their frameworks. Single-round baselines. Each baseline in this family follows the rules-only Chain-of-Thought prompt of Wei et al. [51]: the model receives the game’s rules and a seat assignment (first or second player) and is asked to write a structured policy organized into labeled sections (Opening Principles, Midgame Priorities, Endgame / Closing Rules, Tactical Checks). One LLM call is issued per seat, and the two-seat outputs are bundled into a single per-scenario policy. Multi-round baselines. The three multi-round baselines all use Qwen3.5-35B-A3B as the backbone and run for K=4K=4 rounds, matching the depth used by MAFP. They differ in what each round consumes as input: • SR (Self-Reflection). We follow Shinn et al. [41] to implement verbal self-critique at the policy level. At each round k≥2k≥ 2, each seat is shown only its own previous (round-k−1k-1) policy and is asked to critique and refine it; no opponent policy and no game trace is introduced. • Debate. We follow Liang et al. [27] to implement multi-agent debate. In round 1, N=2N=2 author agents independently propose a policy profile from rules. In rounds k=2,…,Kk=2,…,K, each agent refines its profile after seeing the other agent’s previous profile. After round K, a judge LLM calls aggregates the N final profiles into a single consensus profile. • ToM (K-level reasoning). We follow Zhang et al. [63] to adapt their recursive K-level reasoning framework from per-step action selection to upfront policy authoring. The recursion is structured as a depth-K call stack rather than a K-round outer loop: KReason(k)=LLM(rules)k=1,LLM(rules,KReason(k−1))k>1. KReason(k)\;=\; casesLLM(rules)&k=1,\\ LLM\! (rules,\; KReason(k-1) )&k>1. cases (20) At each level k, both seats’ policies are jointly authored in a single LLM call conditioned on the level-(k−1)(k-1) profile: the level-k first-seat policy is the best response to th level-(k−1)(k-1) second-seat policy, and the level-k second-seat policy is the best response to the level-(k−1)(k-1) first-seat policy. The recursion bottoms out at k=1k=1 with a rules-only naive profile, mirroring Algorithm 1 of Zhang et al. [63] with the recursive unit replaced from a predicted action to a written policy profile for the policy generation tasks. For every baseline, generation runs over the same eight seeds, the same 13 scenarios, and the same structured policy style prompt, so all rows in the comparison share an identical evaluation protocol. A.4 Computational Resource The experiments are conducted on a single node with 2 × NVIDIA A100 (80GB) GPUs. The total computational cost is approximately 300 A100 GPU hours. Appendix B Additional Results Here we report the error bars of the main tables in Table 4 and visualize them in Fig. 5. The results show that MAFP performs comparably to ToM on Tournament Strength while clearly surpassing all other baselines, and exhibits a pronounced advantage over every baseline on Robustness, confirming the statistical significance of our experimental conclusions. Figure 5: Per-method results with error bars visualization. Table 4: Per-method results with error bars (mean ± SEM). Method TS Rob Single Round Q3-1.7B 0.496±0.0080.496± 0.008 0.359±0.0130.359± 0.013 Llama-3.1-8B 0.452±0.0130.452± 0.013 0.316±0.0150.316± 0.015 GPT-5-nano 0.420±0.0130.420± 0.013 0.309±0.0140.309± 0.014 Q3.5-35B 0.500±0.0150.500± 0.015 0.355±0.0150.355± 0.015 Multiple Rounds with Q3.5-35B SR 0.477±0.0120.477± 0.012 0.348±0.0170.348± 0.017 Debate 0.496±0.0180.496± 0.018 0.363±0.0150.363± 0.015 ToM 0.527±0.0070.527± 0.007 0.369±0.0140.369± 0.014 MAFP-Last 0.491±0.0130.491± 0.013 0.374±0.0140.374± 0.014 MAFP 0.533±0.0080.533± 0.008 0.421±0.0180.421± 0.018 Appendix C Prompt Templates We present the prompt templates for the three LLM-based components of our pipeline in Figs. 6, 7, and 8. The aggregation operator AggMAgg_M aggregates a player’s past policies into a single policy that approximates the empirical mixture over the pool. The best-response operator BRMBR_M authors a policy that maximizes expected win-rate against this averaged opponent. For the action operator MactM_act, we uses GTBench’s prompt_agent template [14] and appends the learned policy to the user message. System prompt System Role: You are a strategy summariser. Given K past policies authored by one player (the opponent) across successive fictitious-play rounds, produce ONE synthesised policy that best represents the uniform mixture over that pool. Capture the principles they share, preserve tactical patterns that recur across iterates, and break idiosyncratic ties neutrally. Do NOT cherry-pick a single iterate, and do not invent tactics that no iterate endorses. The output will be handed to a downstream best-response optimiser as if it were the opponent’s actual policy for the next game. Output Format: only the synthesised policy text. No commentary, no markdown fences, no mention of iterate numbers. Produce a structured policy with clearly labelled sections (for example: Opening Principles, Midgame Priorities, Endgame / Closing Rules, Tactical Checks) where each section lists concrete, state-grounded rules. Each section header should end with a colon and appear on its own line. Keep sections focused: the overall policy should be thorough but not exhaustive — prefer depth on the key decision points over enumerating every variation. User prompt Task: ⟨ ⟩ Target seat being summarised: ⟨ ⟩ Number of past policies to average: ⟨K⟩ K Game rules: ⟨ rules⟩ Past policies for the ⟨ ⟩ seat (treat these as a uniform mixture): [Opponent iterate #1] ⟨ 1⟩ [Opponent iterate #2] ⟨ 2⟩ ⋮ Produce a single synthesised ⟨ ⟩ policy, organised into clearly labelled sections, representing the average of the pool above. Figure 6: Prompt template for the aggregation operator AggMAgg_M. ⟨⋅⟩ · marks runtime-filled slots; ⟨ ⟩∈ ∈\first player, second player\. System prompt System Role: You are a game strategy author performing fictitious play in language space. The opponent’s strategy for the next game is the SINGLE policy shown below (a synthesised average over their past iterates). Author a playing policy from scratch that maximises expected win-rate against this average opponent. Output Format: only the policy text. No commentary, no markdown fences. Produce a structured policy with clearly labelled sections (for example: Opening Principles, Midgame Priorities, Endgame / Closing Rules, Tactical Checks) where each section lists concrete, state-grounded rules. Each section header should end with a colon and appear on its own line. Keep sections focused: the overall policy should be thorough but not exhaustive — prefer depth on the key decision points over enumerating every variation. User prompt Task: ⟨ ⟩ Your seat: ⟨ ⟩ Opponent seat: ⟨ seat⟩ Fictitious-play round: ⟨t+1⟩/⟨T⟩ t+1 / T Game rules: ⟨ rules⟩ Opponent’s average policy (synthesised from their past iterates): ⟨ opponent policy⟩ Author a fresh ⟨ ⟩ policy, organised into clearly labelled sections, that maximises expected win-rate against the opponent’s average policy above. Figure 7: Prompt template for the best-response operator BRMBR_M. System prompt You are a powerful gaming agent who can make proper decisions to beat the user in gaming tasks. You are a helpful assistant that strictly follows the user’s instructions. User prompt (prompt_agent format; observation oto_t = rules ++ state) ⟨ rules⟩ ⟨ state: moves so far ++ legal actions⟩ You must choose an legal action to set up advantages. Your output must be in the following format: Action: Your action wrapped with <>, ⟨ -format spec⟩ Please return your answer without explanation! Learned policy: ⟨ text⟩ Figure 8: Prompt template for the action model MactM_act.

Instant research discovery