Computer science and game theory

ABSTRACT

The most dramatic interaction between CS and GT may involve game-theory pragmatics.

REFERENCES

• 1: Bratman, M.E. Intention, Plans, and Practical Reason. CSLI Publications, Stanford University, 1987.
• 2: Xi Chen , Xiaotie Deng, Settling the Complexity of Two-Player Nash Equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.261-272, October 21-24, 2006 [doi>10.1109/FOCS.2006.69]
• 3: Philip R. Cohen , Hector J. Levesque, Intention is choice with commitment, Artificial Intelligence, v.42 n.2-3, p.213-261, March 1990 [doi>10.1016/0004-3702(90)90055-5]
• 4: Conitzer, V. and Sandholm, T. Complexity results about Nash equilibria. IJCAI, 2003, 761--771.
• 5: Conitzer, V. and Sandholm, T. Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. AAAI, 2004.
• 6: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 7: Xiaotie Deng , Christos H. Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research, v.19 n.2, p.257-266, May 1994 [doi>10.1287/moor.19.2.257]
• 8: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 9: Niemela, I., Brewka, G., and Truszczynski, M Nonmonotonic reasoning. In Handbook of Knowledge Representation. F. van Harmelen, V. Lifschitz, and B. Porter, (eds.), Elsevier, 2007.
• 10: Gilboa, I. and Zemel, E. Nash and correlated equilibria Some complexity considerations. Games and Economic Behavior, 80--93, 1989.
• 11: Govindan, S. and Wilson, R. A global Newton method to compute Nash equilibria. Journal of Economic Theory, 2003.
• 12: Amy Greenwald , Michael L. Littman, Introduction to the special issue on learning and computational game theory, Machine Learning, v.67 n.1-2, p.3-6, May 2007 [doi>10.1007/s10994-007-0770-1]
• 13: Halpern, J.Y A computer scientist looks at game theory. Games and Economic Behavior 45,1 (2003) 114--132.
• 14: Halpern, J.Y. Computer science and game theory: A brief survey. In The New Palgrave Dictionary of Economics. S.N. Durlauf and L.E. Blume (eds.) Palgrave MacMillan, 2008.
• 15: Samuel Ieong , Yoav Shoham, Marginal contribution nets: a compact representation scheme for coalitional games, Proceedings of the 6th ACM conference on Electronic commerce, p.193-202, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064030]
• 16: Ehud Kalai, Games, computers, and O.R., Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.468-473, January 28-30, 1996, Atlanta, Georgia, United States
• 17: Kalai, E. Presidential address. The Second World Congress of the Game Theory Society, Marseille, 2004. Games and Economic Behavior, P. Reny (ed.), in press.
• 18: Michael J. Kearns , Michael L. Littman , Satinder P. Singh, Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.253-260, August 02-05, 2001
• 19: Koller, D. and Milch, B. Multiagent influence diagrams for representing and solving games. IJCAI, 2001.
• 20: LaMura, P. Game networks. UAI, 2000.
• 21: Leyton-Brown, K. and Tennenholtz, M. Local-effect games. IJCAI, 2003.
• 22: Linial, N. Game theoretic aspects of computing. In Handbook of Game Theory, R.J. Aumann and S. Hart (eds.), 1339--1395, Elsevier Science, 1994.
• 23: Marvin Minsky, The Emotion Machine: Commonsense Thinking, Artificial Intelligence, and the Future of the Human Mind, Simon & Schuster, 2006
• 24: Neyman, A. Bounded complexity justifies cooperation in finitely repeated prisoner's dilemma. Economic Letters, 1985, 227--229.
• 25: Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
• 26: 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]
• 27: Christos H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences, v.48 n.3, p.498-532, June 1994 [doi>10.1016/S0022-0000(05)80063-7]
• 28: Papadimitriou, C.H. and Yannakakis, M. On bounded rationality and computational complexity. In Proceedings of the Symposium on the Theory of Computing, 1994, 726--733.
• 29: Christos H. Papadimitriou, Algorithms, Games, and the Internet, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.1-3, July 08-12, 2001
• 30: Pappas, P. Belief revision. In Handbook of Knowledge Representation. F. van Harmelen, V. Lifschitz, and B. Porter (eds.). Elsevier, 2007
• 31: Porter, R., Nudelman, E., and Shoham, Y Simple search methods for finding a Nash equilibrium. In Proceedings of the National Conference on Artificial Intelligence, 2004, 664--669.
• 32: Roughgarden, T. Computing equilibria: A computational complexity perspective. Economic Theory, 2008.
• 33: Rubinstein, A. Modeling Bounded Rationality. MIT Press, Cambridge, MA, 1998.
• 34: Savage, L.J. The Foundations of Statistics. John Wiley and Sons, NY, 1954. (Second Edition: Dover Press, 1972).
• 35: Shoham, Y and Leyton-Brown, K. Multiagent Systems: Algorithmic, Game Theoretic, and Logical Foundations. Cambridge University Press, 2008.
• 36: Tennenholtz, M. Program equilibrium. Games and Economic Behavior 49, 2004, 363--373.
• 37: Johan van Benthem, Exploring logical dynamics, Center for the Study of Language and Information, Stanford, CA, 1997
• 38: van Benthem, J. When are two games the same? In LOFT-III, 1998 (ILLC preprint, 1999).
• 39: Rakesh V. Vohra , Michael P. Wellman, Foundations of multi-agent learning: Introduction to the special issue, Artificial Intelligence, v.171 n.7, p.363-364, May, 2007 [doi>10.1016/j.artint.2007.05.002]
• 40: von Neumann, J. and Morgenstern, 0. Theory of Games and Economic Behavior, Second Edition. Princeton University Press, 1947.
• 41: von Stengel, B. Computing equilibria for two-person games. In Handbook of Game Theory, vol. Ill chap. 45. R. Aumann and S. Hart (eds.). Elsevier Amsterdam, 2002, 1723--1759.
• 42: Michael P. Wellman , Amy Greenwald , Peter Stone, Autonomous Bidding Agents: Strategies and Lessons from the Trading Agent Competition (Intelligent Robotics and Autonomous Agents), The MIT Press, 2007
• 43: Zinkevich, M., Bowling, M., and Burch. N. A new algorithm for generating equilibria in massive zero-sum games. In Proceedings of the 22nd Conference on AI, 2007, 788--793.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.9 Management

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search