  This paper compares two leading approaches for robust optimization in the
models of online algorithms and mechanism design. Competitive analysis compares
the performance of an online algorithm to an offline benchmark in worst-case
over inputs, and prior-independent mechanism design compares the expected
performance of a mechanism on an unknown distribution (of inputs, i.e., agent
values) to the optimal mechanism for the distribution in worst case over
distributions. For competitive analysis, a critical concern is the choice of
benchmark. This paper gives a method for selecting a good benchmark. We show
that optimal algorithm/mechanism for the optimal benchmark are equal to the
prior-independent optimal algorithm/mechanism.
  We solve a central open question in prior-independent mechanism design,
namely we identify the prior-independent revenue-optimal mechanism for selling
a single item to two agents with i.i.d. and regularly distributed values. Via
this solution and the above equivalence of prior-independent mechanism design
and competitive analysis (a.k.a. prior-free mechanism design) we show that the
standard method for lower bounds of prior-free mechanisms is not generally
tight for the benchmark design program.
