Supply and demand affect the values of goods exchanged in cooperative trades. Studies of humans and other species typically describe the standard scenario that an increase in demand leads to a higher price. Here, we challenge the generality of that logic with empirical data and a theoretical model. In our study system, “client” fishes visit cleaner wrasse (Labroides dimidiatus) to have ectoparasites removed, but cleaners prefer client mucus, which constitutes “cheating.” We removed 31 of 65 preselected cleaners from a large isolated reef patch. We compared cleaner-client interactions at the reef and a control reef before removal and 4 weeks after removal. Cleaner fish from the experimental treatment site interacted more frequently with large clients (typically visitors with access to alternative cleaning stations), but we did not observe any changes in service quality measures. A game-theoretic analysis revealed that interaction duration and service quality might increase, decrease, or remain unchanged depending on the precise relationships between key parameters, such as the marginal benefits of cheating as a function of satiation or the likelihood of clients responding to cheating as a function of market conditions. The analyses show that the principle of diminishing return may affect exchanges in ways not predicted by supply-to-demand ratios.