# lower bound for Renyi–Ulam Game with lies

Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ).

Game :

1. $A$ chooses an element in {1,2....,n}

2. $B$ tries to guess this number by asking Yes/No questions.

Binary search is a way to solve the problem, so with $\log n$ many queries will be sufficient to solve the problem when player $A$ does not lie. But if player $A$ lie exactly one time than we can problem with $2\log n$ many queries (by just asking the same query two times). There is an optimal way to solve this problem with $\log n + \log \log n +c$ , where $c$ is a constant. We will first ask $\log n$ many queries to $B$ and going to get a $\log n$ bits long binary string and now apply binary search on this binary string. In general when A is allowed to lie say $l$ (constant) then also the number of queries need to solved the problem is $\log n + \log\log n + c$

Questions : 1) How to prove that $\log n + \log\log n + c$ is a lower bound ?

2) If only $\log n$ many queries are allowed in the general case Is there an approximation algorithm for this game ( original solution = $a$ * algorithm's solution, where $a$ is constant).

3) If $l$ is very large (say order of $n$) Is it possible in that case to correctly find out the guessed number ? I tried to use the Hamming distance but not able to come up with a precise answer.

• You are asking many questions. The usual rule is one question per post. For your third question, see this paper: cs.bu.edu/~gacs/papers/liars.pdf. Feb 21, 2017 at 15:03
• For your second question, let $\log n = \log m + \log\log m + c$. Can you use this idea to solve your second question, by partitioning $\{1,\ldots,n\}$ into $m$ intervals in a smart way? Feb 21, 2017 at 15:05
• @ Yuval Filmus for second question if the size of the each interval is constant then I can have a constant approximation factor otherwise I am not able to see it.
– user35837
Feb 21, 2017 at 15:22
• You can do better by varying the size of the intervals. In particular, intervals corresponding to smaller numbers should be shorter. Feb 21, 2017 at 15:26
• For your first question, try using a standard sphere packing bound from coding theory. Feb 21, 2017 at 15:33

For the first question, suppose that you have an algorithm that supports one error, and uses $m$ questions. For each element $i \in \{1,\ldots,n\}$, let $x_{i0}$ be the vector containing the answers to all questions when A doesn't lie, and let $x_{ij}$ be the vector containing the answers to all questions when A lies in question $j$. In total, we have $n$ collections of $m+1$ vectors. All these vectors are distinct: the $m+1$ vectors in a collection are distinct by definition, and vectors belonging to different collections must be distinct since the correct answer is different. We deduce that $(m+1)n \leq 2^m$, and so $m \geq \log n + \log\log n + \Omega(1)$.
For the second question, here is something to try. Let $m$ be a number so that $\log n$ queries suffice to find an element in $\{1,\ldots,m\}$, even when A is allowed to lie at most once. Partition $\{1,\ldots,n\}$ into $m$ intervals $[x_1,x_2),[x_2,x_3),\ldots,[x_m,x_{m+1})$, where $[a,b) = \{a,\ldots,b-1\}$, $x_1 = 1$, and $x_{m+1} = n+1$. Then this gives an $\alpha$-approximation for $\alpha = \max \frac{x_{i+1}-1}{x_i}$. I leave the rest to you.
The third question is addressed in Three thresholds for a liar by Spencer and Winkler. The threshold is $n/3$ (a strategy exists if $\ell < n/3$).