Nash Equilibria for multi-agent network flow with controllable capacities

International audienceIn this work, a multi-agent network flow problem is addressed where a set of transportation-agents can control the capacities of a set of elementary routes A third-party agent, a customer, is interesting in maximizing the product flow transshipped from a source to a sink node through the network and offers a reward that is proportional to the flow value the transportation agents manage to provide. This problem can be viewed as a Multi-Agent Minimum-Cost Maximum-Flow Problem where the focus is put on finding stable strategies (i.e., Nash Equilibria) such that no transportation-agent has any incentive to modify its behavior. We show how such an equilibrium can be characterized by means of augmenting or decreasing paths in a reduced network. We also discuss the problem of finding a Nash Equilibrium that maximizes the flow and prove its NP-Hardness