  We study the problem of designing mechanisms when agents' valuation functions
are drawn from unknown and correlated prior distributions. In particular, we
are given a prior distribution $\D$, and we are interested in designing a
(truthful) mechanism that has good performance for all ``true distributions''
that are close to $\D$ in Total Variation (TV) distance. We show that DSIC and
BIC mechanisms in this setting are strongly robust with respect to TV distance,
for any bounded objective function $\Ocal$, extending a recent result of
Brustle et al. (\cite{Brustle2020}, EC 2020). At the heart of our result is a
fundamental duality property of total variation distance. As direct
applications of our result, we (i) demonstrate how to find approximately
revenue-optimal and approximately BIC mechanisms for weakly dependent prior
distributions; (ii) show how to find correlation-robust mechanisms when only
``noisy'' versions of marginals are accessible, extending recent results of Bei
et. al. (\cite{bei2019correlation}, SODA 2019); (iii) prove that
prophet-inequality type guarantees are preserved for correlated priors,
recovering a variant of a result of D{\"u}tting and Kesselheim
(\cite{Dutting19}, EC 2019); (iv) give a new necessary condition for a
correlated distribution to witness an infinite separation in revenue between
simple and optimal mechanisms, complementing recent results of Psomas et al.
(\cite{psomas2022infinite}, NeurIPS 2022); (v) give a new condition for simple
mechanisms to approximate revenue-optimal mechanisms for the case of a single
agent whose type is drawn from a correlated distribution that can be captured
by a Markov Random Field, complementing recent results of Cai and Oikonomou
(\cite{Cai21}, EC 2021).

Computer Science and Game Theory;Data Structures and Algorithms