Many male animals donate nutritive materials during courtship or mating to their female mates. Donation of large-sized gifts, though costly to prepare, can result in increased sperm transfer during mating and delayed remating of the females, resulting in a higher paternity. Nuptial gifting sometimes causes severe female-female competition for obtaining gifts (i.e., sex-role reversal in mate competition) and female polyandry, changing the intensity of sperm competition and the resultant paternity gains. We built a theoretical model to analyze such coevolutionary feedbacks between nuptial gift size (male trait) and propensity for multiple mating (female trait). Our genetically explicit, individual-based computer simulations demonstrate that a positive correlation between donated gift size and the resultant paternity gain is a requisite for the co-occurrence of large-sized gifts and females’ competitive multiple mating for the gifts. When gift donation imposes monandry, exaggeration of nuptial gift size also occurs under the assumption that the last male monopolizes paternity, although it reduces mating opportunities, also occurs under the assumption that the last male monopolizes paternity. We also analyzed the causes and consequences of the evolution of a female persistence trait in trading of nuptial gifts, that is, double receptacles for nuptial gifts known to occur in an insect group with a “female penis” (Neotrogla spp.).