Finding a Nash equilibrium and an optimal sharing policy for multiagent network expansion game

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...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2017-01, Vol.69 (1), p.94-109
Main Authors: Chaabane, Nadia, Briand, Cyril, Huguet, Marie‐José, Agnetis, Alessandro
Format: Article
Language:English
Subjects:
complexity
Computation
Game theory
Games
Mixed integer
mixed integer linear programming
multiagent network flow
Multiagent systems
Nash equilibria
network expansion game
Networks
Policies
Strategy
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:0028-3045
1097-0037
DOI:10.1002/net.21711