Emergent Cooperation in Multi-Agent Systems: Game Theory Perspectives

참고: 본 글은 AGEIUM Research가 게시하는 논문형 블로그입니다. 실험 결과 수치는 제시된 아키텍처의 **예시 시연(illustrative benchmark)**이며, 참고문헌에 인용된 외부 논문(arxiv·Nature·Science 등)은 실존 검증된 출처입니다.

1. 서론

Multi-agent reinforcement learning has evolved along two largely disconnected research trajectories. Classical MARL literature, rooted in game theory and control theory, emphasizes Nash equilibrium concepts and decentralized learning dynamics. Foundational work on independent learners, policy gradient methods, and actor-critic architectures established that autonomous agents can learn in shared environments, yet convergence guarantees typically assume either fully observable state spaces or the existence of potential games with aligned incentive structures. When these assumptions fracture—as they do in partially observable, heterogeneous-objective settings—coordination deteriorates into defection and reward hacking, a phenomenon well-characterized as the multi-agent analogue of the tragedy of the commons in resource allocation problems.

Separately, mechanism design theory provides a rigorous framework for aligning incentives through strategic choice of payment schemes and communication protocols. Shapley value decomposition offers principled credit attribution among coalition partners, and extensions to coalitional games on networks demonstrate that reputation signals and information asymmetry can stabilize cooperation under repeated interaction. However, classical mechanism design typically assumes quasi-static or one-shot interaction; its application to continuous-time MARL with online learning has remained largely underexplored. Incentive compatibility constraints proven in the mechanism-design literature—particularly in auction theory and collusion-resistant scheme design—have not been systematically integrated with MARL convergence analyses.

The emergence of large language models as agent orchestrators introduces a qualitatively new coordination regime. LLM-agent systems coordinating across tool-calling, planning, and collaborative problem-solving have been observed in preliminary studies to exhibit cooperation levels that challenge simple Nash equilibrium predictions. Plausible causal mechanisms include communication-induced reputation dynamics and model-inherent preference for cooperative language patterns; however, these hypotheses remain informal. No unified framework yet formalizes when and why such cooperation arises, or identifies the causal levers—communication transparency, reputation memory, role assignment—that stabilize or destabilize it across deployment contexts.

Recent work in cooperative AI has begun bridging these gaps, exploring reward shaping, auxiliary objectives, and hierarchical authority structures to induce alignment in multi-agent systems. Counterfactual reasoning and causal inference methods have also been applied to disentangle agent contributions in cooperative settings. Nevertheless, existing approaches typically address either the mechanism-design layer (incentive structure) or the learning-dynamics layer (MARL convergence) in isolation, and almost none are designed to account for the particular affordances and failure modes of LLM-agent systems—partial observability, bounded rationality, and emergent communication protocols that resist traditional game-theoretic characterization.

This work addresses that gap directly. We present the Cooperative Equilibrium Engine (CEE), a three-layer framework that jointly formalizes mechanism design constraints within MARL learning laws, provides empirical instrumentation to detect and measure cooperation across reward, reputation, and communication observables, and offers reproducible tooling enabling systematic, measurable multi-agent cooperation science. The framework's mathematical core computes approximate Nash equilibria via support enumeration for two-player games and fictitious play as a convergent heuristic for n-player settings, grounding the mechanism-design and learning-dynamics layers in a common formal substrate. The remainder of this paper is organized as follows: Section 2 establishes the formal game-theoretic model; Section 3 details the CEE architecture; Sections 4–5 present theoretical guarantees and empirical validation; Section 6 concludes with open directions.

2. 관련 연구

게임 이론은 자율 에이전트 간 상호작용의 수학적 토대를 제공한다. Nash(1950)의 균형 개념은 에이전트들이 상호 최선의 응답으로 수렴하는 지점을 정의했으며, Shapley(1953)의 특성함수 형식은 연합 게임에서 에이전트들의 기여도를 공정하게 분배하는 이론적 틀을 제공했다. 기제 설계(mechanism design) 분야는 Hurwicz, Maskin, Myerson(2007년 노벨경제학상)에 의해 개인의 사적 정보 하에서도 집단적으로 원하는 결과를 도출하는 규칙 체계를 설계하는 문제를 체계화했다. 이들 고전 이론은 다중 에이전트 시스템이 협력할 수 있는 조건과 공정성의 원리를 규정했으나, Shapley 값의 정확한 계산이 조합론적으로 복잡하다는 점으로 인해 대규모 실전 응용에는 제약이 있었다. Castro et al.(2009)은 샘플링 기반 Shapley 값 계산 방법을 제안하여 고차원 연합 게임에서의 적용 가능성을 높였다.

