HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

On the distributed learning of Nash equilibria with minimal information

Octave Boussaton 1 Johanne Cohen 2 Joanna Tomasik 3 Dominique Barth 2
1 CORTEX - Neuromimetic intelligence
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : Route selection is one of the key problems to be treated in telecommunication management and control. We are interested in finding the routes which are balanced from the congestion or cost point of view. The 'classical' load balancing concerns an entire route, from its source node to its destination, which is selected according to its cost. This approach requires therefore the analysis of all existing routes whose number in a graph is exponential in function of the network size. This phenomenon makes a game on path level (macroscopic level) unrealistic. Our goal is to propose an algorithm which can find Nash equilibria by examining a polynomial number of graph network elements. Our main idea consists in choosing an outgoing arc in each node in exception of the destination (microscopic level) instead of an entire path. We achieve this by proposing a distributed algorithm which performs this selection in network nodes. We provide the analysis which proves that our algorithm converges weakly to Nash equilibria. The computation results are encouraging to continue the purely numerical work on the algorithm implementation.
Document type :
Conference papers
Complete list of metadata

Contributor : Evelyne Faivre Connect in order to contact the contributor
Submitted on : Wednesday, November 21, 2012 - 2:43:56 PM
Last modification on : Friday, February 4, 2022 - 3:19:57 AM


  • HAL Id : hal-00755528, version 1


Octave Boussaton, Johanne Cohen, Joanna Tomasik, Dominique Barth. On the distributed learning of Nash equilibria with minimal information. NetGCooP 2012, Nov 2012, Avignon, France. pp.30-37. ⟨hal-00755528⟩



Record views