Finding a Nash equilibrium and an optimal sharing policy for multiagent network expansion game. Issue 1 (14th October 2016)

• Record Type: Journal Article
• Authors: Chaabane, Nadia; Briand, Cyril; Huguet, Marie‐José; Agnetis, Alessandro
• Is Part Of: Networks. Volume 69:Issue 1(2017)
• Page Start: 94
• Page End: 109
• Publication Date: 2016-10-14
• Subjects: multiagent network flow -- Nash equilibria -- complexity -- network expansion game -- mixed integer linear programming; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21711
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : In this work, a multiagent network flow problem is addressed, aiming at characterizing the properties of stable flows and allowing their computation. Two types of agents are considered: transportation‐agents, that carry a flow of products on a given network and another agent, either a producer or a customer, who is willing to ship (receive, respectively), products. Every transportation‐agent controls a set of arcs, each having a capacity that can be increased up to a certain point at a given cost. The other agent (i.e., the customer/producer) is interested in maximizing the flow transshipped through the network. To this aim, we assume it offers the transportation‐agents a reward that is proportional to the realized flow value. This particular multiagent framework is referred to as a Multiagent network expansion game. We characterize and find particular stable strategies (i.e., Nash equilibria) that are of interest for this game. We particularly focus on the problem of finding a Nash Equilibrium and a sharing policy that maximize the value of the total flow. We prove that this problem is NP‐hard in the strong sense and show how such a strategy can be characterized considering paths in specific auxiliary graphs. We also provide a mixed integer linear programming formulation to solve the problem. Computational experiments are provided to prove the effectiveness of our approach and derive some insights for practitioners. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 94–109 2017