How does social structure affect the capacity for innovation? The structure of social networks has a strong impact on how cultural conventions spread and evolve. However, not much is known about its impact on problem solving strategies and the tendency to explore or exploit the solution space. In other words, which kind of social structure facilitates the solution of which kind of problems? We plan a two-side study involving an agent-based simulation and a collective problem solving ex-periment. The study explores the dynamics of exploration-exploitation in joint problem solving by manipulating the structure of social network and the information available to participants (knowing the maximum possible score or not).