Journées Franciliennes de Recherche Opérationnelle
ROADEF




Retour

Programme (JFRO)

Programme de la journée du 25 mars 2005

 

Théorie de jeux et recherche opérationnelle

Carré des Sciences

Amphithéatre Yves Stourdze
Ministère de l'Education Nationale, de la Recherche et de la Technologie
1, rue Descartes - 75005 Paris

9H30 - 10H

Accueil des participants

10H - 12H

 

Exposé : LES JEUX ET LES MECANISMES COMME MODELE DE CALCUL

Michel De Rougemont - LRI, Université Paris II Panthéon-Assas

 

Transparents de l'exposé au format PPT

 

On présente les fondements de la théorie algorithmique des jeux et des mécanismes. Les équilibres de Nash pour les jeux à somme nulle et les jeux matriciels, l'équilibre Arrow-Debreu.
On décrira les résultats classiques de complexité et d'approximation et des exemples de jeux et de mécanismes en Informatique.

 12h00 - 13h50

DÉJEUNER

13h50 - 14h30

 

APPLICATIONS DE LA THEORIE DES JEUX AUX RESEAUX

Thomas Boulogne - Equipe Combinatoire et Optimisation, Université Paris 6

 

 

Nous considérerons des modèles où un grand nombre de paquets (dans le cadre du trafic routier, ceux-ci correspondent à des véhicules), modélisé par un continuum, doivent aller d'un point du réseau à un autre. Pour ce faire les paquets peuvent etre délivrés via différents chemins (routes) possibles. Tout chemin présente un cout dépendant de sa fréquentation ou plus généralement de la répartition des paquets au travers des différents chemins. Les décisions de routage, c'est-à-dire le choix des routes pour les paquets, peuvent se faire de trois manières différentes : la décision centralisée, la décision groupée ou la décision individuelle. Le premier type de décision correspond à un problème de minimisation, les deux autres à des problèmes de jeux. Nous étudierons ces deux derniers types : la décision groupée conduit à un jeu à N personnes dont un concept de solution est l'équilibre de Nash et la décision individuelle à un jeu avec un continuum de joueurs dont un concept de solution est l'équilibre de Wardrop.


14h30-15h10

 

ROUTAGE, GESTION DE RESSOURCES & EQUILIBRES PURS

Johanne Cohen - LORIA, CNRS

 

Transparents de l'exposé au format PDF

 

Notre objectif est de survoler dans le temps imparti par l'intermédiaire de quelques exemples, inspirés de problèmes de routage ou d'allocation de taches, certains résultats qui peuvent etre établis sur leurs équilibres de Nash, en particulier sur l'existence d'équilibres purs.
On cherchera à discuter en parallèle les liens connus entre équilibres de Nash et minimums locaux et globaux de certaines fonctions sur l'état global du système.

 15h10 - 15h30

PAUSE

15h30-16h10

 

GESTION DE COUTS ENTRE OPERATEURS

Loubna Echabbi - PRISM, Université de Versailles Saint-Quentin

 

Transparents de l'exposé au format PPT

 

Nous nous intéressons au routage interdomaine d'un point de vue économique. Nous présentons un modèle de cout basé sur la théorie des jeux.
Les systèmes autonomes appartenant à divers opérateurs agissent comme des agents stratégiques en compétition pour offrir et tarifer leurs services de transit les uns aux autres. En effet, chaque opérateur fixe un prix pour chacun de ses voisins pour chaque unité de trafic en transit.
Les routes effectivement prises par le trafic sont ensuite calculées par BGP selon un critère de cout minimum. Le but de chaque opérateur est de choisir ses prix afin de minimiser ses couts.
Nous nous intéressons à des stratégies particulières de mise à jour des prix que les opérateurs peuvent utiliser localement afin de minimiser leurs couts.
Nous étudions les propriétés de stabilisation liées à de telles stratégies grace à différents scénarios simulés.

 

16h10-17h00

 

A LA RECHERCHE D'UNE SOLUTION "STABLE": DEUX PROBLEMES MELANT RECHERCHE OPERATIONNELLE ET THEORIE DES JEUX

Fanny Pascual et Laurent Gourvès - LAMI, Université d'Evry

 

Transparents de l'exposé de Laurent Gourvès au format PDF

Transparents de l'exposé de Fanny Pascual au format PDF

 

On s'intéresse à deux problèmes issus de la recherche opérationnelle. Dans les deux cas, on recherche une solution stable dans le sens où elle ne sera pas remise en cause par les agents. De plus, la solution recherchée doit optimiser une fonction objectif globale.
Le premier problème consiste à ordonnancer n taches (agents) sur deux machines. D'un point de vue global nous cherchons à minimiser le temps de terminaison de la dernière tache. Du point de vue d'une tache, seule la date à laquelle son exécution se termine est déterminante. Dans ce cadre, une solution stable est un équilibre de Nash, pouvant etre mauvais pour la fonction objectif. Cependant, en relachant la notion d'équilibre de Nash, nous montrons qu'il est possible d'améliorer la fonction objectif globale.
Le second problème concerne la partage équitable du cout d'un service apporté à un ensemble de clients (agents) dans un réseau. Dans ce cadre, une solution est dite stable si elle appartient au coeur du jeux coopératif sous-jacent. Cependant plusieurs solutions stables peuvent exister, et du point de vue d'un agent, engendrer des couts différents. Nous introduisons une mesure d'équité qui capture le mécontentement de chaque agent et nous proposons deux méthodes de partage de cout qui minimisent le pire mécontentement et le mécontentement moyen.