Cognitive Insights and Stable Coalition Matching for Fostering Multi-Agent Cooperation

B-W1. Relatedly, looking through the actual LLM outputs included in the appendices, the level-2 ToM responses seem quite strange. They are worded as if they are predicated on the other agents actually observing actions in advance, rather than anticipating instructions. I am not really sure what is going on here, but reading through it was not at all surprising that the higher ToM agents performed less well on the task, as they appeared to be being mis-instructed.

R.B-W1. We sincerely thank the reviewer for these insightful technical points about ToM levels and agent interactions. We'll address each point:

• ToM implementation works recursively over multiple interactions. When we say "observing" in level-2 ToM responses, this refers to observing outcomes from previous interaction rounds to inform predictions about future actions of other agents. This creates a recursive reasoning chain:

  • Round 1: Initial beliefs
  • Round 2: Update beliefs based on Round 1 observations
  • Round 3: Further updates incorporating both previous rounds And so on...

• To make the exact format of beliefs and nested reasoning processes explicit, we expand our formulation to show the recursive structure for an LLM agent $i$ at cooperation round $R$ (This revision is updated in our manuscript page 4 & 5). We revise its $k$-level ToM function (Eq. 1) as:

  $\text{ToM}\_i^k(o\_i^{1:R}, \hat{a}\_{-i}^{1:R-1}, \\{b^{k-1}\_{i, R}(a\_m^R)\\}\_{m \neq i}) := b\_{i, R}^k$

  where:

  • $o_i^{1:R}$ represents agent $i$'s observation history up to round $R$, including current task state, self-actions, and collaborative teammates.
  • $\hat{a}_{-i}^{1:R-1}$ represents other agents' action history up to round $R-1$
  • $\\{b^{k-1}\_{i, R}(a\_m^R)\\}\_\{m \neq i\}$ captures agent $i$'s prediction of agent $m$'s action at round $R$ based on $(k-1)$-level ToM reasoning: $b^{k-1}\_{i, R}(a\_m^R) = p(a\_m^R | \text{ToM}\_i^{k-1}(o\_i^{1:R}, \hat{a}\_{-i}^{1:R-1}, \\{b^{k-2}\_{i, R}(a\_l^R)\\}\_{l \neq i}))$

• Moreover, we want to emphasize that our core contribution is the coalition formation mechanism as a plug-and-play approach for improving multi-agent cooperation, rather than establishing fundamental properties of ToM levels.

A-W1. The authors start by talking about the set of an agent $i$'s partners $\mu(i)$, but based on their matching algorithm they seem to implicitly assume that $\mu(i)$ is always a singleton (see Equation 2). Otherwise, matchings are stable only when player $i$ would not prefer to be partnered with $j$ over its current set of partners $\mu(i)$. But what would that mean? Are preferences between sets of agents instead of single agents? If so, the relevant comparison would presumably be that agent player $i$ would not prefer to be partnered with any set of other agents over its current set of partners $\mu(i)$.

R.A-W1. Matching Implementation: We sincerely think the reviewer’s thoughtful feedback on the formulation. In our original manuscript, we focus on a one-to-many matching structure, specifically motivated by the Project Manager (PM) and Engineers scenario: PM Role (One Side, Single PM with ToM capabilities) and Engineer Role (Many Side). In our implementation, we enforce a minimum coalition size to ensure effective cooperation. We maintain $|\mu(i)| \geq k$, where k is a predefined #min_coalition_size -1 (typically #min_coalition_size=$\lceil N/2 \rceil$ in our setting, where N is the total number of agents in our experiments).

Generalization to Other Settings. We acknowledge that our implementation also considers other scenarios (like debates where Equal-role agents are forming teams). To accommodate both hierarchical and peer-based scenarios, we propose a generalized formulation adapted to our implementation:

