Social optimum in social groups with give‐and‐take criterion. (3rd December 2015)

• Record Type: Journal Article
• Authors: Aggarwal, Saurabh; Kuri, Joy; Vaze, Rahul
• Is Part Of: International journal of communication systems. Volume 29:Number 7(2016)
• Page Start: 1219
• Page End: 1234
• Publication Date: 2015-12-03
• Subjects: device‐to‐device communication -- peer‐to‐peer networking -- social groups -- free riding; Telecommunication systems -- Periodicals; 621.382
• DOI: 10.1002/dac.3089
• Languages: English
• ISSNs: 1074-5351

Abstract

Summary: 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. Abstract : We consider a 'Social Group' of networked nodes that has access to an expensive resource for downloading data or using low‐cost inter‐node links. Nodes follow the Give‐and‐Take Criterion for inter‐node exchanges with the help of a facilitator. We propose various algorithms and compare their performances with the optimal.