CoChat
Sign Up
PreprintCited by 6Game Theory and ApplicationsArtificial Intelligence in GamesMulti-Agent Systems and Negotiation

The Effect of State Representation on LLM Agent Behavior in Dynamic Routing Games

Open access
Goodyear, Lyle, Guo, Rachel, Johari, Ramesh·2025·arXiv
DOI 10.48550/arxiv.2506.15624arXiv 2506.15624
Open this paper in CoChat — free accountOpen PDF

Abstract

Large Language Models (LLMs) have shown promise as decision-makers in dynamic settings, but their stateless nature necessitates creating a natural language representation of history. We present a unifying framework for systematically constructing natural language "state" representations for prompting LLM agents in repeated multi-agent games. Previous work on games with LLM agents has taken an ad hoc approach to encoding game history, which not only obscures the impact of state representation on agents' behavior, but also limits comparability between studies. Our framework addresses these gaps by characterizing methods of state representation along three axes: action informativeness (i.e., the extent to which the state representation captures actions played); reward informativeness (i.e., the extent to which the state representation describes rewards obtained); and prompting style (or natural language compression, i.e., the extent to which the full text history is summarized). We apply this framework to a dynamic selfish routing game, chosen because it admits a simple equilibrium both in theory and in human subject experiments \cite{rapoport_choice_2009}. Despite the game's relative simplicity, we find that there are key dependencies of LLM agent behavior on the natural language state representation. In particular, we observe that representations which provide agents with (1) summarized, rather than complete, natural language representations of past history; (2) information about regrets, rather than raw payoffs; and (3) limited information about others' actions lead to behavior that more closely matches game theoretic equilibrium predictions, and with more stable game play by the agents. By contrast, other representations can exhibit either large deviations from equilibrium, higher variation in dynamic game play over time, or both.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2506.15624

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • LLM agents face fundamental limitations in long-horizon reasoning due to finite context windows, making effective memory management critical.

    “Large language model (LLM) agents face fundamental limitations in long-horizon reasoning due to finite context windows, making effective memory management critical.”

    From Agentic Memory: Learning Unified Long-Term and Short-Term Memory Management for Large Language Model Agents (2026) · cites this paper as Goodyear et al., 2025

    Section 3 says that agents can struggle to extract relevant information as prompts approach the context-window limit, and it investigates summarizing game history to reduce context use. That supports the importance of managing history, but the paper does not establish a fundamental limitation on long-horizon reasoning; its experiments fit the entire history within the available context window. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • Large language models are fundamentally stateless: their memory is bounded by a finite context window, and information outside that window is forgotten, preventing them from maintaining knowledge across long conversations or evolving tasks.

    “Large Language Models (LLMs) have demonstrated impressive capabilities across a wide range of NLP tasks, but they remain fundamentally stateless , constrained by limited context windows that hinder long-horizon reasoning.”

    From Memory-R1: Enhancing Large Language Model Agents to Manage and Utilize Memories via Reinforcement Learning (2025) · cites this paper as Goodyear et al., 2025

    The Introduction says LLMs are inherently stateless and rely on textual prompts for game history. Section 3 discusses context-window limits and difficulty extracting information as prompts approach them, but says the entire history fit within the window in this study. It does not establish that information outside the window is forgotten or that LLMs cannot maintain knowledge across long conversations or evolving tasks. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • Large language models remain fundamentally stateless, with memory bounded by a finite context window, so information outside the window is forgotten, preventing them from maintaining knowledge across long conversations or evolving tasks.

    “Large Language Models (LLMs) have demonstrated impressive capabilities across a wide range of NLP tasks, but they remain fundamentally stateless , constrained by limited context windows that hinder long-horizon reasoning.”

    From Memory-R1: Enhancing Large Language Model Agents to Manage and Utilize Memories via Reinforcement Learning (2026) · cites this paper as Goodyear et al., 2025

    The Introduction (p. not provided) calls LLMs inherently stateless, and Section 3 (p. not provided) says they can struggle to extract relevant information as prompts approach the context-window limit. The paper does not establish that information outside the window is forgotten or that this prevents knowledge from being maintained across long conversations; its experiments fit the entire history within the available window. (LLM, conf=0.85)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 45

  1. Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin. 2008. Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization.. In COLT. Citeseer, 263-274.
  2. Gati Aher, Rosa I. Arriaga, and Adam Tauman Kalai. 2023. Using Large Language Models to Simulate Multiple Humans and Replicate Human Subject Studies. https://doi.org/10.48550/arXiv.2208.10264 arXiv:2208.10264 [cs. · DOI · Paper page
  3. Elif Akata, Lion Schulz, Julian Coda-Forno, Seong Joon Oh, Matthias Bethge, and Eric Schulz. 2023. Playing repeated games with Large Language Models. https://doi.org/10.48550/arXiv.2305.16867 arXiv:2305.16867. · DOI · Paper page
  4. Lisa P. Argyle, Ethan C. Busby, Nancy Fulda, Joshua Gubler, Christopher Rytting, and David Wingate. 2023. Out of One, Many: Using Language Models to Simulate Human Samples. Political Analysis 31, 3 (July 2023), 337-351. https: //doi.org/10.1017/pan.2023.2 arXiv:2209.06899 [cs. · DOI · Paper page
  5. Sanjeev Arora, Elad Hazan, and Satyen Kale. 2012. The multiplicative weights update method: a meta-algorithm and applications. Theory of computing 8, 1 (2012), 121-164.
  6. Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. 2002. The Nonstochastic Multiarmed Bandit Problem. SIAM J. Comput. 32, 1 (Jan. 2002), 48-77. https://doi.org/10.1137/S0097539701398375 · DOI
  7. Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. 2023. Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection. https://doi.org/10.48550/arXiv.2306.04637 arXiv:2306.04637 [cs. · DOI
  8. Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language Models are Few-Shot Learners. https://doi.org/10.48550/arXiv.2005.14165 arXiv:2005.14165. · DOI · Paper page
  9. Nicolò Cesa-Bianchi and Gábor Lugosi. 2006. Prediction, Learning, and Games. https://doi.org/10.1017/CBO9780511546921 Journal Abbreviation: Prediction, Learning, and Games Publication Title: Prediction, Learning, and Games. · DOI
  10. Andrea Coletta, Kshama Dwarakanath, Penghang Liu, Svitlana Vyetrenko, and Tucker Balch. 2024. LLM-driven Imitation of Subrational Behavior : Illusion or Reality? http://arxiv.org/abs/2402.08755 arXiv:2402.08755 [cs, econ, q-fin]. · arXiv
  11. José R Correa and Nicolás E Stier-Moses. 2011. Wardrop equilibria. Encyclopedia of Operations Research and Management Science. Wiley (2011).
  12. Jinhao Duan, Renming Zhang, James Diffenderfer, Bhavya Kailkhura, Lichao Sun, Elias Stengel-Eskin, Mohit Bansal, Tianlong Chen, and Kaidi Xu. 2024. GTBench: Uncovering the Strategic Reasoning Limitations of LLMs via Game-Theoretic Evaluations. https://doi.org/10.48550/arXiv.2402.12348 arXiv:2402.12348. · DOI · Paper page
  13. Nicoló Fontana, Francesco Pierri, and Luca Maria Aiello. 2024. Nicer Than Humans: How do Large Language Models Behave in the Prisoner's Dilemma? https://doi.org/10.48550/arXiv.2406.13605 arXiv:2406.13605 [physics]. · DOI · Paper page
  14. Yoav Freund and Robert E. Schapire. 1999. Adaptive Game Playing Using Multiplicative Weights. Games and Economic Behavior 29, 1 (Oct. 1999), 79-103. https://doi.org/10.1006/game.1999.0738 · DOI
  15. Fulin Guo. 2023. GPT in Game Theory Experiments. https://doi.org/10.48550/arXiv.2305.05516 arXiv:2305.05516 · DOI
  16. Sergiu Hart and Andreu Mas-Colell. 2013. Simple adaptive strategies: from regret-matching to uncoupled dynamics. Vol. 4. World Scientific.
  17. Nathan Herr, Fernando Acero, Roberta Raileanu, María Pérez-Ortiz, and Zhibin Li. 2024. Are Large Language Models Strategic Decision Makers? A Study of Performance and Bias in Two-Player Non-Zero-Sum Games. https://doi.org/10. 48550/arXiv.2407.04467 arXiv:2407.04467. · DOI
  18. John J. Horton. 2023. Large Language Models as Simulated Economic Agents: What Can We Learn from Homo Silicus? https://doi.org/10.48550/arXiv.2301.07543 arXiv:2301.07543 [econ, q-fin]. · DOI · Paper page
  19. Jen-tse Huang, Eric John Li, Man Ho Lam, Tian Liang, Wenxuan Wang, Youliang Yuan, Wenxiang Jiao, Xing Wang, Zhaopeng Tu, and Michael R. Lyu. 2024. How Far Are We on the Decision-Making of LLMs? Evaluating LLMs' Gaming Ability in Multi-Agent Environments. https://doi.org/10.48550/arXiv.2403.11807 arXiv:2403.11807. · DOI
  20. Jingru Jia, Zehua Yuan, Junhao Pan, Paul E. McNamara, and Deming Chen. 2025. Large Language Model Strategic Reasoning Evaluation through Behavioral Game Theory. https://doi.org/10.48550/arXiv.2502.20432 arXiv:2502.20432 [cs] version: · DOI
  21. Daniel Kahneman and Amos Tversky. 2013. Prospect theory: An analysis of decision under risk. In Handbook of the fundamentals of financial decision making: Part I. World Scientific, 99-127.
  22. Ayato Kitadai, Sinndy Dayana Rico Lugo, Yudai Tsurusaki, Yusuke Fukasawa, and Nariaki Nishino. 2024. Can AI with High Reasoning Ability Replicate Human-like Decision Making in Economic Experiments? https://doi.org/10.48550/arXiv. 2406.11426 arXiv:2406.11426. · DOI
  23. Spyros Kontogiannis and Paul Spirakis. 2005. Atomic selfish routing in networks: A survey. In International Workshop on Internet and Network Economics. Springer, 989-1002.
  24. Yihuai Lan, Zhiqiang Hu, Lei Wang, Yang Wang, Deheng Ye, Peilin Zhao, Ee-Peng Lim, Hui Xiong, and Hao Wang. 2024. LLM-Based Agent Society Investigation: Collaboration and Confrontation in Avalon Gameplay. https://doi.org/10. 48550/arXiv.2310.14985 arXiv:2310.14985 [cs]. · DOI
  25. Tor Lattimore and Csaba Szepesvári. 2020. Bandit algorithms. Cambridge University Press.
  26. Yan Leng. 2024. Can LLMs Mimic Human-Like Mental Accounting and Behavioral Biases? https://doi.org/10.2139/ssrn. 4705130 · DOI
  27. Nelson F. Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. 2024. Lost in the Middle: How Language Models Use Long Contexts. Transactions of the Association for Computational Linguistics 12 (Feb. 2024), 157-173. https://doi.org/10.1162/tacl_a_00638 · DOI · Paper page
  28. Dov Monderer and Lloyd S Shapley. 1996. Potential games. Games and economic behavior 14, 1 (1996), 124-143.
  29. Chanwoo Park, Xiangyu Liu, Asuman Ozdaglar, and Kaiqing Zhang. 2024. Do LLM Agents Have Regret? A Case Study in Online Learning and Games. https://doi.org/10.48550/arXiv.2403.16843 arXiv:2403.16843. · DOI
  30. Joon Sung Park, Joseph C. O'Brien, Carrie J. Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. 2023. Generative Agents: Interactive Simulacra of Human Behavior. https://doi.org/10.48550/arXiv.2304.03442 arXiv:2304.03442 · DOI · Paper page
  31. Steve Phelps and Yvan I. Russell. 2024. The Machine Psychology of Cooperation: Can GPT models operationalise prompts for altruism, cooperation, competitiveness and selfishness in economic games? https://doi.org/10.48550/arXiv.2305.07970 arXiv:2305.07970 [cs. · DOI
  32. Amnon Rapoport, Tamar Kugler, Subhasish Dugar, and Eyran J. Gisches. 2008. Braess Paradox in the Laboratory: Experimental Study of Route Choice in Traffic Networks with Asymmetric Costs. In Decision Modeling and Behavior in Complex and Uncertain Environments, Tamar Kugler, J. Cole Smith, Terry Connolly, and Young-Jun Son (Eds.). Springer, New York, NY, 309-337. https://doi.org/10.1007/978-0-387-77131-1_13 · DOI
  33. Amnon Rapoport, Tamar Kugler, Subhasish Dugar, and Eyran J. Gisches. 2009. Choice of routes in congested traffic networks: Experimental tests of the Braess Paradox. Games and Economic Behavior 65, 2 (March 2009), 538-571. https://doi.org/10.1016/j.geb.2008.02.007 · DOI
  34. Jillian Ross, Yoon Kim, and Andrew W. Lo. 2024. LLM economicus? Mapping the Behavioral Biases of LLMs via Utility Theory. https://doi.org/10.48550/arXiv.2408.02784 arXiv:2408.02784. · DOI
  35. Tim Roughgarden. 2004. Selfish routing with atomic players. In Proc. 16th symp. on discrete algorithms (soda). Citeseer, 1184-1185.
  36. Tim Roughgarden. 2005. Selfish Routing and the Price of Anarchy. MIT Press. Google-Books-ID: 2hjQEAAAQBAJ.
  37. Eilam Shapira, Omer Madmon, Itamar Reinman, Samuel Joseph Amouyal, Roi Reichart, and Moshe Tennenholtz. 2024. GLEE: A Unified Framework and Benchmark for Language-based Economic Environments. https://doi.org/10.48550/ arXiv.2410.05254 arXiv:2410.05254. · DOI
  38. Amos Tversky and Daniel Kahneman. 1974. Judgment under Uncertainty: Heuristics and Biases: Biases in judgments reveal some heuristics of thinking under uncertainty. science 185, 4157 (1974), 1124-1131.
  39. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2023. Attention Is All You Need. https://doi.org/10.48550/arXiv.1706.03762 arXiv:1706.03762 [cs. · DOI · Paper page
  40. Haochuan Wang, Xiachong Feng, Lei Li, Zhanyue Qin, Dianbo Sui, and Lingpeng Kong. 2024. TMGBench: A Systematic Game Benchmark for Evaluating Strategic Reasoning Abilities of LLMs. https://doi.org/10.48550/arXiv.2410.10479 arXiv:2410.10479. · DOI
  41. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. 2022. Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. https://arxiv.org/abs/2201.11903v6 Publication Title: arXiv.org. · arXiv
  42. Lin Xu, Zhiyuan Hu, Daquan Zhou, Hongyu Ren, Zhen Dong, Kurt Keutzer, See Kiong Ng, and Jiashi Feng. 2024a. MAgIC: Investigation of Large Language Model Powered Multi-Agent in Cognition, Adaptability, Rationality and Collaboration. https://doi.org/10.48550/arXiv.2311.08562 arXiv:2311.08562 [cs. · DOI
  43. Yuzhuang Xu, Shuo Wang, Peng Li, Fuwen Luo, Xiaolong Wang, Weidong Liu, and Yang Liu. 2024b. Exploring Large Language Models for Communication Games: An Empirical Study on Werewolf. https://doi.org/10.48550/arXiv.2309.04658 arXiv:2309.04658 [cs. · DOI · Paper page
  44. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2023. ReAct: Synergizing Reasoning and Acting in Language Models. https://doi.org/10.48550/arXiv.2210.03629 arXiv:2210.03629 [cs. · DOI · Paper page
  45. Yauwai Yim, Chunkit Chan, Tianyu Shi, Zheye Deng, Wei Fan, Tianshi Zheng, and Yangqiu Song. 2024. Evaluating and Enhancing LLMs Agent based on Theory of Mind in Guandan: A Multi-Player Cooperative Game under Imperfect Information. https://doi.org/10.48550/arXiv.2408.02559 arXiv:2408.02559. · DOI

Cited by

Sorted by citations

Authors
Goodyear, L., Guo, R., & Johari, R.
Affiliations
Stanford University (US)
ORCID
Goodyear, Lyle
Venue
arXiv
Publisher
arXiv
Published
2025
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2506.15624
arXiv
2506.15624
OpenAlex
W4415334329
Cited by
0
References
0
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Game Theory and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence in Games
  • Physical Sciences › Computer Science › Artificial Intelligence › Multi-Agent Systems and Negotiation
Keywords
large language models, LLM agents, state representation, selfish routing, multi-agent games, game equilibrium, regret

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review