Vous êtes ici : UVSQ RechercheDoctoratSoutenances de thèse

«THEORIE DES GRAPHES, ET DE L’APPROXIMATION POUR LE ROUTAGE, LA COLORATION ET L’APPRENTISSAGE D’EQUILIBRES»

le 7 décembre 2009

Le Lundi 7 Décembre 2009 A 14h00

à

L'UNIVERSITE DE VERSAILLES SAINT-QUENTIN EN-YVELINES Batiment Descartes- Laboratoire PRISM - Salle 301 45 Avenue des Etats Unis - 78000 Versailles


Plan d'accès

Présentée par Madame Johanne COHEN Domaine : Informatique Laboratoire : PRISM

Résumé : Le mémoire présente une sélection de nos travaux de recherche.  Après un chapitre introductif, nous présentons quelques conséquences de la présence de partenaires  économiques dans les réseaux dans le chapitre 2 : nous présentons ainsi un survol du problème algorithmique du calcul d'arbre de plus court chemin en présence d'adversaires, et quelques résultats personnels. Les chapitres 3 et 4 discutent de la frontière entre les problèmes tractables et non tractables sous deux angles différents. Dans le chapitre 3, nous présentons la théorie de l'approximation, en l'illustrant par trois de nos travaux. Deux des algorithmes d'approximation décrits permettent d'assurer une certaine garantie sur l'utilisation de ressources du réseau, et sur une qualité de service. Le troisième problème traite d'approximation d'un problème de la théorie des graphes : la minimisation d'arrangements linéaires pour les graphes d'intervalle. Le chapitre 4 présente des problèmes de coloration de graphes non classiques. Le chapitre 5 est une introduction à la théorie algorithmique des jeux, et des jeux classiques  étudiés en informatique. Il sert essentiellement à définir les concepts utilisés par la suite.

Le chapitre 6 introduit certains modèles de dynamisme en théorie des jeux. Il présente la notion de jeux répétés, et les propriétés de leurs  équilibres de Nash. Il présente les dynamiques de joueurs fictifs, et les dynamiques de meilleure réponse dans le contexte des protocoles de population. Ce dernier point présente nos travaux visant à comprendre ce qui est programmable par de telles dynamiques. Le chapitre 7 présente nos travaux à propos de l'apprentissage d'équilibres de Nash : c'est-à-dire visant à construire des comportements tels que si chacun des joueurs adopte ces comportements alors le système global converge vers un équilibre de Nash. Nous nous intéressons en particulier à l'apprentissage d'équilibres sur les jeux de potentiel ordinal.

 

 

Abstract :  The document presents a selection of our research results. After some introductive chapter, we present some consequences of the presence of economic partners in networks in Chapter 2: we present a survey of the algorithmic problem of computing shortest path trees in presence of economic partners, and some of our own results. Chapter 3 and 4 discuss the frontier between tractable and intractable problems. In Chapter 3, we present the theory of approximation, illustrated by three of our studies. Two of the approximation algorithms that are described provide guarantees on the use of resources of the network and on the quality of service. The last problem is about the approximation of a problem from graph theory: the minimization of linear arrangements for interval graphs. Chapter 4 presents some non-classical coloration graph problems. Chapter 5 is an introduction to algorithmic game theory, and of classical games studied in computer science. It mainly introduces the concepts that are used afterwards in the document. Chapter 6 introduces some models for dynamism in game theory. It presents the notion of repeated game, and the resulting properties on their Nash equilibria. It presents the fictitious player dynamics, and the best response dynamics in the context of population protocols. This is intended to present our work related to the question of understanding what can be computed or programmed by such dynamics. Chapter 7 presents our work about Nash equilibria learning, that is to say about constructing behaviors that guarantee convergence towards Nash equilibria. We focus in particular on the learning of equilibria in ordinal potential games.

Informations complémentaires

MEMBRES DU JURY :

Evripidis Bampis, Professeur des Universités à l'Université d'Evry Val d'Essonne - Rapporteur

Michel HABIB, Professeur des Universités à l'Université de Paris 7 Diderot  - Rapporteur

George D. STAMOULIS, Professeur des Universités à  « Athens University of Economics and Business departement of informatics Grèce - Rapporteur (non présent à la soutenance)

Dominique Barth, Professeur des Universités à l'Université de Versailles Saint Quentin en Yvelines - Examinateur

Christoph Durr, Chargé de recherche Habilité à Diriger des Recherche à l'Ecole Polytechnique - Examinateur

Bruno GAUJAL, Directeur de recherche, à l'Institut National de recherche en Informatique et en Automatique - Examinateur

Joffroy BEAUQUIER, Professeur des Universités à l'Université Paris XI Orsay- Examinateur 

Contact :
Direction de la recherche des Etudes Doctorales et de la Valorisation - DREDVal :