Common-Knowledge Decomposition for Bayesian Games

L' objectif est de

contribuer au développement (théorique et/ou pratique) algorithmique d'une méthode de résolution approchée des jeux bayésiens., Etant donné un jeux Bayésien, la recherche d'information publique peut être réduite à un parcours en profondeur dans graphe dérivé du jeu Bayésien. Nous cherchons à étendre cette méthode pour approximer le jeu Bayésien par un autre jeu, le plus proche possible, contenant de l'information publique. Ce faisant, le temps de calcul pour la recherche d'équilibres de Nash devrait être significativement réduit.Les bases théoriques et une implémentation en C++ de cette décomposition existent déjà.

Les objectifs du stage sont ouverts, mais le stagiaire pourrait de préférence travailler sur un ou plusieurs des aspects suivants :

• mener une validation expérimentale de l'approche de décomposition approchée;
• proposer, mettre en œuvre et évaluer des variantes du programme linéaire permettant la décomposition;
• prouver que le problème de décomposition approchée appartient à la classe de complexité NP.

Pour une meilleure connaissance du sujet de recherche proposé :-, * revue de la littérature

• développement C++
• développement théoriques
• rédaction des résultats obtenu

Les compétences recherchées sont les suivantes: (en gras celles nécessaires)

• connaissances basiques en C++;
• théorie des graphes;
• classes de complexité et réductions.

Langues : Français/Anglais

• Restauration subventionnée
• Transports publics remboursés partiellement
• Congés: 7 semaines de congés annuels + 10 jours de RTT (base temps plein) + possibilité d'autorisations d'absence exceptionnelle (ex : enfants malades, déménagement), Sécurité défense : Ce poste est susceptible d'être affecté dans une zone à régime restrictif (ZRR), telle que définie dans le décret n°2011-1425 relatif à la protection du potentiel scientifique et technique de la nation (PPST). L'autorisation d'accès à une zone est délivrée par le chef d'établissement, après avis ministériel favorable, tel que défini dans l'arrêté du 03 juillet 2012, relatif à la PPST. Un avis ministériel défavorable pour un poste affecté dans une ZRR aurait pour conséquence l'annulation du recrutement.

Politique de recrutement : Dans le cadre de sa politique diversité, tous les postes Inria sont accessibles aux personnes en situation de handicap.

A propos du centre ou de la direction fonctionnelle Le centre Inria de l'Université de Rennes est l'un des huit centres d'Inria et compte plus d'une trentaine d'équipes de recherche. Le centre Inria est un acteur majeur et reconnu dans le domaine des sciences numériques. Il est au cœur d'un riche écosystème de R&D et d'innovation : PME fortement innovantes, grands groupes industriels, pôles de compétitivité, acteurs de la recherche et de l'enseignement supérieur, laboratoires d'excellence, institut de recherche technologique., John F Nash Jr. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48-49, 1950. - Frans A Oliehoek, Shimon Whiteson, and Matthijs TJ Spaan. Exploiting structure in cooperative bayesian games. In Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, pages 654-663, 2012. - Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforcement learning and search, Inria est l'institut national de recherche dédié aux sciences et technologies du numérique. Il emploie 2600 personnes. Ses 215 équipes-projets agiles, en général communes avec des partenaires académiques, impliquent plus de 3900 scientifiques pour relever les défis du numérique, souvent à l'interface d'autres disciplines. L'institut fait appel à de nombreux talents dans plus d'une quarantaine de métiers différents. 900 personnels d'appui à la recherche et à l'innovation contribuent à faire émerger et grandir des projets scientifiques ou entrepreneuriaux qui impactent le monde. Inria travaille avec de nombreuses entreprises et a accompagné la création de plus de 200 start-up. L'institut s'efforce ainsi de répondre aux enjeux de la transformation numérique de la science, de la société et de l'économie.