C-Convexity and Lipschitz Functions

The following definition of c-convexity is a characterization of the "buying price" $\psi$ and "selling price" $\phi$ of an external company, seen in the dual formulation of the Kantorovich problem

where $c$ is the transport cost. As long as the constraint is satisfied, the offer $\phi, \psi$ made by the external company is "competitive". The goal of the company is to maximize its benefit while maintaining its competitiveness, which implies the following relationships

because this way, the selling price is maximized and buying price minimized while the constraint is satisfied.

Definition (c-convexity): Let $c:X\times Y\rightarrow (-\infty,\infty]$. A function $\psi:X\rightarrow (-\infty, \infty]$ is said to be $c$-convex if $\phi\neq \infty$ and there exists some $\xi:Y\rightarrow[-\infty,\infty]$ s.t. $\psi(x)=\sup_y \xi(y) - c(x,y)$.

This is an abstract generalization of convexity, and can be motivated by the well-celebrated Fenchel Moreau theorem, which basically says for any extended real-valued function $f\neq \pm\infty$, $f$ is proper, lower semi-continuous and convex if and only if $f=f^{**}$, where the asterisk denotes the convex conjugate of $f$. When the cost function $c$ is simply the inner product $c(x,y)=x^\top y$ on $\mathbb{R}^d\times \mathbb{R}^d$, the transform in the definition is exactly the convex conjugate of $\xi$.

An important example is when $c$ is a metric function defined on some metric space $X$. Then $c$-convex functions coincide with the family of $1$-Lipschitz functions (which is why the dual Kantorovich form of the Wasserstein distance is taking the supremum over all $1$-Lipschitz functions). To see this, assume $\psi$ is $c$-convex. Then by definition there exists a function $\psi$ s.t. $\psi(x)=\sup_y \xi(y) - c(x,y)$. Fix $x_1,x_2\in X$, letting $y^*$ denote the maximizer of $\xi(y) - c(x_1,y)$, we have

This shows $c$-convex functions are $1$-Lipschitz. Now assume $\psi$ is $1$-Lipschitz, which implies

for any $x_1$. If $x_1=x_2$, then the RHS equals $\psi(x_2)-c(x_2,x_2) = \psi(x_2)$, which means the supremum of the RHS is equal to $\psi(x_2)$; that is