Mutual policing is an important mechanism that maintains social harmony in group-living organisms by suppressing the selfish behavior of individuals. In social insects, workers police one another (worker-policing) by preventing individual workers from laying eggs that would otherwise develop into males. Within the framework of Hamilton's rule there are two explanations for worker-policing behavior. First, if worker reproduction is cost-free, worker-policing should occur only where workers are more closely related to queen- than to worker-produced male eggs (relatedness hypothesis). Second, if there are substantial costs to unchecked worker reproduction, worker-policing may occur to counteract these costs and increase colony efficiency (efficiency hypothesis). The first explanation predicts that patterns of the parentage of males (male parentage) are associated with relatedness, whereas the latter does not. We have investigated how male parentage varies with colony kin structure and colony size in 50 species of ants, bees, and wasps in a phylogenetically controlled comparative analysis. Our survey revealed that queens produced the majority of males in most of the species and that workers produced more than half of the males in less than 10% of species. Moreover, we show that male parentage does not vary with relatedness as predicted by the relatedness hypothesis. This indicates that intra- and interspecific variation in male parentage cannot be accounted for by the relatedness hypothesis alone and that increased colony efficiency is an important factor responsible for the evolution of worker-policing. Our study reveals greater harmony and more complex regulation of reproduction in social insect colonies than that expected from simple theoretical expectations based on relatedness only.