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 © 2015 John Wiley & Sons, Ltd.