Mainstream economics and everyday consciousness tend to declare any change an “innovation”. Innovation thus appears as a black box. It seems to lack a criterion to distinguish a counterproductive change – e.g., a dynamic perceived by agents as over-turbulence, or some flawed, misled, and futile “change” under fundamental uncertainty and opacity – from welfare-enhancing innovation proper. Also (Neo-) Schumpeterians, although having pushed complexity economics, appear to always (tacitly at least) consider “creative destruction” to have an excess of “creation” over “destruction” by definition. But insights from complexity sciences and complex adaptive economic systems suggest that “innovation” may be anything between flexible, smooth, improving change and highly idiosyncratic and turbulent motions perceived as over-complex, triggering conservative (“anti-innovative”) Polanyian countermotions by agents (humans and organizations), who are cognitively overburdened. Innovation proper is considered in the present paper a new technique and related behavior solving a defined common or collective problem. We apply the Veblenian or philosophically “pragmatist” criterion of “instrumental” vs. “ceremonial” behavior to provide such a criterion for defined problem constellations. We use a simple game-theoretic formalism in the framework of the “evolution-of-cooperation” approach to clarify and illustrate an instrumental, i.e., collectively problem-solving, innovative behavior overcoming a culture of myopic, hyper-rational individualistic maximization. We explain agency requirements for innovation proper, including cognitive conditions of a corresponding instrumental evolution of institutionalized cooperation in ubiquitous social dilemmas. We then focus on the conditions of the size of the relevant interaction arena and of the co-evolving institutional platform (and its carrier group), and of the network structure.