• Preference Structure: For agent $i$, preferences over coalitions are defined by belief-action alignment scores: $B\_i(S) = \frac{1}{|S|} \sum\_{j \in S} \phi(b^k\_i(a\_j) - \hat{a}\_j)$ For two potential coalitions S$$_1, S_2: $S\_1 \succ\_i S\_2 \Leftrightarrow B\_i(S\_1) < B\_i(S\_2)$
• Stability: A matching $\mu$ is stable if there exists no blocking coalition $C \subseteq N$ where: (1). $|C| > k$ (minimum size requirement) (2). $\forall i \in C: C \succ\_i \mu(i)$ (coalition preferred by all members)
• Generalization: we discuss the specialized scores in PM and Eng setting in Appendix C.1, where specialized ability scores primarily influence the PM, since effective leadership and coordination capabilities are crucial (as also evidenced by extensive evaluation in Appendix F.3, which detailed in our response R.B-W2.)

We updated our manuscript according to the reviewer's constructive feedback, detailed on pages 5 & 6, highlighted in purple color.

A-W2. The preference order described in equation 4 are based on agents having different skill levels $\alpha_i$ on different tasks, but where do these skill levels come from? More importantly, if the point is to match agents with complementary skills, why does the matching algorithm only compare agents' skills on a single task?

We will clarify the reviewer's concert point by point:

1. Source of Skill Levels ($\alpha_j$): The skill levels come from agents' self-assessment based on their assigned roles and capabilities. For example, in the programming task, an Engineer with testing expertise = 0.9 for testing tasks.
2. Our current work focuses on one task-specific requirement in each (cooperation) round. For instance: If the current agent i needs testing expertise:
   • $\alpha_j$_testing (0.9) > $αₘ$_testing (0.5)
   • We will extend our work by incorporating multi-task skill vectors in the future.

I thank the authors for their very comprehensive response, which has addressed many of my questions and concerns. Below, I include a few final questions and comments.

In all cases, we form one coalition including #min_coalition_size = ⌈N / 2⌉, i.e., 3 agents (task 1) or 2 agents (task 2 & 3). The coalition produces the final output, whether it's code, debate arguments, or reasoning solutions.

This was very helpful to my understanding as previously I assumed that multiple coalitions were involved in solving a given problem. The reasoning behind my interpretation is that:

• The authors' refer to forming multiple coalitions, and their algorithm is a "matching algorithm", where it is implied that agents are matched together to form (multiple) coalitions.
• In (cooperative) game theory, coalition formation refers to the process of partitioning a set of agents into (multiple) coalitions.

This, however, also raises several more questions and concerns for me as a reviewer.

1. First, and this is very minor, if there is only ever one coalition that is used in solving the task, I suggest that the authors drop the phrase "coalition formation" and replace it with something more fitting such as "team selection". If nothing else they should state very clearly very early on in the paper that when they talk about coalition formation, it is about selecting a subgroup of the agents to complete the task, not about partitioning the agents (all of whom then complete the task).
2. The algorithm for finding multiple coalitions now seems like overkill, because it sounds like it is only required to output a single coalition of a size greater than some constant #min_coalition_size where all the agents in the coalition have sufficiently strong belief alignment (with the option to also incorporate skill levels). Do the authors have an argument for why we can't do something simpler?
3. In the experimental baselines, which agents solve the task? E.g. if there is one PM and five engineers, do all five solve the task, or is some random sub-group of size #min_coalition_size selected to solve the task, or something else? This is also important if task skills are incorporated into coalition formation, because if this consideration is not taken into account in the baseline then it is unclear whether simply selecting the most skilled agents is actually what helps them to perform the task better.

I also appreciated the updates to the paper regarding the algorithm for finding coalitions/teams, though I still have a few concerns. First, the authors state that when agent $i$ signals a desire to rematch (in line 9 of Algorithm 1), the algorithm:

• Triggers a new cooperation round and updates the preference orders based on the latest belief-action alignments
• If a stable matching is found, proceed with the new coalitions
• If no stable matching is found, keep the current coalitions for one more round

My questions regarding this are as follows:

1. Why would the preference orders need to be updated? Why have the belief-action alignments been updated?
2. The authors claim that their algorithm computes a stable matching. How then, is the final step ever to be executed? Moreover, even if no stable matching is found, how would running the matching process for one more round help?

