On the distributed learning of Nash equilibria with minimal information

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 metadatas

https://hal-supelec.archives-ouvertes.fr/hal-00755528
Contributor : Evelyne Faivre <>
Submitted on : Wednesday, November 21, 2012 - 2:43:56 PM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM

Identifiers

  • HAL Id : hal-00755528, version 1

Citation

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⟩

Share

Metrics

Record views

686