Stochastic Optimization and Coupling

Stochastic Optimization and Coupling: Structure, Equivalence, and Applications

Introduction and Motivation

The paper "Stochastic Optimization and Coupling" (2603.11448) develops a unified structural theory for a broad class of stochastic optimization problems in which a linear objective functional is maximized over the set of probability measures dominated by a given reference measure, with dominance defined via an integral stochastic order. Such orders, parameterized by a cone $C$ of test functions, generalize objects including Blackwell dominance, first- and higher-order stochastic dominance, and mean-preserving spreads. The analysis synthesizes methods from convex analysis, probability, and mathematical economics, yielding new equivalences and tractable solution characterizations for optimization under these stochastic constraints.

Main Equivalence Theorem

The central technical contribution is a fourfold equivalence for integral stochastic orders parameterized by a cone $C$ of functions. The equivalence asserts:

1. Min-Closure: The cone $C$ is closed under pointwise minima, i.e., $\min\{g_1,g_2\}\in C$ for all $g_1,g_2\in C$.
2. Affine Value Functionals: For any upper semicontinuous $f$, the maximal expected value $V_f^*(\mu)$ over all measures $\nu \preceq_C \mu$ is affine in the reference measure $\mu$.
3. Order-Preserving Couplings: For all $\nu \preceq_C \mu$, there is a Markov kernel $P$ with $\nu = P*\mu$ and $P*\delta_x \preceq_C \delta_x$ for all $x$ (a Strassen-type coupling).
4. Solution Correspondence Structure: The solution correspondence $X_f^*(\mu)$ has a convex graph with decomposable extreme points (the so-called trapezoid graph property).

This structural theorem generalizes and strengthens Strassen's classical result by proving the necessity as well as sufficiency of min-closure for order-preserving coupling and tractable value characterizations.

Characterization and Solution for Stochastic Optimization

The equivalence directly yields a tractable solution method: whenever $C$ is min-closed, the value function for the stochastic optimization problem

$\sup_{\nu \preceq_C \mu} \int f \, d\nu$

is given by the expectation of the $C$-envelope $\overline{f}$ of $f$, i.e.,

$V_f^*(\mu) = \int \overline{f}\, d\mu,$

where $$\overline{f}(x) = \inf\{g(x): g \in C,\, g \geq f\}$$. The $C$-envelope is always in $C$ if $C$ is min-closed. Furthermore, order-preserving couplings reduce the maximization to a pointwise problem, enabling explicit construction of optimal solutions in high-dimensional domains.

The properties of the solution correspondence imply that the extreme points of the feasible set (the "stochastic orbit") are characterized by unique, pointwise extremal couplings; this provides sharp information about the structure of optimal or extremal measures and their supports.

Consequences for Multidimensional Stochastic Orders

Mean-Preserving Spread (MPS) Orbits

The paper applies its framework to multidimensional mean-preserving spread (MPS) orbits, defined via the cone of concave functions. Since this cone is min-closed, all properties of the equivalence theorem apply, including affine value functions and explicit envelope solutions.

For exposed points in MPS orbits (i.e., measures $\nu$ that are not convex combinations of other feasible measures), the paper gives a constructive geometric characterization based on the simplicial decomposition of the domain and unique barycentric splitting. For generic compact convex domains, the exposed points correspond to measures induced by deterministic or simplex-supported couplings aligned to the geometry of concavification.

Figure 2: $f$ and its concave envelope $\overline{f}$, illustrating the construction of an exposed point in a multidimensional MPS orbit.

Stochastic Dominance

First-order (FOSD) and higher-order dominance orders, defined via cones of monotone or monotone-concave functions, also satisfy min-closure. The explicit pointwise decomposition for exposed points and the connection to monotone envelopes enables a unifying treatment across dominance relations and elucidates their geometric structure.

Figure 1: $f$ and its monotone envelope $\overline{f}$, visualizing the supports relevant for FOSD-based stochastic optimization and coupling.

Figure 3: Concave envelope $\widehat{f}$ representing the solution to the value function under MPS or similar min-closed orderings.

By contrast, for mean-preserving contraction (MPC) orbits, the cone of convex functions is not min-closed, so neither the affine nor coupling properties hold; this demonstrates the sharpness of the main theorem and explains the qualitative differences between MPS and MPC orbits, especially in the structure and computation of extremal measures.

Application: Duality for Comparison of Experiments

A key economic implication is the full generalization of Blackwell's theorem on comparison of experiments. The paper identifies all integral stochastic orders over distributions on posterior beliefs that admit two equivalent representations:

• Instrumental value-based: Order induced by value for all functions in a cone $C$.
• Information-theoretic: Order induced by existence of a coupling (or garbling) via a composition-closed set of transition kernels.

The main result establishes that consistency with both representations requires $C$ to be max-closed and the set of kernels to be composition-closed; the correspondence is via a fixed-point property called "Blackwell invariance."

Thus, only dominance relations (of which Blackwell order is the weakest under Bayes plausibility) with these closure properties support consistent duality. The theory delineates the outer limits of information comparison in Bayesian persuasion, dynamic information design, and mechanism design.

Broader Applications and Implications

The equivalence and envelope characterizations have direct implications for constrained information design (e.g., privacy-preserving persuasion and dynamic sampling), mechanism design with ambiguity aversion, and nested optimization problems (Stackelberg games). Among the salient findings:

• When information design constraints (e.g., induced by privacy or information technology) are composition-closed, all results on tractability and envelopes pass through.
• In problems with nested stochastic orders (e.g., Stackelberg hierarchies), the solution always reduces to extremal choices at both the leader and follower levels, with tractable envelopes at each stage.
• In mechanism design and ambiguity aversion, the structure of the test function cone determines whether ambiguity-averse and expected utility representations are behaviorally distinguishable.

These findings unify and generalize a large literature in economic theory and mathematical optimization, and establish sharp boundaries for the kinds of stochastic dominance and ordering structures that permit tractable envelope-based optimization, explicit couplings, and dual representations.

Conclusion

This paper delivers a structural understanding of stochastic optimization with dominance constraints via integral stochastic orders. The main equivalence theorem links min-closure, affineness of the value function, order-preserving couplings, and explicit solution structure, sharply expanding the scope and tractability of stochastic optimization and duality theory. The characterization of Blackwell-consistent orders, the envelope framework, and the pointwise decomposition of extremal measures have broad implications for information, mechanism, and decision theory. The results not only embed and extend classical theorems (e.g., Strassen, Blackwell) but also deliver new, practically applicable insights across economics, optimization, and probability.