  Classical Bayesian mechanism design relies on the common prior assumption,
but such prior is often not available in practice. We study the design of
prior-independent mechanisms that relax this assumption: the seller is selling
an indivisible item to $n$ buyers such that the buyers' valuations are drawn
from a joint distribution that is unknown to both the buyers and the seller;
buyers do not need to form beliefs about competitors, and the seller assumes
the distribution is adversarially chosen from a specified class. We measure
performance through the worst-case regret, or the difference between the
expected revenue achievable with perfect knowledge of buyers' valuations and
the actual mechanism revenue.
  We study a broad set of classes of valuation distributions that capture a
wide spectrum of possible dependencies: independent and identically distributed
(i.i.d.) distributions, mixtures of i.i.d. distributions, affiliated and
exchangeable distributions, exchangeable distributions, and all joint
distributions. We derive in quasi closed form the minimax values and the
associated optimal mechanism. In particular, we show that the first three
classes admit the same minimax regret value, which is decreasing with the
number of competitors, while the last two have the same minimax regret equal to
that of the single buyer case. Furthermore, we show that the minimax optimal
mechanisms have a simple form across all settings: a second-price auction with
random reserve prices, which shows its robustness in prior-independent
mechanism design. En route to our results, we also develop a principled
methodology to determine the form of the optimal mechanism and worst-case
distribution via first-order conditions that should be of independent interest
in other minimax problems.
