Thèse sur les équilibres corrélés et l'apprentissage - F/H

Description de l'offre

about the role

La théorie des jeux est une branche des mathématiques dédiée à la formalisation et à l'analyse de la prise de décisions en situations d'interactions (ex. échecs, Go, économie, enchères, etc.). Les principaux objectifs de l'analyse « non-coopérative » sont la définition de concepts de solutions pertinents, la recherche de profils de stratégies « stables » (existence et calculs) ainsi que l'analyse des propriétés des règles ou algorithmes d'apprentissage implémentés par les joueurs.

Plusieurs notions de stabilités ont été définies. Le concept dominant est appelée équilibre de Nash. Au-delà de la pertinence du concept en lui-même, son succès est essentiellement due à une existence systématique dans les jeux finis [6][7] et à des conditions relativement faibles dans un grand nombre d'autres classes de jeux. En dépit de ces propriétés, il peut être difficile de calculer un équilibre de Nash [8] à cause de la combinatoire sous-jacente.

Un concept de solution plus général, appelé « équilibre corrélé » a été proposé en [1]. Les équilibres corrélés généralisent les équilibres de Nash en introduisant une synchronisation collective sous la forme d'une distribution jointe des stratégies aléatoires (non réduite à une forme produit, i.e. supposant l'indépendance des stratégies aléatoires). Cette corrélation peut être due à une communication entre les joueurs, à une recommandation par un médiateur ou à une synchronisation émergeant d'un partage d'information. En dépit de la généralisation, les équilibres corrélés bénéficient de la propriété d'existence des équilibres de Nash. Ils sont également moins complexes à calculer [8].

Du point de vue de l'apprentissage et du machine learning, les équilibres corrélés ont également montré leur intérêt. Des conditions (assez faibles) sur les jeux et schémas d'apprentissage basés sur le regret induisant la convergence de la séquence de profils de stratégies jouées vers l'ensemble des équilibres corrélés ont été obtenues [3].

Il a également été montré en [5] que tout jeu fini peut être projeté en une réduction duale ou un jeu élémentaire plus simple (moins de stratégies) mais héritant tout de même de certains équilibres corrélés du jeu de départ…

Les propriétés précédentes ont d'importantes conséquences algorithmiques mais servent aussi d'appui pour justifier des équilibres corrélés comme d'une alternative pertinent au concept de Nash.

Du point de vue pratique et des applications, les équilibres corrélés, leurs propriétés et les méthodes de réductions sont particulièrement pertinents pour l'analyse des systèmes complexes et des jeux où les équilibres de Nash sont difficilement calculables ou pour lesquels le comportement collectif a un rôle important (ex. réseaux, économie, biologie).

Cependant, en dépit des attrayantes propriétés des équilibres corrélés, une difficulté persiste, il s'agit de la multiplicité des équilibres et de leur sélection [4], notamment dans le cadre dynamique de l'apprentissage. Dans cette thèse, on propose de mener une recherche innovante sur ces sujets.

Etat de l'art : Les équilibres corrélés, l'apprentissage dans les jeux et le problème de sélection d'équilibre sont le sujet de nombreuses études et d'une riche littérature. Ce socle de connaissance garantit une base solide à la thèse. Récemment, le problème d'apprentissage dans les jeux a mis en évidence [2] le rôle clé des équilibres corrélés.

Le sujet de cette thèse est à la frontière de la théorie des jeux « classique » et de développements plus récents motivés par l'algorithmique et le machine learning.

about you

Formation demandée (master, diplôme d'ingénieur, domaine …) :

·  Master 2 ou école d'ingénieur avec spécialité en mathématiques, mathématiques appliqués (optimisation, jeux, machine learning, etc.) ou computer science

Expériences souhaitées (stages, …) :

·  une expérience passée en théorie des jeux ou machine learning est un plus
Compétences (scientifiques et techniques) et qualités personnelles souhaitées par le poste

·  Compétences scientifiques et techniques

·  Mathématiques (la théorie des jeux est un plus mais pas obligatoire)
·  Algorithmes & machine learning
·  Programmation : python

·  Soft skills

·  rigueur, patience, logique
·  autonomie
·  sociabilité
·  flexibilité et souplesse d'esprit

additional information

·  Objectif scientifique - verrous à lever

En dépit d'attrayante propriétés, les équilibres corrélés continuent de poser la question de la multiplicité et du problème de sélection [4] dans le cadre statique ou dynamique de l'apprentissage.

En effet, dans un jeu, il peut exister plusieurs équilibres corrélés. Le problème d'identification du plus « pertinent » n'est que partiellement résolu par les méthodes de réduction ou les concepts affinés. Ce problème se pose également dans le cadre de l'apprentissage dans les jeux [2] car même si les règles d'apprentissage impliquent une convergence vers un sous-ensemble d'équilibres corrélés, les mécanismes de sélections et d'ajustement ne sont pas encore clairs.

Dans cette thèse, on cherchera à résoudre les problèmes précédents,

·  en étudiant les équilibres corrélés, leurs propriétés et les techniques de réduction ou projection de jeux,
·  en étudiant le problème de sélection d'équilibres corrélés et ses liens aux jeux coopératifs,
·  en concevant et analysant des propriétés pertinentes, algorithmes et règles d'apprentissage résolvant cette difficulté.

·  Approche méthodologique-planning

·  Etude préliminaire et état de l'art,
·  Identification ou conception d'exemples jouets montrant les difficultés et défis résoudre,
·  Identification d'hypothèses sur l'origine de ces difficultés et de solutions candidates,
·  Validation et mise-à-jour des hypothèses et solutions candidates sur les exemples jouets,
·  Rédaction d'article(s)
·  Généralisations, definition de nouveaux problems, etc.
·  Rédaction du manuscrit

·  Références

[1]Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1(1):67{96, 1974.

[2]Holly P. Borowski, Jason R. Marden, and Je_ S. Shamma. Learning efficient correlated equilibria. CoRR, abs/1512.02160, 2015.

[3]Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, USA, 2006.

[4]ROGER B. MYERSON. Game Theory: Analysis of Conict. Harvard University Press, 1991.

[5]Roger B. Myerson. Dual reduction and elementary games. Games and Economic Behavior, 21(1):183-202, 1997.

[6]John Nash. Non-cooperative games. Annals of Mathematics, 54(2):286 295, 1951.

[7]John F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1):48{49, 1950.

[8]Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, USA, 2007.

department

·  description de l'équipe

Au sein d'Orange Labs, vous serez intégré à une équipe de recherche dont les membres sont des chercheurs en mathématiques, informatiques, machine learning ou data science.

La mission de cette équipe est d'éclairer le futur en concevant ou analysant des données, modèles mathématiques et algorithmes résolvant des problèmes théoriques ou appliqués (typiquement dans le cadre network science ou économie).

Les travaux de recherche et innovations sont dirigés par des chercheurs permanents, des doctorants ou des post-docs conjointement avec des partenaires académiques prestigieux dans le cadre de projets nationaux ou internationaux.

·  qu'est ce qui fait la valeur ajoutée de cette offre ?

Ce doctorat vous offre l'opportunité de prendre part à une équipe de recherche au sein d'un grand groupe et d'être guidés par des chercheurs dynamiques sur un problème important à l'interface des mathématiques, de l'informatique et de l'économie.

contract

Thèse