Paul is trying to ascertain an unknown x, out of n possibilities, from an adversary Carole by asking a series of q queries. in the standard "Twenty Questions" Paul wins if and only if n ≤ 2~q. In Liar Games, Carole is allowed, under certain restrictions, to give an incorrect response. Throughout this study Carole will be restricted to give at most k incorrect responses, or lies. Asymptotic analysis here will be for k arbitrary but fixed, k = 1 being a natural and interesting case. The game with ten queries, one hundred possibilities, and (at most) one lie is amusing to play.
展开▼
