\paragraph{Game dynamics and agent architecture} At the beginning of a
game episode, two neural network agents A and B receive, randomly,
either a pair of tools $(tool_1,tool_2)$ (always sampled from
different categories) or a $fruit$. The agent receiving the tools
(respectively the fruit) will be Tool Player (respectively Fruit
Player) for the episode.\footnote{Agents must learn to recognize the
  assigned role.} The agents are also randomly assigned positions, and
the one in position 1 starts the game. Figure \ref{fig:oneround} shows
two turns of the game in which A (blue/left) is Tool Player and in
position 1. The first turn is indexed $t=0$, therefore A will act on
even turns, B on odd turns. At game opening, each agent passes its
input (tool pair or fruit) through a linear layer followed by a tanh
nonlinearity, resulting in embedding $i_A$ (resp.~$i_B$). Then, at
each turn $t$, an agent, for example A, receives the message
$m^B_{t-1}$ from agent B, and accesses its own previous internal state
$s^A_{t-2}$ (we refer to ``memory'' the addition of the agent's previous state). The message $m^B_{t-1}$ is processed by
a RNN, and the resulting hidden state $h^A_t(m^B_{t-1})$ is
concatenated with the agent previous internal state $s^A_{t-2}$ and
the input embedding $i_A$. The concatenated vector is fed to the Body
module, composed of a linear layer followed by tanh. The
output of the Body module is the new A state, $s^A_t$, fed to
Message and Choice decoders.

The Message decoder is an RNN with hidden state
initialized as $s^A_t$, and outputting a probability distribution
$p(m^A_t|s^A_t)$ over possible A messages. At training time, we
sample a message $m^A_t$; at test time we take
the most probable one. The Choice decoder is a linear
layer processing $s^A_t$ and outputting a softmax-normalized vector of
size $3$. The latter represents the probabilities $p(c^A_t|s^A_t)$
over A's possible choices: (i) $c^A_t=0$ to
continue playing, (ii) $c^A_t=1$ to choose tool $tool_1$ and stop (iii)
$c^A_t=2$ to choose tool $tool_2$ and stop. Again, we sample at training
and argmax at test time. If $c^A_t=0$, the game continues. B receives
 message $m^A_t$, its previous state $s^B_{t-1}$ and input embedding $i_B$, and it outputs the tuple ($m^B_{t+1}$, $c^B_{t+1}$, $s^B_{t+1}$) etc., until an agent stops the game, or the maximum number of turns $T_{\text{max}}=20$ is reached.

 When an agent stops by choosing a tool, for example $tool_1$, we
 compute the two utilities $U(tool_1,fruit)$ and $U(tool_2,fruit)$. If
 $U(tool_1,fruit)\ge U(tool_2,fruit)$, that is the best tool was chosen, shared reward is $R=1$. If
 $U(tool_1,fruit)<U(tool_2,fruit)$ or if the agents reach
 $T_{\text{max}}$ turns without choosing, $R=0$.\footnote{We also
   tried directly using raw or normalized scalar utilities as rewards,
   with similar performances.} During learning, the reward is
 back-propagated with Reinforce \citep{Williams:1992}. When the game
 starts at $t=0$, we feed the agent in position $1$ a fixed dummy
 message $m^0$, and the previous states of the agents $s^A_{t-2}$ and
 $s^B_{t-1}$ are initialized with fixed dummy $s^0$. In the no-memory
 ablation, previous internal states are always replaced by $s^0$. When we block
 communication, agent messages are replaced by $m^0$. Supplementary
 Section \ref{suppsec:imp_details} provides hyperparameter and training
 details.
