Market Sharing Games Applied to Content Distribution in Ad Hoc Networks

In third generation (3G) wireless data networks, repeated requests for popular data items can exacerbate the already scarce wireless spectrum. In this paper we propose an architectural and protocol framework that allows 3G service providers to host efficient content distribution services. We off-load the spectrum intensive task of content distribution to an ad hoc network. Less mobile users (resident subscribers) are provided an incentive to cache popular data items while mobile users (transit subscribers) access this data from resident subscribers through the ad hoc network. Since the participants of this data distribution network act as selfish agents, they may collude to maximize their individual pay off. Our proposed protocol discourages potential collusion scenarios. In this architecture the goal (social function) of the 3G service provider is to have the selfishly motivated resident subscribers service as many data requests as possible. However, the choice of which set of items to cache is left to the individual user. The caching game among the different users can be modeled as a market sharing game. This game is a special case of non-atomic congestion games that have been studied in the economics literature. In particular, pure strategy Nash equilibria for this set of games exists. In this work, we study the performance of the outcome of selfish behavior of computationally bounded agents in terms of the social objective function and the speed of convergence to an approximate social function. We show that in the general case where the popularity of the items is arbitrary the {it price of anarchy} can be upper bounded by a factor of 2. When the popularity follows a Zipf distribution the price of anarchy is bounded by 1.45. We also consider computationally bounded agents by modeling them using approximation algorithms. We prove that the selfish behavior of computationally bounded agents converges to an approximate Nash equilibrium in finite number of rounds. Furthermore, we show that even in a single round of improvements by computationally bounded agents, an $O(log n)$ approximate solution can be obtained. Our simulation scenarios show that the price of anarchy is 30% better than that of the worst case analysis and that the system quickly (1 or 2 rounds) converges to a Nash equilibrium.