  The prior independent framework for algorithm design considers how well an
algorithm that does not know the distribution of its inputs approximates the
expected performance of the optimal algorithm for this distribution. This paper
gives a method that is agnostic to problem setting for proving lower bounds on
the prior independent approximation factor of any algorithm. The method
constructs a correlated distribution over inputs that can be generated both as
a distribution over i.i.d. good-for-algorithms distributions and as a
distribution over i.i.d. bad-for-algorithms distributions. Prior independent
algorithms are upper-bounded by the optimal algorithm for the latter
distribution even when the true distribution is the former. Thus, the ratio of
the expected performances of the Bayesian optimal algorithms for these two
decompositions is a lower bound on the prior independent approximation ratio.
The techniques of the paper connect prior independent algorithm design, Yao's
Minimax Principle, and information design. We apply this framework to give new
lower bounds on several canonical prior independent mechanism design problems.
