The evolution of cooperation is a paradox because natural selection should favor exploitative individuals that avoid paying their fair share of any costs. Such conflict between the self-interests of cooperating individuals often results in the evolution of complex, opponent-specific, social strategies and counterstrategies. However, the genetic and biological mechanisms underlying complex social strategies, and therefore the evolution of cooperative behavior, are largely unknown. To address this dearth of empirical data, we combine mathematical modeling, molecular genetic, and developmental approaches to test whether variation in the production of and response to social signals is sufficient to generate the complex partner-specific social success seen in the social amoeba Dictyostelium discoideum. Firstly, we find that the simple model of production of and response to social signals can generate the sort of apparent complex changes in social behavior seen in this system, without the need for partner recognition. Secondly, measurements of signal production and response in a mutant with a change in a single gene that leads to a shift in social behavior provide support for this model. Finally, these simple measurements of social signaling can also explain complex patterns of variation in social behavior generated by the natural genetic diversity found in isolates collected from the wild. Our studies therefore demonstrate a novel and elegantly simple underlying mechanistic basis for natural variation in complex social strategies in D. discoideum. More generally, they suggest that simple rules governing interactions between individuals can be sufficient to generate a diverse array of outcomes that appear complex and unpredictable when those rules are unknown.