We solve the martingale optimal transport problem for cost functionals represented by optimal stopping problems. The measure-valued martingale approach developed in ArXiv: 1507.02651 allows us to obtain an equivalent infinite-dimensional controller-stopper problem. We use the stochastic Perron's method and characterize the finite dimensional approximation as a viscosity solution to the corresponding HJB equation. It turns out that this solution is the concave envelope of the cost function with respect to the atoms of the terminal law. We demonstrate the results by finding explicit solutions for a class of cost functions.

Final version. To appear in SIAM Journal on Control and Optimization. Keywords: nonlinear Martingale optimal transport, dynamic programming, optimal stopping, stochastic Perron's method, viscosity solutions, state constraints, exit time problem, concave envelope, distribution constraints