I appreciated the point about using the $\epsilon$ tolerance to reduce the search space of coalitions, but I would suggest the authors to explicitly mention what happens in this instance in the paper.

Finally, in equation (2) the the belief operator $b^k_i$ applies to a single agent's action $a_j$ (and similarly in line 3 of Algorithm 1). In line 9 of algorithm 1, however it is applied to $a_{\mu(i)}$, which presumably refers to the joint action of the agents $j \in \mu(i)$. Can the authors please explain what is going on here? Why not just use $B_i((\mu(i))$ on line 9?

I also appreciated the updates to the paper regarding the algorithm for finding coalitions/teams, though I still have a few concerns. First, the authors state that when agent $i$ signals a desire to rematch (in line 9 of Algorithm 1), the algorithm:

Triggers a new cooperation round and updates the preference orders based on the latest belief-action alignmentsIf a stable matching is found, proceed with the new coalitionsIf no stable matching is found, keep the current coalitions for one more round

QB1: Why would the preference orders need to be updated? Why/have have the belief-action alignments been updated?

R.QB1. To clarify, the update preference order is not specific to “rematching”, its a standard procedure for “a new cooperation round.” In each new round, the beliefs are updated due to last round updated execution/actions.

QB2: The authors claim that their algorithm computes a stable matching. How then, is the final step ever to be executed? Moreover, even if no stable matching is found, how would running the matching process for one more round help?

R.QA2: Stable Matching and One Round Continuation

• This one more round serves as an adaptation period where alignment scores may naturally improve.

Comprehensive Example: Let us explain why continuing one more round can help through a detailed example:

Initial State (Round t):

Agents: PM, E1, E2, E3
Current Coalition: {PM, E1, E2}
PM's Beliefs & Alignment Scores:
- E1: 0.7 (misaligned)
- E2: 0.6 (misaligned)
**E1, E2 Rematch signal (broadcast information)**

Why Continue One Round?

1. Adaptation Phase (Round t+1):

   • During continued round (given the rematch messages):
   • E1 & E2 knows his last action causes rematch signal
   • E1 & E2 may adapt current action
   • Updated Alignment Scores if actions are adapted:
   • E1: 0.7 → 0.4 (improved)
   • E2: 0.6 → 0.3 (improved)

2. Next Matching Attempt (Round t+2):

   • Coalition {PM, E1, E2} now has better alignment
   • No need to rematch.

Key Insight:

Without this continuation round, we would miss the opportunity for cognitive agents to adapt in subsequent rounds. This reflects the dynamic nature of cognitive agent cooperation, where temporary stability can lead to improved matching conditions.

• We add intuition for this rematching design in our updated manuscript Lines 303-305, and revise the Algorithm 1 to be more detailed.

We thank reviewer P68Z's recognition of our paper's clear motivation, novelty and promising results.

We address specific concerns below point by point:

W1. The ToM formulation presented in Section 4.1 deviates from the common definition of higher-order ToM. When conducting recursive ToM inferences at level-k, agents are only given their own belief at level-(k-1) rather than the beliefs of other agents. I recommend that the authors refer to [1] for its definition of higher-order mental state inference.

R1. We would like to thank the reviewer’s suggestion. We want to clarify that our formulation does align with the definition of higher-order ToM and [1].

• In our paper, lines 286-288 explicitly state that: $k$-level ToM function \text{ToM}i^k(\cdot) to form beliefs $b_i^k$ about the mental states of other agents, based on its observations $o_i$, the actions a{-i} of others, and the $(k-1)$-level beliefs $b_{-i}^{k-1}$ of others.

• The observations and other agents’ actions are cumulated by recursive time.

To make this clearer, we can expand our formulation to explicitly show the recursive time steps t.

W2. The proposed alignment measurement in Section 4.2 may not apply to general high-order ToM inferences in multi-agent systems. For example, “what I think A is thinking about B’s action” and “what I think C is thinking about B’s action” are different 1-level ToM inferences that result in the same alignment measurement as defined in this paper. The authors might want to explicitly define the format of beliefs to clarify the formulation.

R2. As shown in Equation (1), our formulation can indeed express and distinguish between different high-order ToM inferences:

