Near rationality and competitive equilibria in networked systems

ABSTRACT

A growing body of literature in networked systems research relies on game theory and mechanism design to model and address the potential lack of cooperation between self-interested users. Most game-theoretic models applied to system research only describe competitive equilibria in terms of pure Nash equilibria, that is, a situation where the strategy of each user is deterministic, and is her best response to the strategies of all the other users. However, the assumptions necessary for a pure Nash equilibrium to hold may be too stringent for practical systems. Using three case studies on network formation, computer security, and TCP congestion control, we outline the limits of game-theoretic models relying on Nash equilibria, and we argue that considering competitive equilibria of a more general form helps in assessing the accuracy of a game theoretic model, and can even help in reconciling predictions from game-theoretic models with empirically observed behavior.

REFERENCES

• 1: E. Adar and B. Huberman. Free riding on Gnutella. First Monday, 5(10), Oct. 2000.
• 2: 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
• 3: G. Akerlof and J. Yellen. Can small deviations from rationality make significant differences to economic equilibria? Amer. Econ. Rev., 75(4):708--720, Sept. 1985.
• 4: Mark Allman, A web server's view of the transport layer, ACM SIGCOMM Computer Communication Review, v.30 n.5, October 2000 [doi>10.1145/505672.505674]
• 5: M. Baye and J. Morgan. Price dispersion in the lab and on the Internet: Theory and evidence. RAND J. Econ., 35(3), Autumn 2004. To appear.
• 6: N. Christin and J. Chuang. On the cost of participating in a peer-to-peer network. In Proc. IPTPS'04, San Diego, CA, Feb. 2004.
• 7: B.-G. Chun, R. Fonseca, I. Stoica, and J. Kubiatowicz. Characterizing selfishly constructed overlay networks. In Proc. IEEE INFOCOM'04, Hong Kong, Mar. 2004.
• 8: Cisco Secure Consulting. Vulnerability statistics report. http://www.cisco.com/warp/public/778/security/vuln_stats_02-03-00.html.
• 9: B. Cohen. Incentives build robustness in BitTorrent. In Proc. 1st Workshop on Econ. of Peer-to-Peer Syst., Berkeley, CA, June 2003.
• 10: D. Dittrich. The DoS project's "trinoo" distributed denial of service attack tool, Oct. 1999. Available from http://staff.washington.edu/dittrich/misc/trinoo.analysis.
• 11: Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
• 12: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 13: Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570812]
• 14: E. Friedman and S. Shenker. Learning and implementation on the Internet. Working paper. Available from http://ideas.repec.org/p/rut/rutres/199821.html, Aug. 1998.
• 15: J. Goeree and C. Holt. Ten little treasures of game theory and ten intuitive contradictions. Amer. Econ. Rev., 91(5):1402--1422, Dec. 2001.
• 16: J. Goeree and C. Holt. A model of noisy introspection. Games Econ. Behav., 46(2):365--382, Feb. 2004.
• 17: P. Haile, A. Hortaçsu, and G. Kosenok. On the empirical content of quantal response equilibrium. Cowles Foundation Discussion Paper Series, (1432), Aug. 2003.
• 18: G. Hardin. The tragedy of the commons. Science, 162(3859):1243--1248, Dec. 1968.
• 19: Hung-Yun Hsieh , Raghupathy Sivakumar, Performance comparison of cellular and multi-hop wireless networks: a quantitative study, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.113-122, June 2001, Cambridge, Massachusetts, United States
• 20: M. Jackson and A. Wolinsky. A strategic model for social and economic networks. J. Econ. Theory, 71(1):44--74, Oct. 1996.
• 21: P. Klemperer. Using and abusing economic theory. J. Europ. Econ. Assoc., 1(2/3):272--300, April-May 2003.
• 22: D. McFadden. Econometric analaysis of qualitative response models. In Z. Grilliches and M. Intriligator, editors, Handbook of Econometrics, volume~II, pages 1396--1456. Elsevier, Amsterdam, Netherlands, 1984.
• 23: R. McKelvey and T. Palfrey. Quantal response equilibria for normal form games. Games Econ. Behav., 10(1):6--38, July 1995.
• 24: David Moore , Vern Paxson , Stefan Savage , Colleen Shannon , Stuart Staniford , Nicholas Weaver, Inside the Slammer Worm, IEEE Security and Privacy, v.1 n.4, p.33-39, July 2003 [doi>10.1109/MSECP.2003.1219056]
• 25: J. Nash. Non-cooperative games. Annals of Mathematics, 54(2):286--295, Sept. 1951.
• 26: 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]
• 27: R. Radner. Collusive behavior in noncooperative epsilon-equilibria of oligopolies with long but finite lives. J. Econ. Theory, 22:136--154, 1980.
• 28: S. Russell and D. Subramanian. Provably bounded-optimal agents. J. Artif. Intel. Res., 2:575--609, May 1995.
• 29: 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]
• 30: J. Shneidman and D. Parkes. Rationality and self-interest in peer-to-peer networks. In Proc. IPTPS'03, pages 139--148, Berkeley, CA, Feb. 2003.

INDEX TERMS

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

General Terms:
Design, Economics, Theory

Keywords:
competitive equilibria, distributed systems, game theory, modeling