A decentralised algorithm for minimizing multi-agent congestion cost on a network
# 184
Abstract
Consider a model wherein a given set of agents need to reach the goal node of a network. The cost for each agent on any link depends on the congestion on that link as well as on a cost component that is private to that agent. We propose a multi-agent congestion cost minimization (MACCM) algorithm for minimizing the total cost incurred by the agents. Our algorithm is fully decentralised, uses linear function approximations that addresses privacy of agents' costs as well as scalability aspects and achieves sub-linear regret. Each agent maintains an estimate of the global objective function and the algorithm relies on a multi-agent version of extended value-iteration. We illustrate computations on a hard instance. Our model is a generalisation of a classical learning problem, learning the stochastic shortest path problem.
N. Hemachandra is a Professor at Industrial Engineering and Operations Research, IIT Bombay. His current academic research interests include sequential decision models like Reinforcement learning, Multi-armed bandit problems, Markovian decision models, and other Operations Research methodologies like Learning algorithms, Game theory, etc., including their applications for resource allocation problems arising in the context of supply and value chains, communication networks, logistics, etc