Jeux à travers la lentille de algèbre et géométrie de l'optimisation – GALOP

Shapley a introduit les jeux stochastiques en 1953, et c’est depuis un sujet d'études intensives. Ils modélisent les interactions dynamiques dans un environnement qui change en fonction du comportement des joueurs. Leurs applications incluent l'organisation industrielle, l’économie des ressources, et les réseaux de communication. Pour un grand nombre de jeux stochastiques on sait décrire les stratégies d'équilibre et les gains des joueurs en utilisant des systèmes d'équations et d’inéquations polynomiales. Dans ce dialogue entre jeux et systèmes polynomiaux le défi est de diminuer la distance entre les bornes inférieures et supérieures apparaissant dans le calcul des équilibres, et d'obtenir des estimations précises de la complexité. Certains cas particuliers de jeux stochastiques continus nécessitent d’optimiser une fonction linéaire en restriction à un ensemble convexe opportun défini par des inégalités linéaires matricielles. Ce problème est connu sous le nom de programmation semi-définie (SDP).

GALOP focalise sur les caractéristiques algébriques et géométriques des jeux stochastiques. Elle amène des outils géométrique et algébriques originaux et innovants, basés sur le calcul symbolique-numérique, exploitant la géométrie et la structure du problème considéré et améliorant l'état de l'art. Avec ces outils nous introduisons des algorithmes et des bornes précises pour des jeux stochastiques à deux joueurs à somme nulle.
Notre approche: dépend du nombre solutions (sensibilité à la sortie), produit toujours un résultat numérique, géométrique, ou combinatoire, correct (certifié), et exploite la structure de l'entrée comme le caractère creux, les symétries, la géométrie de l’ensemble solution (structure).

GALOP est structurée selon trois axes. Dans "jeux stochastiques" nous ciblons des algorithmes et des bornes précises pour calculer les parame`tres des jeux stochastiques en utilisant des techniques de la géométrie algébrique réelle effective et nous introduisons un nouvel arsenal d'outils algébriques dans la théorie des jeux effective. Dans "géométrie d'optimisation" nous étudions la courbe centrale SDP pour approfondir notre compréhension du problème et découvrir des nouveaux algorithmes semi-numeriques. Nous considérons également des techniques symboliques- numériques pour l'optimisation polynomiale, basées sur la méthode du point critique. Finalement, dans "outils algébriques", nous nous focalisons sur des bornes séparantes de systèmes polynomiaux admettant une structure spéciale, et nous nous concentrons sur la résolution de polynômes univariés. Nous fournissons un logiciel efficace, certifié, open source, pour la résolution sur les réels de polynomiaux univariés. Il peut être utilisé seul via FLINT ou via des systèmes de calcul formel généraux. Nous l’intégrons avec le meilleur logiciel de calcul de bases de Groebner FGb pour produire un outil de pointe pour résoudre exactement les systèmes polynomiaux 0-dimensionnels.

Les jeux stochastiques et la SDP impactent de nombreuses disciplines de recherche, unifient beaucoup de questions, et sont un paradigme de modélisation dans les applications. Ainsi, raisonner sur leurs propriétés en utilisant l’algèbre et la géométrie constitue un véritable défi, tout en ouvrant également de nouvelles directions de recherche.