Attributing Emergence in Million-Agent Systems

• URL: http://arxiv.org/abs/2605.11404v1
• Date: Tue, 12 May 2026 01:49:41 GMT
• Title: Attributing Emergence in Million-Agent Systems
• Abstract summary: Large language models (LLMs) can simulate human-like reasoning and decision-making in individual agents.<n>Such studies require attributing macro emergence to individual agents.<n>We adapt Aumann--Shapley path-integral attribution to LLM-powered MAS at million-agent scale.
• Score: 68.53670424791751
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models (LLMs) can simulate human-like reasoning and decision-making in individual agents. LLM-powered multi-agent systems (MAS) combine such agents to simulate population-scale social phenomena such as polarization, information cascades, and market panics. Such studies require attributing macro emergence to individual agents, but existing axiomatic methods scale combinatorially in $N$ and have been confined to $N \lesssim 10^3$, while the phenomena they explain occur at $N \geq 10^6$. We address this gap by adapting Aumann--Shapley path-integral attribution to LLM-powered MAS at million-agent scale; the resulting method satisfies all four axioms, runs four to five orders of magnitude faster than sampled Shapley on the same hardware. We use this method to test the scale gap empirically: across 14 days of public Bluesky data ($1{,}671{,}587$ active users), we compute the attribution at both full scale and the visibility-biased $N = 10^2$ convenience sample used by small-scale studies, and the two disagree structurally. At full scale the long tail and middle tier jointly carry the majority; the biased small panel attributes almost everything to a few high-follower accounts. We then prove that under any nonlinear macro indicator the disagreement cannot be reduced by post-hoc rescaling: an Attribution Scaling Bias theorem shows that no global rescaling factor can reconcile small-scale and full-scale attribution. Full-scale attribution is therefore not a methodological choice but a theoretical requirement for any nonlinear macro indicator.

Related papers

• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• Poor Man's Agentic Modeling: Simulating Large LLM-Agent Societies on a Laptop [0.0]
  We create a simulation of a large language model society using a few hundred agents.<n>We map perception and memory to an effective theory and a predicted $N$-trend of the surrogate error.
  arXiv  Detail & Related papers  (2026-07-19T08:44:38Z)
• Collective Alignment in LLM Multi-Agent Systems: Disentangling Bias from Cooperation via Statistical Physics [0.0]
  We present a model-agnostic statistical-physics method to disentangle social conformity from intrinsic bias, compute critical exponents, and probe the collective behavior and possible phase transitions of multi-agent systems.<n>We find that collective alignment is dominated by an intrinsic bias rather than by cooperative neighbor coupling, producing field-driven crossovers instead of genuine phase transitions.
  arXiv  Detail & Related papers  (2026-05-11T13:13:44Z)
• Descent-Guided Policy Gradient for Scalable Cooperative Multi-Agent Learning [14.185814237633958]
  Descent-Guided Policy Gradient (DG-PG) is a framework that constructs noise-free per-agent guidance gradients.<n>We prove that DG-PG reduces gradient variance from $(N)$ to $mathcalO(1)$, preserves the equilibria of the cooperative game, and achieves agent-independent sample complexity.
  arXiv  Detail & Related papers  (2026-02-23T17:45:08Z)
• Mean-Field Reinforcement Learning without Synchrony [11.907264672363718]
  Mean-field reinforcement learning scales to large populations by reducing each agent's dependence on others to a single summary statistic -- the mean action.<n>Existing MF-RL theory is built on the mean action and does not extend to $$.<n>We construct the Temporal Mean Field framework around the population distribution $$ from scratch, covering the full spectrum from fully synchronous to purely sequential decision-making.
  arXiv  Detail & Related papers  (2026-02-20T06:42:08Z)
• Large Language Models Are Bad Dice Players: LLMs Struggle to Generate Random Numbers from Statistical Distributions [50.1404916337174]
  We present the first large-scale, statistically powered audit of native probabilistic sampling in large language models (LLMs)<n>We show that batch generation achieves only modest statistical validity, with a 13% median pass rate, while independent requests collapse almost entirely.<n>We conclude that current LLMs lack a functional internal sampler, necessitating the use of external tools for applications requiring statistical guarantees.
  arXiv  Detail & Related papers  (2026-01-08T22:33:12Z)
• From Debate to Equilibrium: Belief-Driven Multi-Agent LLM Reasoning via Bayesian Nash Equilibrium [52.28048367430481]
  Multi-agent frameworks can boost the reasoning power of large language models (LLMs), but they typically incur heavy computational costs and lack convergence guarantees.<n>We recast multi-LLM coordination as an incomplete-information game and seek a Bayesian Nash equilibrium (BNE)<n>We introduce Efficient Coordination via Nash Equilibrium (ECON), a hierarchical reinforcement-learning paradigm that marries distributed reasoning with centralized final output.
  arXiv  Detail & Related papers  (2025-06-09T23:49:14Z)
• Minimax-Optimal Multi-Agent Robust Reinforcement Learning [7.237817437521988]
  We extend the Q-FTRL algorithm citepli2022minimax to the RMGs in finite-horizon setting, assuming access to a generative model.<n>We prove that the proposed algorithm achieves an $varepsilon$-robust coarse correlated equilibrium (CCE) with a sample complexity (up to log factors) of $widetildeOleft(H3Ssum_i=1mA_iminleftH,1/Rright/varepsilon2right), where $S$ denotes the
  arXiv  Detail & Related papers  (2024-12-27T16:37:33Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  We show that model-based MARL achieves a sample complexity of $tilde O(|S||B|(gamma)-3epsilon-2)$ for finding the Nash equilibrium (NE) value up to some $epsilon$ error. We also show that such a sample bound is minimax-optimal (up to logarithmic factors) if the algorithm is reward-agnostic, where the algorithm queries state transition samples without reward knowledge.
  arXiv  Detail & Related papers  (2020-07-15T03:25:24Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.