AAAI Publications, Twelfth International Conference on the Principles of Knowledge Representation and Reasoning

Font Size: 
I Don't Want to Think About it Now: Decision Theory with Costly Computation
Joseph Y. Halpern

Last modified: 2010-04-27


Computation plays a major role in decision
making.  Even if an agent is willing to ascribe a probability to all states and a utility to all outcomes, and maximize expected utility, doing so might present serious computational problems.  Moreover, computing the
outcome of a given act might be difficult.  In a companion paper we develop a framework for game theory  with costly computation, where the objects of choice are Turing machines.  Here we apply that framework to
decision theory.  We show how well-known phenomena like
first-impression-matters biases (i.e., people tend to put more weight on evidence they hear early on), belief polarization (two people with different prior beliefs, hearing the same evidence, can end up with diametrically opposed conclusions), and the status quo bias (people are much more likely to stick with what they already have) can be easily captured in that framework.  Finally, we use the framework  to define so me new notions: value of computational information (a computational variant of value of information) and computational value of conversation.


decision making; computational complexity

Full Text: PDF