Mafia like behavior, where individuals cooperate under the threat of punishment, occurs not only in humans, but is also observed in several animal species. Observations suggest that avian hosts tend to accept a certain degree of parasitism in order to avoid retaliating punishment from the brood parasite. To understand under which conditions it will be beneficial for a host to cooperate, we model the interaction between hosts and parasites as an evolutionary game. In our model, the host's behavior is plastic, and thus, its response depends on the previous interactions with the parasite. We find that such learned behavior in turn is crucial for the evolution of retaliating parasites. The abundance of this kind of mafia behavior oscillates in time and does not settle to an equilibrium. Our results suggest that retaliation is a mechanism for the parasite to evade specialization and to induce acceptance by the host.