Evolutionary theory predicts that mutualisms based on the reciprocal exchange of costly services should be susceptible to exploitation by cheaters. Consistent with theory, both cheating and discrimination against cheaters are ubiquitous features of mutualisms. Several recent studies have confirmed that host species differ in the extent that they are able to discriminate against cheaters, suggesting that cheating may be stabilized by the existence of susceptible hosts (dubbed “givers”). We use an evolutionary game-theoretical approach to demonstrate how discriminating and giver hosts associating with mutualist and cheater partners can coexist. Discriminators drive the proportion of cheaters below a critical threshold, at which point there is...