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 no benefit to investing resources into discrimination. This promotes givers, who benefit from mutualists but allow cheater populations to rebound. We then apply this model to the plant-mycorrhizal mutualism and demonstrate it is one mechanism for generating host-specific responses to mycorrhizal fungal species necessary to generate negative plant-soil feedbacks. Our model makes several falsifiable, qualitative predictions for plant-mycorrhizal population dynamics across gradients of soil phosphorus availability and interhost differences in ability to discriminate. Finally, we suggest applications and limitations of the model with regard to coexistence in specific biological systems.