source/src/sections/_IV_applications.tex

\section{Applications of Generalized Convexity}

\subsection{Optimal Transport}

An optimal transport problem concerns relating a distribution of mass $\mu \in \Delta(X)$ on one space to a distribution of mass $\eta \in \Delta(Y)$ on another space in a "sensible, cost-minimizing" way. The phrase "sensible, cost-minimizing" is intentionally broad and may be interpreted in several ways, as discussed below.

Minimizing a cost is equivalent to maximizing its negation. Hence, we work with the surplus function $\Phi(x, y) = -c(x, y)$ and frame the problem as a maximization to keep the analogy with convexity clearer.

The original problem, defined by Monge, is to find the optimal transportation map $\gamma: X \to Y$ that preserves measures:
\begin{align*}
\sup_{\gamma: X \to Y} & ; \mathbb{E}_{\mu}[\Phi(x, \gamma(x))] \\
\text{s.t.} \qquad & \gamma_\# \mu = \eta
\end{align*}

where $\gamma_\# \mu$ denotes the pushforward of $\mu$ under $\gamma$.

This turned out to be a difficult problem as even the existence of measure-preserving maps is a subtle issue. For example, if $X = \{x_1, x_2\}$ and $Y = \{y_1\}$ with uniform measures, there is no measure-preserving map.

Significant progress was made by considering a relaxation first formulated by Kantorovich: finding a transportation plan $\pi \in \Pi(\mu, \eta)$, where a coupling $\Pi(\mu, \eta)$ is the set of all joint distributions on $X \times Y$ with marginals $\mu$ and $\eta$.

The Kantorovich problem is:
\begin{align*}
\sup_{\pi \in \Pi(\mu, \eta)} & ; \mathbb{E}_\pi[\Phi(x, y)]
\end{align*}

The space of transportation plans(couplings) is weak-* compact under mild regularity conditions, which ensures the existence of an optimal plan.

Because the Kantorovich problem is a linear program, it admits a dual. The dual solutions are intimately related to generalized convexity:

\begin{align*}
&\inf_{\phi: X \to \R, \psi: Y \to \R} & \mathbb{E}_\mu[\phi(x)] + \mathbb{E}_\eta[\psi(y)] \\
&\text{s.t.}&\\
&\forall (x, y) \in X \times Y& \phi(x) + \psi(y) \geq \Phi(x, y)
\end{align*}

We refer to $\phi$ and $\psi$ as Kantorovich potentials. A basic fact from optimal transport theory is that it is without loss to assume $\phi$ is $Y$-convex and $\psi = \phi^X$. To see this, let $(\hat{\phi}, \hat{\psi})$ be optimal:

\begin{align*}
\hat{\psi}(y) &\geq \Phi(x, y) - \hat{\phi}(x) \\
\implies \hat{\psi}(y) &\geq \sup_{x \in X} { \Phi(x, y) - \hat{\phi}(x) } = \hat{\phi}^X(y)
\end{align*}

So $\hat{\phi}^X \leq \hat{\psi}$, and by the Fenchel--Young inequality,

\begin{align*}
\Phi(x, y) \leq \hat{\phi}(x) + \hat{\phi}^X(y)
\end{align*}

Thus, $\hat{\phi}^X$ is feasible and at least as good as $\hat{\psi}$, so we can replace $\hat{\psi}$ by $\hat{\phi}^X$. Similarly, we can replace $\hat{\phi}$ by $\hat{\phi}^{YX}$.  The new $\phi = \hat{\phi}^{YX}$ is $Y$-convex and $\hat{\psi} = \hat{\phi}^{X} = \hat{\phi}^{XYX} = \phi^{X}$.

Hence, the Kantorovich dual problem can be rewritten as:
\begin{align*}
\inf_{\phi \in \mathcal{C}^Y(X)} \; \mathbb{E}_\mu[\phi(x)] + \mathbb{E}_\eta[\phi^X(y)]
\end{align*}

Another key result from the literature is that

% TODO show what conditions needed to be met
\begin{align*}
\pi(x, y) > 0 \implies \nabla \phi(x) = \nabla_x \Phi(x, y)
\end{align*}

When $\nabla_x \Phi(x, \cdot)$ is a diffeomorphism, we can invert it to get the transportation map $\gamma: X \to Y$:

\begin{align*}
\gamma(x) = (\nabla_x \Phi(x, \cdot))^{-1} (\nabla \phi(x))
\end{align*}

