Handling Multiple Costs in Optimal Transport: Strong Duality and Efficient Computation

Meyer Scetbon, Laurent Meunier, Jamal Atif, Marco Cuturi

Abstract

We introduce an extension of the Optimal Transport problem when multiple costs are involved. Considering each cost as an agent, we aim to share equally between agents the work of transporting one distribution to another. To do so, we minimize the transportation cost of the agent who works the most. Another point of view is when the goal is to partition equitably goods between agents according to their heterogeneous preferences. Here we aim to maximize the utility of the least advantaged agent. This is a fair division problem. Like Optimal Transport, the problem can be cast as a linear optimization problem. When there is only one agent, we recover the Optimal Transport problem. When two agents are considered, we are able to recover Integral Probability Metrics defined by $\alpha$-H"older functions, which include the widely-known Dudley metric. To the best of our knowledge, this is the first time a link is given between the Dudley metric and Optimal Transport. We provide an entropic regularization of that problem which leads to an alternative algorithm faster than the standard linear program.

Introduction

Standard Optimal Transport (OT) is designed to find the most efficient way to move mass from one distribution to another based on a single cost function. However, real-world scenarios often involve multiple stakeholders or varying conditions. For example, in fair division problems, one must split a heterogeneous resource among multiple people with different preferences. In robust logistics, work must be distributed among multiple providers so that no single provider is overburdened.

This paper introduces Equitable and Optimal Transport (EOT), a framework that extends classical OT to handle multiple cost functions or agents simultaneously. By minimizing the maximum cost incurred by any single agent, EOT provides a mathematically rigorous way to achieve "fairness" in resource allocation and work distribution, solvable via a new, efficient Sinkhorn-style algorithm.

Methods

The core of EOT is a minimax primal formulation: it seeks a partition of the total transport plan into $N$ sub-plans (one per agent) that minimizes the maximum individual cost.

Figure 1: Setup of a transport problem with three distinct cost functions: Negative Euclidean, Negative Square Euclidean, and Negative 1.5 L1 cost.

Key technical contributions include:

  1. Strong Duality: The authors prove that a dual version of the problem exists and is equivalent to the primal. This dual involves "potentials" (similar to Kantorovich potentials) and a probability simplex constraint that weights the different cost functions.
  2. Entropic Regularization: To make the problem computationally tractable, the authors add a Kullback-Leibler (KL) divergence penalty. This turns the rigid linear program into a strictly convex optimization problem.
  3. Projected Alternating Maximization (PAM): They derive a new algorithm to solve the regularized dual. While standard OT uses the Sinkhorn algorithm, EOT requires an additional projection step onto the probability simplex to find the optimal weighting of agents.

Key Insights and Results

  • The Dudley Metric Connection: One of the most surprising findings is that the Dudley metric—a fundamental tool in probability theory—is actually a special case of EOT. This provides a new, faster way to approximate the Dudley metric using entropic regularization.
  • Fairness by Design: EOT naturally satisfies two major fairness criteria from economics: Proportionality (each agent gets at least $1/N$ of the total utility) and Equitability (all agents end up with the exact same utility/cost at the optimum).
  • Mass Partitioning: Unlike standard OT, where mass is moved along a single optimal path, EOT partitions the mass so that different agents handle different "parts" of the transport task based on their specific cost advantages.
Figure 2: Visualization of how mass is partitioned among three agents. The total transport plan is decomposed into sub-plans ($\mu_1^*, \mu_2^*, \mu_3^*$) with weights $\lambda_i^*$ to ensure each agent receives the same total utility.

Experiments on synthetic datasets demonstrate that the proposed PAM algorithm is significantly faster than standard Linear Programming (LP). For sample sizes where LP solvers become too costly (e.g., $n=500$), PAM provides high-accuracy estimates in seconds. The authors also show that as the regularization parameter $\epsilon$ approaches zero, the EOT solution converges to the ground truth optimal transport plan.

Conclusion

Equitable and Optimal Transport offers a robust framework for multi-agent resource allocation. While the PAM algorithm shows great practical performance, formal proofs of its convergence rates and extensions to Monge formulations remain promising avenues for future research.

Summary updated

Abstract

We introduce an extension of the Optimal Transport problem when multiple costs are involved. Considering each cost as an agent, we aim to share equally between agents the work of transporting one distribution to another. To do so, we minimize the transportation cost of the agent who works the most. Another point of view is when the goal is to partition equitably goods between agents according to their heterogeneous preferences. Here we aim to maximize the utility of the least advantaged agent. This is a fair division problem. Like Optimal Transport, the problem can be cast as a linear optimization problem. When there is only one agent, we recover the Optimal Transport problem. When two agents are considered, we are able to recover Integral Probability Metrics defined by $\alpha$-H\"older functions, which include the widely-known Dudley metric. To the best of our knowledge, this is the first time a link is given between the Dudley metric and Optimal Transport. We provide an entropic regularization of that problem which leads to an alternative algorithm faster than the standard linear program.
BibTeX
@inproceedings{scetbon2021handling,
  author = {Meyer Scetbon and Laurent Meunier and Jamal Atif and Marco Cuturi},
  title = {{Handling Multiple Costs in Optimal Transport: Strong Duality and Efficient Computation}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=6xxl12VzcC7},
}
Figure