Equitable and Optimal Transport with Multiple Agents

Meyer Scetbon, Laurent Meunier, Jamal Atif, Marco Cuturi
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:2035-2043, 2021.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-scetbon21a, title = { Equitable and Optimal Transport with Multiple Agents }, author = {Scetbon, Meyer and Meunier, Laurent and Atif, Jamal and Cuturi, Marco}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {2035--2043}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/scetbon21a/scetbon21a.pdf}, url = {https://proceedings.mlr.press/v130/scetbon21a.html}, 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. } }
Endnote
%0 Conference Paper %T Equitable and Optimal Transport with Multiple Agents %A Meyer Scetbon %A Laurent Meunier %A Jamal Atif %A Marco Cuturi %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-scetbon21a %I PMLR %P 2035--2043 %U https://proceedings.mlr.press/v130/scetbon21a.html %V 130 %X 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.
APA
Scetbon, M., Meunier, L., Atif, J. & Cuturi, M.. (2021). Equitable and Optimal Transport with Multiple Agents . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:2035-2043 Available from https://proceedings.mlr.press/v130/scetbon21a.html.

Related Material