Who is Helping Whom? Analyzing Inter-dependencies to Evaluate Cooperation in Human-AI Teaming Upasana Biswas, Vardhan Palod, Siddhant Bhambri, Subbarao Kambhampati Abstract State-of-the-art methods for Human-AI Teaming and Zero-shot Cooperation focus on task completion i.e. task rewards, as the sole evaluation metric while being agnostic to ‘how’ the two agents work with each other. Furthermore, subjective user studies only offer limited insight into the quality of cooperation existing within the team. Specifically, we are interested in understanding the cooperative behaviors arising within the team when trained agents are paired with humans - a problem that has been overlooked by the existing literature. To formally address this problem, we propose the concept of constructive interdependence - measuring how much agents rely on each other’s actions to achieve the shared goal - as a key metric for evaluating cooperation in human-agent teams. We interpret interdependence in terms of action interactions in a STRIPS formalism, and define metrics that allow us to assess the degree of reliance between the agents’ actions. We pair state-of-the-art agents HAT with learned human models as well as human participants in a user study for the popular Overcooked domain, and evaluate the task reward and teaming performance for these human-agent teams. Our results demonstrate that although trained agents attain high task rewards, they fail to induce cooperative behavior, showing very low levels of interdependence across teams. Furthermore, our analysis reveals that teaming performance is not necessarily correlated with task reward, highlighting that task reward alone cannot reliably measure cooperation arising in a team. 1 Introduction Achieving zero-shot cooperation (ZSC) to build agents capable of working with a wide range of partners remains a long-withstanding challenge in cooperative AI. This capability is particularly important in the setting of human-agent teaming (HAT) to develop agents that must interact and work alongside humans. Popular approaches in these settings use cooperative reinforcement learning, where agents learn with limited set of training partners and generalize these skills to collaborate with previously unseen partners during deployment. Performance of these agents when paired with a partner are commonly evaluated using metrics such as mean episode rewards over multiple runs ( Yu et al. 2023 ; Strouse et al. 2022 ; Lou et al. 2023 ) or the time-steps taken to complete the task in the environment ( Sarkar et al. 2023 ; Zhao et al. 2022a ) . However, evaluating a team using metrics which measure only the task reward obscures critical details about the performance of the individual teammates and the interactions that arise between them, especially in cases where they can successfully complete the task without necessarily cooperating with each other. This becomes a particularly worrisome problem when these agents are paired with human teammates, where the human may pick the slack of the non-performing AI teammate and still be able to complete the task efficiently. Figure 1 : Depicted are two strategies to fill a pot with onions in a cooking game. The coordinated strategy (right) is more efficient than the individual strategies (left), but runs the risk of failure if cooperation is not achieved. Here, we borrow from the distinction introduced in ( Zhang et al. 2016 ) , Required cooperation (RC) refers to scenarios where the participation of all team members is necessary to achieve the shared goal whereas non-required cooperation (Non-RC) describes settings where each individual can achieve the goal independently, without relying on the contributions of other teammates. For example, consider a human-agent team working in the environment layout shown in Figure 1 from the Overcooked Game. The players act together in the environment to cook and deliver soups by collecting onions, cooking them in a pot, transferring the soup to a dish, and delivering it at the serving station. The participation of both players is not required to complete the task. The team could complete the task using a strategy with minimal interactions between the teammates, such as one where only the human is completing the task and the agent is merely staying out of the human’s way. The team could also be using a strategy where the human and the agent interact and collaborate with each other by using the passing counter to pass onions. Using only the task reward to evaluate the performance would assign the same reward to both teams regardless of their teaming performance. Therefore, in non-RC settings, the task performance is not representative of the teaming performance. This raises a natural question: what is the value of cooperation in settings where it is not strictly required to achieve the goal? To answer this question, it is important to note that ZSC agents are supposed to adapt their behavior and do the best response to diverse partner policies, including those that involve coordination between the teammates. For non-RC settings, Matignon et al. 2012 ; Fulda and Ventura 2007 describe the shadowed equilibrium problem in cooperative RL when there are multiple equilibria (since there are exist multiple way to achieve the task in a non-RC setting, including the agents doing the task independently vs working together). This brings about a persistent challenge in cooperative reinforcement learning is that, during training, agents may fail to encounter cooperative strategies—leading them to converge on behaviors that do not require coordination ( Lerer and Peysakhovich 2019 ) . This creates a significant risk of miscoordination in the ad hoc setting of zero-shot cooperation and human-agent teaming. For instance, in Fig. 1 , if one player attempts to follow a cooperative policy—such as passing the onion—but their partner defaults to an uncoordinated strategy, the result is a coordination failure ( Carroll et al. 2020 ) . Focusing on only the task reward to evaluate the performance of a ZSC agent hides this fundamental failure of the agent—specifically, the inability of the agent to engage in cooperative behavior when paired with a partner wants to cooperate. Such failures are especially damaging in human-agent teaming, where an agent’s failure to reciprocate or respond to cooperative intent can erode human trust, harm team cohesion, and degrade overall performance ( ) . Therefore, to truly assess the capabilities of ZSC agents, especially when they are used for human-agent teaming, it is imperative to evaluate their teaming performance—not just their task success. Only by measuring how well agents cooperate with diverse partners can we develop robust, generalizable solutions for real-world human-agent collaboration. In an effort to measure cooperative behavior in a team, we focus on a specific form of cooperation in teams characterized by structured interdependence among team members, as introduced in ( Johnson et al. 2020 ) . Such interdependence is central to many real-world human-agent teaming applications, as seen for the domains of Urban Search and Rescue ( Pateria et al. 2019 ) , collaborative trash removal ( Ghavamzadeh et al. 2006 ) , and multi-agent predator-prey systems ( Wu et al. 2023 ; Barton et al. 2018b ) . Four types of task interdependence have been identified in the study of teamwork: pooled, sequential, reciprocal, and team interdependence ( Verhagen et al. 2022 ; Singh et al. 2016 ; Singh et al. 2014 ) . In this work, we focus on measuring the sequential and reciprocal interdependencies arising in human-agent teams. We propose a novel metric for measuring such interdependencies between a human and an agent working as a team, which can be used as a quantifiable measure of cooperation. We map a two-player Markov Game to a symbolic STRIPS formalism, introducing symbolic structure to the world states and the actions, allowing tracking of the interdependencies within the players in a human-agent team. We pair state-of-the-art methods trained for zero-shot cooperation and human-agent teaming for the Overcooked domain with human teammates in a user study, as well as with a learned human model Wang et al. 2024a . While our metric is generalizable to any domain, we choose Overcooked because it is a popular benchmark for testing cooperation in multi-agent and human-agent teams, leading to the development of numerous approaches for zero-shot cooperation and human-agent teaming in this domain ( Strouse et al. 2022 ; Carroll et al. 2020 ; Zhao et al. 2022b ; Yu et al. 2023 ; Li et al. 2024 ) , thus making it a good testbed for assessing the current state-of-the-art. We use the proposed metrics to comprehensively evaluate the teaming performance of these human-agent teams. Using this metric, we are trying to answer the following research questions: 1. Are ZSC agents capable of engaging in cooperative behavior when paired with partners that attempt to initiate cooperation? 2. How much cooperative behavior is induced in teams when these agents are partnered with human teammates in non-RC settings? 3. How does the degree of cooperative behavior vary when these agents are paired with human teammates in Required Cooperation (RC) versus Non-Required Cooperation (Non-RC) settings? 4. To what extent do these agents initiate cooperative behavior in human-agent teams, and how effectively can they recognize and respond to cooperative intent when it is initiated by the human partners? Our results show that ZSC agents are unable to induce/respond to cooperative behavior when paired with partners that attempt to initiate cooperation. Even when the partner follows a known coordination policy, agents don’t respond to interdependencies initiated by the partner. In Non-RC settings, human-agent teams often achieve high task rewards, but are accompanied by minimal constructive interdependencies, indicating a lack of cooperation arising in these teams. In contrast, in RC settings, higher task rewards are consistently aligned with higher constructive interdependencies. Across all settings, ZSC agents seldom initiate interdependencies themselves and don’t respond to those initiated by human teammates. Overall, ZSC agents lack the ability to respond to, or initiate cooperative behaviors in settings where cooperation is helpful but not enforced. 2 Related Works Previous works in human-agent teaming use task performance or episodic reward ( Strouse et al. 2022 ; Yu et al. 2023 ; Zhao et al. 2022b ; Li et al. 2024 ; Wang et al. 2024a ; Lou et al. 2023 ) to evaluate the team’s performance. ( Zhao et al. 2022a ; Knott et al. 2021 ; Fontaine et al. 2021 ) emphasize the significance of designing different metrics for evaluation such as collaborative fluency, robot and human idle time etc. ( Zhao et al. 2022a ) and subjective user studies to measure trust, engagement and fluency of the agents when paired with a human ( Zhao et al. 2022a ; Ma et al. 2022 ; Nalepka et al. 2021 ) . However, such metrics depend heavily on specific environment layouts and task structures. Subjective user studies only offer limited insight into the quality of cooperation existing within the team. In contrast, the proposed metric of interdependence is generalizable across domains. Zhang et al. 2024 capture outcomes and certain aspects of the collaboration process such as contribution rate, individual effort, communication frequency whereas Bishop et al. 2020 uses action-based metrics like Productive Chef Actions (PCA), PCA duration, and Chef Role Contribution (CRC) to quantify individual effort and role distribution during task execution. Ries et al. 2024 uses the team member contribution calculated as the difference between the relative proportion of tasks completed by humans versus AI agents. While these metrics measure the contribution of the agents to the task, they do not measure the underlying cooperative dynamics or the structural task dependencies between the actions of the team members. We discuss and compare the interdependence metric with the evaluation presented by Wang et al. 2025 , who examine how human-agent teams adapt and evolve over time, focusing on the dynamic processes that shape team interactions and outcomes. Aspects of team formation such as shared goals and team acceptance are measured through subjective perception ( Liang et al. 2019 ) , whereas the interdependence metric can objectively reveal whether team members are acting in ways that enable or anticipate each other’s contributions. Successful creation and fulfillment of interdependencies indicate role adherence ( Wang et al. 2024b ) , team trust and coordination ( Moran et al. 2013 ; Cai et al. 2019 ) . Johnson et al. 2014 ; Johnson et al. 2020 places interdependence at the center of their model for designing human-machine systems, making it the organizing principle around which the rest of the team’s structure and behavior revolves. Barton et al. 2018a ; Wu et al. 2023 ; Barton et al. 2018b leverage Convergent Cross Mapping (CCM) to measure causal influence between time-series of agent actions, primarily focusing on low-level motion coordination. In contrast, our approach aims to capture more structured and symbolic task interdependencies. Verhagen et al. 2022 ; Singh et al. 2014 have identified four primary types of task interdependence in human-agent teams: pooled, sequential, reciprocal, and team interdependence. Pooled interdependence involves team members working independently without interaction, while sequential interdependence requires tasks to be performed in order. Reciprocal interdependence requires team members taking turns to complete portions of a task, and team interdependence involves concurrent execution of individual tasks with potential joint actions. We define interdependence when the effect of one agent’s action satisfies the precondition of another’s, modeled through a STRIPS-based formalism. This allows us to identify both unidirectional (sequential) and bidirectional (reciprocal) dependencies. 3 Preliminaries 3.1 Two-Player Markov Game A two-player Markov game for a human-AI cooperation scenario can be defined as \langle S,A,T,R\rangle where S is the set of world states, A:A_{1}\times A_{2} where A_{i} is set of possible actions for agent i, T:S\times A_{1}\times A_{2}\rightarrow S is the transition function mapping the present state and the joint action of the agents to the next state of the world, R_{i}:S\times A_{1}\times A_{2}\rightarrow R_{i} is the reward function mapping the state of the world and the joint action to the global reward. For a 2-player cooperative markov game, R=R_{1}=R_{2} where R is the global environment reward function. The joint policy is defined as \pi=\left(\pi_{1},\pi_{2}\right) where the policy \pi_{i}:S\rightarrow A_{i} is defined for an agent i over set of possible actions A_{i} . The objective of each agent i is to maximize the expected discounted return \mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}R(s^{t},a^{t}_{1},a^{t}_{2})\right] by following the policy \pi from a given state. Therefore, the policy \pi is learned by optimizing the task reward received by the agents from the environment. 3.2 Multi-Agent Planning Problem A STRIPS problem is represented as \langle P,A,I,G\rangle where P is the set of propositions which can be used to denote facts about the world, A is the set of planning actions, I is the initial state and G is the goal state. Each fluent p\in P is a symbolic, variable that describes the current state of the environment, with each proposition representing a specific property of an object in the world. The possible fluents for the Overcooked environment can be counter-empty - describes whether the counter is empty or not, pot-ready - indicates whether the soup is ready in the pot, soup-served - indicates whether the soup has been served at the serving station etc. I denotes the propositions representing the initial state of the world and G denotes the propositions corresponding to the goal state of the world. A planning action can be defined as a=<\text{pre(a)},\text{add(a)},\text{del(a)}> where pre(a) is the set of propositions that must be true before the action can be executed, add(a) are the propositions that become true after the action is performed and del(a) are the propositions that become false after the action is performed. Extending this to multiple agents, a Multi-agent Planning task can be denoted as \langle P,N,\{A_{i}\}_{i=1}^{N},I,G\rangle where N is the number of agents and A_{i} is the set of actions for the agent i. We assume that the agents take turns to act and not in parallel. A plan is defined as a sequence of actions \left(\{a_{i}^{1}\}_{i=1}^{N},\{a_{i}^{2}\}_{i=1}^{N},\dots,\{a_{i}^{n}\}_{i=1}^{N}\right) where n is the number of steps in the plan. A plan is a solution \Pi if it is a sequence of actions that can be applied to the initial state I and results in a world state which satisfies G i.e. \Pi=\left(\{a_{i}^{1}\}_{i=1}^{N},\{a_{i}^{2}\}_{i=1}^{N},\dots,\{a_{i}^{n}\}_{i=1}^{N}\right) is a valid solution plan if \{a_{i}^{n}\}_{i=1}^{N}\left(\dots\dots\left(\{a_{i}^{2}\}_{i=1}^{N}\left(\{a_{i}^{1}\}_{i=1}^{N}\left(I\right)\right)\right)\right)\subseteq G 4 Interdependencies 4.1 Problem Statement We pose the human-agent teaming problem as a two-player Markov game, where the actions of the teammates take place sequentially. We focus on the case where the team is trying to reach a set of goal states S_{G} such that S_{G}\subseteq S . The states in S_{G} are absorbing i.e. \forall s\in S_{G} and a^{G}_{i}\in A_{i} , we have T(s,\{a^{G}_{i}\}_{i=1}^{2})=0 . We represent the solution trajectory for a single agent \tau_{i} as \tau_{i}=\left(a^{t}_{i},a^{t+1}_{i},\dots a^{k}_{i}\dots a^{n}_{i}\right) and the joint-action solution trajectory \tau of two agents starting from timestep t and reaching a goal state at timestep n as \tau=\left(\left(a^{t}_{1},a^{t}_{2}\right),\left(a^{t+1}_{1},a^{t+1}_{2}\right)\dots\left(a^{n}_{1},a^{n}_{2}\right)\right) . An execution trace Tr of a policy \pi from an initial state s^{t} as is denoted as \left(s^{t},a^{t},s^{t+1},a^{t+1},\dots s^{n}\right) , where Tr corresponds to the state-action sequence that starts at timestep t and terminates at a goal state s^{n}\in S_{G} at a timestep n , with a^{k}=\left(a^{k}_{1},a^{k}_{2}\right) and a^{k}_{i}=\pi_{i}\left(s^{k}\right) . The agents receive a task reward R_{\text{task}} at the end of Tr and \tau on reaching the goal state. We define our problem Given the execution trace Tr and the joint solution trajectory \tau of a team, we only receive R_{\text{task}} which does not represent how good or "cooperative" the solution trajectory \tau is. To capture the cooperative interactions arising between the teammates in \tau , we define the concept of interdependence in the next section. 4.2 Mapping the Markov Game to STRIPS In a Markov Game, the state at a current timestep s_{t}\in S is typically a high-dimensional vector. s_{t} can be denoted as a symbolic state with a set of true propositions p_{t} which denotes the current state of the world. Doing this, we effectively describe each state as a finite set of relevant symbolic facts. Therefore, there exists a function \mathcal{F}:S\rightarrow P mapping the states to symbolic propositions. Here, we refer to Fig. 1 . We consider the predicate counter-empty to denote if the middle counter is empty. We consider the transition when the green-hat agent ( A_{2} ) takes an action to place the onion on the counter. The state at which the agent performs this action has the proposition counter-empty set as True, while the action sets counter-empty as False in the next state. Therefore, mapping the state to a symbolic state helps us capture the effect of the agents’ actions in terms of relevant symbols. We can recall from the execution trace Tr of a Markov Game that the state of the world at time t is s^{t} . From s^{t} , taking action a^{t} causes the state of the world to change to s^{t+1} . We can map each transition \left(s^{t},s^{t+1},a^{t}\right) to the symbolic formulation with the help of \mathcal{F} . s^{t+1} can be represented as a set of true propositions p_{t+1} and s^{t} can be represented as p_{t} . Similarly, we now map the action a^{t}=\left(a_{1}^{t},a_{2}^{t}\right) to a symbolic representation. Recall that since the teammates take turns to play, a^{t}=\left(a_{1}^{t},\text{no-op}\right) or a^{t}=\left(\text{no-op},a_{2}^{t}\right) . For action a^{t}_{i} , there exists a mapping from \left(s^{t},a^{t}_{i},s_{t+1}\right) to a STRIPS style planning action such that \text{pre}\left(a^{t}_{i}\right)\subseteq p_{t},\text{add}\left(a^{t}_{i}\right)\subseteq p_{t+1} and \text{del}\left(a^{t}_{i}\right)\subseteq P\setminus p_{t+1} . Therefore, the solution trajectory \tau can be represented as a joint solution plan \Pi , where each single-agent action a_{i}^{t} in the trajectory can be represented as a_{i}^{t}=\left<\text{pre($a_{i}^{t}$)},\text{add($a_{i}^{t}$)},\text{del($a_{i}^{t}$)}\right> . This way we can track the preconditions and effects of the actions of individual agents in the trajectory as symbolic propositions and track the interdependencies between them. 4.3 Agent Interdependencies Given a joint-action solution trajectory \tau and the solution trajectory \tau_{i} for an agent i, we define the following properties about \tau and \tau_{i} to formalize the concept of interdependence for the solution trajectory: Definition 4.1 . For \tau , we define Interdependence Int as a pair of actions (a_{i}^{t_{0}+k},a_{j}^{t_{0}})_{i\neq j} such that add(a_{j}^{t_{0}})\subseteq pre(a_{i}^{t_{0}+k}) . An Interdependent pair of actions (a_{i}^{t_{0}+k},a_{j}^{t_{0}})_{i\neq j} has two agents, a Giver agent performing the action a_{j}^{t_{0}} and a Receiver agent performing the action a_{i}^{t_{0}+k} . Each interdependent pair of actions is going to be associated with an object \texttt{obj}_{int} . Definition 4.2 . For \tau_{i} , the set of Trigger actions is \texttt{Tr}_{i}=\left(a_{i}\mid\forall a_{j}\in A_{j}\cap j\not=i,\text{eff}\left(a_{i}\right)\subseteq\text{pre}\right) where a_{i}\in C_{i} . Definition 4.3 . For any object in the world and a starting timestep t_{0} , the object influence trajectory from time t_{0} , denoted by \tau_{\texttt{obj}}^{t_{0}} , captures all state transitions in the plan from timestep t_{0} onward where this object is involved. \tau_{\texttt{obj}}^{t_{0}}=\left\{(p_{t},a_{t},p_{t+1})\mid t\geq t_{0},\ \exists p\in\text{pre}(a_{t})\cup\text{add}(a_{t})\cup\text{del}(a_{t})\text{ where }\texttt{obj}\in\textit{O}(p)\right\} where \textit{O}(p) denotes the set of objects mentioned in proposition p . In other words, \tau_{\texttt{obj}}^{t_{0}} includes all transitions from timestep t_{0} onward where the object explicitly appears in the action’s conditions or effects. Also, we have p^{G}_{n} i.e. the set of goal predicates at the end of the trajectory. Here, other objects that are affected by obj can be captured in the state of that object. Definition 4.4 . An interdependence \texttt{Int}=(a_{i}^{t_{0}+k},a_{j}^{t_{0}})_{i\neq j} is a Goal Reaching Interdependence if the final state of the object associated with that interdependence ( \text{obj}_{\text{int}} ) is also present in the set of goal predicates. Using p^{\texttt{obj}_{\text{int}}}_{{\text{final}}} to denote the last entry in \tau_{\texttt{obj}_{\text{int}}}^{t_{0}} , I is a goal reaching interdependence if p^{\texttt{obj}_{\text{int}}}_{{\text{final}}}\subseteq p^{G}_{n} . Definition 4.5 . Let p^{\text{obj}}_{t} denote the predicate for that object at timestep t, therefore containing nformation about the state of obj at t. An interdependence \texttt{Int}=(a^{t_{0}+k}_{i},a^{t_{0}}_{j}) associated with object \texttt{obj}_{\text{int}} is said to be a Non-looping Interdependence if the following conditions hold: 1. The giver agent (agent j ), who gives the object \texttt{obj}_{\text{int}} at timestep t_{0} , does not receive the object back in the same state at any future timestep t>t_{0}+k : \nexists t>t_{0}+k,\ \text{s.t.}\ \text{agent }j\text{ receives }\texttt{obj}_{\text{int}}\text{ in the same state as at time }t_{0} 2. The receiver agent (agent i ), who receives the object at timestep k+t_{0} , did not have the object in that same state at any time t