Market sharing games applied to content distribution in ad-hoc networks

ABSTRACT

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 offload the spectrum intensive task of content distribution to an ad-hoc network. Less mobile users (resident subscribers) are provided incentives 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 payoff. 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 activity among the different users can be modeled as a market sharing game. In this work, we study the Nash equilibria of market sharing games and the performance of such equilibria in terms of a social function. These games are a special case of congestion games that have been studied in the economics literature. In particular, pure strategy Nash equilibria for this set of games exist. We give a polynomial-time algorithm to find a pure strategy Nash equilibrium for a special case while it is is NP-Hard to do so in the general case. As for the performance of Nash equilibria, we show that the price of anarchy -- the worst-case ratio between the social function at any Nash equilibrium and at the social optimum -- 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 in the special case where caching any item has a positive reward for all players. We prove that the selfish behavior of computationally bounded agents converges to an approximate Nash equilibrium in a finite number of improvements. Furthermore, we show that even with one improvement by each player, 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 steps) converges to a Nash equilibrium.

REFERENCES

• 1: 3G Today. http://www.3gtoday.com/.
• 2: Luzi Anderegg , Stephan Eidenbenz, Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939011]
• 3: L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and Zipf-like distributions: Evidence and implications. In Proceedings of IEEE INFOCOM, pages 126--134, 1999.
• 4: Sonja Buchegger , Jean-Yves Le Boudec, Performance analysis of the CONFIDANT protocol, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513828]
• 5: Chandra Chekuri , Sanjeev Khanna, A PTAS for the multiple knapsack problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.213-222, January 09-11, 2000, San Francisco, California, United States
• 6: Stephan Eidenbenz , V. S. Anil Kumar , Sibylle Zust, Equilibria in topology control games for ad hoc networks, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.2-11, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941081]
• 7: M. Jakobsson, J.-P. Hubaux, and L. Buttyan. A micro-payment scheme encouraging collaboration in multi-hop cellular networks. In Proceedings of Financial Cryptography, pages 15--33, 2003.
• 8: Haitao Lin , Mainak Chatterjee , Sajal K. Das , Kalyan Basu, ARC: an integrated admission and rate control framework for CDMA data networks based on non-cooperative games, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939019]
• 9: Haiyun Luo , Ramachandran Ramjee , Prasun Sinha , Li (Erran) Li , Songwu Lu, UCAN: a unified cellular and ad-hoc network architecture, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939021]
• 10: I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economics Behavior, 13:111--124, 1996.
• 11: D. Monderer and L. S. Shapley. Potential games. Games and Economics Behavior, 14:124--143, 1996.
• 12: J. F. Nash. Equilibrium points in N-person games. In Proceedings of National Academy of Sciences (NAS), pages 48--49, 1950.
• 13: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 14: Pavan Nuggehalli , Vikram Srinivasan , Carla-Fabiana Chiasserini, Energy-efficient caching strategies in ad hoc wireless networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778419]
• 15: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 16: R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 17: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 18: Françoise Sailhan , Valérie Issarny, Cooperative Caching in Ad Hoc Networks, Proceedings of the 4th International Conference on Mobile Data Management, p.13-28, January 21-24, 2003
• 19: Naouel Ben Salem , Levente Buttyán , Jean-Pierre Hubaux , Markus Jakobsson, A charging and rewarding scheme for packet forwarding in multi-hop cellular networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778418]
• 20: V. Vazirani. Approximation Algorithms. Springer-Verlag New York, Incorporated, Jun 1999.
• 21: Adrian Vetta, Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.416, November 16-19, 2002
• 22: Jia Wang, A survey of web caching schemes for the Internet, ACM SIGCOMM Computer Communication Review, v.29 n.5, October 1999 [doi>10.1145/505696.505701]
• 23: Z. Xiang, Z. Zhong, and Y. Zhong. A cache cooperation management for wireless multimedia streaming. In Proceedings of the IEEE International Conferences on Info-tech and Info-net ICII, pages 328--333, 2001.
• 24: S. Zhong, J. Chen, and Y. R. Yang. Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks. In Proceedings of IEEE INFOCOM, pages 1987--1997, 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Economics, Theory

Keywords:
3g wireless networks, ad-hoc networks, nash equilibrium, price of anarchy, unified architecture