Finding A Maximum Stable Flow In A Multi-agent Network With Controllable Capacities

Prof.

Nadia Chabaane.
LAAS (Laboratoire d'Analyse et d'Architecture des SystÃ¨mes - CNRS) Toulouse, France

Course Type

Seminars

Calendar

14 maggio alle 9, Laboratorio di Metodi Decisionali.

Room

Program

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. The customer offers a reward that is proportional to the net flow from the source to the sink. 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. Our work will address the problem of finding a Nash equilibrium that maximizes the flow value, which turns out to be NP-hard.