Equitable and Optimal Transport with Multiple Agents

We introduce a minmax problem extending optimal transport (OT) when multiple costs are considered. We consider a linear optimization problem which allows to choose locally among $N\geq 1$ rescaled cost functions in order to minimize the cost of transport, yet achieve global robustness by maximizing against those scalings subject to simplicial constraint. When $N=1$, we recover the classical OT problem; for $N=2$ we are able to recover integral probability metrics defined by $\alpha$-Hölder functions, which includes the Dudley metric. We derive the dual formulation of the problem and show that strong duality holds under some mild assumptions. In the discrete case, as with regular OT, the problem can be solved with a linear program. We provide a faster, entropic regularized formulation of that problem. We validate our proposed approximation with experiments on real and synthetic datasets.

• Machine Intelligence

• Algorithms and Theory