Theory assumes that fair trade among mutualists requires highly reliable communication. In plant-animal mutualisms the reliability of cues that indicate reward quality is often low. Therefore, it is controversial whether communication allows animal mutualists to regulate their reward intake. Here we show that even loose relationships between fruit brightness and nutritional rewards (r2 = 0.11-0.35) allow birds to regulate their nutrient intake across distinct European plant-frugivore networks. Resident, over-wintering generalist frugivores that interact with diverse plant species select bright, lipid-rich fruits, whereas migratory birds select dark, sugar- and antioxidant-rich fruits. Both nutritional strategies are consistent with previous physiological experiments suggesting that over-wintering generalists aim to maximize their energy intake, whereas migrants aim to enhance the build-up of body fat, their immune response and oxidative status during migration. Our results suggest that animal mutualists require only weak cues to regulate their reward intake according to specific nutritional strategies.