Equitable and Optimal Transport with Multiple Agents

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.

References in corpus (11)

• Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
• Sample Complexity of Sinkhorn divergences
• Interpolating between Optimal Transport and MMD using Sinkhorn Divergences
• Subspace Robust Wasserstein Distances
• Towards Optimal Transport with Global Invariances
• Linear Time Sinkhorn Divergences using Positive Features
• Learning to Match via Inverse Optimal Transport
• Learning Cost Functions for Optimal Transport
• Comparing distributions: ${\ell }_1$ geometry improves kernel two-sample testing
• Feature Robust Optimal Transport for High-dimensional Data
• Multi-type Resource Allocation with Partial Preferences

Cited by in corpus (1)

• Decentralized and Equitable Optimal Transport