This diffeomorphism property, also called the twist condition, may be viewed as a relaxation of the single-crossing property (Spence--Mirrlees condition) used in mechanism design \cite{mirrlees1971exploration, spence1978job}.

Another classic result is Brenier's theorem \cite{brenier1991polar}, which states that for

\begin{align*}
    c(x, y) = \norm{x - y}_2^2
\end{align*}

the optimal transport map is gradient of a convex function.

In summary, generalized convex functions and their gradients characterize the solutions to the Kantorovich and Monge problems, respectively.

\subsection{Mathematical Economics}

The following is a general setting for mechanism design problems: there are outcomes $X$, each priced according to a pricing scheme $t: X \to \R$. An agent has a type $y \in Y$ unknown to the seller affecting how much they value each outcome. Their utility $u(x,y)$ is the value $\Phi(x,y)$ they get from the outcome, given their type, minus their payment $t(x)$:

\begin{align*}
u(x, y) = \Phi(x, y) - t(x)
\end{align*}

The buyer chooses the outcome that maximizes their utility given their type. Let's assume $X$ to be compact so that there exists a utility maximizing outcome. The indirect utility $v: Y \to \R$ is the maximum utility an agent of type $y$ can secure:

\begin{align*}
v(y) = \max_{x \in X} { \Phi(a(x), y) - t(x) }
\end{align*}

Hence, the indirect utility is an $X$-convex function.

The seller wants to maximize their profit (or any other objective) by choosing the optimal price function $t$. The challenge is that the buyer will respond to changes in prices and change their behavior. Hence we are dealing with a bilevel optimization problem. As bilevel optimization problems are generally hard, we use the revelation principle to simplify the problem.

By the revelation principle, regardless of our objective, it is without loss of generality to restrict attention to direct revelation incentive compatible(DRIC) mechanisms: mechanisms where agents are asked for their type and have no incentive to misreport. Any mechanism has a DRIC equivalent, that is one that generates the same indirect utility for the buyer and the same profit for the seller. Intuitively, for any mechanism, there exists a DRIC mechanism mimicking it by asking the players for their types and simulating their optimal strategy.

So we focus on finding a DRIC. Since now both the price and outcome only depend on the reported type, a DRIC is characterized by a pair of functions $(a, t)$, where $a: Y \to X$ is the allocation function deciding what outcome to assign to each type and $t: Y \to \R$ is the payment function deciding how much to charge each type. So the indirect utility is:

\begin{align*}
    v(y) = \max_{\hat{y} \in Y} \Phi(a(\hat{y}), y) - t(\hat{y})
\end{align*}

% TODO make these sups max by compactness
Since the mechanism is IC, we can apply the envelope theorem:
\begin{align*}
\nabla v(y) = \nabla_y \Phi(a(y), y)
\end{align*}

When $\nabla_y \Phi(\cdot, y)$ is invertible, we have $a(y) = (\nabla_y \Phi(\cdot, y))^{-1} (\nabla v(y))$, so the outcome is determined by the gradient of the indirect utility $v$. Again, this is a relaxation of the single crossing property. Using this, we can write the payment in terms of the indirect utility:

\begin{align*}
t(y) =& \Phi(a(y), y) - v(y) \\
=& \Phi(a(y), y) - v(y_0) + v(y_0) - v(y) \\
=& \Phi(a(y), y) - v(y_0) \\
&- \int_0^1  (y - y_0)^T \nabla v(y_0 + \lambda(y - y_0))  \, d\lambda
\end{align*}

Thus, any DSIC mechanism is characterized by the choice of an indirect utility function, which needs to be an $X$-convex function as pointed out earlier. The only caveat is that the indirect utility function should be non-negative; otherwise, agents will not participate(individual rationality). Therefore, for any objective, the optimization problem faced by the market maker reduces to finding a non-negative $X$-convex function that maximizes some functional, i.e the revenue.

For example, when maximizing revenue, the problem can be formulated as:
\begin{align*}
\max_{v \in \mathcal{C}^X(Y), v \geq 0} \Phi((\nabla_y \Phi(\cdot, y))^{-1} (\nabla v(y)), y) - v(y_0) \\
+ \int_0^1 \nabla v(y_0 + t(y - y_0)) (y - y_0) \, dt
\end{align*}

See \cite{ekeland2010notes} for a more detailed discussion.