Affordable Access

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

Authors
  • Aggarwal, Saurabh
  • Kuri, Joy
  • Vaze, Rahul
Type
Preprint
Publication Date
Aug 08, 2013
Submission Date
Aug 08, 2013
Identifiers
arXiv ID: 1308.1911
Source
arXiv
License
Yellow
External links

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

Report this publication

Statistics

Seen <100 times