Google Research

Equitable and Optimal Transport with Multiple Agents

  • Meyer Scetbon
  • Laurent Meunier
  • Jamal Atif
  • Marco Cuturi
AISTATS 2021 (to appear)


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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work