Load Balancing Congestion Games and their Asymptotic Behavior

Abstract : A central question in routing games has been to establish conditions for the uniqueness of the equilibrium, either in terms of network topology or in terms of costs. This question is well understood in two classes of routing games. The first is the non-atomic routing introduced by Wardrop on 1952 in the context of road traffic in which each player (car) is infinitesimally small; a single car has a negligible impact on the congestion. Each car wishes to minimize its expected delay. Under arbitrary topology, such games are known to have a convex potential and thus a unique equilibrium. The second framework is splitable atomic games: there are finitely many players, each controlling the route of a population of individuals (let them be cars in road traffic or packets in the communication networks). In this paper, we study two other frameworks of routing games in which each of several players has an integer number of connections (which are population of packets) to route and where there is a constraint that a connection cannot be split. Through a particular game with a simple three link topology, we identify various novel and surprising properties of games within these frameworks. We show in particular that equilibria are non unique even in the potential game setting of Rosenthal with strictly convex link costs. We further show that non-symmetric equilibria arise in symmetric networks.
Type de document :
Communication dans un congrès
NEtwork Games. Optimization and Control, Nov 2016, AVIGNON, France
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01378907
Contributeur : Eitan Altman <>
Soumis le : mardi 11 octobre 2016 - 00:56:44
Dernière modification le : vendredi 31 août 2018 - 09:12:07
Document(s) archivé(s) le : jeudi 12 janvier 2017 - 13:17:47

Fichier

camera-ready-4.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01378907, version 1

Collections

Citation

Eitan Altman, Corinne Touati. Load Balancing Congestion Games and their Asymptotic Behavior. NEtwork Games. Optimization and Control, Nov 2016, AVIGNON, France. 〈hal-01378907〉

Partager

Métriques

Consultations de la notice

314

Téléchargements de fichiers

62