Liar Liar, Pants on Fire

K. Gajjar, S. Bhandari
Anand Deo
Friday, 24 Mar 2017, 17:15 to 18:15
A-201 (STCS Seminar Room)
The Liars Game is a turn-based two-player game (lets call the two players Alice and Bob). The game is specified by two positive integers $k$ and $n$ which are known to both Alice and Bob.

The game begins with Alice choosing two positive integers $x$ and $N$ such that $x$ lies between $1$ and $N$ (inclusive).  Alice keeps $x$ secret, and truthfully tells $N$ to Bob. Now Bob tries to obtain information about $x$ by asking Alice questions. Each question consists of Bob specifying a set $S$ of positive integers of his choice, and asking Alice whether $x$ belongs to the set $S$. Bob may ask an unbounded (but finite) number of such questions to Alice. Alice must answer each question with a yes or a no, but she is permitted to lie. The only restriction is that, among any $k+1$ consecutive questions asked by Bob, Alice must answer at least one of them truthfully.

After Bob has finished his interrogation, he must specify a set $X$ of at most n positive integers. If $x$ belongs to $X$, then Bob wins. If he is unable to do this, Alice wins. In this talk, we will see the following results.

* For all $k$, if $n$ is at least $2^k$, then there is a strategy that guarantees a win for Bob.
* For all sufficiently large $k$, there exists an $k$ such that if $n$ is at least $1.99^k$, then there is a strategy for Alice that can prevent Bob from guaranteeing a win.

In the first half of the talk, Kshitij will explain the problem statement with the help of an example and provide a proof of $1$ using elementary counting techniques. In the second part of the talk, Siddharth will provide two different proofs of $2$, one using Lováss local lemma and the other using a potential function. Time permitting, we will also see a generalization of the Liars Game.