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.
翻译:当涉及多种成本时,我们引入了最佳运输问题的延伸。 将每种成本作为一个代理商, 我们的目标是在代理人之间平均分担将一个分销到另一个分销的工程。 要做到这一点, 我们就能将最有效工作的代理商的运输成本降到最低。 另一个观点是, 目标是根据不同偏好在代理人之间公平分配货物。 我们在这里的目标是最大限度地扩大最不优惠的代理商的效用。 这是一个公平的分割问题。 与最佳运输公司一样, 问题可以作为一个线性优化问题被抛出。 当只有一个代理商时, 我们恢复了最佳运输问题。 当两个代理商被考虑时, 我们就能回收由$\alpha$- H\\'older 函数定义的全方位概率计量, 其中包括广为人知的 Dudley 度。 根据我们所知, 这是第一次在Dudley 公标度和 Optimal Transport 之间设定一个连接。 我们为该问题提供了一种昆虫化的正规化, 导致一种比标准线性程序更快的替代算法。