Experiences applying game theory to system design

ABSTRACT

We applied techniques from game theory to help formulate and analyze solutions to two systems problems: discouraging selfishness in multi-hop wireless networks and enabling cooperation among ISPs in the Internet. It proved difficult to do so. This paper reports on our experiences and explains the issues that we encountered. It describes the ways in which the straightforward use of results from traditional game theory did not fit well with the requirements of our problems. It also identifies an important characteristic of the solutions we did eventually adopt that distinguishes them from those available using game theoretic approaches. We hope that this discussion will help to highlight formulations of game theory which are well-suited for problems involving computer systems.

REFERENCES

• 1: A. Adya, P. Bahl, J. Padhye, A. Wolman, and L. Zhou. A multi-radio unification protocol for IEEE 802.11 wireless networks. Technical Report MSR-TR-2003-41, Microsoft Research, June 2003.
• 2: D. Aguayo, J. Bicket, S. Biswas, D. S. J. D. Couto, and R. Morris. MIT roofnet implementation. http://www.pdos.lcs.mit.edu/roofnet/design/, Aug. 2003.
• 3: Aditya Akella , Srinivasan Seshan , Richard Karp , Scott Shenker , Christos Papadimitriou, Selfish behavior and stability of the internet:: a game-theoretic analysis of TCP, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 4: S. J. Brams. Negotiation Games: Applying game theory to bargaining and arbitration. Routeledge, 1990.
• 5: 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]
• 6: Levente Buttyán , Jean-Pierre Hubaux, Stimulating cooperation in self-organizing mobile ad hoc networks, Mobile Networks and Applications, v.8 n.5, p.579-592, October 2003 [doi>10.1023/A:1025146013151]
• 7: David D. Clark , John Wroclawski , Karen R. Sollins , Robert Braden, Tussle in cyberspace: defining tomorrow's internet, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 8: J. Crowcroft, R. Gibbens, F. Kelly, and S. Ostring. Modelling incentives for collaboration in mobile ad hoc networks. In WiOpt, Mar. 2003.
• 9: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571856]
• 10: K. Lai, M. Feldman, I. Stoica, and J. Chuang. Incentives for cooperation in peer-to-peer networks. In Workshop on Economics of Peer-to-Peer Systems, June 2003.
• 11: R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan. Encouraging cooperation in multi-hop wireless networks. Technical Report CSE-04-06-01, University of Washington, June 2004.
• 12: R. Mahajan, D. Wetherall, and T. Anderson. Interdomain routing with negotiation. Technical Report CSE-04-06-02, University of Washington, June 2004.
• 13: Sergio Marti , T. J. Giuli , Kevin Lai , Mary Baker, Mitigating routing misbehavior in mobile ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.255-265, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345955]
• 14: R. B. Myerson and M. A. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 29(2), Apr. 1983. Cited in Brams {4}.
• 15: M. J. Osborne and A. Rubenstein. A course in game theory. MIT Press, 1994.
• 16: B. Raghavan and A. C. Snoeren. Priority forwarding in ad hoc networks with self-interested parties. In Workshop on Economics of Peer-to-Peer Systems, June 2003.
• 17: H. Raiffa. The art and science of negotiation. Harvard University Press, 1982.
• 18: 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]
• 19: S. Saroiu, K. Gummadi, and S. D. Gribble. A measurement study of peer-to-peer file sharing systems. In Multimedia Computing and Networking, Jan. 2002.
• 20: Scott J. Shenker, Making greed work in networks: a game-theoretic analysis of switch service disciplines, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.819-831, Dec. 1995 [doi>10.1109/90.477727]
• 21: V. Srinivasan, P. Nuggehalli, C. F. Chiasserini, and R. R. Rao. Cooperation in wireless ad hoc networks. In IEEE INFOCOM, Mar. 2003.
• 22: A. Urpi, M. Bonuccelli, and S. Giordano. Modelling cooperation in mobile ad hoc networks: A formal description of selfishness. In WiOpt'03 Workshop: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Mar. 2003.
• 23: S. Zhong, Y. Yang, and J. Chen. Sprite: A simple, cheat-proof, credit-based system for mobile ad hoc networks. In IEEE INFOCOM, Mar. 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.m Miscellaneous

General Terms:
Design, Economics

Keywords:
game theory, incentives, interdomain routing, system design, wireless networks