Tragedy of the Commons in Online Social Search

Online social search (OSS) brings forth a new way to harness the Internet for answers. In this paper, we study the non-cooperation problem in OSS. We propose an analytical model that captures the behavior of OSS nodes, and, from a gaming-strategy point of view, analyze various strategies an individual node can utilize to allocate its awareness capacity. Based on this we derive the Pareto inefficiency in terms of the system cost. We also propose an incentive scheme under which the optimal state of individual nodes is also optimal for the whole system. Extensive simulations show that the strategy under our proposed incentive mechanism outperforms other strategies in terms of the system cost and the search success rate. To the best of our knowledge, this is the first study of the tragedy-of-the-commons problem in OSS.