Game–theory models have indicated that the evolution of mixed strategies of cheating and honesty in many mutualisms is unlikely. Moreover, the mutualistic nature of interspecific interactions has often been difficult to demonstrate empirically. We present a game–theory analysis that addresses these issues using cleaning symbioses among fishes as a model system. We show that the assumption of constant pay–offs in existing models prevents the evolution of evolutionarily stable mixed strategies of cheating and honesty. However, when interaction pay-offs are assumed to be density dependent, mixed strategies of cheating and honesty become possible. In nature, cheating by clients often takes the form of retaliation by clients against cheating cleaners, and we show that mixed strategies of cheating and honesty evolve within the cleaner population when clients retaliate. The dynamics of strategies include both negative and positive effects of interactions, as well as density-dependent interactions. Consequently, the effects of perturbations to the model are nonlinear. In particular, we show that under certain conditions the removal of cleaners may have little impact on client populations. This indicates that the underlying mutualistic nature of some interspecific interactions may be difficult to demonstrate using simple manipulation experiments.