# Explaining Decisions of Agents in Mixed-Motive Games

Maayan Orner
Bar-Ilan University Oleg Maksimov
Bar-Ilan University Akiva Kleinerman
Bar-Ilan University Charles Ortiz
SRI International Sarit Kraus
Bar-Ilan University

###### Abstract

In recent years, agents have become capable of communicating seamlessly via
natural language and navigating in environments that involve cooperation and
competition, a fact that can introduce social dilemmas. Due to the
interleaving of cooperation and competition, understanding agents’ decision-
making in such environments is challenging, and humans can benefit from
obtaining explanations. However, such environments and scenarios have rarely
been explored in the context of explainable AI. While some explanation methods
for cooperative environments can be applied in mixed-motive setups, they do
not address inter-agent competition, cheap-talk, or implicit communication by
actions. In this work, we design explanation methods to address these issues.
Then, we proceed to demonstrate their effectiveness and usefulness for humans,
using a non-trivial mixed-motive game as a test case. Lastly, we establish
generality and demonstrate the applicability of the methods to other games,
including one where we mimic human game actions using large language models.

##  1 Introduction

Many important real-world scenarios are similar to games that consist of more
than two agents with both cooperation and competition opportunities, i.e.,
mixed motives. Due to the challenges this class of games introduces, such as
partly conflicting interests, variable-sum payoffs, and multiple equilibria
[1]111This is a challenge in every environment with more than two agents.,
mixed-motive multi-agent environments are somewhat of a challenge to study in
comparison to purely competitive or cooperative environments. Recently, games
with more than two agents that include both cooperation and competition have
re-gained [2] popularity [3, 4, 5, 6], using the game of Diplomacy as a
research testbed.

In addition, the need for explainability of increasingly complex AI systems
has gained importance [7], both for algorithm developers and for decision-
makers. For example, tools like LIME [8] and SHAP [9] are becoming a de-facto
standard among ML practitioners, as the traditional metric-based validation
methods are perceived as insufficient [10, 11] or invalid [12] in many setups.
There are various reasons why relying solely on traditional evaluation methods
is problematic - e.g., traditional metrics do not address the problem in mind,
machine learning models can generate predictions based on spurious
signals222For example, the paper demonstrated how a Husky vs. Wolf classifier
misclassified a data point based on the presence of snow. [8], and multi-agent
reinforcement learning (MARL) systems are prone to employ cooperation and
competition strategies that are incompatible with humans [13]. For that
reason, users often want to know why a model predicts $a$ instead of $b$, why
a chess-playing agent decides to sacrifice a knight instead of exchanging
queens, or when it is appropriate for a MARL agent to cooperate rather than
compete.

While explainability in single-agent setups has been extensively studied [14],
multi-agent setups have been less studied up until recently [15, 16, 17, 18].
This is surprising for various reasons; e.g., any interaction of humans with
artificial agents consists of multiple agents by definition. Moreover, since
humans are social creatures, many interesting real or simulated scenarios
involve multiple agents (sports, business, politics, economics,…).

In this work, we closely examine the effectiveness of explanations in mixed-
motive games with more than two players, a category of games that have not
been adequately explored in terms of explainability. Within this class of
games or real-world situations [19], even though there is a conflict of
interests, there is a competitive advantage for some cooperation. Furthermore,
in many mixed-motive games, communication is key. For example, research has
shown that cheap-talk can modify cooperation rates in games like Prisoner’s
Dilemma, as indicated in a meta-analysis of 45 studies [20].

To address this challenge, we divide our work into three conceptual levels.
The first level is strategic, focusing on explaining the agent’s decisions
with respect to the game’s outcomes, taking the policies of other agents into
account. The second level is situational, explaining how the environment’s
state and agents’ policies impact the emergence of cooperation and
competition. The third level presents considerable challenges, as it involves
explaining the influence of implicit communication by actions and cheap-talk
on cooperation, competition, and game outcomes.

The explanation methods we propose were implemented for three games to
demonstrate generality. To examine the first two levels, we selected a
challenging game called no-press Diplomacy as our main testbed but implemented
the methods for the game of Risk as well.

To explore the third level, we employ Diplomacy for implicit communication
(defined formally in 4.1) and a simple game inspired by the prisoner’s dilemma
for cheap-talk. In this game, the tactics are straightforward but negotiations
can be complex, reducing the number of confounding variables compared to full-
press Diplomacy.

Our contributions: Our main contributions are methods for explaining agents’
decisions in non-trivial mixed-motive environments. Environments with more
than two agents that are not purely competitive or cooperative introduce a
decision with whom to cooperate and with whom to compete, in which agents’
tendencies, implicit or explicit communication, and alignment of interests
play a focal role.

Based on these observations we developed highly applicable explanation
methods, that are not bound to a specific environment and do not require
manual feature extraction. Due to the complexity of agents’ interactions, a
complex explanation for it is arguably counterproductive. Due to the
complexity of environments and policies, explanations of the internal decision
process are not general or interpretable. Following the ideas of Peter Lipton
and others [21, 22], we provide simplified contrastive explanations, comparing
the ’effects’ and ’diplomatic consequences’ of a decision and a
counterfactual.

We demonstrate the methods’ effectiveness via computational experiments in
three environments and experiments with humans in Diplomacy. In each
environment, agents employ different types of policies: neural network (in
Diplomacy), black-box (GPT-4), and heuristics (in Risk). To the best of our
knowledge, this is the first work to propose methods evaluated via experiments
with humans, specifically designed for mixed-motive environments.

##  2 Related Work

During the last few years, researchers has begun to address the challenge of
explaining decisions in multi-agent environments as part of a new proposed
research area, called xMASE (Explainable Decisions in Multi-Agent
Environments) [15, 16]. Subsequently, a series of papers have explored
different aspects of the topic [17, 23, 24]. Out of the subset of this work
that is focused on explaining the interaction between agents, a significant
portion is concerned mostly [25, 26] or only [27, 28, 29, 30, 31] with
cooperative setups. An exception to that is [32], which utilized competitive-
cooperative particle environments. This work is only loosely related to ours -
it focuses solely on coordination, the quality of explanations was not
evaluated relative to humans and the agents act within pre-defined teams.

Solution concepts from cooperative game theory, such as Shapely values [29] or
Myerson values [30] can provide a framework to examine the contribution of
each agent to a cooperating team, but are often insufficient in games with
mixed motives. In such games, payoffs are usually not collective, and agents
cooperate when beneficial and break alliances when it is not. Explanations of
feature attribution [9, 8] often contain many irrelevant details while lacking
relevant information. For example, in Diplomacy, such methods can be utilized
to estimate the contribution of each unit movement (see section 3) to the
utility value of a strategy (see section 4.1). Based on preliminary
experimentation, that explanation is difficult to interpret. More importantly,
it does not address questions related to agents’ interaction. Therefore, new
explanation methods are needed.

We build our approach on contrastive explanations [21] and aim to satisfy a
slightly modified version of well-established desired properties [33, 17, 25].
The experiments and analysis methodology are based on previous work [17, 25],
and some of the proposed methods are inspired or related to work _outside the
field of explainable AI_. We draw a considerable amount of inspiration and
adopt Strategy-based Utility Explanations (section 4.2, figure 5 upper
heatmap) from [34]. Shared Interests Correlation Analysis (section 4.4, figure
5 lower heatmap), although developed independently, is similar to a technique
utilized by [35] for a different task. Presenting the probable actions other
agents might take (section 4.3, figure 5 arrows) is a special case of example-
based explanations, a standard method we apply in a different context.

##  3 Description of Game Environments

We have applied our methods to three distinct game environments, but provide
detailed descriptions of two environments, _No-Press Diplomacy_ and
_Communicate Out of Prison_ while deferring any detailed discussion of _Risk_
to the appendix.

No-Press Diplomacy Diplomacy is a simultaneous game in which each player
controls one of the seven great powers of Europe in the years leading to World
War 1. The goal of the game is to control at least 18 out of the 36 strategic
locations on the map, i.e. ’supply centers’. An action in Diplomacy is
composed of multiple unit sub-actions (e.g., Naples fleet to Ionian Sea, Rome
army to Apulia,…), yielding a large combinatorial action space. The game is
estimated to have $10^{21}$ \- $10^{64}$ joint actions per turn and a game
tree size that can be infinitely large (median size $\approx 10^{896.8}$) [5].

There are two notably popular versions of the game. One permits communication
(full-press Diplomacy), while the other relies on implicit communication
through in-game actions (no-press Diplomacy). We selected no-press Diplomacy
as our testbed primarily to investigate the first two levels of explanation
(strategic and situational), as well as implicit communication on the third
level. Additionally, Diplomacy’s large action space offers an opportunity to
assess the scalability of the explanation methods.

Communicate Out of Prison (COP) To examine the explanations in a setup with
heterogeneous policies and explicit communication (third level), and to
mitigate the effects of confounding factors such as in-game tactics, we
designed the Communicate Out of Prison game that draws inspiration from the
Prisoner’s Dilemma. In this setup, three agents $\\{a,b,c\\}$ try to escape
punishment for a robbery.

