Decentralized and Equitable Optimal Transport
This work addresses decentralized coordination in optimal transport for networks of agents, offering incremental improvements in efficiency and equity.
The paper tackles the decentralized optimal transport problem by reformulating it as a constraint-coupled optimization and proposes a single-loop decentralized algorithm with O(1/ε) iteration complexity, matching centralized approaches, and extends this to a decentralized equitable version with improved O(1/ε) complexity over existing centralized O(1/ε²) methods.
This paper considers the decentralized (discrete) optimal transport (D-OT) problem. In this setting, a network of agents seeks to design a transportation plan jointly, where the cost function is the sum of privately held costs for each agent. We reformulate the D-OT problem as a constraint-coupled optimization problem and propose a single-loop decentralized algorithm with an iteration complexity of O(1/ε) that matches existing centralized first-order approaches. Moreover, we propose the decentralized equitable optimal transport (DE-OT) problem. In DE-OT, in addition to cooperatively designing a transportation plan that minimizes transportation costs, agents seek to ensure equity in their individual costs. The iteration complexity of the proposed method to solve DE-OT is also O(1/ε). This rate improves existing centralized algorithms, where the best iteration complexity obtained is O(1/ε^2).