$ToM_i^k(o_i, a_{−i}, b_{−i}^{k−1}) := b_i^k$

Let's use the reviewer's example to demonstrate how our formulation handles different ToM inferences:

1. "What agent i thinks A is thinking about B's action":

• This involves $b_i^2$ where i is reasoning about A's belief ($b_A^1$) about B's action

• The nested belief structure captures: i → A → B

2. "What agent i thinks C is thinking about B's action":

• This involves a different $b_i^2$ where i is reasoning about C's belief ($b_C^1$) about B's action

• The nested belief structure captures: i → C → B

These two are distinct in our formulation because:

• $b_{-i}^{k−1}$ includes the different (k-1)-level beliefs of agents A and C
• The resulting $b_i^k$ maintains these distinct belief.

W3. The multi-agent setup for each evaluation scenario is not clearly described. It is unclear how many agents are involved, what their action and observation spaces are, and how they collaborate. For instance, the interactive programming scenario appears to be a centralized system with full observation, as the PM is the only agent making decisions and ToM inferences. Then the value of ToM is less salient in such a single-agent system.

R3. While the programming task had a hierarchical structure, Section 6.4 describes our debate setting which demonstrates full multi-agent dynamics:

• Multiple agents (6 debaters) with ToM capabilities
• Peer-to-peer interactions within teams

W4. The two evaluation metrics are the optimization objectives of the proposed algorithm rather than direct measurements of LLM agents’ collaboration performance or “cooperation trends.” The claim that “agents with higher ToM capabilities may not necessarily exhibit better cooperative trends” conflicts with the results shown in Tables 3 and 4, where agents with ToM perform better. I recommend using other metrics, such as task completion rate or efficiency, to provide consistent conclusions and increase criterion validity.

R4. Results and Core Contribution: The apparent conflict the reviewer notes actually demonstrates our key finding:

• Raw ToM capabilities alone may not improve cooperation (shown in earlier results),

• But our matching mechanism effectively leverages ToM to enhance team performance (Tables 3 and 4).

• This is precisely why our core contribution - the coalition formation mechanism - is valuable:

  • Without matching: Higher ToM didn't necessarily improve cooperation
  • With matching: Significantly improved performance across tasks by effectively leveraging the high ToM agents

We have utilized different metrics for different purposes:

• FTM measures raw ToM effects on cooperation
• Task-specific metrics (Pass@1, win rates) validate practical benefits for cooperation.
• Coalition stability shows sustained cooperation improvements

Hi authors, thanks for your response. I am still confused by the following questions and would like to hear your input.

R1: Since $b_{-i}^{k-1}$ is the hidden mental states of other agents, how could agent i get access to it during ToM inference $\text{ToM}_i^k$?

R2: What is the exact format of belief $b_{i}^{k}$?. How are those different nested reasoning precesses represented?

R4: I do not think FTM and coalition stability are valid evaluation metrics, because they are the exactly same function your algorithem aims to maximize. Using those metric to quantify "cooperation trend" causes circular reasoning issues. The evaluation results presented in Table 2 and Figure 2 are basiclly a sanity check. Your conclusion that "Raw ToM capabilities alone may not improve cooperation" is not supported by external matrics like Pass@1 and win rates.

R5: My concern is addressed. Thanks for the clarification.

Q1 & Q2: Thanks for the clarification. I would suggest add those details to the paper.

We sincerely thank the reviewer's quick feedback. We will address the follow-up questions as follows:

R1: Since b−ik−1 is the hidden mental states of other agents, how could agent i get access to it during ToM inference ToMik?

RR1: We apologize for the confusion. As stated in line 213/214 of our original manuscript, what we want to denote $b_{-i}^{k-1}$ as the set of $(k-1)$-level beliefs of other agents.

To clarify, we revise the notation agent $i$'s beliefs about other agents as $\\{b_i(a_m)\\}_{m \neq i}$ (detailed in updated manuscript page 4 Eq.1). This is derived from agent $i$'s own observations and interactions, not direct access to others' mental states.

Additionally, the beliefs are stored as memory for each agent, used for ToM inference.

R2: What is the exact format of belief bik?. How are those different nested reasoning precesses represented?

RR2: To make the exact format of beliefs and nested reasoning processes explicit, we expand our formulation to show the recursive structure for an LLM agent $i$ at cooperation round $R$ (This revision is updated in our manuscript page 4 & 5).

We revise its $k$-level ToM function (Eq. 1) as:

$\text{ToM}\_i^k(o\_i^{1:R}, \hat{a}\_{-i}^{1:R-1}, \\{b^{k-1}\_{i, R}(a\_m^R)\\}\_{m \neq i}) := b\_{i, R}^k$

where:

• $o_i^{1:R}$ represents agent $i$'s observation history up to round $R$, including current task state, self-actions, and collaborative teammates.
• $\hat{a}_{-i}^{1:R-1}$ represents other agents' action history up to round $R-1$
• $\\{b^{k-1}\_{i, R}(a\_m^R)\\}\_\{m \neq i\}$ captures agent $i$'s prediction of agent $m$'s action at round $R$ based on $(k-1)$-level ToM reasoning: $b^{k-1}\_{i, R}(a\_m^R) = p(a\_m^R | \text{ToM}\_i^{k-1}(o\_i^{1:R}, \hat{a}\_{-i}^{1:R-1}, \\{b^{k-2}\_{i, R}(a\_l^R)\\}\_{l \neq i}))$

The recursive belief structure at round $R$ is defined as:

• Level 0: Direct state-action beliefs:

  $b\_{i, R}^0 = \text{ToM}\_i^0(o\_i^{1:R}, \hat{a}\_{-i}^{1:R-1})$ Just record the cooperation history, without considering any ToM reasoning

• Level 1: First-order beliefs

  $b\_{i, R}^1(a\_j^R) = p(a\_j^R|b\_{i,R}^0)$ Reasoning about agent $j$'s action in current round $R$.

• Level k: Higher-order nested beliefs

  $b\_{i, R}^k(a\_j^R) = p(a\_j^R|\text{ToM}\_i^{k-1}(o\_i^{1:R}, \hat{a}\_{-i}^{1:R-1}, \\{b^{k-2}\_{i, R}(a\_m^R)\\}\_{m \neq i}))$

R5: My concern is addressed. Thanks for the clarification. Q1 & Q2: Thanks for the clarification. I would suggest add those details to the paper.

RR5. We sincerely thank the reviewer for constructive feedback. We have added additionally discussion (highlighted in purple color) for non-LLM belief-alignment calculation in Appendix A (Page 16), and case study for specialized scores in Appendix C.1 (Page 20).

We sincerely thank reviewer BmBs for highlighting our contribution of combining coalition matching with Theory of Mind.

W1. The calculation of the semantic similarity of beliefs and actions is left to the LLM, this does not lend itself to a general approach as the title alludes to. It is made clear throughout the paper that this is applied to LLMs however and I do not see this as a big weakness, but would like to see this made clear in the title if possible.

R1. We appreciate the reviewer's comments about the semantic similarity calculation and its implications for generalizability.

• For LLM-based agents, our approach leverages one of the key advantages of LLMs: their ability to handle open-ended trajectories. The self-evaluation method allows LLMs to assess alignment in complex, unstructured action spaces where traditional similarity metrics might fall short. This is particularly valuable in scenarios involving natural language interactions and creative problem-solving, where the action space cannot be easily enumerated.

• For non-LLM environments, our matching mechanism could be adapted more straightforwardly due to the typically more constrained and well-defined action spaces. For example, in game environments, actions could be discrete choices or continuous control signals. In such cases, belief-action alignment could be computed using traditional similarity metrics like Euclidean distance, KL divergence, or task-specific reward functions. While this would require more careful design of the action space for each specific task, the computation of alignment scores would be more straightforward and computationally efficient.

We will make this distinction clearer to better reflect the current focus of our work, and we propose modifying the title to explicitly mention LLM-based agents.

