Liar Liar, Pants on Fire


K. Gajjar, S. Bhandari


School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Navy Nagar
Mumbai 400005


Friday, 24 March 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.