On complexity as bounded rationality (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On complexity as bounded rationality (extended abstract)

Full text

Pdf (872 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 726 - 733

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Christos H. Papadimitriou	Department of Computer Science and Engineering, University of California at San Diego
Mihalis Yannakakis	AT&T Bell Laboratories, Murray Hill, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 76, Citation Count: 27

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/195058.195445 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AH	R. J. humann, S. Hart (editors) Handbook of Game Theory with Economic Applications, vol. I, North-Holland, 1992.
	Ax	R. Axelrod The Evolution of Cooperation, Basic Books, 1984.
	BP	E. Ben-Porath "The complexity of computing a best response automaton in repeated games with mixed strategies," Games and Economzc Behavior 2, pp. 1-12, 1990.
	DP	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]
	FW	L. Fortnow, D. Whang "Optimality and domination in repeated games with bounded players," manuscript, 1993.
	GKZ	Itzhak Gilboa , Ehud Kalai , Eitan Zemel, The complexity of eliminating dominated strategies, Mathematics of Operations Research, v.18 n.3, p.553-565, Aug. 1993 [doi>10.1287/moor.18.3.553]
	GZ	I. Gilboa, E. Zemel "Nash and correlated equilibria some complexity considerations," Games and Economic Behavior 1, pp. 80-93, 1{989.
	KM	D. Koller, N. Megiddo "The complexity of twoperson zero-sum games in extensive form," 1990.
	MW	N Megiddo , A Wigderson, On play by means of computing machines, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.259-274, March 1986, Monterey, California, United States
	Ne	A. Neyman "Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma," Economics Letters 19, pp. 227-229, 1985.
	Pa	C. H. Papadimitriou "On players with a bounded number of states," Games and Economic Behavior, 1992.
	Ru	A. Rubinstein "Finite automata play the repeated prisoner's dilemma," J. Econ. Theory, 1986.
	Sa	S. Sahni "Computationally related problems," SIAM J. Computing 3, pp. 262-279, 1974.
	Si	Herbert A. Simon, The sciences of the artificial (3rd ed.), MIT Press, Cambridge, MA, 1996
	So	S. Sorin "Repeated games with complete information," Chapter 4 in {AH}, 1992.

CITED BY 27

	Christos H. Papadimitriou, Database metatheory: asking the big queries, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, May 22-25, 1995, San Jose, California, United States
	Xiaotie Deng , Toshihide Ibaraki , Hiroshi Nagamochi, Combinatorial optimization games, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.720-729, January 05-07, 1997, New Orleans, Louisiana, United States
	Kate Larson , Tuomas Sandholm, Bargaining with limited computation: deliberation equilibrium, Artificial Intelligence, v.132 n.2, p.183-217, November 2001
	Artur Czumaj , Piotr Krysta , Berthold Vöcking, Selfish traffic allocation for server farms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
	Christopher D. Rosin , Richard K. Belew, A competitive approach to game learning, Proceedings of the ninth annual conference on Computational learning theory, p.292-302, June 28-July 01, 1996, Desenzano del Garda, Italy
	Georg Gottlob , Gianluigi Greco , Francesco Scarcello, Pure Nash equilibria: hard and easy games, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana
	N. M. Gotts , J. G. Polhill , A. N. R. Law, Agent-Based Simulation in the Study of Social Dilemmas, Artificial Intelligence Review, v.19 n.1, p.3-92, March 2003
	Olivier Gossner , Penélope Hernández, On the complexity of coordination, Mathematics of Operations Research, v.28 n.1, p.127-140, February 2003
	Lance Fortnow , Peter Kimmel, Beating a finite automaton in the big match, Proceedings of the 7th conference on Theoretical aspects of rationality and knowledge, July 22-24, 1998, Evanston, Illinois
	Scott Aaronson, The complexity of agreement, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Song Shen , Gregory M. P. O'Hare, Wireless sensor networks, an energy-aware and utility-based BDI agent approach, International Journal of Sensor Networks, v.2 n.3/4, p.235-245, April 2007
	Carlos Rodríguez Lucatero , Rafael Lozano Espinosa, Application of automata learning algorithms to robot motion tracking, Proceedings of the 4th WSEAS International Conference on Signal Processing, Robotics and Automation, p.1-6, February 13-15, 2005, Salzburg, Austria
	Matt Lepinski , David Liben-Nowell , Seth Gilbert , April Rasala Lehman, Playing games in many possible worlds, Proceedings of the 7th ACM conference on Electronic commerce, p.150-159, June 11-15, 2006, Ann Arbor, Michigan, USA
	Rob Powers , Yoav Shoham , Thuc Vu, A general criterion and an algorithmic framework for learning in multi-agent systems, Machine Learning, v.67 n.1-2, p.45-76, May 2007
	Thuc Vu , Rob Powers , Yoav Shoham, Learning against multiple opponents, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	Christos H. Papadimitriou , Oded Goldreich , Avi Wigderson , Alexander A. Razborov , Michael Sipser, The future of computational complexity theory: part I, ACM SIGACT News, v.27 n.3, p.6-12, Sept. 1996
	Christos H. Papadimitriou, Database metatheory: asking the big queries, ACM SIGACT News, v.26 n.3, p.13-30, Sept. 1995
	Christian Borgs , Jennifer Chayes , Nicole Immorlica , Adam Tauman Kalai , Vahab Mirrokni , Christos Papadimitriou, The myth of the folk theorem, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Alex Fabrikant , Christos H. Papadimitriou, The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.844-853, January 20-22, 2008, San Francisco, California
	Joseph Y. Halpern, Beyond nash equilibrium: solution concepts for the 21st century, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, p.1-10, August 18-21, 2008, Toronto, Canada
	Haris Aziz , Mike Paterson, False name manipulations in weighted voting games: splitting, merging and annexation, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary
	Stuart J. Russell , Devika Subramanian, Provably bounded-optimal agents, Journal of Artificial Intelligence Research, v.2 n.1, p.575-609, August 1994
	Yoav Shoham, Game theory pragmatics: a challenge for AI, Proceedings of the 23rd national conference on Artificial intelligence, p.1606-1608, July 13-17, 2008, Chicago, Illinois
	Stuart Russell, Rationality and intelligence, Proceedings of the 14th international joint conference on Artificial intelligence, p.950-957, August 20-25, 1995, Montreal, Quebec, Canada
	Rob Powers , Yoav Shoham, Learning against opponents with bounded memory, Proceedings of the 19th international joint conference on Artificial intelligence, p.817-822, July 30-August 05, 2005, Edinburgh, Scotland