Techniques are described for using multiple successive interactions with multiple responders in order to perform a variety of types of tasks, such as to generate solutions to abstract or conceptual problems. In some situations, at least some of the multiple responders are humans available to perform tasks and/or provide information, such as to provide responses to questions in exchange for payment. The multiple successive interactions with the responders may be used to iteratively refine the problem and its abstract intermediate solutions until the refinements are sufficiently detailed and tangible as to allow detailed final solutions to be generated. In some situations, the interactions with the responders may be performed as part of an automated service for generating solutions to a variety of types of problems, such as in exchange for payment from the users or others who specify the problems.