깊은 학습 기반의 다중 에이전트 강화학습(MARL) 시대는 고전 게임 이론과 현대 신경망을 결합하는 새로운 방향을 열었다. Foerster et al.(2018)의 반사실적 다중 에이전트 정책 그래디언트(counterfactual multi-agent policy gradients, COMA)는 각 에이전트가 자신의 개별 행동이 팀 성과에 미친 한계 기여를 학습하도록 설계했으며, 이는 Shapley 값의 정신을 신경망 학습에 내재화한 시도로 볼 수 있다. Rashid et al.(2018)의 QMIX는 가치 함수를 에이전트 개별 값 함수들의 단조함수로 인수분해하여 협력적 MARL에서의 수렴 성질을 이론적으로 보장하는 구조적 제약을 도입했다. Yu et al.(2022)은 근래에 proximal policy optimization(PPO)이라는 기초적 정책 그래디언트 방법이 협력 다중 에이전트 게임에서 예상 이상으로 효과적임을 실증했으며, 이는 MARL 문제 해결이 복잡한 특화 알고리즘뿐 아니라 기본 원리의 적절한 적용으로도 가능함을 시사한다.

대규모 언어 모델(LLM) 기반 에이전트의 출현은 다중 에이전트 협력의 패러다임을 근본적으로 변화시켰다. Park et al.(2023)의 생성형 에이전트 연구는 단순한 지시 수행을 넘어 에이전트들이 자율적으로 목표를 추구하고, 행동을 성찰하며, 미래를 계획하는 순환적 주기를 거치면서 자연스러운 상호작용을 전개하는 모습을 보여주었다. 이러한 연구들은 에이전트들이 명시적인 보상 신호 없이도 문맥 정보와 사전 학습된 세계 모델로부터 협력의 동기와 방식을 도출할 수 있음을 시사한다. Akata et al.(2023)의 연구는 LLM 에이전트 간 협력의 이머전트한 성질—즉, 상향식으로 자발적으로 나타나는 협력 현상—을 보다 명시적으로 다루었다. 이는 게임 이론의 정적 나쉬 균형 개념이 아닌 동적이고 진화하는 협력 형태를 관찰하고 측정할 수 있음을 의미한다.

그러나 현재까지 이 세 연구 영역—고전 게임 이론, 강화학습 기반 협력 메커니즘, LLM 기반 이머전트 협력—은 주로 분절되어 발전해 왔다. 기제 설계와 Shapley 값 이론은 협력의 공정성과 안정성을 규정하나, 신경망 학습 프로세스 내에서 이러한 원리들이 구체적으로 어떻게 구현되고 제약되는지에 대한 통합적 이해는 제한적이다. MARL 알고리즘들은 에이전트 간 합의된 전략을 학습하지만, LLM 에이전트들이 보유한 사전 학습 모델과 언어적 합리화 능력이 학습 과정을 어떻게 중재하고 변형하는지는 충분히 탐구되지 않았다. LLM 에이전트 협력 연구는 자연성과 현실성을 강조하지만, 협력의 안정성 조건, 공정한 기여 분배의 원리, 나쉬 균형과의 관계는 명시적으로 다루어지지 않는 경우가 많다.

이 연구는 이러한 갭을 메우기 위해 설계되었다. 게임 이론의 엄밀한 수학적 프레임워크를 현대 LLM 에이전트의 협력 능력에 적용하고, 동시에 MARL의 학습 동역학 통찰을 통합함으로써, 에이전트 협력의 안정성, 공정성, 그리고 창발적 특성을 동시에 분석할 수 있는 통합적 관점을 제시한다. AgentArena 플랫폼은 이러한 통합의 구체적 구현이며, 게임 이론적 제약과 LLM 기반 자율성이 실제로 어떻게 상호작용하는지를 실험적으로 검증하기 위한 테스트베드로 기능한다.

3. 배경

The problem of computing equilibria in multi-agent systems sits at the intersection of game theory, cooperative artificial intelligence, and mechanism design. Nash equilibrium — the joint strategy profile where no player has unilateral incentive to deviate — constitutes the central solution concept for strategic interaction [Nash 1950]. However, translating this theoretical construct into computational practice reveals substantial obstacles as player count and action-space cardinality grow.

For two-player games, support enumeration exploits the fact that an equilibrium can be pinpointed by iterating over pairs of support subsets and solving the resulting linear feasibility program for each candidate. The procedure is polynomial in the size of a fixed support set, but the number of support-pair combinations is combinatorially large — exponential in the number of pure strategies in the worst case [Savani & von Stengel 2006]. In practice, effective implementations exploit sparsity and early termination to make the approach feasible for moderate action spaces, but the method does not generalize to n-player settings: the equilibrium characterization for more than two players requires a system of polynomial equations whose solution count is not bounded by any polynomial in game size [Daskalakis et al. 2009, PPAD-hardness].

Multi-player cooperative games introduce a distinct challenge: how to fairly attribute joint payoffs to individual contributors. Shapley value theory provides the unique allocation satisfying efficiency, symmetry, dummy, and additivity axioms [Shapley 1953], but exact computation requires summing over all 2ⁿ coalitions. For n ≥ 20 this becomes computationally intractable. Castro et al. [2009] introduced a stratified sampling estimator that constructs Shapley estimates from randomly drawn permutations, achieving mean-squared error bounded by O(n²/ε²) samples for approximation tolerance ε. While this eliminates exponential coalition enumeration, its practical cost remains nontrivial for large n because each sampled permutation requires a full marginal-contribution evaluation; moreover, variance grows with heterogeneous player contributions, demanding more samples to maintain accuracy guarantees [Mitchell et al. 2022].

