Paper deep dive
History Matters: Meta-policy Delegation with Heterogeneous Multi-agent Reinforcement Learning
Ziqing Lu, Avinash Reddy Mudireddy, Sarra Alqahtani, Weiyu Xu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/5/2026, 3:21:52 AM
Summary
This paper proposes a framework for collaborative multi-agent systems (MAS) using Multi-Agent Reinforcement Learning (MARL) to handle task delegation among heterogeneous agents with varying capabilities and costs. The authors introduce a history-dependent policy formulation where agents consider past interactions (joint actions) to make delegation decisions, moving beyond standard Markovian state-dependence. Two key frameworks are presented: one for management/delegation constraints and another for a virtual monetary mechanism to incentivize cooperation and trust. The goal is to minimize execution costs while maintaining effective task performance in resource-constrained scenarios.
Entities (7)
Relation Signals (5)
History-Dependent Policy → dependson → Interaction History
confidence 95% · an agent's policy depends not only on the current state... but also on the interaction history, including previous joint actions
MARL → enables → Sequential Delegation Decisions
confidence 94% · We first develop a multi-agent reinforcement learning-based (MARL) delegation training that enables agents to make sequential delegation decisions
History-Dependent Policy → improves → Coordination
confidence 93% · This history-dependent formulation can improve coordination even in fully observable environments
Heterogeneous Multi-Agent Systems → minimizes → Total Execution Cost
confidence 92% · enables agents to make sequential delegation decisions while minimizing the total execution cost
Virtual Money Transfer → facilitates → Collaboration
confidence 91% · The virtual money is separate from the environmental rewards... By tracking the balances and constraining transfers, the system can encourage collaborations
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:AI agents are expected to play an increasingly important role in future decision-making systems. In this paper, we consider collaborative systems composed of heterogeneous multi-agent systems (MAS), where their members have different capabilities and operating costs. We study how agents can delegate tasks to one another so that certain research tasks can be completed effectively under resource-constrained scenarios. We first develop a multi-agent reinforcement learning-based (MARL) delegation training that enables agents to make sequential delegation decisions while minimizing the total execution cost. We then extend this approach to MARL with prescribed delegation topologies. Furthermore, we introduce two new frameworks for collaboration and delegation in multi-agent systems. The first framework proposes that an agent's policy depends not only on the current state of the underlying Markov decision process but also on the interaction history, including previous joint actions. This history-dependent formulation can improve coordination even in fully observable environments, where conventional MARL methods typically restrict policies to depend only on the current state. The second framework proposes a novel, potentially multi-dimensional monetary mechanism to facilitate the collaboration and delegation for MAS.
Tags
Links
- Source: https://arxiv.org/abs/2608.03833v1
- Canonical: https://arxiv.org/abs/2608.03833v1
Trouble viewing inline? Open PDF directly →
Full Text
69,671 characters extracted from source content.
Expand or collapse full text
History Matters: Meta-policy Delegation with Heterogeneous Multi-agent Reinforcement Learning Ziqing Lu Department of Applied Mathematics and Computational Science University of Iowa luz@wfu.edu &Avinash Reddy Mudireddy∗ Department of Electrical and Computer Engineering University of Iowa avinashreddy-mudireddy@uiowa.edu &Sarra Alqahtani Department of Computer Science Wake Forest University sarra-alqahtani@wfu.edu These authors contributed equally to this work. Weiyu Xu Department of Electrical and Computer Engineering University of Iowa weiyu-xu@uiowa.edu Abstract AI agents are expected to play an increasingly important role in future decision-making systems. In this paper, we consider collaborative systems composed of heterogeneous multi-agent systems (MAS), where their members have different capabilities and operating costs. We study how agents can delegate tasks to one another so that certain research tasks can be completed effectively under resource-constrained scenarios. We first develop a multi-agent reinforcement learning-based (MARL) delegation training that enables agents to make sequential delegation decisions while minimizing the total execution cost. We then extend this approach to MARL with prescribed delegation topologies. Furthermore, we introduce two new frameworks for collaboration and delegation in multi-agent systems. The first framework proposes that an agent’s policy depends not only on the current state of the underlying Markov decision process but also on the interaction history, including previous joint actions. This history-dependent formulation can improve coordination even in fully observable environments, where conventional MARL methods typically restrict policies to depend only on the current state. The second framework proposes a novel, potentially multi-dimensional monetary mechanism to facilitate the collaboration and delegation for MAS. 1 Introduction AI agents have emerged as a promising approach for solving complex, multi-step problems. Large language models (LLMs) often serve as the reasoning engines of these agents, enabling them to interpret tasks, generate plans, use external tools, and coordinate specialized models or other agents. As agentic systems become more capable, they are also increasingly likely to contain multiple models with different capabilities, ownership relationships, and operating costs. Despite their potential, deploying LLM-based agents can be expensive. Reliance on API-based models may incur substantial and unpredictable costs due to massive token usage. Using a premium model for every decision is often unnecessary: Smaller or less expensive models may be sufficient for routine tasks, while stronger models may be needed only for difficult or high-consequence decisions. Thus, an effective multi-agent system must determine both how to solve a task and which agent should execute each step. Existing work addresses this cost-performance trade-off through model routing, multi-agent orchestration, and MARL-based collaboration. FrugalGPT, RouteLLM, and AutoMix select or cascade models according to expected quality, task difficulty, and invocation cost (Chen et al., 2023; Ong et al., 2025; Aggarwal et al., 2024), while Router-R1 and MasRouter use learned controllers to make sequential routing, role-assignment, and model-selection decisions (Zhang et al., 2025b; Yue et al., 2025). MAGRPO and CoLLM instead apply MARL to improve the task-level policies of LLM agents operating within predefined collaboration protocols (Liu et al., 2026b, a). Graph-based frameworks such as GPTSwarm and G-Designer optimize computational or communication connections among agents (Zhuge et al., 2024; Zhang et al., 2025a). Our focus is complementary but distinct: we learn a delegation layer over agents that already possess pretrained task policies. Delegation is an explicit agent action rather than a decision imposed entirely by a centralized router. This formulation allows us to study which agent should execute, who may delegate to whom, and how execution decisions depend on agent costs and prior interactions. Accordingly, we formulate task delegation among LLM-based agents as a MARL problem, enabling the delegation layer to adaptively and efficiently assign each task to the most appropriate agent, which then executes its own pretrained policy. Delegation also raises questions on agents’ willingness to collaborate. Whether an agent accepts a costly task may depend on whether another agent previously cooperated, fulfilled a delegation, or provided compensation, rather than because of the current physical state alone. Although histories are commonly used in partially observable environments to infer hidden state, we consider a different role for history: past joint actions and inter-agent interactions are strategically relevant even when the environmental state is fully observable. Such histories can support reciprocity, trust, and intertemporal incentives that may not be expressible by policies restricted to the current Markov state that were traditionally considered in fully observable MGs robust-marl; zero-sum-game; bai2020provable. Thus it is natural to ask “Which agents should be trusted to perform the tasks using their own pre-trained policies?” A related question is that “When should agents trust their peers and delegate the work of solving the tasks to their peers?” In this paper, we investigate how agents should delegate tasks to other agents in a collaborating environment. Our contributions include the following: 1. Our work formulates delegation itself as a sequential multi-agent decision problem. Agents with heterogeneous pretrained capabilities choose whether to execute, delegate, or remain inactive; We propose a formulation in which AI agents delegate tasks to their peers subject to management and delegation constraints. The framework is designed to reduce operational costs and may also support the development of safer and more reliable multi-agent systems oversight_game. 2. We introduce a history-dependent policy formulation tailored to collaboration and delegation. The policies may depend on the public interaction history, including previous joint actions and states, rather than only on the current environmental state. We show that conditioning on previous behavior can support reciprocal collaboration outcomes. 3. To make history-dependent policies practical in MARL, we propose a virtual money-transfer framework that supports collaboration and delegation. An agent’s money balance provides a compact summary of its past interactions, including previous actions and transfers. The virtual money is separate from the environmental rewards that measure the agent’s actual task performance. By tracking the balances and constraining transfers, the system can encourage collaborations that lead to higher environmental rewards across time steps. Related works: oversight_game formulates an oversight game in which human supervisors decide when to intervene and when to rely on a supervised agent’s pretrained policy during MARL training. Its human–agent delegation mechanism is designed for safety guarantees. In contrast, our work studies delegation among agents as a cost-allocation problem, with the primary objective of minimizing execution costs while maintaining effective task performance. action_trading studies action trading, where selfish agents can trade their actions in exchange for reward, and shows empirically that such action trading can increase the overall reward. Our money transfer framework differs in two aspects: First, the virtual money is separate from environmental rewards and records past interactions. This distinction is useful when task-level rewards are not transferable, while an internal budget can still be exchanged to facilitate delegation. Second, payments depend on the joint action, rather than only on the receiver’s individual action. The formulation of our transferable money system is also different from the series of peer-incentivation (PI) works because our formulation treats money as a component of the state variable, while PI type of works, such as DRIVE DRIVE and LIO LIO, usually treat incentives primarily as reward-shaping signals used for policy learning. A line of reputation-based MARL research, including anastassacos2021cooperationreputationdynamicsreinforcement; ren2025bottomupreputationpromotescooperation, also incorporates the effect from past interactions. However, the information resulted by past interactions in those works is either formulated as an explicit social norm or a learned social evaluation, and the resulting reputation score directly reshapes its environmental reward. In contrast, our money variable is neither a judgment of an agent’s social standing nor a reward-shaping term. It is a transferable and budget-constrained balance. For more related works in routing across LLMs and MARL for LLM collaboration, please see Appendix A. 2 Problem Formulation Consider a collaborative Markov game (MG) with n agents: ℳ=,,,P,R,γ,μi1=1n,T,K, =\N,S,A,P,R,γ,\ _i\_1=1^n,T,K\, (1) where N is the number of agents with ||=n|N|=n, S is the shared state space, =1×⋯×nA=A_1×…×A_n is the joint agent-group action space, P:×→[0,1]P:S×A×S→[0,1] is the transition probability function that depends on the joint action of the group, γ∈[0,1)γ∈[0,1) is the discount factor, T is the number of steps in each episode and K is the number of episodes. Each agent is individually pre-trained in the same environment and equipped with its own learned policy μi:×i→[0,1],i=1…n _i:S×A_i→[0,1],i=1… n. The stronger the agent i is in intelligence, the better its pre-learned policy μi _i. We consider this collaborative MG built on top of these pre-trained policies. This MG can be viewed as an extra “wrapper” layer between the pre-training of LLM agents and the deployment of these agents. The output of this MARL interface is :×→[0,1] π:S×A→[0,1], which is the joint group policy used to delegate tasks to specific agents. Notice that the delegation policy π is independent of the pre-trained policies μii=1n\ _i\_i=1^n. Define each agent’s one-step reward as Ri:×i→ℝR_i:S×A_i . Then the collaborative one-step reward is R(st,t)=∑i∈Ri(st,t)R(s_t, a_t)= _i R_i(s_t, a_t). The collaborating group aims to maximize the objective function J()=,P[∑t=1Tγt−1∑i∈Ri(st,t)]. J( π)=E_ π,P [ _t=1^Tγ^t-1 _i R_i(s_t, a_t) ]. (2) On top of the collaborative game, we further introduce different delegation structures that are applicable in different scenarios. First, the management constraints, meaning that some agents have ownership of or control over the actions of fellow agents. Second, the delegation constraints, which generalize management constraints by allowing any agent to delegate tasks to any other agent. Third, the most general and realistic setting is money trading, in which agents incentivize others to undertake delegated tasks by allocating a portion of their held money as payment. 2.1 Management Constraints In the simplest case, assume that the stronger agent has one-way control over its fellow agent, and thus can mandatorily delegate work through this management structure. We take a 33 agent system as an example. Name the three agents A,BA,B, and C. Suppose that agent A has control over agent B, and agent B has control over agent C. Although A(B) is a more capable agent than B(C), B(C) is more cost-efficient in simple tasks than its corresponding superior. Therefore, when dealing with simple tasks, superiors have incentives to delegate tasks to their fellow agents. Regardless of whether each agent chooses to delegate or adopt its pre-trained action, there is only one agent actually executing at each step. We assume that agents have heterogeneous capabilities and execution costs. At each time step, the current state contains sufficient information for agents to identify the task. Each agent knows everybody’s capabilities and costs for the given task. Thus, before choosing whether to execute or delegate, agent i can determine which agents are able to complete the task and can compare their expected performance and execution costs. In this formulation, we adopt the full-information assumption and treat these profiles as known to all agents. We formulate the collaborative delegation game as follows A,B,C,,,R,P,γ,μA,μB,μC\\A,B,C\,S,A,R,P,γ,\ _A, _B, _C\\: The shared state space S is the same state space where agents were previously trained. For every agent i, its action space is augmented by its own delegation action space and the no-operation action, i′=i∪i∪no−opA_i =A_i _i∪\no-op\, with iD_i defined as A=dA→B,B=dB→C,C=∅.D_A=\d_A→ B\,D_B=\d_B→ C\,D_C= . Each delegation action di→jd_i→ j means the agent i delegates the tasks to agent j. The expanded joint action space is the product of expanded action spaces =Πi=A,B,Ci′∪i∪no−opA= _i=A,B,C\ A_i _i∪\no-op\. The transition probability function, discount factor are defined the same way as those of (1). μA,μB,μC\ _A, _B, _C\ are the pre-learned policies. For example, for each LLM agent, μi(a~i|s) _i( a_i|s) denotes its fixed task-execution policy. This policy is induced by the agent’s underlying pre-trained language model and available tools. Given a task state or context s, μi _i determines a distribution over the responses or environmental actions available to agent i. Sequential Execution Rules: At each time step t, there is only one agent would actually execute the delegated task. If agent i selects to perform, its action is sampled from its own pre-trained policy aμi∼μia_ _i _i. The execution action aexeca_exec of the group is chosen in the following way: aexec=aμA, if =(aμA,⋅,⋅),aμB, if =(dA→B,aμB,⋅),aμC, if =(dA→B,dB→C,aμC). a_exec= casesa_ _A, if a=(a_ _A,·,·),\\ a_ _B, if a=(d_A→ B,a_ _B,·),\\ a_ _C, if a=(d_A→ B,d_B→ C,a_ _C). cases Here “⋅·” means any action of the corresponding agent. This execution rule follows exactly the hierarchical relations between agents A, B and C. The reward function of each agent RiR_i consists of two parts: the environmental reward R¯ R and the individual execution or delegation cost iC_i. The environmental reward R¯:×exec→ℝ R:S×A_exec is generated in correspondence to the executed action aexeca_exec, and is the same for any agent i in the group. The other part of the reward function is the individual execution or delegation cost i:i∪i∪no−op→ℝ.C_i:A_i _i∪\no-op\ . If agent i chooses to execute, then the execution cost is generated according to the specific execution cost i(aμi)C_i(a_ _i) (For example, the execution cost of each agent can be represented by the API usage cost of the corresponding LLM.); If agent i chooses to delegate the task, there is a relatively smaller delegation cost i(di→j)C_i(d_i→ j); If no−opno-op is chosen, i(no−op)=0,∀i∈C_i(no-op)=0,∀ i . Therefore, one-step reward function of each agent i is formulated as Ri(s,)=αR¯(s,aexec)−βi(ai),R_i(s, a)=α R(s,a_exec)- _i(a_i), where α and β are scaling factors, since the environmental reward and the money cost differ in units. The objective of the agent group is still to maximize (2). 2.2 Delegation Constraints In a more general case, when delegation is assigned in interactive ways between every two pairs of agents, delegation constraints can be represented through a directed graph. For example, an arrow from Agent A to Agent B represents A choosing to delegate to B, and vice versa. Compared to subsection 2.1, we omit the strict hierarchical relation in delegation rules. With the same three-agent example as in 2.1, we let all other settings be the same but modify the action spaces and the execution rules The individual delegation action space iD_i of each agent i is now expanded, and any agent can delegate the task to any other agent in the group. A=dA→B,dA→C,B=dB→A,dB→C,D_A=\d_A→ B,d_A→ C\,D_B=\d_B→ A,d_B→ C\, C=dC→A,dC→BD_C=\d_C→ A,d_C→ B\ Networked Execution Rules: Multiple agents can execute at the same time. The execution action is now a 33-element vector a, with each element indicating whether and with what action an agent is executing. Here (exec)i( a_exec)_i denotes the i-th element of the execution action. (exec)i=aμi,if∃j≠i:aj=dj→iai∼μi. ( a_exec)_i=a_ _i,if cases∃\,j≠ i:\ a_j=d_j→ i\ \\ a_i _i. cases This execution rule means that an agent performs if and only if some other agent delegates the task to it and it does not delegate to any other agent. For initialization, at the beginning of every episode, an oracle delegates the task to a selected subset of agents. The individual reward remains the same as that of 2.1, and the group objective is the same as (2). In realistic human societies, whether a delegation relationship can be formed often depends on an individual’s willingness to accept a costly task. To capture this feature, we allow each agent’s willingness to accept such a task to depend on its previous interactions with other agents. In particular, an agent may be more willing to trust a peer and accept a delegated task if they have chosen collaborative joint actions in the past. We therefore model each agent’s policy as depending on the history of past states and joint actions, rather than only on the current state. 2.3 Policies Dependent on Past Interactions In this subsection, we consider a class of history-dependent policies that differs from the conventional Markov policies commonly used in the MARL literature robust-marl; zero-sum-game; bai2020provable. Under a Markov policy, each agent selects its action based only on their current state. By contrast, under a history-dependent policy, an agent may condition its action on the entire past interactions of the game. Consider a finite dynamic game with n participants =,1×⋯×n,P,T,r.G=\S,A_1×·s×A_n,P,T,r\. Let xt∈x_t denote the state at time t, and let t=(at1,…,atn) a_t=(a_t^1,…,a_t^n) denote the joint action at time t, 1≤t≤T1≤ t≤ T. We define the public history available at time t by ht=(x1,1,x2,2,…,xt−1,t−1,xt).h_t=(x_1, a_1,x_2, a_2,…,x_t-1, a_t-1,x_t). The public history hth_t contains all past states, all past joint actions, and the current state. For each agent i, a deterministic history-dependent policy profile is a sequence of policies πtit=1T\ _t^i\_t=1^T, where each history dependent policy maps from the public history up to time t to the action space of agent i, πti:ℋt→i,t=1,…,T, _t^i:H_t _i,\ t=1,…,T, where ℋtH_t denotes the set of histories up to time t. A Markov policy is a special case of history-dependent policies, where the policy depends only on the current state and is irrelevant to past trajectories: πti(ht)=μti(xt). _t^i(h_t)= _t^i(x_t). The key advantage of a history-dependent policy is that it allows agents to reward, punish, or condition their actions based on the previous behavior of other agents. The following example illustrates why this additional dependence on history is more realistic and can even incentivize equilibrium policies with higher returns. Notice that the regular Markov policy space is a subspace of the history-dependent policy space, so the return of a history-dependent policy is at least as good as that of a Markov policy. Motivating example: Consider a two-agent dynamic game with two agents A and B, with two time steps T=2T=2, and with a state space =s1,s2S=\s_1,s_2\. The state at time t is denoted by xtx_t. The action spaces are 1=aA,1,aA,2,2=aB,1,aB,2A_1=\a_A,1,a_A,2\,\ A_2=\a_B,1,a_B,2\. The joint action is written as t=(atA,atB) a_t=(a_t^A,a_t^B). At the first time step, agent A’s action determines the reward: r1(x1,1)=(0,0),if a1A=aA,1,(−0.1,1),if a1A=aA,2, r_1(x_1, a_1)= cases(0,0),&if a_1^A=a_A,1,\\ (-0.1,1),&if a_1^A=a_A,2, cases where aA,2a_A,2 is costly for agent A, but beneficial for agent B. At the second time step, agent B’s action determines the reward: r2(x2,2)=(0,0),if x2=s1 and a2B=aB,1,(9,0),if x2=s1 and a2B=aB,2,(0,10),if x2=s2 and a2B=aB,1,(9,10),if x2=s2 and a2B=aB,2 r_2(x_2, a_2)= cases(0,0),&if x_2=s_1 and a_2^B=a_B,1,\\ (9,0),&if x_2=s_1 and a_2^B=a_B,2,\\ (0,10),&if x_2=s_2 and a_2^B=a_B,1,\\ (9,10),&if x_2=s_2 and a_2^B=a_B,2 cases where aB,2a_B,2 benefits agent A, while agent B’s own second-step reward is independent of whether it chooses aB,1a_B,1 or aB,2a_B,2. The state transition is given by ℙ(x2=s2∣x1=s1,1)=0.5,ℙ(x2=s1∣x1=s1,1)=0.5,∀1∈P(x_2=s_2 x_1=s_1, a_1)=0.5,P(x_2=s_1 x_1=s_1, a_1)=0.5,∀ a_1 . History-dependent Nash equilibrium. Under the history-dependent policy formulation, the following policy profile is one deterministic Nash equilibrium: π1A(h1)=aA,2,π2A(h2) any action in 1, _1^A(h_1)=a_A,2, _2^A(h_2) any action in A_1, π1B(h1) any action in 2,π2B(h2)=aB,1,if a1A=aA,1,aB,2,if a1A=aA,2. _1^B(h_1) any action in A_2, _2^B(h_2)= casesa_B,1,&if a_1^A=a_A,1,\\ a_B,2,&if a_1^A=a_A,2. cases This policy is history-dependent because agent B’s second-period action depends on the past joint action 1 a_1, not only on the current state x2x_2. Under this policy profile, agent A chooses the costly action aA,2a_A,2 at the first time step. In response, agent B chooses aB,2a_B,2 at the second time step, which rewards agent A. The expected returns are V0A=−0.1+0.5(9+9)=8.9,V_0^A=-0.1+0.5(9+9)=8.9, and V0B=1+0.5(0+10)=6.V_0^B=1+0.5(0+10)=6. Markov Nash equilibrium. Now suppose that agents are restricted to Markov policies. Then agent B’s second-period policy can depend only on the current state x2x_2, but not on agent A’s first-period action. Therefore, the history-dependent reward mechanism described above is no longer available. An example Markov equilibrium is given by π1A(x1)=aA,1,π2A(x2) can be any action in 1, _1^A(x_1)=a_A,1, _2^A(x_2) can be any action in A_1, π1B(x1) can be any action 2,π2B(x2)=aB,1. _1^B(x_1) can be any action A_2, _2^B(x_2)=a_B,1. Under this Markov policy profile, agent A does not choose the costly first-period action, since agent B’s future action cannot be conditioned on whether A previously helped B. The expected returns are V0A=0+0.5(0+0)=0,V_0^A=0+0.5(0+0)=0, and V0B=0+0.5(0+10)=5.V_0^B=0+0.5(0+10)=5. In fact, we cannot find any equilibrium for history-independent policies where agent B achieves a reward bigger than 66. We numerically verified that among all the Markov deterministic equilibria policies, there are 33 possible outcomes in terms of value: (0,0,5.0),(4.5,5.0),(9.0,5.0)\(0,0,5.0),(4.5,5.0),(9.0,5.0)\, where within each tuple, the first element is the return of agent A and the second element is the return of agent B. Meanwhile, among all the history-dependent deterministic equilibria, there are 55 possible outcomes: (0.0,5.0),(4.4,6.0),(4.5,5.0),(8.9,6.0),(9.0,5.0)\(0.0,5.0),(4.4,6.0),(4.5,5.0),(8.9,6.0),(9.0,5.0)\. This example illustrates that history-dependent policies can support reciprocity mechanisms that are not expressible by Markov policies. Since future actions can depend on past joint actions, one agent may be incentivized to take a costly action early in the game if another agent can condition its later behavior on that action. In this sense, history-dependent policies may support equilibria with higher returns than those obtained under the Markov policy restriction. Algorithm: We develop a Two-step Nash Value Iteration Algorithm to find the overall deterministic Nash equilibrium policy that favors agent B. In the case when there are multiple pure Nash equilibria, depending on the agents’ need, Algorithm 1 outputs the policy profile that favors the return of the chosen agent i. Please refer to Appendix B for details of this algorithm. We prove that the output of this algorithm is a history-dependent pure-strategy Nash equilibrium. Theorem 1. Consider a finite two-step dynamic game. If the two-step continuation game admits at least one pure-strategy Nash equilibrium, and that at least one induced one-step game admits a pure-strategy Nash equilibrium, then Algorithm 1 returns a pure-strategy subgame-perfect Nash equilibrium policy profile. Proof. We prove by showing that none of the agent i prefers to deviate from the output policy π∗π^* at any time step t=1t=1 and t=2t=2. Please see Appendix C for details of this proof. ∎ Extension of Algorithm 1 to Finite n-step Games: The two-step algorithm can be extended to an n step dynamic game by induction. First, solve the final two-step continuation game, consisting of times n−1n-1 and n using Algorithm 1. This generates the set of deterministic history-dependent Nash equilibrium continuation policies for the last two steps. Next, apply each continuation policy for the previous step n−2n-2. For every possible history hn−2h_n-2, compute the immediate reward plus the expected equilibrium value generated by the selected continuation policy. Then find the Nash equilibria of this induced one-step game and combine each equilibrium action with the continuation policy. This gives the equilibrium policies for the last three steps. Repeat this procedure backward until the algorithm yields the deterministic history-dependent Nash equilibrium policies for the entire n-step dynamic game. 2.4 Delegation Through Transferable Money We now consider a more realistic setting in which agents can form delegation contracts through transferable money. The key feature of this framework is that money is separate from the environmental rewards that agents aim to maximize. The reward function represents the real-world utility obtained by each agent from the environment, while money only serves as an internal medium as a record of past joint actions and states, and money enables delegation and coordination in a distributed multi-agent reinforcement learning. Consider a Markov game (1). Let sts_t denote the environmental state at time t, and let iA_i be the environmental action space of agent i. To improve this regular Markov game with a money transfer mechanism, each agent is equipped with a money balance state wti≥0,∀t,iw^i_t≥ 0,∀ t,i, and define the augmented individual state as s~ti=(st,wti) s^i_t=(s_t,w^i_t). Now the individual state records both the environmental state and the leftover money balance of agent i. More generally, the money can be multi-dimensional instead of a scalar. At each time step t, each agent i chooses a physical action atia_t^i and a money transfer action ti p_t^i. This physical action is mapped from the environmental policy ati∼πienv(s~ti)a^i_t _i^env( s^i_t). Money Transfer Actions The money transfer action of each agent i is ti=[ptij]j≠i∈ℝ+n−1 p_t^i=[p^ij_t]_j≠ i ^n-1_+. Its domain is determined by a prescribed contract: Cri:→ℝn−1Cr^i:A ^n-1 that maps from each joint action to a list of fixed prices agent i is willing to pay for other agents. At time step t, if agent j performs the corresponding physical action aja_j at step t, agent i pays money ptji=Crji()p^ji_t=Cr^i_j( a) to agent j (we can also make the amount depend on historical actions). Thus, the discrete money transfer actions ti p^i_t are chosen according to the current augmented state and the current joint action (it can also depend on historical actions or trajectories): ti∼πitr(⋅|s~t,t). p^i_t π^tr_i(·| s_t, a_t). Agent i’s transfer policy is therefore denoted by πitr:s~t×→ℝ+n−1. _i^tr: s_t×A ^n-1_+. This policy determines the vector of payments [ptij]j≠i[p^ij_t]_j≠ i made by agent i to all other agents. The full policy of agent i is therefore πi=(πienv,πitr) _i=( _i^env, _i^tr), and the joint policy is =(env,tr). π=( π^env, π^tr). Insufficient Money Balance When agent i wants to pay more than its current balance, i.e., ‖ti‖1>wti\| p_t^i\|_1>w_t^i, then the desired joint action is not feasible, and agent i needs to turn to an affordable joint action. When wtiw_t^i drops to 0, then no transfer is allowed. The agent’s objective is still purely environmental: J()=[∑t=1T∑i=1Nγt−1Ri(st,t)],J( π)=E π[ _t=1^T _i=1^Nγ^t-1R_i(s_t, a_t)], and money does not directly enter the reward function. 3 Numerical Analysis This section presents the numerical results tied to the mechanisms introduced in the problem formulations. We begin with management and delegation structures on MARL. The delegation policy is trained for solving GSM8K (cobbe2021gsm8k), a public grade-school math word-problem benchmark with reference answers, using one shared solver stack and changing only the interaction rule between the two subsections. Protocol knobs that matter for reproducibility—prices, caches, seeds, hyper-parameters, and compute—are collected in Appendix D. The remaining subsections treat history-dependent policies and money transfer separately. Shared GSM8K stack. We use three frozen solvers of different strength and cost on this math benchmark: Nemotron 3 Ultra as solver A, Llama 3.2 3B as solver B, and Llama 3.2 1B as solver C. Only a centralized DQN coordinator π is trained; A, B, and C stay frozen. Synthetic token prices make solver A expensive and solver C cheap (Appendix D). Before training the MARL interface, we cache each solver’s GSM8K answers and offline correctness labels once; during training π reuses those fixed offline answers and labels instead of calling the solvers or a live labeler at every step, which keeps the runs reproducible (Appendix D). Each episode packs 3232 questions, allows up to three attempts per question (fail penalty −1-1), and runs for 10001000 episodes with γ=0.99γ=0.99, cost weight λ=100λ=100, and handoff fee α=0.05α=0.05. Unless noted otherwise, we report mean± of return, accuracy, and cost across seeds 0–1919. The always-Ultra baseline is a no-handoff policy that sends every question to solver A alone, under the same caches and cost rules as the learned policy in that subsection. 3.1 Management Constraints on GSM8K Here we put the hierarchy of Section 2.1 on GSM8K in a restricted form. The coordinator may use only three routes along the chain A→B→CA→ B→ C: (i) solver A answers alone; (i) A hands the question to solver B, and B answers; or (i) the question is passed A→B→CA→ B→ C, and solver C answers. Exactly one solver runs on each attempt. Skipping straight from A to C (allowed in the theory section) is turned off here, so every handoff must follow the chain in order. The step reward credits a correct answer under the offline labels, charges for the solve and for each handoff, and applies a failure penalty after three misses: r=Rcorr−λCsolve(aexec)−λCedge(ne,aexec)+Rfail,r\;=\;R_corr\;-\;λ\,C_solve(a_exec)\;-\;λ\,C_edge(n_e,a_exec)\;+\;R_fail, where Cedge=neαCsolveC_edge=n_e\,α\,C_solve with α=0.05α=0.05, and RfailR_fail is 0 on ordinary steps and −1-1 after three failed attempts (so the leading “++” adds a negative penalty; see Appendix D). Table 1 and Figure 1 show the results in the late MARL training. The always-Ultra baseline has return 23.90±0.3023.90±0.30 at the cost of $0.063±0.002 0.063±0.002 per episode. The MARL learned coordinator reaches 27.56±0.3227.56±0.32 return at the cost of $0.033±0.002 0.033±0.002 per episode (about $31.1 31.1 vs. $60.8 60.8 cumulative over 10001000 episodes), with accuracy 0.982±0.0020.982±0.002 versus 0.971±0.0020.971±0.002. That is roughly +3.7+3.7 return at about half the synthetic cost. A paired Wilcoxon signed-rank test over the 2020 seed-wise late-train means finds higher return and lower cost than always-Ultra in all 2020 seeds (two-sided p=2−19p=2^-19). Figure 2 tracks which solver is called. Late policies lean on solver B, still ask solver A on a nontrivial share, and almost never rely on solver C. Late-train metric DQN+map DQN no map always-Ultra Return 27.56±0.3227.56±0.32 27.65±0.2827.65±0.28 23.90±0.3023.90±0.30 Accuracy 0.982±0.0020.982±0.002 0.982±0.0020.982±0.002 0.971±0.0020.971±0.002 Cost ($/ep) 0.033±0.0020.033±0.002 0.032±0.0020.032±0.002 0.063±0.0020.063±0.002 Cum. cost ($/10001000) 31.1±0.731.1±0.7 31.1±0.731.1±0.7 60.8±0.260.8±0.2 Table 1: Management Constraints: Late-training metrics (last 100100 episodes; mean± over 2020 seeds). Figure 1: Management constraints on GSM8K: mean± over 2020 seeds for return, accuracy, per-episode cost, and cumulative cost (MARL learned coordinator vs always-Ultra). Figure 2: Management constraints: share of attempts using Ultra (A), Llama 3B (B), and Llama 1B (C) over training (mean± over 2020 seeds). 3.2 Delegation Constraints on GSM8K We keep the same GSM8K stack and swap to the freer delegation rule indicated in section 2.2. The coordinator first chooses a non-empty kickoff set among the seven options A\\A\, B\B\, C\C\, A,B\A,B\, A,C\A,C\, B,C\B,C\, and A,B,C\A,B,C\\. Then, each of A, B, and C chooses one of the three actions: answer, pass to the first other agent, or pass to the second other agent. Packing kickoff with the three local choices gives 7×33=1897× 3^3=189 joint discrete actions. An agent answers only if it was handed the task (by kickoff or by a peer pass) and it chooses to answer; Multiple agents may answer in the same attempt. We count the attempt as successful if any agent is correct. We charge the sum of those agents’ solve costs, and add α=0.05α=0.05 edge fee (each kickoff, handoff, and peer pass). Besides always-Ultra, we roll out the frozen management coordinator from section 3.1 on the same packets for a matched comparison. Always-Ultra is evaluated in the same graph environment, so it also pays the kickoff edge fee when solver A is started. Table 2 and Figure 3 show results in the late training. Against Always-Ultra, which returns 23.31±0.3023.31±0.30 at the cost of $0.068±0.002 0.068±0.002 per episode, the graph coordinator reaches 25.20±0.4225.20±0.42 return at the cost of $0.043±0.002 0.043±0.002/episode, with accuracy 0.961±0.0050.961±0.005 versus 0.971±0.0020.971±0.002. There is about 1.91.9 increased return at roughly 37%37\% lower per-episode cost. The cumulative synthetic cost over 10001000 episodes falls from about $66.7 66.7 to $45.5 45.5. The same Wilcoxon test again finds a higher return and lower cost than Always-Ultra in all 2020 seeds with two-sided p=2−19p=2^-19. On matched packets, the management coordinator is still ahead. It returns 28.70±0.1828.70±0.18, with accuracy 0.986±0.0010.986±0.001, at the cost $0.024±0.001 0.024±0.001 per episode. Therefore, the graph delegation beats never handing off, while the hierarchy policy remains stronger on return at a lower cost in these runs. Figure 4 shows the executor mix. Compared with management routing, the graph policies call solver C more often, and sometimes several agents answer the same question. That freer pattern helps explain why return and accuracy sit a bit below the hierarchy policy, even though the cost stays below Always-Ultra. Late-train metric DQN+map DQN no map always-Ultra Mgmt. π Return 25.20±0.4225.20±0.42 25.21±0.3325.21±0.33 23.31±0.3023.31±0.30 28.70±0.1828.70±0.18 Accuracy 0.961±0.0050.961±0.005 0.961±0.0040.961±0.004 0.971±0.0020.971±0.002 0.986±0.0010.986±0.001 Cost ($/ep) 0.043±0.0020.043±0.002 0.043±0.0020.043±0.002 0.068±0.0020.068±0.002 0.024±0.0010.024±0.001 Cum. cost ($/10001000) 45.5±0.645.5±0.6 45.4±0.645.4±0.6 66.7±0.266.7±0.2 23.9±0.123.9±0.1 Table 2: Delegation constraints: Late-training metrics (last 100100 episodes; mean± over 2020 seeds; handoff fee α=0.05α=0.05). Mgmt. π is the frozen management coordinator on the same packets. Figure 3: Delegation constraints on GSM8K: mean± over 2020 seeds for return, accuracy, per-episode cost, and cumulative cost (learned coordinator vs always-Ultra). Figure 4: Delegation constraints: share of attempts with Ultra (A), Llama 3B (B), and Llama 1B (C) executing over training (mean± over 2020 seeds; shares may sum above one when several agents answer). 3.3 Interactions of Distributed Agents with the Money Trading Mechanism This experiment trains two independent Q-learning agents with and without the money transfer mechanism for comparison. The environment works as follows: There are two agents A and B participating in the sequential games. In the training, there are 2020 steps in each episode, and 50005000 episodes in total. The agents alternate in being the active agent: Agent A is active in one phase, typically the odd-numbered steps, and agent B is active in another phase, typically in even-numbered steps. However, only the action of the currently active agent affects the physical rewards. A state has two components s=(phase,t)s=(phase,t) where phase∈s1,s2phase∈\s_1,s_2\ indicates which which agent is active. tt is the current time step index. This experiment has two phases, and therefore, the state space is =(s1,t),(s2,t):t=0,…,20S=\(s_1,t),(s_2,t):t=0,…,20\. The action space of each agent is binary: A=B=0:Null,1:YesA_A=A_B=\0:Null,1:Yes\, where NullNull means “do not help with others”, and YesYes means “help the other agent”. The transition of states is deterministic, such that the state alternates between the two possible phases as s1→s2→s1→…→s2s_1→ s_2→ s_1→…→ s_2 regardless of the joint actions. The time counter tt increases by 11 after every step within each episode. The active agent chooses whether to incur a small personal cost to generate a large benefit for the other agent. When agent A is active, the reward function is that (rtA,rtB)=(0,0), if A chooses Null(−1,100), if A chooses Yes. (r^A_t,r^B_t)= cases(0,0), if $A$ chooses Null\\ (-1,100), if $A$ chooses Yes cases. Symmetrically, if B is active, then the reward function is (rtA,rtB)=(0,0), if B chooses Null(100,−1), if B chooses Yes. (r^A_t,r^B_t)= cases(0,0), if $B$ chooses Null\\ (100,-1), if $B$ chooses Yes cases. The returns of the independent Q-learning with and without a money transfer mechanism are shown in Figure 5. Figure 5: Training Returns of Independent Q-learning with Money Transfer Mechanism 1. Independent Q-learning (IQL) Agents A and B maintain separate Q-functions and independently select their actions using an ε -greedy policy. Each agent updates its action values using only its own environmental reward, while treating the other agent’s behavior as part of the environment. After the 50005000-episode training, the learned policy is that both agents refuse to collaborate. On agent A’s turns, agent A always chooses the action NullNull. On agent B’s turns, agent B always chooses the action NullNull as well. This non-cooperative joint policy results in a 0 episodic environmental return. 2. IQL with Money Transfer With the new formulation, we consider an extended independent Q-learning with money transfers. The environment is augmented with transferable money balances, and therefore a state consists of s=(phase,t,)s=(phase,t, w), where =(w1,w2) w=(w_1,w_2) is the money balances of both agents. Each agent starts with an initial balance of 11 unit. Before the active agent chooses its physical action, the other agent acts as the payer and decides whether to offer a fixed payment 11 unit for the YesYes action. An offer is made only when the payer has sufficient funds: wi≥1w_i≥ 1. If the payment is made, the corresponding amount is transferred from the payer’s balance to the active agent’s balance, and the contract requires the active agent choosing the action YesYes. After 50005000 training episodes, the learned joint policy is that on agent A’s turns, agent B transfers one unit to A. By contract, agent A chooses the action YesYes to help the agent B. The physical and money policies are symmetric on agent B’s turns. For every episode with 2020 time steps, both agents helped at all 1010 of their active stages and obtained an environmental return of 990990. Thus, the money-transfer framework successfully supported the fully cooperative outcome. 4 Conclusion In this paper, we study the delegation problem among a heterogeneous multi-agent group. We also proposed frameworks of collaboration/delegation for multi-agent systems with history-based policies and money-based policies. In terms of limitations, this work has not addressed the pricing of the joint actions based on history, even though we have shown that certain pricing of the joint actions can help the agents achieve collaborations. More efficient algorithms are needed for finding the Nash equilibra and coarse correlated equilbria using history-dependent policies. References [1] P. Aggarwal, A. Madaan, A. Anand, S. P. Potharaju, S. Mishra, P. Zhou, A. Gupta, D. Rajagopal, K. Kappaganthu, Y. Yang, S. Upadhyay, M. Faruqui, and Mausam (2024) AutoMix: automatically mixing language models. In Advances in Neural Information Processing Systems, Vol. 37. External Links: Document, Link Cited by: §A.1, §1. [2] L. Chen, M. Zaharia, and J. Zou (2023) FrugalGPT: how to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.05176. External Links: Document, Link Cited by: §A.1, §1. [3] Q. J. Hu, J. Bieker, X. Li, N. Jiang, B. Keigwin, G. Ranganath, K. Keutzer, and S. K. Upadhyay (2024) RouterBench: a benchmark for multi-LLM routing system. arXiv preprint arXiv:2403.12031. External Links: Document, Link Cited by: §A.1. [4] H. Li, Y. Zhang, Z. Guo, C. Wang, S. Tang, Q. Zhang, Y. Chen, B. Qi, P. Ye, L. Bai, Z. Wang, and S. Hu (2026-07) LLMRouterBench: a massive benchmark and unified framework for LLM routing. In Findings of the Association for Computational Linguistics: ACL 2026, San Diego, California, United States, p. 37733–37754. External Links: Document, Link Cited by: §A.1. [5] S. Liu, T. Chen, R. Amiri, and C. Amato (2026) Learning decentralized LLM collaboration with multi-agent actor critic. arXiv preprint arXiv:2601.21972. External Links: Document, Link Cited by: §A.2, §1. [6] S. Liu, Z. Liang, X. Lyu, and C. Amato (2026) LLM collaboration with multi-agent reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence 40 (38), p. 32150–32158. External Links: Document, Link Cited by: §A.2, §1. [7] I. Ong, A. Almahairi, V. Wu, W. Chiang, T. Wu, J. E. Gonzalez, M. W. Kadous, and I. Stoica (2025) RouteLLM: learning to route LLMs from preference data. In International Conference on Learning Representations, External Links: Link Cited by: §A.1, §1. [8] Y. Yue, G. Zhang, B. Liu, G. Wan, K. Wang, D. Cheng, and Y. Qi (2025-07) MasRouter: learning to route LLMs for multi-agent systems. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Vienna, Austria, p. 15549–15572. External Links: Document, Link Cited by: §A.1, §1. [9] G. Zhang, Y. Yue, X. Sun, G. Wan, M. Yu, J. Fang, K. Wang, T. Chen, and D. Cheng (2025) G-Designer: architecting multi-agent communication topologies via graph neural networks. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, p. 76678–76692. External Links: Link Cited by: §1. [10] H. Zhang, T. Feng, and J. You (2025) Router-R1: teaching LLMs multi-round routing and aggregation via reinforcement learning. In Advances in Neural Information Processing Systems, Vol. 38. External Links: Link Cited by: §A.1, §1. [11] M. Zhuge, W. Wang, L. Kirsch, F. Faccio, D. Khizbullin, and J. Schmidhuber (2024) GPTSwarm: language agents as optimizable graphs. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235, p. 62743–62767. External Links: Link Cited by: §1. Appendix A Related Work A.1 Cost-Aware Routing Across Language Models A growing body of work studies how to exploit differences in the capabilities and costs of available language models. FrugalGPT considers prompt adaptation, model approximation, and cascades of language models to reduce inference cost while maintaining response quality [2]. RouteLLM learns a router from preference data to select between a stronger, more expensive model and a weaker, less expensive model [7]. AutoMix first queries a smaller model and uses self-verification together with a partially observable decision process to determine whether the query should be escalated to a larger model [1]. RouterBench and LLMRouterBench provide standardized datasets and evaluation frameworks for studying routing performance and performance–cost trade-offs across collections of language models [3, 4]. These approaches primarily treat routing as a selection problem in which a centralized controller assigns a query to one or more passive models. The routed models do not independently choose whether to execute, delegate, or reject a task. Our management formulation shares the objective of assigning simple tasks to inexpensive agents and difficult tasks to more capable agents, but it represents execution and delegation as actions within a Markov game. The resulting policy therefore describes not only which model should be used, but also which agent initiates the delegation and which delegation paths are feasible under the organizational structure Recent work has extended routing from single-step model selection to sequential decision making. Router-R1 formulates multi-model routing and aggregation as an RL problem in which an LLM router interleaves internal reasoning with model-invocation actions and receives a cost-aware reward [10]. MasRouter expands the routing problem to multi-agent systems by jointly determining a collaboration mode, assigning fixed roles, and selecting an LLM for each role using a cascaded controller [8]. These methods are particularly close to our cost-performance objective because they adaptively determine which model capabilities should be invoked rather than relying on a fixed cascade. Nevertheless, the router in these systems remains a centralized orchestrator that constructs or controls the multi-agent workflow. In our framework, delegation is instead endogenous to the participating agents. An agent may exercise its pretrained policy, delegate to another agent, or remain inactive, and the validity and outcome of these choices depend on the actions of the other agents. This formulation supports questions that are not represented by centralized routing, including whether a delegated agent accepts execution, how authority constrains delegation, how reciprocal behavior develops over repeated interactions, and how agents compensate one another for costly actions. A.2 Multi-Agent Reinforcement Learning for LLM Collaboration Recent studies have directly formulated LLM collaboration as a cooperative MARL problem. Liu et al. introduce Multi-Agent Group Relative Policy Optimization, or MAGRPO, which jointly fine-tunes multiple LLM agents using group-level feedback in multi-agent, multi-turn writing and coding tasks [6]. Their algorithm addresses the limitation that independently pretrained language models are not necessarily optimized to coordinate and demonstrates that collaborative behavior can be improved through a shared multi-agent training objective. In another work, CoLLM-C [5] uses a centralized critic during training, whereas CoLLM-DC uses decentralized critics. The comparison shows that Monte Carlo optimization and decentralized value estimation can perform well in relatively short-horizon, dense-reward tasks, while a centralized critic is more effective in long-horizon or sparse-reward settings. This work establishes centralized training with decentralized execution as a promising approach for optimizing LLM-agent collaboration and is directly relevant to the algorithmic implementation of multi-step delegation. MAGRPO and CoLLM are the closest prior works to ours in their use of MARL for multiple LLM agents. However, the learning targets are different. These methods primarily optimize the agents’ language-generation policies within a specified collaboration and execution protocol. Participating agents produce responses or actions according to their assigned roles, and MARL improves how effectively those agents collaborate. Our primary formulation instead learns a meta-policy over agents that already possess pretrained task policies. The meta-policy determines whether a particular pretrained policy should be exercised and whether execution should be delegated to another agent. Thus, MAGRPO and CoLLM optimize behavior within a collaborative arrangement, whereas our framework optimizes the delegation and activation structure governing which underlying capability is used. In other words, our framework can be utilized in conjunction with MAGRPO and CoLLM. The treatment of heterogeneity also differs. Existing LLM-MARL experiments may pair agents with different model architectures or complementary roles, but they do not primarily formulate heterogeneity as a capability; cost trade-off in which invoking a stronger policy incurs a larger execution cost. Our formulation explicitly associates the underlying agents with different policy quality and operating costs and learns when the additional capability of an expensive agent justifies its use. Moreover, our delegation policies may be restricted by management or delegation relationships, while the LLM-MARL methods above assume a predefined protocol describing which agents participate and how their outputs are combined. Finally, the two lines of work assign different roles to interaction history. In decentralized LLM collaboration, local trajectories and centralized information are useful for handling partial observability and estimating long-horizon returns. In our history-dependent game, previous actions, delegation choices, and transfers are also strategically meaningful. Agents may condition future behavior on whether another agent previously cooperated, accepted a costly task, or honored a payment. This distinction allows history to support reciprocity and intertemporal incentives even when the current environmental state is fully observable Closer to our terminology of delegation and contracts, Ivanov et al. combine deep RL with principal–agent contract theory so a principal can steer agents through outcome-contingent payments [ivanov2024principal], while Zhu et al. propose COMMAND, in which a principal LLM competitively delegates reasoning tasks to multiple agent LLMs [zhu2025command]. Relative to these lines, we focus on cost-aware management and graph-style delegation among frozen heterogeneous solvers, together with history-dependent reciprocity and transferable money inside a Markov-game wrapper. Appendix B Algorithm Finding History-dependent Policies 1 alg:time2-nash-vi Algorithm 1 Two-step Nash Equilibrium Value Iteration 0: Initial state x1x_1; state space S; action spaces AA_A and BA_B; transition probabilities P(x2∣x1,1)P(x_2 x_1, a_1); rewards rtir_t^i and for i∈A,B,t∈1,2i∈\A,B\,t∈\1,2\. 0: A deterministic history-dependent Nash equilibrium policy profile that maximizes agent B’s value. Define the set of feasible two-step histories: ℋ2=(1,x2):1∈,x2∈H_2= \( a_1,x_2): a_1 ,x_2 \ for each history h2=(1,x2)∈ℋ2h_2=( a_1,x_2) _2 do Define the two-step normal-form game by Q2i(h2,2)=r2i(x2,2),i∈A,B.Q^i_2(h_2, a_2)=r^i_2(x_2, a_2), i∈\A,B\. Compute the set of pure Nash equilibria ℰ2(h2)=2∈:Q2i(h2,(a2i,2−i))≥Q2i(h2,(a~2i,2−i)),∀a~2i∈i,∀i∈1,2,…,NE_2(h_2)= \ a_2 : array[]lQ^i_2 (h_2,(a^i_2, a^-i_2) )≥ Q^i_2 (h_2,( a^i_2, a_2^-i) ), ∀ a^i_2 _i,∀ i∈\1,2,…,N\\\[2.84526pt] array \ end for Enumerate all deterministic continuation selectors σ2:ℋ2⟶ _2:H_2 satisfying σ2(h2)∈ℰ2(h2),∀h2∈ℋ2 _2(h_2) _2(h_2), ∀ h_2 _2 Initialize the set of candidate equilibrium policy profiles: ←∅C← for each continuation selector σ2∈2 _2 _2 do for each joint action 1∈ a_1 at t=1t=1, do Compute the continuation value Wiσ2(x1,1)=∑x2∈P(x2∣x1,1)r2i(x2,σ2(1,x2)),∀iW_i _2(x_1, a_1)= _x_2 P(x_2 x_1, a_1)r^i_2\! (x_2, _2( a_1,x_2) ),∀ i Compute the induced utilities at t=1t=1 Q1i,σ2(x1,1)=r1i(x1,1)+Wiσ2(x1,1)Q^i, _2_1(x_1, a_1)=r^i_1(x_1, a_1)+W_i _2(x_1, a_1) end for Find the set of pure Nash equilibria of the induced game at t=1t=1: ℰ1(σ2)=1:Q1i,σ2(x1,(a1i,1−i))≥Q1i,σ2(x1,(a~1i,1−i)),∀a~1i∈i,∀iE_1( _2)= \ a_1: array[]lQ_1^i, _2 (x_1,(a_1^i, a_1^-i) )≥ Q_1^i, _2 (x_1,( a_1^i, a_1^-i) ), ∀ a_1^i _i,∀ i array \ for each 1∈E1(σ2) a_1∈ E_1( _2) do Construct the equilibrium policy profile π=(1,σ2)π= ( a_1, _2 ) Set Viπ(x1)=Q1i,σ2(x1,1),∀i,∀x1∈,∀πV_i^π(x_1)=Q^i, _2_1(x_1, a_1), ∀ i,∀ x_1 ,∀π Add π to C end for end for Select π∗=argmaxπ∈‖Viπ‖1π^*= _π \|V_i^π\|_1 return π∗π^* and its equilibrium value Viπ,∗i=1N)\V_i^π,*\_i=1^N) Appendix C Proof of Theorem 1 Proof. We prove by showing that none of the agents i prefers to deviate from the output policy π∗π^* at any time step t=1t=1 and t=2t=2. Without the loss of generality, suppose that agent i changes its policy in both steps. Instead of adopting π1i,∗(x1)=a1i,∗ and π^i,*_1(x_1)=a^i,*_1 and π2i,∗(x2,1)=a2i,∗ π^i,*_2(x_2, a_1)=a^i,*_2 The agent takes a~1i and a~2i,a~ti≠ati,∗, and a~ti∈i,t∈1,2 a^i_1 and a^i_2, a_t^i≠ a_t^i,*, and a_t^i _i,t∈\1,2\ separately in two steps. We denote the deviated joint action at time step t as ~t=(a~ti,t−i) a_t=( a_t^i, a^-i_t). Then, there will be a worse or equal reward for the second time step for agent i for every possible history h2h_2, i.e., Q2i(h2,~2)≤Q2i(h2,2∗).Q_2^i (h_2, a_2 )≤ Q_2^i (h_2, a^*_2 ). Then, the continuation values for agent i become worse for every possible first-step action 1 a_1, r2i(x2,~2)≤r2i(x2,2∗) r_2^i(x_2, a_2)≤ r_2^i(x_2, a_2^*) (3) ⇒ Wiσ~(x1,1)≤Wiσ∗(x1,1), W_i σ(x_1, a_1)≤ W_i^σ^*(x_1, a_1), where σ~(1,x2)=~2) σ( a_1,x_2)= a_2), and σ∗(1,x2)=2∗σ^*( a_1,x_2)= a^*_2. The agent i also deviates from a1i,∗a_1^i,* to a~1i a_1^i, then we compare the utilities of it at t=1t=1 if it deviates from 1∗ a_1^* found by Algorithm 1. Q1i,σ∗(x1,1∗)−Q1i,σ~(x1,~1) Q_1^i,σ^*(x_1, a_1^*)-Q_1^i, σ(x_1, a_1) =r1i(x1,1∗)+Wiσ∗(x,1∗)−r1i(x1,~1)−Wiσ~(x1,1~) =r_1^i(x_1, a_1^*)+W_i^σ^*(x, a_1^*)-r_1^i(x_1, a_1)-W_i σ(x_1, a_1) =r1i(x1,1∗)+Wiσ∗(x,1∗)−Wiσ~(x1,1∗)+Wiσ~(x1,1∗) =r_1^i(x_1, a_1^*)+W_i^σ^*(x, a_1^*)-W_i σ(x_1, a_1^*)+W_i σ(x_1, a_1^*) −r1i(x1,~1)−Wiσ~(x1,1~) -r_1^i(x_1, a_1)-W_i σ(x_1, a_1) =[(r1i(x1,1∗)+Wiσ~(x1,1∗))−(r1i(x1,~1)+Wiσ~(x1,1~))] =[ (r_1^i(x_1, a^*_1)+W_i σ(x_1, a^*_1) )- (r_1^i(x_1, a_1)+W_i σ(x_1, a_1) )] +(Wiσ∗(x,1∗)−Wiσ~(x1,1∗)) + (W_i^σ^*(x, a_1^*)-W_i σ(x_1, a_1^*) ) Since 1∗ a_1^* is the Nash equilibrium action of the first step found by the algorithm, we know that by adopting the same continuation selector σ~ σ, the first big term is greater than 0, and we already proved that the second term is greater than 0 in (3). Therefore Q1i,σ~(x1,~1)≤Q1i,σ∗(x1,1∗),Q_1^i, σ(x_1, a_1)≤ Q_1^i,σ^*(x_1, a_1^*), and we prove that no agent i wants to deviate from the Nash equilibrium policy π∗π^* found by Algorithm 1. ∎ Appendix D Implementation details for the GSM8K studies This appendix collects protocol details for Subsections 3.1–3.2 that are omitted from the main text for space. Nothing here changes the reported numbers; it only records how those numbers were produced (needed for reproducibility). Why GSM8K. We evaluate on GSM8K [cobbe2021gsm8k] (main split), a public grade-school math word-problem benchmark with reference solutions. We use GSM8K because (i) free-form answers can be checked against a gold solution, (i) the corpus is large enough to carve out a fixed ability-map bank, a training pool, and the official test holdout, and (i) accuracy varies sharply across our three frozen solvers, so cost–accuracy trade-offs are meaningful. Solvers and synthetic prices. We use three frozen solvers: Nemotron 3 Ultra (A), Llama 3.2 3B Instruct (B), and Llama 3.2 1B Instruct (C). Only the coordinator π is trained (centralized DQN). Synthetic token prices ($/1M input/output) are $1.00/$3.00 1.00/ 3.00 for Ultra, $0.25/$1.50 0.25/ 1.50 for Llama 3B, and $0.05/$0.10 0.05/ 0.10 for Llama 1B; these are experimental parameters, not live provider invoices. Offline preprocessing. Before any RL training, each solver answers eligible GSM8K items once, and we record measured token usage. Separately, we ask Nemotron 3 Ultra to mark each stored answer as correct or incorrect relative to the GSM8K reference solution. This is an offline labeling step used to measure solver accuracy and to score cached training episodes. Listings 1–2 summarize the corresponding preprocessing and training entrypoints; the full scripts are provided in the code-and-data supplementary ZIP (not via a web URL). Using Ultra both as one of the three solvers and as this offline labeler is a practical choice rather than a modeling requirement. A separate model (for example GPT-5.5 or GLM-5.2) could have done the same labeling job; we used Ultra because it was available to us at negligible additional cost, and because checking free-form answers against the GSM8K reference is a narrow comparison task. On a hand-checked sample of 200200 items, Ultra’s labels agreed with our judgments in every case, so we used it for the full offline labeling pass. On a held-out development bank, the resulting accuracies are about 96.7%96.7\% for Ultra, 84.5%84.5\% for Llama 3B, and 53.7%53.7\% for Llama 1B. Tokens spent on this offline labeling are excluded from the step cost used by π. From GSM8K main, 10001000 official-train items form a fixed ability map (empirical success rates by difficulty and solver). The remaining 64736473 training items are used to train π, and the official test set (13191319) is held out. Cached answers and correctness labels are reused throughout training so that policies facing the same question see the same solver outputs. In particular, we do not call the solvers or a live labeler at every RL step: π reads the already-cached offline answers and labels, which makes the GSM8K coordinator experiments reproducible. Training protocol, seeds, and baseline. An episode contains 3232 questions. A question may be retried up to three times; after three failures the environment advances with penalty −1-1. We use γ=0.99γ=0.99, cost weight λ=100λ=100, and 10001000 training episodes. Each GSM8K study reports mean± over 2020 independent runs with seeds 0,1,…,19\0,1,…,19\; for seed s we set the environment, NumPy, and PyTorch RNGs from s before training. Figures in the main text use the ability-map observation; a paired no-map run gives nearly the same aggregates and is summarized in the tables. Both GSM8K studies use a handoff fee rate α=0.05α=0.05 (defined per subsection). The always-Ultra baseline sends every question to Ultra with no handoff to B or C, under the same caches and the same cost accounting as the learned policy in that subsection. Hyper-parameters and selection. Table 3 lists the final coordinator settings shared by both GSM8K studies (delegation uses 189189 discrete joint actions instead of 33). During development we fixed the environment protocol early (episode length 3232, three retries, λ=100λ=100, α=0.05α=0.05, γ=0.99γ=0.99) after small sanity runs and retained a standard DQN schedule (Adam learning rate 10−310^-3, ε decay 1→0.051\!→\!0.05 over 20,00020,000 gradient steps, replay buffer 80,00080,000, target sync every 200200 updates, hidden size 128128). We did not run a large grid search; all reported seeds use this single final configuration. Hyper-parameter Value Optimizer / learning rate Adam / 10−310^-3 Discount γ 0.990.99 Cost weight λ / handoff fee α 100100 / 0.050.05 Episodes × questions/episode 1000×321000× 32 Max attempts per question / fail penalty 33 / −1-1 Hidden size / batch / replay buffer 128128 / 3232 / 80,00080,000 Target sync / ε schedule every 200200; 1→0.051\!→\!0.05 over 2020k steps Seeds 0–1919 Table 3: Final DQN / environment hyper-parameters for the GSM8K management and delegation studies. Compute. Coordinator training ran on NVIDIA A100-SXM4-80GB GPUs under Linux, using Python 3.103.10, PyTorch 2.5.12.5.1 (CUDA 12.112.1 wheels), NumPy, Gymnasium, and HuggingFace transformers for local Llama solves and caches. Each seed used a single A100; offline Ultra labeling used API calls and is excluded from the step cost charged to π. Management reward terms. In Subsection 3.1, the shared step reward is r=Rcorr−λCsolve(aexec)−λCedge(ne,aexec)+Rfail.r\;=\;R_corr\;-\;λ\,C_solve(a_exec)\;-\;λ\,C_edge(n_e,a_exec)\;+\;R_fail. Here Rcorr∈0,1R_corr∈\0,1\ is one if the chosen solver’s cached answer is correct under the offline Ultra labels above, and zero otherwise; Csolve(aexec)C_solve(a_exec) is that solver’s synthetic token cost; nen_e is the number of handoffs on the chosen route (0, 11, or 22); Cedge(ne,aexec)=neαCsolve(aexec)C_edge(n_e,a_exec)=n_e\,α\,C_solve(a_exec) with α=0.05α=0.05 is a small fee for each handoff; λ=100λ=100 scales the dollar costs into the reward; and Rfail=−1R_fail=-1 only after three failed attempts on the same question. In short, we pay for answering and also pay a little for each pass down the chain. Delegation cost accounting. In Subsection 3.2, we count the attempt as successful if any answering agent is correct under the offline Ultra labels, and we charge the sum of those agents’ solve costs. In addition, each kickoff handoff and each peer pass pays a small edge fee of α=0.05α=0.05 times the recipient’s expected solve cost, matching the handoff fee used in the management study. Always-Ultra is evaluated in the same graph environment, so it also pays the kickoff edge fee when Ultra is started. Code and entrypoints. Listings 1–2 summarize the offline pipeline and DQN entrypoints; the full scripts are in the code-and-data supplementary ZIP. ⬇ 1# Offline GSM8K preprocessing (conceptual; full scripts in code release) 2items = load_gsm8k_main() # Cobbe et al., GSM8K main 3label, train, test = split(items, 4 label_n=1000, seed=0) # test = official 1319 5for solver in [Ultra, Llama3B, Llama1B]: 6 cache[solver] = answer_once(label + train + test) # store tokens 7for (q, ans) in all_cached_pairs(cache): 8 judge[q, ans] = Ultra_marks_vs_gold(q, ans) # offline only 9ability_map = success_rates(label, judge) # difficulty x solver 10# RL samples from train caches; judge tokens excluded from step cost Listing 1 Offline preprocessing used before both GSM8K RL studies. ⬇ 1# Coordinator training entrypoints (seed S in 0..19; PYTHONPATH=src) 2python experiments/exp21_management/run_train.py \ 3 --config configs/exp21/cache_dqn_v1_run3.yaml --seed S 4python experiments/exp22_delegation/run_train.py \ 5 --config configs/exp22/dqn_v2_edge_fee_with_map.yaml --seed S 6# Warm/label helpers: run_warm_cache.py, run_label.py, 7# run_build_ability_map_local.py (same experiments/ tree) Listing 2 Training and preprocessing entrypoints for the GSM8K studies.