If $\Omega \subset \mathcal{X}\times\mathcal{X}$ is arbitrary, e.g. with just one element $(x_1, x_2)$ and $P = \delta_{x_1}$. Then the probability $P(C_\Omega(P, \hat{P}_n) > t)$ is just always 1. What are you hoping for in the first case?

Tim Carson's counterexample seems to work well. $\rho(x | x \in R_\theta E)$ is basically the point mass at 0, so the rotation $R_\theta$ is not a valid transport. Note that $\rho(x | x \in R_\theta E)$ is very different from the pushforward $\rho(x | x \in E) \circ R_{\theta}^{-1}$.

That's just convention, but I thought a different symbol for marginals and joint distribution might be easier to read.

Well, for negative $a$, the curve $a \mapsto I^a(X;Y)$ is increasing, so the highest value is at $a=0$, which shows the reverse of inequality (2).

Not sure about a condition for $I^a(X;Y) \geq 0$. Could you make your counterexample more concrete? I might have gotten the terms confused with $I^{-a}$, I basically calculated with $I^a$ but also allowed $a \leq 0$. Of course, there might also be an error in my calculations.

To make sure it is not a typo: For $I^a(X;Y)$ you are only adjusting $\bar{p}(x_i)$ but still use the initial $p(y_j)$?

@NikWeaver That was simpler than expected, thanks!

What is $c$? Also, why doesn't the second point imply the first? Or do you want some uniform boundedness?

Some questions: What is the ground metric on $\mathbb{R}^d$ for the Wasserstein distance? If $F(Y)$ is the square of the Wasserstein 2 distance, how do your thoughts show Lipschitz continuity (your inequality is without the square)?

I'm not saying it is efficient, but what one can always do is to optimize directly over $\pi \in \Pi(P, Q)$ satisfying $\langle D,\pi \rangle \leq c$. Since $\pi \mapsto P$ is linear, you obtain an objective function which is as nice as previously, and with a linear inequality constraint. Standard solvers will be able to solve it given $n$ is small enough. Further, there is of course a bunch of literature for when $f$ is linear, i.e. $f(P) = \int g \,dP$ in the Wasserstein "distributionally robust optimization" literature.

Two quick comments: First, I posted a wrong answer earlier where I simply messed up a detail, sorry! Second should "$\varphi(x) + \psi(y) \leq c(x, y)$ for almost all ..." be instead pointwise (since no measure on the product space is given)?

Could you explain your definition of $S$ being strictly proper? What is the space of functions that $S$ is a minimiser among (and perhaps what is the precise optimization problem)?