TY - GEN

T1 - An approach to bounded rationality

AU - Ben-Sasson, Eli

AU - Kalai, Adam Tauman

AU - Kalai, Ehud

PY - 2007/12/1

Y1 - 2007/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=57549083411&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57549083411&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:57549083411

SN - 9780262195683

T3 - Advances in Neural Information Processing Systems

SP - 145

EP - 152

BT - Advances in Neural Information Processing Systems 19 - Proceedings of the 2006 Conference

T2 - 20th Annual Conference on Neural Information Processing Systems, NIPS 2006

Y2 - 4 December 2006 through 7 December 2006

ER -