Fictitious play offers a tractable heuristic for n-player games, iteratively updating each player's mixed strategy as a best response to the empirical frequency of opponents' historical play [Brown 1951]. Convergence to Nash equilibrium is proven for two-player zero-sum games [Robinson 1951], potential games [Monderer & Shapley 1996], and certain dominance-solvable structures, but no general convergence guarantee exists for arbitrary n-player non-cooperative games. The method's practical convergence rate is sensitive to initialization, step-size scheduling, and the presence of cycles in the best-response correspondence; in cyclic coordination games fictitious play is known to diverge [Shapley 1964]. Adapting fictitious play from a learning-dynamics concept to a finite-time equilibrium-approximation algorithm therefore requires explicit convergence monitoring and iteration budgeting.

Existing agent coordination frameworks in multi-agent reinforcement learning (MARL) and decentralized planning have largely circumvented equilibrium computation in favor of independent Q-learning [Tan 1993] or centralized optimization under restricted information structures [Oliehoek & Amato 2016]. When equilibrium solutions are sought, implementations typically restrict generality by exploiting structural properties — zero-sum payoffs, dominant strategies, or known symmetries — that simplify computation but limit applicability. Methods designed for general-sum, general-structure games tend to scale poorly and offer limited interpretability of resulting strategy profiles [Shoham et al. 2007]. Furthermore, credit assignment and equilibrium computation are typically treated as decoupled problems in the MARL literature, despite their deep interdependence in cooperative settings where Shapley fairness axioms can conflict with equilibrium incentive constraints [Roughgarden 2010]. This decoupling represents an unresolved gap between the theoretical requirements for stable cooperative computation and the algorithmic infrastructure available in current deployed systems.

4. 방법론

The Cooperative Equilibrium Engine (CEE) is structured as a three-layer computational framework, each layer addressing a distinct failure mode in multi-agent cooperation: equilibrium instability, credit misattribution, and behavioral rigidity under partial observability. The architecture is implemented primarily in Rust, chosen for its deterministic memory model and zero-cost abstractions, which are essential when embedding the engine as a sub-process within latency-sensitive LLM-agent orchestration pipelines.

The first layer constitutes the mathematical equilibrium core. For two-player finite normal-form games, CEE computes approximate Nash equilibria via support enumeration: an exhaustive procedure that iterates over all candidate support pairs and, for each pair, solves the induced linear feasibility system to test whether a valid mixed-strategy equilibrium exists on that support. Although the number of candidate supports is exponential in the number of pure strategies per player — O(2^m · 2^n) for an m×n game — the method is exhaustive and exact up to numerical tolerance, meaning it will find every Nash equilibrium that exists; in practice it is tractable for the small-to-moderate strategy counts typical of LLM-agent coordination scenarios (m, n ≤ 20). For the general n-player case, exact equilibrium computation is PPAD-complete, and CEE therefore applies fictitious play as an anytime heuristic: agents maintain empirical frequency distributions over opponent histories and respond optimally to those distributions at each iteration. Convergence of fictitious play is guaranteed for two-player zero-sum games and for finite potential games but is not guaranteed in general symmetric games, a limitation explicitly acknowledged; CEE addresses this by coupling fictitious play with an exploitability-threshold early-stopping criterion that halts iteration when the gap between the current strategy profile and the best-response value falls below a configurable ε. The mathematical core exposes a stratified dispatch interface: callers specify game dimensionality at construction time, routing to the support-enumeration solver for the two-player case or to the fictitious-play heuristic otherwise, with both paths sharing a common equilibrium representation type that enforces weight normalization — Σᵢ wᵢ = 1 — as a compile-time invariant.

The second layer provides Shapley-value credit assignment. Exact Shapley computation requires evaluating the characteristic function over all 2^n coalitions, which is computationally prohibitive for agent counts exceeding approximately fifteen. CEE instead applies the Castro et al. (2009) sampling approximation, which estimates Shapley values by averaging marginal contributions over randomly ordered agent permutations; the method achieves an additive ε-approximation with probability 1 − δ using O(n² / ε² · log(n/δ)) permutation samples in the general case. When the cooperation structure is expressible as a tree-structured coalition graph — a natural fit for hierarchical task decomposition scenarios common in multi-agent LLM pipelines — the marginal-contribution computations can be organized via tree dynamic programming, reducing the per-sample cost from O(n) to a constant number of passes over the tree's O(n) edges, yielding a practical O(n) evaluation cost per sample rather than the O(n²) general-case cost. The credit assignment module outputs per-agent Shapley indices that are fed back as shaped reward signals during episodic resets, closing the loop between equilibrium selection and individual incentive alignment. This feedback pathway is crucial in scenarios where the Nash equilibrium is not Pareto-optimal: redistributing value according to Shapley fairness nudges the agent population away from defection-dominant basins without requiring centralized coordination or explicit side payments.