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

Paper: 2606.19308 Authors: Leyang Shen, Yang Zhang, Xiaoyan Zhao, Chun Kai Ling, Tat-Seng Chua Categories: cs.CL, cs.MA

The Gap

Existing LLM-based multi-agent systems (MAS) excel at execution complexity — breaking a task into subtasks and solving them in parallel (e.g., software engineering, planning). But they fall apart on decision-making tasks where stakeholders’ choices are mutually dependent. Call this stance entanglement: you cannot optimize Agent A’s strategy without knowing what Agent B will do, and vice versa.

Prior work treats each agent as a purely cooperative module that independently produces a sub-plan (divide-and-conquer). This ignores the strategic interdependence. Single-round prompting or even multi-round chat (which lacks a formal convergence guarantee) cannot handle the feedback loop of decisions.

This paper closes that gap by importing fictitious play from game theory: agents learn by best-responding to the empirical mixture of others’ past actions, iterating until equilibrium.

+-------------------+
| Existing: LLM MAS  |
| (divide-conquer)   |
| handles execution  |
+--------+----------+
         |
         | Fails at decision tasks
         v
+--------+----------+
| Gap: Stance        |
| entanglement       |
| (mutual dependence)|
+--------+----------+
         |
         | Use game theory
         v
+--------+----------+
| Hypothesis: Fict.  |
| play can iter.     |
| converge to eq.    |
+--------+----------+
         |
         | Proposed MAFP
         v
+--------+----------+
| Method: Each agent |
| best responds to   |
| empirical mix of   |
| others' past act.  |
+--------+----------+
         |
         | Evaluate on 2-player zero-sum games
         v
+--------+----------+
| Evidence: MAFP     |
| beats single-round |
| and multi-round    |
| baselines in       |
| tournament & rob.  |
+--------+----------+
         |
         v
+-------------------+
| Conclusion: MAFP   |
| solves stance ent. |
+-------------------+

The Increment

One sentence: Before this paper, LLM MAS had no principled way to handle strategic interdependence in decision tasks; after MAFP, they can iteratively converge to near-optimal strategies by treating decision-making as equilibrium search.

Core Mechanism

MAFP has five components:

1. Agents – each represents a stakeholder with a utility function (e.g., payoff matrix or preference description).
2. History – a per-agent list of all actions they have taken so far.
3. Empirical Mixture – for each agent, the uniform distribution over all past actions of every other agent.
4. Best Response – using an LLM to compute the action that maximizes the agent’s utility given the current mixture of others.
5. Iteration Loop – repeat for $T$ rounds, then aggregate strategies (e.g., average) for final policy.

Data flow:

• At round $t$, each agent $i$ computes the mixture $\pi_{-i}^t$ = average of all actions in the histories of all other agents.
• Then $i$ prompts the LLM with a description of its own utility and $\pi_{-i}^t$ to get a best-response action $a_i^t$.
• Append $a_i^t$ to $i$‘s history.
• After $T$ rounds, output the final strategy as the average of all actions (or the last round’s actions).

             +-----------------+
             | Initialize      |
             | histories empty |
             +-------+---------+
                     |
                     v
          +----------+----------+
          | For t = 1 to T:     |
          +----------+----------+
                     |
            +--------+--------+
            | For each agent i|
            +--------+--------+
                     |
                     v
    +-----------------+-----------------+
    | Compute mixture of others'        |
    | past actions: pi_{-i}^t = avg     |
    | (hist_{-i}[1..t-1])               |
    +-----------------+-----------------+
                     |
                     v
    +-----------------+-----------------+
    | LLM best-response:                |
    | a_i^t = argmax u_i(a, pi_{-i}^t) |
    +-----------------+-----------------+
                     |
                     v
    +-----------------+-----------------+
    | Append a_i^t to history_i         |
    +-----------------+-----------------+
                     |
                     v
          +----------+----------+
          | Next t               |
          +----------+----------+
                     |
                     v
          +----------+----------+
          | Output final strategy|
          | (e.g., average)      |
          +---------------------+

