Finding a Maximum Stable Flow in a Multi-agent Network with Controllable Capacities
Résumé
Multi-agent network games have become a promising interdisciplinary research area with important links to many application fields such as transportation. In these applicative areas, decision processes often involve several agents, each one having its own autonomy, its own objectives and its own constraints. In this work, a basic multi-agent transportation problem is considered where a set of agents (transportation-agents) can control the capacities of a set of elementary routes, modeled as arcs inside a transportation network. Each transportation-agent incurs a cost proportional to the capacity that it chooses for its routes. One particular agent (a customer agent) is interesting in maximizing the product flow transshipped from a source to a sink node through the network. We assume that it offers a reward that is proportional to the flow that the transportation-agents manage to provide. This reward is shared among the transportation-agents according to a pre-established sharing policy, each of them willing to maximize its own profit. This problem can be viewed as a Multi-Agent Minimum-Cost Flow Problem where the focus is put on finding stable strategies (i.e., Nash Equilibrium) such that no transportation-agent has any incentive to modify its behavior. We show how such equilibrium can be characterized by means of augmenting or decreasing path in a reduced network.
Our presentation will address the problem of finding a Nash equilibrium that maximizes the flow value, which turns out to be NP-hard. We explain how such a problem can be modeled and solved by mixed integer linear programming (MILP), using a finite number of primal-dual constraints. An experimental study will also be provided for assessing the approach effectiveness on a large set of problem instances.