The optimal transportation problem, which originated in the work of Gaspard Monge in 1781, provides a fundamental and quantitave way to measure the distance between probability distributions. It has led to many successful applications in PDEs, Geometry, Statistics and Probability Theory. Recently, and motivated by problems in Financial Mathematics, variations on this problem were introduced by requiring the transport plans to abide by certain "fairness rules," such as following martingale paths. One then specifies a stochastic state process and a costing procedure, and minimize the expected cost over stopping times with a given state distribution. Recent work has uncovered deep connections between this type of constrained optimal transportation problems, the celebrated Skorokhod embeddings of probability distributions in Brownian motion, and Hamilton-Jacobi variational inequalities. This talk is based on joint work with Young-Heon Kim and Aaron Palmer.