In this paper we investigate model-independent bounds for exotic options written on a risky asset. Based on arguments from the theory of Monge-Kantorovich mass-transport we establish a dual version of the problem that has a natural financial interpretation in terms of semi-static hedging. In particular we prove that there is no duality gap.