  We propose an interactive multi-agent classifier that provides provable
interpretability guarantees even for complex agents such as neural networks.
These guarantees consist of lower bounds on the mutual information between
selected features and the classification decision. Our results are inspired by
the Merlin-Arthur protocol from Interactive Proof Systems and express these
bounds in terms of measurable metrics such as soundness and completeness.
Compared to existing interactive setups, we rely neither on optimal agents nor
on the assumption that features are distributed independently. Instead, we use
the relative strength of the agents as well as the new concept of Asymmetric
Feature Correlation which captures the precise kind of correlations that make
interpretability guarantees difficult. We evaluate our results on two
small-scale datasets where high mutual information can be verified explicitly.
