  It is known that the Azema-Yor solution to the Skorokhod embedding problem
maximizes the law of the running maximum of an uniformly integrable martingale
with given terminal value distribution. Recently this optimality property has
been generalized to expectations of certain bivariate cost functions depending
on the terminal value and the running maximum.
  In this paper we give an extension of this result to another class of
functions. In particular, we study a class of cost functions with the property
that the corresponding optimal embeddings are not Azema-Yor. The suggested
approach is quite straightforward modulo basic facts of the Monge-Kantorovich
mass transportation theory. Loosely speaking, the joint distribution of the
running maximum and the terminal value in the Azema-Yor embedding is
concentrated on the graph of a monotone function, and we show that this fact
follows from the cyclical monotonicity criterion for solutions to the
Monge-Kantorovich problem.
  Keywords: Skorokhod problem, Azema-Yor embedding, Monge-Kantorovich problem,
optimal transport, supermodular functions, running maximum and the terminal
value of a martingale.
