An Approach to Bounded Rationality

Eli Ben-Sasson, Adam Tauman Kalai, Ehud Kalai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

A central question in game theory and artificial intelligence is how a rational agent should behave in a complex environment, given that it cannot perform unbounded computations. We study strategic aspects of this question by formulating a simple model of a game with additional costs (computational or otherwise) for each strategy. First we connect this to zero-sum games, proving a counter-intuitive generalization of the classic min-max theorem to zero-sum games with the addition of strategy costs. We then show that potential games with strategy costs remain potential games. Both zero-sum and potential games with strategy costs maintain a very appealing property: simple learning dynamics converge to equilibrium.

Original languageEnglish (US)
Title of host publicationNIPS 2006
Subtitle of host publicationProceedings of the 19th International Conference on Neural Information Processing Systems
EditorsBernhard Scholkopf, John C. Platt, Thomas Hofmann
PublisherMIT Press Journals
Pages145-152
Number of pages8
ISBN (Electronic)0262195682, 9780262195683
StatePublished - 2006
Event19th International Conference on Neural Information Processing Systems, NIPS 2006 - Vancouver, Canada
Duration: Dec 4 2006Dec 7 2006

Publication series

NameNIPS 2006: Proceedings of the 19th International Conference on Neural Information Processing Systems

Conference

Conference19th International Conference on Neural Information Processing Systems, NIPS 2006
Country/TerritoryCanada
CityVancouver
Period12/4/0612/7/06

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Fingerprint

Dive into the research topics of 'An Approach to Bounded Rationality'. Together they form a unique fingerprint.

Cite this