Response to Reviewer's Comments (Continued)
**(Refined) Complete Proof of Proposition 5.2**:
Consider an instance with $N$ iid distributions on binary support $\{N-\alpha_1, N + \alpha_2\}$ for $ \alpha_1 \in (0, 1), \alpha_2 > 0$ such that the probabilities are chosen to make the mean of each distribution precisely $N$ -- i.e., the probability of taking the smaller value is $\frac{\alpha_2}{\alpha_1 + \alpha_2}$. For the purpose of this proof, one should think of $N, \alpha_2$ as being very large. The prophet value $\text{OPT}$ can be calculated as following:
$$\text{OPT} = (N + \alpha_2) \cdot [1 - (\frac{\alpha_2}{\alpha_2+\alpha_1})^N] + (N - \alpha_1) \cdot (\frac{ \alpha_2}{\alpha_2 + \alpha_1})^N.$$
We first claim that, for *any* $\alpha_1 \in(0, 1)$, no threshold $T \in (N - \alpha_1, N + \alpha_2]$ can guarantee at least $1/2$ competitive ratio for non-strategic settings. Intuitively, this is because any such threshold will give up any realization of $N- \alpha_1$ value, which leads to bad performance when the probability of having at least one realization of $ N + \alpha_2$ is small (i.e., when $\alpha_2$ is very large). Detailed calculation is as below: any threshold $T \in (N - \alpha_1 , N + \alpha_2] $ only accepts the realized $N + \alpha_2$ value, hence the expected payoff for non-strategic (ns) setting is (i.e., the first term of $\text{OPT}$) $$u^{ns}(T) = (N + \alpha_2) \cdot [ 1 - (\frac{\alpha_2 }{\alpha_2 + \alpha_1 })^N].$$
Therefore,
\begin{eqnarray*}
\frac{u^{ns}(T)}{\text{OPT}} &=& \frac{ (N + \alpha_2) \cdot [ 1 - (\frac{\alpha_2 }{\alpha_2 + \alpha_1 })^N] }{ (N + \alpha_2) \cdot [ 1 - (\frac{\alpha_2 }{\alpha_2 + \alpha_1 })^N] + (N - \alpha_1) \cdot (\frac{ \alpha_2}{\alpha_2 + \alpha_1})^N } \\
&=& \frac{ 1 }{ 1 + \frac{N - \alpha_1}{N + \alpha_2} \cdot \frac{(\frac{ \alpha_2}{\alpha_2 + \alpha_1})^N}{ 1 - (\frac{\alpha_2 }{\alpha_2 + \alpha_1 })^N } }
\end{eqnarray*}
We now analyze the limit of the key term $ \frac{N - \alpha_1}{N + \alpha_2} \cdot \frac{( \frac{ \alpha_2}{\alpha_2 + \alpha_1})^N}{ 1 - (\frac{\alpha_2 }{\alpha_2 + \alpha_1 })^N } $. To ease the analysis, we re-parameterize the above term with $\alpha_2 = \frac{\alpha_1 N }{ \alpha}$ with free parameter $\alpha$ to obtain
\begin{eqnarray*}
\frac{N - \alpha_1}{N + \alpha_2} \cdot \frac{( \frac{ \alpha_2}{\alpha_2 + \alpha_1})^N}{ 1 - (\frac{\alpha_2 }{\alpha_2 + \alpha_1 })^N } = \frac{N - \alpha_1}{N} \frac{1}{1 + \alpha_1/\alpha} \cdot \frac{( \frac{ N }{N + \alpha})^N}{ 1 - (\frac{ N }{N + \alpha })^N } = A(N, \alpha; \alpha_1)
\end{eqnarray*}
Since $\alpha_1 \in (0, 1)$ is fixed. Now fix $\alpha$ and let $N \to \infty$, we have $\lim_{N \to \infty} A(N, \alpha; \alpha_1) = \frac{1}{1 + \alpha_1/\alpha} \cdot \frac{e^{-\alpha} }{ 1 - e^{-\alpha} }$. Now, letting $\alpha \to 0$ and applying standard l'hopital's rule, we have $\lim_{ \alpha \to 0 } \frac{1}{1 + \alpha_1/\alpha} \cdot \frac{e^{-\alpha} }{ 1 - e^{-\alpha} } = \lim_{ \alpha \to 0 } \frac{\alpha e^{-\alpha} }{(\alpha + \alpha_1)(1 - e^{-\alpha} ) } = 1/\alpha_1$. As a consequence, we have $\lim_{N \to \infty, \alpha_2 \to \infty} \frac{u^{ns}(T)}{\text{OPT}} = \frac{\alpha_1}{\alpha_1 + 1}$. Thus, for any $\alpha_1 \in (0, 1)$, there exists an IID instance with large enough $N$ and $ \alpha_2 $ such that no threshold $T \in (N-\alpha_1, N + \alpha_2]$ can achieve CR at least $1/2$.
The above analysis shows that the only threshold $T$ that can guarantee a CR at least $1/2$ in the above class of instances must satisfy $T \le N-\alpha_1$.
Any such threshold will achieve searcher's utility $u^s(T) = N$ in the strategic setting since all players will reveal no reward information, leading to expected reward value $N$ for each player.
A similar limit analysis using the same reparameterization $\alpha_2 = \frac{\alpha_1 N }{ \alpha}$ shows that $ \lim_{\alpha \to 0 }\lim_{N \to \infty} \frac{u^{s}(T)}{\text{OPT}} = \frac{1}{1+\alpha_1}$.
The arguments above shows that for any $\alpha_1 < 1$, as $N, \alpha_2 \to \infty$ in the above instances, any threshold that has CR at least $1/2$ in non-strategic setting will have CR tending to $ \frac{1}{1+\alpha_1}$ in the strategic setting. Since this conclusion holds for any $\alpha_1 \in (0, 1)$, it rules out the possibility of having an $(1/2+\alpha)$-robust threshold (even outside the $1/2$-approximation threshold spectrum as in Definition 2.2) for any $\alpha > 0$.