Many natural and social systems display global organization and coordination without centralized control. The origin of this global coordination is a topic of great current interest. Here we investigate a density-classification task as a model system for coordination and information processing in decentralized systems. We show that sophisticated strategies, selected under idealized conditions, are not robust to environmental changes. We also demonstrate that a simple heuristic is able to successfully complete the classification task under a broad range of environmental conditions. Our findings hint at the possibility that complex networks and ecologically efficient rules coevolve over time.