Learning Individual Policies in Large Multi-agent Systems through Local Variance Minimization
This addresses coordination inefficiencies for self-interested agents in large-scale systems like transportation networks, representing an incremental improvement with a novel method for a known bottleneck.
The paper tackles the problem of coordinating self-interested agents in large multi-agent systems, such as ride-hailing services, by modeling them as Stochastic Non-atomic Congestion Games and proposing a Multi-Agent Reinforcement Learning mechanism that minimizes variance in agent values. The result shows that this approach reduces variance in taxi driver revenues while achieving higher joint revenues compared to leading methods.
In multi-agent systems with large number of agents, typically the contribution of each agent to the value of other agents is minimal (e.g., aggregation systems such as Uber, Deliveroo). In this paper, we consider such multi-agent systems where each agent is self-interested and takes a sequence of decisions and represent them as a Stochastic Non-atomic Congestion Game (SNCG). We derive key properties for equilibrium solutions in SNCG model with non-atomic and also nearly non-atomic agents. With those key equilibrium properties, we provide a novel Multi-Agent Reinforcement Learning (MARL) mechanism that minimizes variance across values of agents in the same state. To demonstrate the utility of this new mechanism, we provide detailed results on a real-world taxi dataset and also a generic simulator for aggregation systems. We show that our approach reduces the variance in revenues earned by taxi drivers, while still providing higher joint revenues than leading approaches.