Social optimum in Social Groups with Give-and-Take criterion

Saurabh Aggarwal, Joy Kuri, Rahul Vaze

Abstract

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. Alternatively, nodes can also acquire the universe by exchanging segments among themselves at low cost using a local network interface. While local exchanges ensure minimum cost, "free riders" in the group can exploit the system. To prohibit free riding, we propose 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 aggregate cardinality of the nodes' segment sets. First, we present a randomized algorithm, whose analysis yields a lower bound on the expected aggregate cardinality, as well as an approximation ratio of 1/4 under some conditions. Four other algorithms are presented and analyzed. We identify conditions under which some of these algorithms are optimal.

Introduction

In modern mobile environments, groups of nodes (e.g., smartphones in a local area) often seek to acquire a complete set of data segments, referred to as the "universe." While these segments can be downloaded from expensive external sources like cellular base stations, local peer-to-peer (P2P) or device-to-device (D2D) exchanges via Bluetooth or Wi-Fi offer a significantly lower-cost alternative.

However, the success of such cooperative systems is often hindered by "free riders"—nodes that consume data from others without contributing any in return. This paper addresses this challenge by introducing the Give-and-Take (GT) criterion, a strict fairness rule designed to prevent exploitation while maximizing the aggregate cardinality (the total number of segments held across all nodes in the group).

The Give-and-Take (GT) Criterion

The GT criterion mandates that an exchange between two nodes is only permitted if it is mutually beneficial. Specifically, node $i$ can download from node $j$ if and only if $i$ provides at least one segment to $j$ that $j$ does not already possess. This ensures that every transaction involves a reciprocal transfer of information, inherently prohibiting free riding.

Evolution of nodes' segment sets under a specific schedule, illustrating the GT criterion in action.

The core problem explored is finding a schedule of these exchanges that maximizes the total number of segments held by the group. Since finding the absolute social optimum is NP-hard, the authors propose and evaluate several polynomial-time heuristics.

Proposed Algorithms

The paper presents five distinct algorithms for scheduling GT exchanges:

  1. Randomized Algorithm: Pairs nodes randomly; if they satisfy the GT criterion, they perform a "Full Exchange" of all missing segments.
  2. Greedy-Links (GL): At each step, it selects the pair that leaves the maximum number of potential future exchange links available in the network.
  3. Polygon Algorithm: A structured, shifted round-robin approach designed for scenarios where every node starts with at least one unique segment.
  4. Greedy-Incremental (GI): A "short-sighted" approach that picks the pair providing the largest immediate increase in aggregate cardinality.
  5. Rarest First (RF): Prioritizes exchanges involving segments held by the fewest nodes to increase their overall availability.
Visualization of link activation stages in a structured scheduling approach like the Polygon Algorithm.

Key Insights and Results

Extensive simulations demonstrate that Greedy-Links (GL) and Rarest First (RF) are the top performers, achieving the absolute social optimum in over 95% of test cases. A significant finding is that "looking ahead" (as GL does by preserving future links) is far more effective than seeking immediate gains (as GI does).

Furthermore, the authors prove that the Randomized Algorithm becomes asymptotically optimal as the number of nodes increases. In large groups, simple random pairing is sufficient to ensure that nearly every node eventually acquires the full universe of data. Under specific initial conditions, the randomized approach is also proven to provide at least a 1/4 approximation of the social optimum.

Conclusion

By transforming fairness from an incentive into a hard constraint, the Give-and-Take criterion effectively eliminates free riding in social data-sharing networks. The proposed algorithms, particularly Greedy-Links and the Randomized approach for large scales, provide efficient ways to maximize data availability within local groups, reducing reliance on expensive external resources.

Summary updated

Abstract

We consider a "Social Group" of networked nodes, seeking a "universe" of segments. Each node has subset of the universe, and access to an expensive resource for downloading data. Alternatively, nodes can also acquire the universe by exchanging segments among themselves, at low cost, using a local network interface. While local exchanges ensure minimum cost, "free riders" in the group can exploit the system. To prohibit free riding, we propose 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 aggregate cardinality of the nodes' segment sets. First, we present a randomized algorithm, whose analysis yields a lower bound on the expected aggregate cardinality, as well as an approximation ratio of 1/4 under some conditions. Four other algorithms are presented and analyzed. We identify conditions under which some of these algorithms are optimal
BibTeX
@article{aggarwal2016social,
  author = {Saurabh Aggarwal and Joy Kuri and Rahul Vaze},
  title = {{Social optimum in Social Groups with Give-and-Take criterion}},
  journal = {Int. J. Commun. Syst.},
  year = {2016},
  url = {https://openreview.net/forum?id=dMj0MxINLf},
}
Figure