  This paper considers prior-independent mechanism design, in which a single
mechanism is designed to achieve approximately optimal performance on every
prior distribution from a given class. Most results in this literature focus on
mechanisms with truthtelling equilibria, a.k.a., truthful mechanisms. Feng and
Hartline (2018) introduce the revelation gap to quantify the loss of the
restriction to truthful mechanisms. We solve a main open question left in Feng
and Hartline (2018); namely, we identify a non-trivial revelation gap for
revenue maximization.
  Our analysis focuses on the canonical problem of selling a single item to a
single agent with only access to a single sample from the agent's valuation
distribution. We identify the sample-bid mechanism (a simple non-truthful
mechanism) and upper-bound its prior-independent approximation ratio by 1.835
(resp. 1.296) for regular (resp. MHR) distributions. We further prove that no
truthful mechanism can achieve prior-independent approximation ratio better
than 1.957 (resp. 1.543) for regular (resp. MHR) distributions. Thus, a
non-trivial revelation gap is shown as the sample-bid mechanism outperforms the
optimal prior-independent truthful mechanism. On the hardness side, we prove
that no (possibly non-truthful) mechanism can achieve prior-independent
approximation ratio better than 1.073 even for uniform distributions.