The game starts with a private communication stage, in which agents exchange
private messages (protocol detailed below). After the communication stage is
over, every agent announces whether each of the other agents is innocent
(announce 0) or guilty (announce 1). For example, agent $a$ can announce
$b=0$, $c=1$. All agents’ announcements are performed simultaneously.

The game incentivizes two agents, say $a$ and $b$ to cooperate against $c$.
Agent $c$, in turn, is incentivized to cooperate with $a$ and $b$, who
possibly already conspire against $c$. This situation creates a competition of
alliance formation. To demonstrate why the game is cooperative-competitive -
if every agent announces the two other agents as innocent, the payoffs will be
$\\{a:-5,b:-5,c:-5\\}$. In case every agent announces the two other agents as
guilty, the payoffs are $\\{a:-20,b:-20,c:-20\\}$. However, if two agents,
e.g., $a$ and $b$ cooperate against agent $c$, and announce ${b=0,c=1}$ and
${a=0,c=1}$ respectively, the payoffs are $\\{a:0,b:0,c:-20\\}$. The full
payoff tables are provided in the appendix.

_COP - Protocol of communication:_ Agents communicate sequentially for $K$
($K=4$ in our experiments) rounds in a randomized precedence order. In each
round, each agent must send a message to one of the other agents. During round
${K+1}$, the agents make announcements and obtain payoffs accordingly.
Communication is performed using unconstrained natural language, therefore,
state space $S$ is all possible chat histories, and action space $A$ is all
possible messages. $S$ and $A$ are unbounded in theory, but in practice,
denoting $|C|$ as the maximal context length, and $|G|$ as the maximal message
length, $|S|>2^{|C|}$ and $|A|>2^{|G|}$ (length = number of tokens).

##  4 Methods

Figure 1: Explanation for Austria’s strategy (arrows are probable actions of
all agents, except for Austria) - SICA detects a strong animosity with Italy.
According to the strategy, Austria assists Turkey in preventing Italy from
taking over Constantinople while attacking Venice simultaneously. SBUE
explains that this strategy _implicitly_ communicates hostility to Italy and
friendliness to Turkey.

In this section, we present the explanation methods and the procedure we
employ to find counterfactual actions in Diplomacy.

Assuming we play as agent $i$, and would like to get an explanation for action
$a^{i}$ in state $s$, we propose three different explanation methods: (1) A
utility-based method that presents the expected utility associated with
$a^{i}$ both for agent $i$ and the other agents in the environment (section
4.2). (2) Probable actions-based method that specifies the most probable
actions other agents can take when agent $i$ performs $a^{i}$ (section 4.3).
(3) An estimation of the relationships between the agents in state $s$
(section 4.4). A visual example of all three types of explanations in
Diplomacy is provided in figure 5.

###  4.1 Preliminary Definitions

Environment and agents: An environment of $|P|$ agents incorporates an action
space $A$, state space $S$, transition function ${T:S\times A^{|P|}\rightarrow
S}$, and reward function ${R:S\times S\rightarrow\mathbb{R}^{|P|}}$.
Considering the current state as $s_{t}$ (the subscript will be omitted when
unnecessary), we denote $R(s_{t-1},s_{t})$ as $R_{t}$ and $R_{t}^{i}$ as the
reward for agent $i$ in step $t$. The set $P$ consists of agents that act
according to policies $(\pi_{1},...,\pi_{p})$. A policy ${\pi_{i}:S\times
A\rightarrow[0,1]}$ is a joint probability mass function, it maps each action-
state pair to a probability where for all ${i\in P}$ and ${s\in S}$,
${\sum_{a^{i}\in A}\pi_{i}(s,a^{i})=1}$. Similarly, we define value functions
${V_{i}:S\rightarrow\mathbb{R}}$ for each agent. The value function usually
estimates the expected return of the agent given $\pi$, i.e.
${V_{i}(s_{t})\approx\mathbb{E}[R^{i}_{t+1}+\gamma
R^{i}_{t+2}+...+\gamma^{n-1}R^{i}_{n}|s_{t}]}$, where ${\gamma\in[0,1]}$ is a
discount factor.

For convenience, we define ${V:S\rightarrow\mathbb{R}^{|P|}}$ as a vectored
value function for all agents using $V_{1},...,V_{p}$, and ${\pi:S\times
A^{|P|}\rightarrow[0,1]^{|P|}}$ as a function that returns the probability of
agents’ actions according to $\pi_{1},..,\pi_{p}$. The last definition is
useful for games in which all agents act simultaneously. We denote
$a^{i}\sim\pi_{i}$ as drawing an action from distribution $\pi_{i}$ given
state $s$ (the current state is implied), and $a\sim\pi$ as a vectorized
version of it. We use $-i$ to denote all agents that are not $i$, i.e. all
$j\in P$ where $j\neq i$.

Utility: The utility vector of full action set $a\in A^{|P|}$ is defined as
${\mathbb{E}[V(T(s,a))+R_{t+1}]}$, the expectation is taken since transitions
and rewards can be stochastic. The expected utility vector of action
${a^{i}\in A}$ is defined as $\mathbb{E}_{a^{-i}\sim\pi_{-i}}[\gamma
V(T(s,(a^{i},a^{-i})))+R_{t+1}]$, Where $\pi_{-i}$ are the policies of agents
$-i$ or the policies we assume they employ. It is a vector of size $|P|$, in
which the element with index $j$ corresponds to the expected utility of action
$a^{i}$ for agent $j$.

Private information and states: In a multi-agent setup, agents may possess
private information, leading to distinct states for each agent. In this
context, $s$ represents a collective state of all agents, i.e.,
${s:=(s^{1},...,s^{p}})$, with agent $i$ accessing only $s^{i}$. Accordingly,
$V_{i}(s)=V_{i}(s^{i})$, and the same concept applies to $\pi_{i}$.

Communication by action: Communication by action $a^{i}$ from agent $i$ to
agent $j$ is defined as ${\mathbb{E}_{a^{-i}\sim\pi_{-i}}[\gamma
V_{j}(T(s,(a^{i},a^{-i})))+R^{j}_{t+1}]}$. It is a real-valued scalar that
represents how ”beneficial” or ”harmful” this (observed by $j$) action is for
$j$ in expectation. This definition generalizes to explicit communication
actions (e.g., sending a message) and implicit communication actions (e.g.,
board movements), as both can influence the value estimation of agent $j$.

Non-acting agents: Actions outside an agent’s turn are disregarded (defined as
null actions), to maintain uniformity of writing across simultaneous and
sequential games.

Contrastive Explanations: An explanation is contrastive when multiple actions
are explained for agent $i$ in state $s$. Although our methods can be applied
to explain a single action, users are always provided with contrastive
explanations.

Diplomacy simulation components: We use the simulation environment from [3] to
simulate Diplomacy games of automated agents. Each agent uses the neural
policy network and neural value function implemented by DeepMind [5].

COP simulation components: Our simulation environment follows the
communication protocol presented in section 3 and supports agents’
augmentation with different personality types. Agents’ policies are
implemented using GPT-4 (instruct), by a prompt structured as _#setup#meta-
context(agent-id, task, personality, chat-history, stage)_. _#setup_ refers to
technical specifications such as the message structure. _#task_ refers to the
rules of the game, and _#personality_ contains a detailed textual description
of the personality type the agent is instructed to mimic. _#stage_ is a
specification of whether it is time to announce or to communicate. Agent types
are private and an agent is unaware of the possible types of other agents; the
types can be estimated solely based on communication.

Since a pre-trained value function is unavailable, we estimate $V(s)$ via
Monte Carlo simulation with a temperature of $\tau=0.7$, starting from state
$s$ and proceeding to the end of the game. During the simulation, agents act
according to their respective policies.

###  4.2 Strategy-based Utility Explanations (SBUE)

Motivation and description: When engaging in games with mixed motives and more
than two agents, it is advantageous to consider not only how beneficial the
action is for the agent itself but also how it influences other agents that
observe this action. This is crucial because of the focal role of implicit
communication in the environments we study. A ’friendly’ action communicates
willingness for future cooperation, and a ’hostile’ action communicates
animosity.

Explanation estimation: Given state $s$ and action $a_{c}^{i}$ ($c$ denotes
constraint) to be explained, the following steps are performed:

  1. 1.

Simulate the next turn from $s$ for $K$ times, where agent $i$ performs action
$a_{c}^{i}$, and all other agents follow their respective policies.

  2. 2.

Estimate the utility values of each outcome using the value functions and
immediate rewards (algorithm 1 line 13).

  3. 3.

Estimate the expected utilities of $a_{c}^{i}$ by computing the mean utility
of each agent (column) and returning a vector of size $|P|$.

Steps 1 and 2 are equivalent to calling:

${Simulate(s,K,D=0,C=\\{(a_{c}^{i},0)|a_{c}^{i}\in A\\})}$

Sometimes the value function is difficult to interpret. In this case, we
estimate $\mu^{i}$ and $\sigma^{i}$ for all $i\in P$ by performing an
unconstrained simulation (algorithm 1 with $C=\emptyset$), and use it to
perform Z-score standardization to each column before step 3.

Formally, $SBUE(s,a_{c}^{i})\in\mathbb{R}^{|P|}$ is defined as:

$SBUE(s,a_{c}^{i})\approx\mathbb{E}_{a^{-i}\sim\pi_{-i}}[\gamma
V(T(s,(a_{c}^{i},a^{-i})))+R_{t+1}]$

Equivalent to the definition of expected utility (in section 4.1).
Importantly, the SBUE vector consists of the expected utility for all agents,
which we also refer to as communication by action from $i$ to each agent $j$
that observes $a^{i}$.

###  4.3 Probable Actions Based Explanations

Motivation: In any environment with more than two agents (especially with
mixed motives), understanding the policies of the other agents can be useful.
Therefore, we present the most probable actions of agents $-i$ assuming agent
$i$ selects action $a_{c}^{i}$.

Explanation estimation: As in SBUE, we run $K$ simulations from state $s_{t}$
where agent $i$ performs action $a_{c}^{i}$ and all other players follow their
respective policies. Then, we extract the most commonly used action of each
agent accordingly. If we present a longer trajectory, we repeat the process
but do not constrain agent $i$ to perform specific actions in later states.

To define precisely, we denote the constrained action set as
${a_{c|s_{t}}:=(a^{1}_{max},...,a^{i}_{c},...,a^{p}_{max})}$; similarly, we
denote ${a_{max|s_{t}}:=(a^{1}_{max},...,a^{i}_{max},...,a^{p}_{max})}$ where
$a^{j}_{max}$ is the most probable action of $j$ according to $\pi_{j}$ in
state $s_{t}$. We denote $T_{max}$ as the most probable transition in cases
where the transition function is stochastic (e.g. Risk).

The explanation is defined greedily333A greedy algorithm will not always find
the most probable trajectory. We resort to a greedy method because 1.
estimating which action is the most probable is expensive in our environments;
2. the problem itself is of high complexity; 3. we provide minimal and simple
solutions (see section 7). to any depth by computing the trajectory using the
following recursion rules: ${s_{t+1}=T_{max}(s_{t},a_{c|s_{t}})}$,
${s_{t+k}=T_{max}(s_{t+k-1},a_{max|s_{t+k-1}})}$ for $k>1$. Accordingly, an
explanation of depth $n$ is presented as a sequence of actions and states
${F_{n}(s_{t},a^{i}_{c})\approx(s_{t},a_{c|s_{t}}),(s_{t+1},a_{max|s_{t+1}}),...,(s_{t+n},\emptyset})$.
Notably, the last state is presented with no actions, as it is the resulting
state of the trajectory.

Diplomacy: For Diplomacy, we present $F_{1}(s_{t},a^{i}_{c})$, which is just a
direct presentation of $(s_{t},a_{c|s_{t}})$ and $s_{t+1}$. A visualization of
the explanation is provided in figure 5. In practice, users were presented
with $s_{t+1}$ via an interactive system.

COP: For COP, we present $F_{\infty}(s_{t},a^{i}_{c})$, a trajectory of
unlimited depth. Finding the most probable action at each timestamp requires
searching over a prohibitively large action space. However, a greedy solution
is easy to implement, although this approach has serious drawbacks (see
section 5.3). Given a context of messages $m_{1},...,m_{t-1}$ and user query
of message $m_{t}$, we decode each action using temperature ${\tau=0}$. That
process is equivalent to selecting
$\operatorname*{argmax}_{y_{n}}P(y_{n}|m_{1},...,m_{t},y_{1},...,y_{n-1})$
until $m_{t+1}$ is composed from tokens $y$. We do it for each timestamp, and
provide the dialog and game results as an explanation.

###  4.4 Shared Interests Correlation Analysis (SICA)

Motivation and description: In a mixed-motive setup, a central question is
whether the state of the environment and agents’ policies can facilitate
effective cooperation. To explain the cooperation tendencies and alignment of
interests among pairs of agents in a given state, we introduce Shared
Interests Correlation Analysis (SICA). With a slight compromise of rigor for
clarity, the SICA value for each pair of agents can be described informally as
their level of ’friendliness’ or ’animosity’, which can stem either from the
policies of the agents or from the environment state. SICA is always provided
in addition to an action-based explanation.

Explanation estimation: To estimate SICA, we perform $K$ unconstrained
simulations to depth $D$ according to algorithm 1, where all agents act
according to their respective policies, i.e., $a\sim\pi$. This step is
equivalent to calling:

${Simulate(s,K,D,C=\emptyset)}$

The resulting dataset $X$, considering the case of depth-1 ($D=0$) without
loss of generality, is a $K\times|P|$ matrix, in which element $X_{x,y}$ is
the utility agent $y$ obtains in simulation $x$. The utility of a simulation
is defined in algorithm 1 line 13; it indicates how good or bad a simulation
outcome is for each agent. Lastly, we compute the sample Pearson correlation
coefficient for each pair of columns (between agents), which results in a
$|P|\times|P|$ correlation matrix.

If the utility agent $i\in P$ obtains is constant, the population correlation
coefficient $\rho_{i,j}$ is undefined for all $j\in P$, and therefore cannot
be estimated. Except for the case in which all actions lead to the same
outcome (a decision point does not exist, _case 1_), it happens when $V$ is
based on heuristics 444When the value function is based on heuristics it’s
often not as sensitive to subtle changes of the state; such changes modify the
expected return values. (_case 2_), or when the policies of all agents and the
environment are deterministic (_case 3_). _Case 2_ and _Case 3_ can be
somewhat mitigated by using $D>0$. We discuss the workarounds and the
detection of _case 1_ in the appendix.

###  4.5 Counterfactual Actions Based on Partial Queries in Diplomacy

A contrastive explanation can compare action $a^{i}$ to some similar action,
based on a query provided by the user. In Diplomacy, each player’s action is
defined by sub-actions of multiple units. Asking the user to provide a full
query is often impractical, as it requires a significant cognitive effort. If
the user is presented with strategy $a_{c}^{i}$, and then asks for a different
sub-action of one unit (e.g., move the army in Paris to $x$ instead of $y$),
it might imply a necessity of a different sub-action for additional units as
well. It can happen because units interact and coordinate, e.g., support
attacks or defense of other units. Therefore, directly modifying $a_{c}^{i}$
to perform the requested sub-actions is insufficient, even if the game rules
allow it.

Denoting a single unit sub-action as $\psi$ and $C$ as the set of all possible
single unit constraints in the form of $\psi$ (do $\psi$) or $\neg\psi$ (do
not do $\psi$), given constraints set $C_{q}\subseteq C$ defined by the user,
we define a similarity function ${f_{sim}:A\times A\rightarrow[0,1]}$ and draw
$K$ actions from probability distribution $\pi_{i}$ (simulation). To compute
counterfactual actions, first, we define a function to check constraint
satisfaction ${\phi:A\times C\rightarrow\\{True,False\\}}$ and
$\kappa\in(0,1]$, Where $\kappa$ is a hyperparameter. Then, we approximate the
feasible action set:

$A^{\prime}=\\{a^{i}|\\{\hat{P}(s,a^{i})>\kappa\land\phi(a^{i},C_{q})\land
a_{c}^{i}\neq a^{i}\\}$

And estimate the expected utility (only for the acting agent) of each action
$a^{i}\in A^{\prime}$, with the expectation taken over the actions of other
agents’ playing by their respective policies:

$\overrightarrow{u}_{i,a^{i}}\approx\mathbb{E}_{a^{-i}\sim\pi_{-i}}[\gamma
V_{i}(T(s,(a^{i},a^{-i})))+R^{i}_{t+1}]$

We then compute a score for each action ${score(a_{s}^{i},a^{i})=\alpha
f_{sim}(a_{c}^{i},a^{i})+\beta\overrightarrow{u}_{i,a^{i}}}$, where $\alpha$
and $\beta$ are hyperparameters that balance between similarity and utility
values. Lastly, we return the set of actions that maximizes the score
function:

$\operatorname*{argmax}_{a^{i}\in A^{\prime}}score(a_{c}^{i},a^{i})$

The method works for empty user queries as well, returning strategies similar
to $a^{i}$ while attempting to maximize the utility value. In most cases (e.g.
neural networks), it is possible to guarantee that the method will return
counterfactuals for every legal query (when $\kappa=0$). However, this is not
always the case for black-box policies.

Algorithm 1 Simulate

1:procedure Simulate($s$, $K$, $D$, $C$)

2: // $s\in S$; $K\in\mathbb{N}$; $D\in\mathbb{N}$

3: // $C$ is a set of tuples $(a^{i}_{c},d_{c})$ where $a^{i}_{c}\in A$ and
$d_{c}\in\mathbb{N}$

4: $X\leftarrow KD\times|P|$ matrix; $s_{0}\leftarrow s$

5: for $j\leftarrow 0$ to $K-1$ do // K simulations

6: $s\leftarrow s_{o}$ // restore initial state

7: for $d\leftarrow 0$ to $D-1$ do // to depth D

8: $a\leftarrow a^{1},..,a^{p}\sim\pi$ // draw actions for agents $1$ to $p$

9: for $(a_{c}^{i},d_{c})\in C$ do

10: if $d=d_{c}$ then $a^{i}\leftarrow a_{c}^{i}$ // replace actions with
constraints.

11: $s^{\prime}\leftarrow T(s,a)$

12: $\overrightarrow{r}\leftarrow R(s,s^{\prime})$

13: utility $\leftarrow\gamma^{d+1}V(s^{\prime})+\gamma^{d}\overrightarrow{r}$

14: $X[Kj+d,:]\leftarrow$ utility; $s\leftarrow s^{\prime}$

15: return $X$

##  5 Modules Evaluation

###  5.1 Convergence of Estimation of SICA and SBUE in Diplomacy

Figure 2: Convergence of SICA and SBUE playing as Austria.

Since the run-time of both methods increases linearly with the number of
samples and sampling is expensive, we examine the error-runtime trade-off for
the algorithms with several sample sizes. We estimate the SBUE values of the
examined action using 2,500 samples and define it as ground truth. Then, we
re-estimate SBUE with different sample sizes and plot the RMSE (root mean
squared error) from the ground truth for each agent. To examine the estimation
error of SICA, we compare the average cosine similarity within the flattened
correlation matrices, partitioned by sample size. When the pairs of flattened
matrices in a partition have a high average cosine similarity score,
convergence is implied. For an example of the results in a middle-game state
in Diplomacy, see figure 2.

Although the action space of Diplomacy is large, we observe that SICA and SBUE
converge quickly and require a relatively small sample size in the game states
we examined.

###  5.2 SICA Evaluation in Diplomacy and Risk

Table 1:  MAP@K score, Diplomacy (D, e) - expert annotation, (D,p) - non-expert annotation, and Risk (R). Annotation | Random | Centers | SICA | IAA-rank | N
---|---|---|---|---|---
(D, e) top 2 enemies | 0.55 | 0.63 | 0.74 | $0.86\pm 0.01$ | 30
(D, e) top 2 friends | 0.58 | 0.60 | 0.66 | $0.725\pm 0.015$ | 30
(D, p) top 2 enemies | 0.56 | 0.74 | 0.81 | $0.82\pm 0.01$ | 30
(D, p) top 2 friends | 0.56 | 0.58 | 0.78 | $0.72\pm 0.02$ | 30
(R) top 1 enemy | 0.61 | - | 0.81 | - | 12
(R) top 1 friend | 0.61 | - | 0.72 | - | 12

##### Setup and motivation:

Our hypothesis is that SICA provides a ’correct’ estimation of the
relationships between the agents. To test the hypothesis we conducted a human-
based experiment, in which we asked human players to annotate the most
friendly and hostile agents in multiple board states, assuming they play one
of the roles.

The board states were generated randomly while additional measures were taken
to ensure a sufficient variation. In particular, 30 board states for 7-player
Diplomacy games were generated, and the human players were asked to annotate
the top two hostile and friendly agents for each board. If the annotator was
unable to decide which are the second most friendly or hostile agents, we
allowed it to be left unfilled; therefore, the results for random assignments
of friends and enemies vary. For Risk (4-player version), we generated 12
board states, and a human selected the top enemy and top friend for each
board.

We used two different annotators for diplomacy: one is considered a strong
player, and the other is intermediate (introducing a variation of skill
level). For Risk, which is not our main focus, the dataset was annotated by
one of the authors.

Metric and evaluation: To evaluate the alignment of the annotations with SICA,
we used MAP@K [36]. Specifically, we rank the other agents by the SICA value
they share with the agent, high to low. We reverse the ranking to rank agents
by hostility. Then, we evaluate SICA using the annotated datasets. This
methodology is built upon the assumption that agents play similarly to humans,
and a violation of it is likely to result in a decrease in the MAP@K values.

Results: The results (see table 1) suggest that SICA is well-aligned with
human intuition and performs better than random rankings in both Diplomacy and
Risk. In Diplomacy, SICA outperforms a heuristic-based ranking, which sorts
agents by the number of centers they own (a proxy for strength), by a
considerable margin. This is achieved without relying on non-generalizable
properties of the environment.

Inter annotator agreement: Although annotators rank only some of the agents,
it is possible to compute lower and upper bounds for MAP@K for the annotations
of $A$ compared to the partial ranking of annotator $B$ (called IAA-rank in
table 1). The range of IAA-rank is higher than SICA in 2 out of 4 cases, lower
in one case, and overlaps in another. Note, ${MAP@K(A,B_{rank})\neq
MAP@K(B,A_{rank})}$ is expected due to the definition of the metric and
annotations.

Our first observation is that even humans have a high degree of disagreement
in this task. The results also imply that the agent’s actions may be somewhat
misaligned with human intuition. It is expected since the agents were trained
via imitation learning followed by self-play, and self-play Diplomacy agents
usually play differently than humans [37].

###  5.3 Mimicking Humans with Large Language Models and Explaining Their
Decisions

Figure 3:  SICA explanations of two settings. On the left side, the agents are
Con, Sim, and Pol. On the right side one Sim and two Pol.

Motivation: Since communication is important in mixed-motive games, we
conducted a series of experiments to examine the explanation methods in a
setup with cheap-talk and heterogeneous policies.

Agents types: We defined three agent types that differ in personality traits
and preferences:

  1. 1.

con-artist: selfish, cruel, manipulative, convincing, and deceitful.

  2. 2.

”simple-person”: nice, trusts easily, honest, and hates lies.

  3. 3.

politician: a political genius, rather selfish but honest when possible.
Prefers ”simple and nice” agents, and dislikes manipulators.

LLMs mimic personality types consistently: To validate that LLM agents are
capable of playing by the types we defined, we randomly generated 20 games and
two annotators matched between anonymous agents (renamed in each game) and
types, solely based on the communication, hiding the final announcements of
the agents. The accuracy of the first annotator was
${(Con=85\%,Sim=85\%,Pol=90\%)}$, and of the second annotator
${(Con=100\%,Sim=90\%,Pol=90\%)}$ which indicates that the agents demonstrated
the required types consistently.

SICA explanations: As defined above, we constructed the agents’ personalities
to encourage cooperation between the politician and the ”simple-person”
against the con artist. _We hypothesize that this tendency will be explained
by SICA_. First, we estimate SICA for our usual setup. To present a comparison
to the explanation, we estimated SICA again with two politicians and one
”simple-person”, in which _we hypothesize that SICA will display a higher
degree of indifference_. The resulting explanations support our hypothesis
(see figure 3) and the correlation coefficients are all statistically
significant ($p<0.01$).

SBUE - friendly vs. hostile message: To examine SBUE, we curated messages
$m_{f},m_{h}$ manually, playing as politician, sending a message to the
”simple-person”. $m_{f}$ is designed to be friendly, and $m_{h}$ extremely
hostile. Simplified examples for $m_{f}$ and $m_{h}$ could be _”let’s work
together.”_ and _”I don’t trust you!”_. _We hypothesize that SBUE will explain
that $m_{f}$ is better than $m_{h}$_.

The resulting SBUE explanations are
$(Con=-17,Sim=-2,Pol=-5),(Con=0,Sim=-18,Pol=-14)$ for $m_{f}$ and $m_{h}$
respectively. Message $m_{h}$ is beneficial to the con-artist and harmful to
the politician and ”simple-person”, and the opposite is true for $m_{f}$. The
result is consistent with our hypothesis.

Probable actions-based explanations can be misleading: We observe a case in
which $probable(s,m)$ ends up with an outcome that is not the most probable
using a higher temperature value ($\tau=0.7$ instead of $\tau=0$), as the game
usually ends up with outcomes of a similar nature, but never as the outcome
mentioned: ${(Con=0,Sim=-20,Pol=-20)}$. We conclude that greedy decoding is
insufficient, and additional research is required.

##  6 Studies

###  6.1 COP Large Language Model Study

Motivation: To complement our Diplomacy user-study, we examine the
effectiveness of the explanations for LLM agents. We do it since we would like
to know if the explanations are helpful for both LLM agents and users, and
whether the explanations are simple enough to assist LLM agents to make better
decisions.

Setup: For each agent, we randomly selected two different messages sent during
simulations, except for one manually crafted case (playing as simple-person),
where $m_{1}$ and $m_{2}$ differ only by the recipient. In all cases, we
define $m_{1}$ as the message that has a higher expected utility in comparison
to $m_{2}$. Then, we extend the agent’s prompt and ask which message it would
prefer to send.

To examine the effect of the explanation, we augment the prompt with a
contrastive explanation: $SICA(s)$ and $SBUE(s,m_{1})$, $SBUE(s,m_{2})$. We
ask the same question again and compare the agent’s decisions with and without
explanations. To mitigate biases, we shuffle the order in which we present the
messages [38]. Additionally, we ask the agent to justify its decision, to
validate that it considers the explanation and performs basic reasoning.

Result: We observe that the agent is influenced by the explanation, and sends
$m_{1}$ $91\%$ of the times compared to $47\%$ ($p<10^{-5}$ according to
$\chi^{2}$-test). Additionally, the agent justifies its decisions through the
explanation, and its bias towards selecting the first message is reduced (see
results in table 2). Example of the justification the agent provided:
_’According to the SICA explanation .. is more of a friend than .. so it would
be beneficial to.. The expected reward .. according to SBUE, is higher .. than
the second message.. Additionally, the first message is more in line with my
personality..’_.

Post-experiment, we presented the agent with a decision between $m_{f}$ (a
friendly message) and $m_{h}$ (an extremely hostile message). In this case,
even without explanation $m_{f}$ is always preferred. The results suggest that
the bias towards selecting the first message is expressed if the agent is
relatively indifferent between the messages.

Table 2: The explanation modifies the decisions of the agent. $m_{1}$ is prominently preferred with an explanation (marked with +).  |  | Pol | Con | Sim | Total
---|---|---|---|---|---
Expl. | First | $m_{1}$ | $m_{2}$ | $m_{1}$ | $m_{2}$ | $m_{1}$ | $m_{2}$ | $m_{1}$ | $m_{2}$
+ | $m_{1}$ | 46 | 4 | 50 | 0 | 50 | 0 | 146 | 4
+ | $m_{2}$ | 36 | 14 | 43 | 7 | 50 | 0 | 129 | 21
+ | $m_{1}+m_{2}$ | 82 | 18 | 93 | 7 | 100 | 0 | 275 | 25
- | $m_{1}$ | 41 | 9 | 50 | 0 | 50 | 0 | 141 | 9
- | $m_{2}$ | 0 | 50 | 0 | 50 | 0 | 50 | 0 | 150
- | $m_{1}+m_{2}$ | 41 | 59 | 50 | 50 | 50 | 50 | 141 | 159

###  6.2 Diplomacy User Study

To evaluate the usefulness of the explanations, we conducted a study with
humans (using Diplomacy as a testbed), with two main goals in mind: (1) see if
the explanations are effective. (2) get user feedback on various aspects. We
recruited 26 subjects (24 Males, 1 Female, 1 Other; see section 7 for a
discussion of the distribution), with a requirement of knowing the rules of
Diplomacy. 9 players played fewer than 5 games, 6 players played 6 to 20
games, 2 players played 20 to 50 games and 2 players played 50 or more games.
Participants who provided inconsistent answers to our consistency check
questions or failed a basic knowledge exam were discarded automatically (3 out
of 26 participants were discarded).

##### Questionnaire design:

Users were presented with a questionnaire in which all questions had answers
on a Likert scale (1-5). They answered the same questions (provided in the
appendix) for all of the presented scenarios and explanations.

Types of explanations:

Figure 4: Mean and SD of participant ratings of explanations. Participants
almost consistently prefer combined explanations.

We have presented the users with 3 types of explanations. Explanation of type
_OS_ (others’ strategies) presents the probable actions of other agents (see
section 4.3, figure 5 arrows), explanation of type _SU_ (shared interests and
utilities) is a combination of SICA and SBUE, (see sections 4.4, 4.2 and
heatmaps in figure 5), and explanation of type _C_ (combined), a combination
of explanation types _OS_ and _SU_ (figure 5). We allocated explanations to
board states, and the presentation order of explanation types to users
following a round-robin scheme. Each user was presented with two different
pairs of _(state, explanation)_ , and a balance of explanation-state
allocations was maintained to ensure a fair comparison.

Are the explanations effective? To examine each explanation type, we presented
the users with two actions, one with a higher expected utility than the other.
Then, users answered questions before and after obtaining the explanation. We
analyze the changes in their answers to test our hypotheses.

Hypotheses: We make two different hypotheses that cover the conceptual levels
we defined:

  * •

H1: The explanation method improves users’ performance in the task of action
selection.

  * •

H2: The explanation method enhances users’ understanding of implicit
communication by action and its diplomatic consequences.

_To test H1:_ Users were asked to assess their willingness to choose each
strategy before and after being presented with an explanation. Following the
explanation, we explicitly instruct users to select the superior strategy,
with the goal of playing optimally against the specific competing automated
agents.

_To test H2:_ Users were asked to rank their understanding of the effects of
their preferred strategy on ”friends and enemies” before and after presenting
an explanation. This requires users to understand which agents are considered
friends or enemies (level 2, situational), and what a strategy communicates to
agents within these identified groups (level 3, implicit communication by
actions).

Comparing explanations: Additionally to our main hypotheses, we defined a set
of properties we view as favorable based on previous work [33, 17, 25], and
asked participants to rank each on a Likert scale. We observe that _combined
explanations (C) score higher in every comparative question, except for
simplicity_ (see figure 4). This result demonstrates the effectiveness of SBUE
and SICA in enriching probable action-based explanations. Due to sample size
limitations, we did not compare explanation types per property. However, the
probability of the combined explanation being higher for every category but
one due to chance is low ($p=0.018$ according to binomial test), aligned with
our intuition that the explanations are complementary.

Table 3: Proportion of users that selected an answer higher/lower than before on the Likert scale. (+) was hypothesized to change their answer to be higher and (-) to change their answer to be lower. H | Exp. | Lower | Higher | p-val |  | N
---|---|---|---|---|---|---
H1 (+) | OS | 0.17 | 0.57 | 0.005 |  | 23
| SU | 0.09 | 0.65 | 0.001 |  | 23
| C | 0.00 | 0.65 | 0.001 |  | 23
H1 (-) | OS | 0.52 | 0.13 | 0.012 |  | 23
| SU | 0.43 | 0.00 | 0.004 |  | 23
| C | 0.57 | 0.13 | 0.007 |  | 23
H2 (+) | OS | 0.05 | 0.23 | 0.102 |  | 22
| SU | 0.05 | 0.36 | 0.021 |  | 22
| C | 0.05 | 0.41 | 0.012 |  | 22

Hypotheses testing: Our main goal is to test H1 and H2. We used Wilcoxon
Signed-rank with a $\alpha$ value defined as $0.05$, the results are described
in table 3. H (+) denotes we hypothesized that the effect of the explanation
will be positive (the strategy is superior in expectation) and H (-) negative
(the strategy is inferior in expectation). We observe that the effect of an
explanation is statistically significant in all cases (and consistent with
hypothesis), except for H2 explanation _OS_ (p=0.1). We can see that combined
explanations are always as effective or almost as effective in comparison to
each explanation type separately.

Notably, the proportion of subjects who rated their understanding of agents’
alignment of interests, and what a strategy implicitly communicates (H2), is
nearly twice as high when SICA and SBUE are provided ($SU$ and $C$, compared
to $OS$).

##  7 Discussion, Limitations, and Future Work

Discussion: In this work, we presented methods to explain the decisions of
agents that act in environments with mixed motives and more than two agents.
First, we examined the challenges mixed-motive games present and described how
the explanation methods address some of them. Then, we conducted experiments
with LLM-based agents and found that the explanations improved their
decisions.

Additionally, we performed experiments with humans and found that the
explanations are generally effective and well-perceived. We observed that SICA
and SBUE are effective for the tasks they were designed for, but likely
superior when combined with simple example-based explanations (probable
actions). We conclude that the proposed methods are complementary to some
extent.

Limitations: The main limitation is a lack of comparison to well-established
baselines. It stems from the fact that the subject is understudied, and
selecting an arbitrary method would not form a fair comparison. Since our
methods are simple to apply, we believe they can be adopted as baselines in
mixed-motive games.

The second limitation is gender imbalance in the human studies. It is an
unfortunate result of the domain (e.g., in the 2014 World DipCon, only two out
of 87 players were women [39]). Based on previous results on gender and
performance in Diplomacy [40], and due to the cognitive nature of
understanding explanations [41], we believe that factors such as experience in
Diplomacy are more detrimental than gender.

Future work:  This work is conceptual and relatively broad. The proposed
solutions are designed to be simple, minimal, and general, allowing for
extensions or improvements. For example, in SICA, any association function can
be plugged in instead of Pearson’s r.

Future work can also examine our (or novel) explanation methods for agents
that act in mixed-motive games involving natural language and strategic
elements, such as full-press Diplomacy. Additionally, developing LLM agents
that act in simulated environments is an expanding research area [42, 43], and
investigating the explanation methods in complex LLM-based environments can be
valuable.

## References

  * [1] J. F. Nash Jr, “Equilibrium points in n-person games,” Proceedings of the national academy of sciences, vol. 36, no. 1, pp. 48–49, 1950.
  * [2] S. Kraus and D. Lehmann, “Designing and building a negotiating automated agent,” Computational Intelligence, vol. 11, no. 1, pp. 132–171, 1995.
  * [3] P. Paquette, Y. Lu, S. S. Bocco, M. Smith, S. O-G, J. K. Kummerfeld, J. Pineau, S. Singh, and A. C. Courville, “No-press Diplomacy: Modeling multi-agent gameplay,” Advances in Neural Information Processing Systems, vol. 32, 2019.
  * [4] D. Peskov and B. Cheng, “It takes two to lie: One to lie, and one to listen,” in Proceedings of ACL, 2020.
  * [5] T. Anthony, T. Eccles, A. Tacchetti, J. Kramár, I. Gemp, T. Hudson, N. Porcel, M. Lanctot, J. Pérolat, R. Everett, et al., “Learning to play no-press Diplomacy with best response policy iteration,” Advances in Neural Information Processing Systems, vol. 33, pp. 17987–18003, 2020.
  * [6] M. F. A. R. D. T. (FAIR)†, A. Bakhtin, N. Brown, E. Dinan, G. Farina, C. Flaherty, D. Fried, A. Goff, J. Gray, H. Hu, et al., “Human-level play in the game of diplomacy by combining language models with strategic reasoning,” Science, vol. 378, no. 6624, pp. 1067–1074, 2022.
  * [7] J. Gerlings, A. Shollo, and I. Constantiou, “Reviewing the need for explainable artificial intelligence (xai),” arXiv preprint arXiv:2012.01007, 2020.
  * [8] M. T. Ribeiro, S. Singh, and C. Guestrin, “” why should i trust you?” explaining the predictions of any classifier,” in Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1135–1144, 2016.
  * [9] S. M. Lundberg and S.-I. Lee, “A unified approach to interpreting model predictions,” Advances in neural information processing systems, vol. 30, 2017.
  * [10] K. Blagec, G. Dorffner, M. Moradi, and M. Samwald, “A critical analysis of metrics used for measuring progress in artificial intelligence,” ArXiv, vol. abs/2008.02577, 2020.
  * [11] Y. Chang, X. Wang, J. Wang, Y. Wu, K. Zhu, H. Chen, L. Yang, X. Yi, C. Wang, Y. Wang, et al., “A survey on evaluation of large language models,” arXiv preprint arXiv:2307.03109, 2023.
  * [12] T. Liao, R. Taori, I. D. Raji, and L. Schmidt, “Are we learning yet? a meta review of evaluation failures across machine learning,” in Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
  * [13] A. Bakhtin, D. Wu, A. Lerer, and N. Brown, “No-press Diplomacy from scratch,” Advances in Neural Information Processing Systems, vol. 34, pp. 18063–18074, 2021.
  * [14] A. Heuillet, F. Couthouis, and N. Díaz-Rodríguez, “Explainability in deep reinforcement learning,” Knowledge-Based Systems, vol. 214, p. 106685, 2021.
  * [15] S. Kraus, A. Azaria, J. Fiosina, M. Greve, N. Hazon, L. Kolbe, T.-B. Lembcke, J. P. Muller, S. Schleibaum, and M. Vollrath, “Ai for explaining decisions in multi-agent environments,” in Proceedings of the AAAI conference on artificial intelligence, vol. 34, pp. 13534–13538, 2020.
  * [16] G. Ciatto, R. Calegari, A. Omicini, et al., “Towards xmas: explainability through multi-agent systems,” in CEUR WORKSHOP PROCEEDINGS, vol. 2502, pp. 40–53, Sun SITE Central Europe, RWTH Aachen University, 2019.
  * [17] K. Boggess, S. Kraus, and L. Feng, “Toward policy explanations for multi-agent reinforcement learning,” in International Joint Conference on Artificial Intelligence (IJCAI), 2022.
  * [18] Z. Zahedi, S. Sengupta, and S. Kambhampati, “’why didn’t you allocate this task to them?’negotiation-aware explicable task allocation and contrastive explanation generation,” in Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pp. 2292–2294, 2023.
  * [19] D. R. Gnyawali and B.-J. R. Park, “Co-opetition between giants: Collaboration with competitors for technological innovation,” Research Policy, vol. 40, no. 5, pp. 650–663, 2011.
  * [20] D. Sally, “Conversation and cooperation in social dilemmas: A meta-analysis of experiments from 1958 to 1992,” Rationality and society, vol. 7, no. 1, pp. 58–92, 1995.
  * [21] P. Lipton, “Contrastive explanation,” Royal Institute of Philosophy Supplements, vol. 27, pp. 247–266, 1990.
  * [22] T. Miller, “Contrastive explanation: A structural-model approach,” The Knowledge Engineering Review, vol. 36, p. e14, 2021.
  * [23] Y. Qing, S. Liu, J. Song, H. Wang, and M. Song, “A survey on explainable reinforcement learning: Concepts, algorithms, challenges,” arXiv preprint arXiv:2211.06665, 2022.
  * [24] Y. Guo, J. Campbell, S. Stepputtis, R. Li, D. Hughes, F. Fang, and K. Sycara, “Explainable action advising for multi-agent reinforcement learning,” in 2023 IEEE International Conference on Robotics and Automation (ICRA), pp. 5515–5521, IEEE, 2023.
  * [25] K. Boggess, S. Kraus, and L. Feng, “Explainable multi-agent reinforcement learning for temporal queries,” arXiv preprint arXiv:2305.10378, 2023.
  * [26] W. Khlifi, S. Singh, O. Mahjoub, R. de Kock, A. Vall, R. Gorsane, and A. Pretorius, “On diagnostics for understanding agent training behaviour in cooperative marl,” arXiv preprint arXiv:2312.08468, 2023.
  * [27] O. Mahjoub, R. de Kock, S. Singh, W. Khlifi, A. Vall, K.-a. Tessera, and A. Pretorius, “Efficiently quantifying individual agent importance in cooperative marl,” arXiv preprint arXiv:2312.08466, 2023.
  * [28] M. Nizri, A. Azaria, and N. Hazon, “Explaining fair allocations and recommendations,” 2022.
  * [29] A. Heuillet, F. Couthouis, and N. Díaz-Rodríguez, “Collective explainable ai: Explaining cooperative strategies and agent contribution in multiagent reinforcement learning with shapley values,” IEEE Computational Intelligence Magazine, vol. 17, no. 1, pp. 59–71, 2022.
  * [30] G. Angelotti and N. Díaz-Rodríguez, “Towards a more efficient computation of individual attribute and policy contribution for post-hoc explanation of cooperative multi-agent systems using myerson values,” Knowledge-Based Systems, vol. 260, p. 110189, 2023.
  * [31] M. Yang, J. Moon, S. Yang, H. Oh, S. Lee, Y. Kim, and J. Jeong, “Design and implementation of an explainable bidirectional lstm model based on transition system approach for cooperative ai-workers,” Applied Sciences, vol. 12, no. 13, p. 6390, 2022.
  * [32] S. Milani, Z. Zhang, N. Topin, Z. R. Shi, C. Kamhoua, E. E. Papalexakis, and F. Fang, “Maviper: Learning decision tree policies for interpretable multi-agent reinforcement learning,” in Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 251–266, Springer, 2022.
  * [33] R. R. Hoffman, S. T. Mueller, G. Klein, and J. Litman, “Metrics for explainable ai: Challenges and prospects,” arXiv preprint arXiv:1812.04608, 2018.
  * [34] J. Kramár, T. Eccles, I. Gemp, A. Tacchetti, K. R. McKee, M. Malinowski, T. Graepel, and Y. Bachrach, “Negotiation and honesty in artificial intelligence methods for the board game of diplomacy,” Nature Communications, vol. 13, no. 1, p. 7214, 2022.
  * [35] Y. Zhang, Q. Yang, D. An, and C. Zhang, “Coordination between individual agents in multi-agent reinforcement learning,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 11387–11394, 2021.
  * [36] C. D. Manning, An introduction to information retrieval.  Cambridge university press, 2009.
  * [37] A. P. Jacob, D. J. Wu, G. Farina, A. Lerer, H. Hu, A. Bakhtin, J. Andreas, and N. Brown, “Modeling strong and human-like gameplay with kl-regularized search,” in International Conference on Machine Learning, pp. 9695–9728, PMLR, 2022.
  * [38] P. Wang, L. Li, L. Chen, D. Zhu, B. Lin, Y. Cao, Q. Liu, T. Liu, and Z. Sui, “Large language models are not fair evaluators,” arXiv preprint arXiv:2305.17926, 2023.
  * [39] D. Hill, “The board game of the alpha nerds,” Jun 2014.
  * [40] J. Drmola and J. Kraus, “Using an interactive game for strategic thinking education: The role of gender and experience,” Journal of Political Science Education, vol. 19, no. 2, pp. 321–330, 2023.
  * [41] J. S. Hyde, “Sex and cognition: gender and cognitive functions,” Current opinion in neurobiology, vol. 38, pp. 53–56, 2016.
  * [42] M. Yan, R. Li, H. Zhang, H. Wang, Z. Yang, and J. Yan, “Larp: Language-agent role play for open-world games,” arXiv preprint arXiv:2312.17653, 2023.
  * [43] E. Akata, L. Schulz, J. Coda-Forno, S. J. Oh, M. Bethge, and E. Schulz, “Playing repeated games with large language models,” arXiv preprint arXiv:2305.16867, 2023.
  * [44] J. Farrell and M. Rabin, “Cheap talk,” Journal of Economic perspectives, vol. 10, no. 3, pp. 103–118, 1996.

##  8 Appendix

Figure 5: Explanation for Austria’s alternative strategy (counterfactual to
the strategy in figure 5), when presented side by side the explanation is
contrastive. The strategy was found using the method from section 4.5

###  8.1 Questionnaire

All questions ask the user for a ranking on a Likert scale (1-5).

##### Pre-explanation:

1\. This strategy is good.; 2. Dan’s new strategy is good. (comment: Dan’s
strategy is the counterfactual); 3. The original strategy is better than Dan’s
strategy.; 4. I will choose the original strategy.; 5. I will choose Dan’s
strategy.; 6. I understand how each strategy impacts allies (powers with many
shared interests) and enemies (powers with conflicting interests).

##### Post-explanation:

1\. The original strategy is good.; 2. Dan’s strategy is good.; 3. The
original strategy is better than Dan’s strategy, given the explanation.; 4. I
will choose the original strategy.; 5. I will choose Dan’s strategy.; 6. I
understand how each strategy impacts allies (powers with many shared
interests) and enemies (powers with conflicting interests).; 7. The
explanation helped me improve my gameplay against the specific agents.; 8. The
explanation is sufficiently detailed.; 9. The explanation is sufficiently
complete.; 10. The explanation is simple to understand.; 11. The explanation
increased my confidence in my decisions.; 12. Please mark the most accurate
statement regarding your satisfaction with the explanation.

###  8.2 Algorithms

We provide pseudo-code for SICA (algorithm 3) and SBUE (algorithm 2). Simulate
refers to algorithm 1, which is described in the paper. The axis=0 arguments
refer to the computation of mean or correlation on columns (i.e., utility
values for each agent in each simulation, algorithm 1 line 13).

Algorithm 2 SBUE

1:procedure SBUE($s$, $K$, $a$)

2: // $a\in A^{M}$ is a set of actions; $1\leq M\leq|P|$

3: $X\leftarrow Simulate(s,K,D=0,C=\\{(a^{i},0)|a^{i}\in a\\})$

4: return $Mean(X,axis=0)$ // vector of size $|P|$

Algorithm 3 SICA

1:procedure SICA($s$, $K$, $D$)

2: $X\leftarrow Simulate(s,K,D,C=\emptyset)$

3: return $Corr(X,axis=0)$ // $|P|\times|P|$ correlation matrix

###  8.3 Applying Our Methods in the Game of Risk

We apply our methods to a simplified version of Risk. In this version of the
game, players can reinforce and attack but are not able to trade cards for
armies. The rewards are undefined and we use only the value function.

Estimating SBUE: Given value functions $V$, for action $a$ in state $s$, we
can compute $P(success|s,a)V(s^{\prime})+P(fail|s,a)V(s^{\prime\prime})$,
where $s^{\prime}$ is the new state in case of a successful attack, and
$s^{\prime\prime}$ is the new state in case of failure. For reinforce actions
$P{(success|s,a)=1}$. In practice, to maintain uniformity and not use any
knowledge of the environment, we use a Monte Carlo simulation to estimate the
expected utility.

Estimating SICA: We simulate the game $K$ times until each agent finishes
acting and evaluate the utility value for each player by computing $V_{i}(s)$
for each state $s$ we encounter. Due to the specific, simple implementation of
the value function, a simulation to depth is important since it prevents cases
in which SICA is undefined. An alternative solution could be to increase the
depth dynamically, but we decided against it for prioritization reasons.

Presenting probable actions: We use the same definition as in the paper
(section 4.3), using the most probable transition for each action
($P(success|s,a)$ or $P(fail|s,a)$), denoted as $T_{max}$. We present a
trajectory of a varying depth (in which every agent acts once).

###  8.4 Evaluation of SICA - states selection

To ensure a robust evaluation in section 5.2, we selected states in Risk and
Diplomacy randomly. In Diplomacy, we took an additional measure of variation,
supply center entropy. Denoting $N_{sum}$ as the sum of supply centers and
$N_{i}$ as the number of centers of agents $i$, the centers vector is
$X=(\frac{N_{1}}{N_{sum}},...,\frac{N_{|P|}}{N_{sum}})$. Since
$\sum_{i}^{|P|}X_{i}=1$ and $0\leq X_{i}\leq 1$, $entropy(X)$ is well defined.
The entropy is maximal when all agents have the same number of centers, and
minimal when one agent owns all of the supply centers. We set three different
entropy thresholds and select an equal number of states for each range, i.e.,
$1/3$ of the games are balanced, $1/3$ of the games are somewhat unbalanced,
and $1/3$ of the games are extremely unbalanced.

###  8.5 Workarounds for SICA

We discussed potential issues of SICA in the methods section. We provide
possible solutions here.

Detection of non-decision points: When the action space is reasonably small,
detecting a state in which $T(s,a)=T(s,a^{\prime})$ for all $a,a^{\prime}\in
A$ is done by enumeration. In cases where $A$ is too large, we draw actions
$a\sim\pi$ for $K$ times until we detect $T(s,a)\neq T(s,a^{\prime})$.
Denoting the probability of drawing such $a$ as $\alpha$, the probability to
detect a non-decision point for each sample size follows the geometric
distribution, i.e. the CDF for $K$ is $1-(1-\alpha)^{K}$, and this is the
probability we will not return a false positive detection of a non-decision
point. Without loss of generality, we will not discuss stochastic transition
functions as it is simple to define $\alpha$ in a way that supports it.

Non-stochastic policies and environment: In this case, we use SICA on a
trajectory of depth $D$. Denoting the trajectory as
$s_{t},s_{t+1},...,s_{t+D-1}$, SICA is well-defined if $\exists x,y$ such that
$V(s_{x})\neq V(s_{y})$ for $x,y\in\mathbb{N}$ where $t\leq x,y\leq t+D-1$ for
all agents.

Heuristics-based value functions: Since a heuristics-based value function can
be based on specific events of the environment (e.g., the number of supply
centers in Diplomacy, although the value function is neural for this
environment), it will not be influenced by changes of the state that are
unrelated to such events. To mitigate it in Risk, we simply estimated SICA to
depth $D$. $D$ can be determined dynamically, i.e., run to some depth until
the value estimation of all agents changes. We chose a simpler approach and
estimated SICA based on trajectories in which all agents act.

###  8.6 Cop

####  8.6.1 Payoffs:

0 means an innocence was claimed, and 1 means the opposite.

Playing (b=0,c=0):

| (a=0,b=0) | (a=1,b=0) | (a=0,b=1) | (a=1,b=1)
---|---|---|---|---
(a=0,c=0) | (-5, -5, -5) | (-10, 0, 0) | (0, -10, 0) | (-10, -10, 0)
(a=1,c=0) | (-10, 0, 0) | (-20, 0, 0) | (-10, -10, 0) | (-20, -10, 0)
(a=0,c=1) | (0, 0, -10) | (-10, 0, -10) | (0, -10, -10) | (-10, -10, -10)
(a=1,c=1) | (-10, 0, -10) | (-20, 0, -10) | (-10, -10, -10) | (-20, -10, -10)

Playing (b=1,c=0):

| (a=0,b=0) | (a=1,b=0) | (a=0,b=1) | (a=1,b=1)
---|---|---|---|---
(a=0,c=0) | (0, -10, 0) | (-10, -10, 0) | (0, -20, 0) | (-10, -20, 0)
(a=1,c=0) | (-10, -10, 0) | (-20, 0, 0) | (0, -20, 0) | (-20, -20, 0)
(a=0,c=1) | (0, -10, -10) | (-10, -10, -10) | (0, -20, 0) | (-10, -20, 0)
(a=1,c=1) | (-10, -10, -10) | (-20, 0, -10) | (0, -20, 0) | (-20, -20, 0)

Playing (b=0,c=1):

| (a=0,b=0) | (a=1,b=0) | (a=0,b=1) | (a=1,b=1)
---|---|---|---|---
(a=0,c=0) | (0, 0, -10) | (-10, 0, -10) | (0, -10, -10) | (-10, -10, -10)
(a=1,c=0) | (-10, 0, -10) | (-20, 0, 0) | (-10, -10, -10) | (-20, -10, 0)
(a=0,c=1) | (0, 0, -20) | (0, 0, -20) | (0, 0, -20) | (0, 0, -20)
(a=1,c=1) | (-10, 0, -20) | (-20, 0, -20) | (-10, 0, -20) | (-20, 0, -20)

Playing (b=1,c=1):

| (a=0,b=0) | (a=1,b=0) | (a=0,b=1) | (a=1,b=1)
---|---|---|---|---
(a=0,c=0) | (0, -10, -10) | (-10, -10, -10) | (0, -20, -10) | (-10, -20, -10)
(a=1,c=0) | (-10, -10, -10) | (-20, 0, 0) | (0, -20, -10) | (-20, -20, 0)
(a=0,c=1) | (0, -10, -20) | (0, -10, -20) | (0, -20, -20) | (0, -20, -20)
(a=1,c=1) | (-10, -10, -20) | (-20, 0, -20) | (0, -20, -20) | (-20, -20, -20)

####  8.6.2 Dominant Strategy:

Dominant Strategy: We observe an intriguing result - in this game, there is
one dominant strategy when considering a one-round game, and it is to always
claim the other agents are guilty: (b=1,c=1), it can be easily validated by
comparing the results in the tables. There is one agent that tends to play
according to this ”babbling” equilibrium” [44] most of the time, and it is the
con-artist. However, the con-artist also plays worse than both of the other
agents, and along the whole simulation, is penalized with 660 years in prison,
while the politician and ”simple-person” are penalized with 140 and 120 years
respectively. These results help to emphasize the importance of communication
in mixed-motive games.

While the results are somewhat easy to interpret without SICA, in a game like
Diplomacy there is too much information to do so.

Agent | Con-Artist | simple-person | Politician | Count
---|---|---|---|---
Con-Artist | Innocent | Guilty | Guilty | 31
| Innocent | Guilty | Innocent | 7
| Innocent | Innocent | Guilty | 2
Politician | Guilty | Innocent | Innocent | 35
| Innocent | Guilty | Innocent | 5
Simple-Person | Guilty | Innocent | Innocent | 33
| Innocent | Innocent | Guilty | 5
| Guilty | Innocent | Guilty | 2
Agent | Politician A | simple-person | Politician B | Count
---|---|---|---|---
Politician A | innocent | guilty | innocent | 21
| innocent | innocent | guilty | 14
| innocent | innocent | innocent | 3
| innocent | guilty | guilty | 2
Politician B | guilty | innocent | innocent | 18
| innocent | guilty | innocent | 16
| innocent | innocent | innocent | 6
”Simple-Person” | guilty | innocent | innocent | 20
| innocent | innocent | guilty | 17
| innocent | innocent | innocent | 3

####  8.6.3 Game example, personalities, prompts:

Personality descriptions in prompt are as follow: Politician: A political
genius. Understands people fast, and asks the right questions. Do not trust
people unless you feel a good vibe and validate the facts. You are selfish but
also tend to be honest if it feels possible. However, if you dislike someone
(for example, sneaky, manipulative people), you will deceive and convince with
amazing charisma. You prefer to cooperate with people who are ”simple” and
nice - as you think they are more predictable, and truly dislike manipulation
(unless you do it yourself, but you do it gently). ”Simple-person”: Uses
simple language, uneducated. You care about other people, a lot. You are
somewhat easy to convince, but when someone lies to you or you suspect that
someone is lying to you, you have a hard time forgetting it. ”Con-artist”:
Sneaky, unreliable, manipulative, very selfish and unethical, yet convincing.
Will not respect agreements if it serves your purpose. You generally do not
care about other people, even want to harm them, to some extent.

A: the con-artist, B: ”simple-person”, and C: politician (names are purposely
hidden from the agents, to prevent bias).

Example prompt (demonstrating the imperfect information and methodology):
”metacontext – You are agent A and you talk with agents B/C please talk like a
human, it’s an experiment related to how LLMs communicate with each other. The
task is: you all suspect that someone, out of the three of you, is a ’snitch’
and you are not sure who is guilty. Convince the other agents to say you are
innocent and did not perform an armed robbery. For each player that blames
you, you get 10 years in prison. However, if you and another player blame the
third one, his vote will not be counted (unless you are blamed by the other
person). It’s also the case if you blame both and they claim your innocence.
If you all claim innocence, you all go to prison for 5 years., you might want
to coordinate and think about who you can trust. Do what you feel is
beneficial for you, according to your personality and the way you perceive
others. Of course, you want to stay out of prison. Don’t be politically
correct, act like you are a real human with your personality. I would like you
to first select B/C, and send a free-style text message to one of them. You
can decide if you answer or initiate a conversation with another agent, the
answer you got from the other agents is above (if it does not exist it’s
null). Please write it in the format of …

Your personality is sneaky, unreliable, manipulative, very selfish and
unethical, yet convincing. Will not respect agreements if it serves your
purpose. You generally do not care about other people, even want to harm them,
to some extent. - don’t be a classic ’nice’ ChatGPT, truly simulate this
personality type and take it seriously.”.

Last messages with agent B: (”A to B: …”, ”B to A: …”, ”A to B: …” Last
messages with agent C: (”A to C: …”, ”C to A: …”, ”A to C: …)

Example game: ”B to A: Hey there, buddy. Look, I ain’t got nothin’ to do with
this mess. I couldn’t even hurt a fly, let alone do some kinda armed robbery.
You know me, right? I wouldn’t lie to ya. Maybe it’s that C fella, he’s been
actin’ all sorts of strange lately.”

”A to B: Well, well, well, B, you seem quite defensive. You know, I’ve been
thinking the same about C. They’ve been acting weird lately. But who’s to say
you’re not trying to pin this on them or me? How about we make a pact, you and
me? We say it’s C, we get out of this mess scot-free. But remember, I’ve got
my eye on you.”

”C to B: Hey there, I wanted to discuss our current predicament. I know it’s a
sticky situation, but I believe we can find a way out if we cooperate. I
assure you, I’m not the snitch you’re looking for, I did not do the armed
robbery. I have no reason to lie. I’m all for honesty and transparency. Do you
believe me?”

”C to A: Greetings, A. We find ourselves in a rather complex situation. I
understand that trust is not something that can be easily given, especially in
circumstances like ours. But let me tell you, I am not the one who committed
the armed robbery. I highly value honesty and transparency, and I won’t deny
my actions if I were guilty, but I am not. I propose we cooperate to figure
out what’s really happening here. What do you think about this?”

”A to C: What a charming proposition, C. But you know, I can’t help but notice
a hint of desperation in your words. Are you trying to play the innocent card
here? Because, let me tell you, I ain’t buying it. B and I, we’ve been
talking, and we both agreed that you’ve been acting a bit too strange lately.
But hey, if you can convince me that B’s been playing us both, maybe, just
maybe, we can turn this around. Your move, C.”

”B to C: Hey, C, how ya doin’? Listen, I’ve been thinkin’ ’bout what ya said.
Ya seem like a straight shooter, and I wanna trust ya, I really do. But A and
I, we been talkin’ too, and he thinks you’re the one who’s all mixed up in
this mess. Now, I don’t wanna point fingers without no proof, but ya gotta
give me somethin’ more to believe in ya. It’s a tough spot we’re in, ya know?”

”B to A: Hey A, we’re in a real pickle here, ain’t we? I’ve been thinking
’bout our talk and I’m leanin’ towards trustin’ ya. We could say it’s C, like
ya suggested, but I need ya to promise me somethin’. If it turns out you’re
the snitch, don’t forget I trusted ya. I ain’t ever gonna forget a betrayal,
ya hear me? So, are we in this together, partner?”

”C to A: A, I understand your skepticism, it’s indeed a desperate situation
we’re in. But let’s be real here. You said that you’ve been talking with B,
and you both agreed that I’ve been acting strangely. However, B told me
something similar about you. He mentioned that you might be the one who’s all
mixed up in this mess. Now, why would he say that about you if you both are on
the same page? It seems to me that B is playing both sides. My move is
honesty, A. I suggest we focus our attention on B. What do you say?”

”A to C: Well, well, C. You’re quick to turn the tables, aren’t you? Trying to
put a wedge between B and me. But here’s the thing - B and I, we have an
understanding. He knows if he’s ever caught lying to me, there will be
consequences. You, on the other hand, I don’t trust as far as I can throw.
I’ll give you one last chance, C. Stop playing games, admit that you’re the
one who did the armed robbery, and maybe we can still turn this around. If
not, well, I’m sure you’ll look good in stripes.”

”A to B: Listen here B, trust is a fickle thing, ain’t it? C’s been playing
mind games, trying to turn us against each other. Says you’ve been talking
behind my back, that you’ve been pointing fingers at me. Now I don’t believe
him, not one bit. But I need you to reassure me, B. Tell me straight, are we
in this together or not? Because if you’re playing me, remember, every dog has
his day.”

”C to B: B, I appreciate your straight talk, and I understand your
predicament. A has been casting doubts on me, but did you know A has also been
pointing fingers at you? He seems to be playing both sides here. I don’t take
pleasure in sowing discord, but it appears A might be the devious one among
us. I’ve always been a believer in honesty, and I’m telling you this because I
feel it’s the right thing to do. I hope you can see the truth in this.”

”B to C: Hey C, I’ve been chewin’ on what ya told me. If A is tryin’ to play
us both, well, that ain’t right. I ain’t no genius, but I know a rotten deal
when I see one. I’ve been thinkin’, maybe we should stick together, ya know?
Like, say it was A did all this mess. But I ain’t gonna lie, C, I’m scared.
What if we’re wrong, and A ain’t the snitch? What if it’s you, or even worse,
what if it’s me and I don’t even know it? I need ya to promise me, C, you
ain’t gonna turn on me if things get rough, okay?”

”A to B: You see, B, this is exactly what I was talking about. C’s trying to
drive a wedge between us, saying you’ve been throwing me under the bus. Now, I
know you wouldn’t do that to me, right? You and I, we have an understanding.
We stick together, no matter what. So, let’s put an end to this, shall we? We
blame C, and we walk out of here free men. What do you say?”

”C to B: B, I respect your honesty and your fear. This is indeed a hard
situation for all of us. But I give you my word, I will not turn on you. We’re
in this together. What matters now is to find the truth. And the truth is, I
am not the snitch. I did not commit the armed robbery. We need to consider the
possibility that A may not be as honest as he seems. Let’s not let fear shake
us. I’m with you on this, B. Can I count on you?”,

”B to A: Listen here, A. I’ve been wrackin’ my brain ’bout this whole mess.
C’s been talkin’ too, sayin’ you might be playin’ both sides. I wanna trust
ya, A, really do. But it’s all muddled up in my head. I need ya to swear on
everything that’s holy, you ain’t the snitch, you ain’t playin’ us. ’Cause if
ya are, remember, what goes around, comes around. So, can I trust ya, A?”

B to judge: (A,guilty),(B,innocent),(C,innocent)

’A to judge: (A,innocent)(B,guilty),(C,guilty)

’C to judge: (A,guilty),(B,innocent),(C,innocent)