W2. In the debate environment the baselines where both affirmative and negative lead to a bias of the affirmative winning 65.45% of the time, that is they are both using the same method. This is a cause for concern that this result may not be robust enough and might simply be taking advantage of this bias, is it possible to show the results the other way around? (With your model placed in the negative.)

R2. We thank the reviewer raise a valid concern about the affirmative side bias in our debate experiments. To address this, we conducted additional experiments with our model on the negative side:

Remarks: These results demonstrate that:

• The coalition matching mechanism provides robust benefits regardless of the debate side.
• The improvement over baseline is consistent with our original findings.

Minor: The acronym FTM (Fraction of trust members/Frequency of team matching) is used multiple times making some sections difficult to understand.

We will revise the paper to maintain "FTM" only for "Fraction of Trusted Members".

Q1. For a non-LLM environment, how will the matching scores be calculated?

Please refer to our response R1 to W1.

Q2. In the debate environment the baselines where both affirmative and negative lead to a bias of the affirmative winning 65.45% of the time, that is they are both using the same method. This is a cause for concern that this result may not be robust enough and might simply be taking advantage of this bias, is it possible to show the results the other way around? (With your model placed in the negative.)

Please refer to our response R2 to W2.

We thank reviewer zFGd's recognition of our paper's clear motivation, novelty and promising results.

We address specific concerns below point by point:

W1. Whilst the authors do mention that the coalition formation is generally an NP-hard problem, they do not offer any ideas about potential future possibilities that would help with the scalability of the framework

We thank the reviewer for raising this important point about scalability. We propose to add a dedicated discussion of scalability solutions in our future work section (section 7).

• For example, we can employ preference list truncation where agents only maintain preferences for a bounded number of potential partners, reducing the complexity from O(n²) to O(kn) where k is a fixed constant much smaller than n.
• Additionally, for future work, we can implement a hierarchical matching approach where agents are first grouped into clusters based on their ToM levels and task requirements, and then matching is performed within these smaller clusters. This would reduce the search space.

W2. I do not understand the prompt referenced in Appendix A and the corresponding LLM output. The belief model is rather vague, and when looking at the output of the alignment scores it seems a bit arbitrary - e.g. the belief model does not mention using an object oriented approach, but in the alignment score this seems to be highly valued? I am just slightly concerned that some of the alignment scores outputted by the LLMs are not particularly strong signals and ideally it would be measured using something more robust. Overall, my main concern is the potential scalability of the proposed framework, with firstly the coalition forming being difficult and secondly the requirement to generate beliefs over all other agents. Furthermore, whilst the empirical results are good and I am not downplaying them, I am not convinced the proposed settings are those that can really leverage ToM fully. However, this is not impacting my score.

We acknowledge the reviewer's concern about the robustness of alignment scores and propose to clarify:

• Alignment Score Measurement: For LLM-based agents, our approach leverages one of the key advantages of LLMs: their ability to handle open-ended trajectories and perform nuanced semantic comparisons. The self-evaluation method allows LLMs to assess alignment in complex, unstructured action spaces where traditional similarity metrics might fall short.
• Alternative Approaches: For non-LLM environments with well-defined action spaces, traditional metrics (e.g., Euclidean distance) could be used instead. We acknowledge this as an important direction for future work and will discuss alternative measurement approaches in our revised paper.
• We want to emphasize that our core contribution is the coalition formation mechanism as a plug-and-play approach for improving multi-agent cooperation with ToM agents.

Q1. For the insight that low ToM exhibits better cooperation compared to high ToM, I wonder how specific this is to the environment being looked at. For example, the multi-agent programming setting, at least to me, does not strike me as an environment that requires much ToM to successfully cooperate in, therefore low ToM being more successful may simply be due to the lower complexity of using it. Have the authors noticed this same trend in other environments?

Our evaluation utilized different settings:

• Programming Tasks: Despite being relatively structured, we observed higher ToM agents exhibiting overthinking and reduced cooperation.
• Debate Setting (Section 6.4): Even in this highly social environment, we found higher ToM agents sometimes overthinking and showing less cooperative behavior initially.
• We agree this opens interesting directions for future research on how environmental complexity interacts with ToM levels.