Hm, that gives me an idea: study lying as a computational complexity problem. Just as we can study how much computing power it takes to distinguish random data from encrypted data, we can study how much computing power it takes to formulate (self-serving) hypotheses that take too much effort to distinguish from the truth.
Just a thought...
(Scott Aaronson's paper opened my eyes on the subject.)
I don't know much about the problem in question, but there's a related open problem in number theory.
Suppose I am thinking of a positive integer from 1 to n. You know this and know n. You want to figure out my number but are only allowed to ask if my number is in some range you name. In this game it is easy to see that you can always find out my number in less than 1+log2 n questions.
But what if I'm allowed to lie k times for some fixed k (that you know). Then the problem becomes much more difficult. A general bound in terms of k and n is open.
This suggests to me that working out problems involving lying, even in toy models, can quickly become complicated and difficult to examine.
Here's the new thread for posting quotes, with the usual rules: