\section{Measuring communication impact}
\label{sec:setup}

\paragraph{Message Effect} is computed
on single turns and uses causal theory \citep{Pearl:etal:2016} to
quantify how much what an agent utters impacts the other, compared to
the counterfactual scenario in which the speaking agent said something
else.

Consider message $m^A_t$ uttered by A at turn $t$. If
$c^A_t=0$ (that is, A continues the game), $m^A_t$ is processed by
 B, along with $s^B_{t-1}$ and $i^B$. At the next turn, B outputs
a choice $c^B_{t+1}$ and a message $m^B_{t+1}$ drawn from
$p(c^B_{t+1},m^B_{t+1}|s^B_{t+1})$. B's state $s^B_{t+1}$ is
deterministically determined by $m^A_t,c^A_t,s^B_{t-1},i^B$, so we can
equivalently write that $c^B_{t+1}$ and $m^B_{t+1}$ are drawn from
$p(c^B_{t+1},m^B_{t+1}|m^A_t,c^A_t,s^B_{t-1},i^B)$. Conditioning on
$c^A_t,s^B_{t-1},i^B$ ensures there are no confounders when we analyze
the influence from $m^A_t$ \citep{Pearl:etal:2016}. Supplementary Figure
\ref{fig:causalgraph} shows the causal graph supporting our assumptions. We
will not from here onwards write the conditioning on
$c^A_t,s^B_{t-1},i^B$ explicitly.

We define $z^B_{t+1}=(c^B_{t+1},m^B_{t+1})$. We want to estimate how much the message from A, $m^A_t$, influences the next-turn behaviour (choice and message) of B, $z^B_{t+1}$. % \footnote{We consider only one-turn influence, and disregard the influence a message could have at more that one turn away.}
We thus measure the discrepancy between the conditional distribution $p(z^B_{t+1}|m^A_t)$ and the marginal distribution $p(z^B_{t+1})$ not taking $m^A_t$ into account. However, we want to assess agent B's behaviour under \emph{other possible received messages} $m^A_t$. To do so, when we compute the marginal of agent B's $p(z^B_{t+1})$, we intervene on $m^A_t$ and draw the messages from the \emph{intervention distribution}. We define $\tilde{p}(z^B_{t+1})$, the marginal computed with counterfactual messages $m'^A_t$, as:
\begin{align}
\tilde{p}(z^B_{t+1})=\sum_{m^A_t}p(z^B_{t+1}|m'^A_t)\tilde{p}(m'^A_t)
\label{eq:margint}
\end{align}
where $\tilde{p}(m'^A_t)$ is the intervention distribution, different from $p(m^A_t|s^A_t)$. If at turn $t$, A continues the game, we define the \emph{Message Effect} ($\text{ME}$) from agent A's message $m^A_t$ on agent B's choice and message pair, $z^B_{t+1}$ as:
\begin{align}
&\text{ME}^{A\rightarrow B}_t=\text{KL}\Big(p(z^B_{t+1}|m^A_t)||\tilde{p}(z^B_{t+1})\Big)
\end{align}
where $\text{KL}$ is the Kullback-Leibler divergence, and $\tilde{p}(z^B_{t+1})$ is computed as in Eq.~\ref{eq:margint}. This allows us to measure how much the conditional distribution differs from the marginal. Algorithm \ref{algo:algoME} shows how we estimate $\text{ME}^{A\rightarrow B}_t$. In our experiments, we draw $K=10$ samples $z^B_{t+1,k}$, and use a uniform intervention distribution $\tilde{p}(m'^A_t)$ with $J=10$. This kind of counterfactual reasoning is explored in depth by \citet{Bottou:etal:2013}. \citet{Jaques:etal:2018} and \newcite{Lowe:etal:2019} present related
measures of causal impact based on the Mutual Information (MI) between
influencing and influenced agents. We discuss in Supplementary Section
\ref{suppsec:me} possible issues with the MI-based approach.

\newcommand{\nextnr}{\stepcounter{AlgoLine}\ShowLn}
\RestyleAlgo{boxed}
\SetAlgoCaptionSeparator{}
\LinesNotNumbered
\begin{algorithm}[t]
Given the message $m^A_t$ from agent A.\\
\nextnr Sample $K$ pairs $z^B_{t+1,k}\sim p(z^B_{t+1}|m^A_t)$.\label{step:sampB}\\
\nextnr Sample $J$ counterfactuals $m'^A_{t,j} \sim \tilde{p}(m'^A_t)$. \label{step:sampCount}\\
\nextnr For each $z^B_{t+1,k}$, do
\label{step:marg}
\vspace{-5pt}
\begin{align}
&\tilde{p}(z^B_{t+1,k})=\sum_{j=1}^{J}p(z^B_{t+1,k}|m'^A_{t,j})\tilde{p}(m'^A_{t,j}). \nonumber
\end{align}
\nextnr Return
\vspace{-5pt}
\begin{align}
\text{ME}^{A\rightarrow B}_t=\frac{1}{K}\sum_{k=1}^{K}\log\frac{p(z^B_{t+1,k}|m^A_t)}{\tilde{p}(z^B_{t+1,k})}. \nonumber
\end{align}
\caption{Computation of $\text{ME}^{A\rightarrow B}_t$.}
\label{algo:algoME}
\end{algorithm}

\paragraph{Bilateral communication} Intuitively, there has been a proper dialogue if, in the course of a conversation, each agent has said at least one thing that influenced the other. We operationalize this through our \emph{bilateral communication}
measure. This is a binary, per-game score, that is positive only if in
the game there has been at least one turn with significant message
effect \emph{in both directions}, i.e., $\exists~t,~t'~s.t.~\text{ME}^{A\rightarrow B}_t > \theta$ and $\text{ME}^{B \rightarrow A}_{t'} > \theta$. We set $\theta=0.1$.\footnote{We considered setting $\theta$ to (i) the average $\text{ME}$ returned by untrained agents, but this led to a threshold extremely close to $0$, and (ii) the average of the agents' $\text{ME}$ values, but this counterintuitively penalized pairs of agents with high overall communication influence.}
