Equitable and Optimal Transport with Multiple Agents

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ölder 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: From Efficiency to Fairness

Standard Optimal Transport (OT) is fundamentally utilitarian: it seeks the most efficient way to move mass from a source to a target by minimizing the total aggregate cost. However, many real-world scenarios—such as distributing tasks among workers or the fair division of resources (e.g., cake-cutting)—require more than just efficiency. In these cases, it is crucial to ensure that no single agent is overburdened or unfairly treated.

This paper introduces Equitable and Optimal Transport (EOT), a framework that bridges the gap between OT and Fair Division theory. By minimizing the maximum cost across multiple agents (or maximizing the minimum utility), EOT provides a mathematically rigorous approach to achieving fairness in resource allocation while maintaining the structural benefits of the OT framework.

The EOT Framework

The authors define EOT as a min-max problem: finding a transport plan that minimizes the cost of the agent who "works the most." This formulation naturally leads to equitability; under mild conditions, the optimal solution is one where every agent's cost is identical.

Visualization of multiple transportation costs (agents) between two distributions.

In the multi-agent setting, each agent may have a different cost function (e.g., Euclidean, squared Euclidean, or $L_1$ distances). EOT balances these heterogeneous preferences to find a stable partition where no two agents would benefit from swapping their assigned resources.

Theoretical Bridges: The Dudley Metric

A significant theoretical contribution of this work is the formal link established between OT and the Dudley metric. The Dudley metric is a well-known tool in probability theory, but it previously lacked a clear transport-based interpretation. The authors demonstrate that the Dudley metric is a specific case of EOT where one agent has a "trivial" cost and another uses a standard distance metric. This discovery allows the Dudley metric to be computed much faster using the authors' regularized algorithm.

Algorithmic Innovation: Entropic Regularization and PAM

Solving large-scale linear programs for EOT is computationally expensive ($O(n^3 \log n)$). To address this, the authors apply entropic regularization—a technique popularized by the Sinkhorn algorithm—to smooth the objective function.

They introduce the Projected Alternating Maximization (PAM) algorithm. While standard Sinkhorn updates two scaling vectors, PAM adds a third step: a projection onto a probability simplex to balance the "weights" of the different agents, ensuring the transport plan is split equitably.

Decomposition of the optimal transport plan into equitable shares for three agents, achieving balanced costs.

Key Results and Benchmarks

The paper evaluates the EOT framework using synthetic benchmarks, including 2D Gaussian distributions and wind-effect simulations where transportation costs vary daily. Key findings include:

  • Speed and Scalability: The PAM algorithm is orders of magnitude faster than standard Linear Programming (LP). For sample sizes of $n=500$, LP becomes computationally prohibitive, while PAM converges in seconds.
  • Accuracy: PAM provides higher accuracy and more stable convergence compared to other optimization methods like Accelerated Projected Gradient Ascent (APGA).
  • Fairness: The authors formally prove that EOT satisfies "Proportionality" (each agent receives at least $1/N$ of the total utility) and "Equitability."

Limitations and Future Work

While PAM performs exceptionally well in practice, a formal proof of its convergence rate remains an open problem. Additionally, the current framework assumes resources are "divisible" (fluid-like) and does not yet address the "Monge formulation" for indivisible units. Future research may explore applying EOT to high-dimensional machine learning problems, such as fair GANs or multi-domain adaptation.

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ölder 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{scetbon2021equitable,
  author = {Meyer Scetbon and Laurent Meunier and Jamal Atif and Marco Cuturi},
  title = {{Equitable and Optimal Transport with Multiple Agents}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=6xxl12VzcC7},
}
Figure