Incentive Compatible Influence Maximization in Social Networks with Application to Viral Marketing

Information diffusion and influence maximization are important and extensively studied problems in social networks. Various models and algorithms have been proposed in the literature in the context of the influence maximization problem. A crucial assumption in all these studies is that the influence probabilities are known to the social planner. This assumption is unrealistic since the influence probabilities are usually private information of the individual agents and strategic agents may not reveal them truthfully. Moreover, the influence probabilities could vary significantly with the type of the information flowing in the network and the time at which the information is propagating in the network. In this paper, we use a mechanism design approach to elicit influence probabilities truthfully from the agents. Our main contribution is to design a scoring rule based mechanism in the context of the influencer-influencee model. In particular, we show the incentive compatibility of the mechanisms and propose a reverse weighted scoring rule based mechanism as an appropriate mechanism to use.

Social optimum in social groups with give-and-take criterion

We consider a Social Group' of networked nodes, seeking a universe' of segments. Each node has a subset of the universe and access to an expensive resource for downloading data. Nodes can also acquire the universe by exchanging copies of segments among themselves, at low cost, using inter-node links. While exchanges over inter-node links ensure minimum cost, some nodes in the group try to exploit the system. We term such nodes as non-reciprocating nodes' and prohibit such behavior by proposing the give-and-take' criterion, where exchange is allowed if each node has segments unavailable with the other. Under this criterion, we consider the problem of maximizing the number of nodes with the universe at the end of local exchanges. First, we present a randomized algorithm that is shown to be optimal in the asymptotic regime. Then, we present greedy links algorithm, which performs well for most of the scenarios and yields an optimal result when the number of nodes is four. The polygon algorithm is proposed, which yields an optimal result when each of the nodes has a unique segment. After presenting some intuitive algorithms (e.g., greedy incremental algorithm and rarest first algorithm), we compare the performances of all proposed algorithms with the optimal. Copyright (c) 2015 John Wiley & Sons, Ltd.

Males, but not females, mate with multiple partners: a laboratory study of a primitively eusocial wasp Ropalidia marginata

The intense interest in social Hymenoptera, on account of their elaborate sociality and the paradox of altruism, has often suffered from considerable gender imbalance. This is partly due to the fact that worker behaviour and altruism are restricted to the females and partly because males often live off the nest. Yet, understanding the males, especially in the context of mating biology is essential even for understanding the evolution of sociality. Mating patterns have a direct bearing on the levels of intra-colony genetic relatedness, which in turn, along with the associated costs and benefits of worker behaviour, are central to our understanding of the evolution of sociality. Although mating takes place away from the nest in natural colonies of the primitively eusocial wasp Ropalidia marginata, mating can be observed in the laboratory if a male and a female are placed in a transparent, aerated plastic container, and both wasps are in the range of 5-20 days of age. Here, we use this setup and show that males, but not females, mate serially with multiple partners. The multiple mating behaviour of the males is not surprising because in nature males have to mate with a number of females, only a few of whom will go on to lay eggs. The reluctance of R. marginata females to mate with multiple partners is consistent with the expectation of monogamy in primitively eusocial species with totipotent females, although the apparent discrepancy with a previous work with allozyme markers in natural colonies suggesting that females may sometimes mate with two or three different males remains to be resolved.