A biblioteca é fornecida pelo pacote libtcmalloc-minimal4 , disponível em repositórios para 16.04 (e 16.10).
O jogo requer a versão de 32 bits da biblioteca que parece (pista encontrada em esta questão do GitHub ) por isso, se você estiver executando um sistema de 64 bits e não tiver pacotes de 32 bits, será necessário executar:
sudo dpkg --add-architecture i386
e, em seguida, instale com o sufixo :i386 :
sudo apt install libtcmalloc-minimal4:i386