Structural metaphor: Think of a jazz jam session where musicians (agents) play improvised solos. In the first round, each musician plays whatever they feel, ignoring others. After each round, they listen to recordings of everyone’s past solos, form a mental “average style” of the band, then improvise a new solo that fits that style best (according to their own musical taste). Over many rounds, the band converges to a coherent groove — an equilibrium that no one wants to deviate from. MAFP is the algorithmic version: the LLM plays the role of the musician’s intuition, the history is the recording library, and the best-response is choosing the note that harmonizes with the average of all previous notes.

Key Concepts

• Fictitious Play
  Imagine two friends guessing each other’s favorite ice cream flavor. You keep a tally of all flavors your friend has chosen so far. Then you pick the flavor that you think will make both of you happiest, assuming your friend will randomly pick from their past choices. That’s fictitious play: you assume their future behavior is a random draw from their past distribution. Under mild conditions, this process converges to a Nash equilibrium.

• Stance Entanglement
  Two politicians declaring their policies — each wants to maximize votes, but the optimal policy for one depends on the other’s policy. You cannot compute candidate A’s best policy without considering candidate B’s planned response. That’s stance entanglement: decisions are not independent; they are tangled.

• Best Response
  Given your opponent’s strategy, what move gives you the highest payoff? In a game of Rock-Paper-Scissors, if you know your opponent always picks Rock, your best response is Paper. In MAFP, the LLM computes this by reasoning about the utility function and the empirical mixture it receives.

Framework Shift

Before (mainstream approach):

Task ----> Sub-task 1 ----> Agent A (independent output)
    ----> Sub-task 2 ----> Agent B (independent output)
    ----> Sub-task 3 ----> Agent C (independent output)
         Final output = merge of independent pieces

After (this paper):

Round 1:
Agent A: [--- observe B & C past ---] -> best response a1
Agent B: [--- observe A & C past ---] -> best response b1
Agent C: [--- observe A & B past ---] -> best response c1
Store (a1,b1,c1) in history.
Round 2:
... iterate ...
Final: converge to equilibrium strategies

One sentence: From parallel independent optimization to sequential interdependent best-response, the core shift is treating decision-making as an equilibrium-seeking process rather than a decomposition problem.

Expert Assessment

Problem choice: Real gap. Stance entanglement is ubiquitous in economics, politics, and multi-agent AI. The field was overdue for a principled game-theoretic injection into LLM MAS. Not manufactured — it follows naturally from the limitations of divide-and-conquer.

Method maturity: Clever insight, not brute force. Fictitious play is a well-understood classical algorithm; the novelty is making it work with LLMs as best-response oracles. There is a simpler approach: just have agents talk to each other in multi-round dialog — but that lacks convergence guarantees and often degenerates. MAFP provides structure. That said, the paper could have explored whether simpler heuristics (e.g., weighted majority) also work; that comparison is missing.

Experimental integrity: Fair baselines (single-round, multi-round chat, a naive no-LLM heuristic). Metrics (tournament strength, robustness) are appropriate. However, the testbed is limited to 2-player zero-sum games (e.g., Rock-Paper-Scissors variants). Real-world decision tasks involve more players and non-zero-sum utilities. Red flag: the number of iterations T is small (5–10) — does true convergence happen? The paper doesn’t show convergence diagnostics. Also, the LLM cost per iteration is high; no cost analysis.

Writing quality: Clear overall, but the “stance entanglement” concept is introduced but never formally defined (e.g., as a game-theoretic condition). The methods section is dense but skips the prompt template used — that’s the most practical part! If the authors added a sample prompt and a convergence analysis, the paper would be much stronger.

Verdict: weak accept — a solid first step that opens a direction, but the experimental scope and lack of formalization limit immediate impact.

Takeaways

• Iterative best-response with history mixing can be applied to any multi-agent negotiation task (e.g., resource allocation, contract negotiation) where you can define utility functions for each agent. Steal the pattern: collect past decisions → compute empirical distribution → LLM best-responds → repeat.
• Use average of past actions as a cheap approximation of opponent strategy — it avoids expensive inner-loop reasoning about opponent beliefs.
• Game theory as a cheap correctness layer for LLM agents — instead of hoping the LLM spontaneously converges to good joint behavior, enforce the structure of fictitious play. If you have a multi-agent LLM system that currently uses free-form chat, consider replacing it with this iterative procedure; you’ll get better guarantees and reproducibility.