Recover unknown vector through shifted argmax queries

Question

$\DeclareMathOperator*{\argmax}{arg\,max}$ I am interested in finding an efficient algorithm for the following problem:

Let $x \in [0,1]^n$ be some vector, with $x_n = 1$. We want to recover $x$, solely by asking queries of the form $$\texttt{argmax}(x+v) := \argmax_{1 \le i \le n}{x_i + v_i}$$ where $v \in \mathbb{R}^n$ is an arbitrary additive shift. In case of multiple occurrences of the maximum value, the smallest $i$ is returned.

A simple algorithm is to do binary search over each component of $x$ one-by-one. This requires $O(n \log 1/\epsilon)$ queries to recover $x$ up to precision $\epsilon$.

Is it possible to do better? My intuition is that it might be, as every query $i \gets \texttt{argmax}(x + v)$ gives us $\log_2 n$ bits of information. So in principle we could hope for an algorithm that uses $O(\frac{n \log 1/\epsilon}{\log_2 n})$ queries.

Answer 1

The following argument suggests that the factor $O(n)$ cannot be improved. Suppose for a contradiction that $x\in\{0,1\}^n$ and after queries with $v_1,\dots,v_{n-1}\in\mathbb R^n$ we determined that $x=(1,\dots,1)$.

Pick an index $j\in\{1,\dots,n\}$ which was an answer for no queries and let $x'\in\{0,1\}^n$ be the same as $x$ with the only difference that the $j$th component of $x'$ is $0$. Then for $x'$ we obtain the same query answers as for $x$, so we cannot hope to distinguish $x$ from $x'$, a contradiction.