  We introduce and study a notion of strong duality for two classes of
optimization problems commonly occurring in probability theory. That is, on an
abstract measurable space $(\Omega,\mathcal{F})$, we say that an equivalence
relation $E$ on $\Omega$ satisfies ``strong duality'' if $E$ is
$(\mathcal{F}\otimes\mathcal{F})$-measurable and if there exists a
sub-$\sigma$-algebra $\mathcal{G}$ of $\mathcal{F}$ such that for all
probability measures $\mathbb{P},\mathbb{P}'$ on $(\Omega,\mathcal{F})$ we have
\[ \sup_{A\in\mathcal{G}}\vert \mathbb{P}(A)-\mathbb{P}'(A)\vert =
\min_{\tilde{\mathbb{P}}\in\Gamma(\mathbb{P},\mathbb{P}')}(1-\tilde{\mathbb{P}}(E)),
\] where $\Gamma(\mathbb{P},\mathbb{P}')$ denotes the space of couplings of
$\mathbb{P}$ and $\mathbb{P}'$, and where ``min'' asserts that the infimum is
in fact achieved. The results herein, which can be seen as a surprising
extension of Kantorovich duality to a class of irregular costs, give wide
sufficient conditions for strong duality to hold. These conditions allow us to
recover many classical results and to prove novel results in stochastic
calculus, random sequence simulation, and point process theory.
