WG211/M7Name

Theory of mind and bounded rationality without interpretive overhead

Oleg Kiselyov and Chung-chieh Shan

Computers and humans that work well together have beliefs about each other's intentions, about each other's desires about each other's beliefs, and so on. To practise such a _theory of mind_, agents need to slip easily into each other's shoes. Ideally, when Agent A reasons about Agent B with complete certainty, Agent A should simulate Agent B's mind as efficiently as if that simulation were reality. Modeling agents as programs, we want Agent A to interpret Agent B's program _without interpretive overhead_, that is, as efficiently as if that program ran directly. A programming language with _delimited control operators_ lets us eliminate interpretive overhead in a computational model of bounded-rational agents that reason about each other probabilistically. The key is to reify stochastic programs as probability distributions using the increasingly popular _finally tagless_ technique for embedding programming languages. We demonstrate the idea with a simplistic model of plausibly deniable bribing.