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.

Reference :http://ac.els-cdn.com/S0304397503005814/1-s2.0-S0304397503005814-main.pdf?_tid=a880fa14-f82d-11e6-81df-00000aacb35e&acdnat=1487678746_7307f01621c154d9f6e006fc8b992ad0

  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 21 '17 at 15:03
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Feb 21 '17 at 15:05
  • $\begingroup$ @ 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. $\endgroup$ – user35837 Feb 21 '17 at 15:22
  • $\begingroup$ You can do better by varying the size of the intervals. In particular, intervals corresponding to smaller numbers should be shorter. $\endgroup$ – Yuval Filmus Feb 21 '17 at 15:26
  • 1
    $\begingroup$ For your first question, try using a standard sphere packing bound from coding theory. $\endgroup$ – Yuval Filmus Feb 21 '17 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$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy