Equitable and Optimal Transport with Multiple Agents
This work addresses fair resource allocation and transport problems in multi-agent systems, offering a novel theoretical connection and computational improvement, though it is incremental in extending existing Optimal Transport frameworks.
The paper tackles the problem of extending Optimal Transport to multiple agents by minimizing the maximum transportation cost among agents, which also relates to fair division by maximizing the utility of the least advantaged agent. It shows that with two agents, the problem recovers Integral Probability Metrics like the Dudley metric, providing a novel link to Optimal Transport, and introduces an entropic regularization algorithm that is faster than standard linear programming.
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 $α$-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.