Résumé - Sur la complexité des équilibres corrélés optimaux dans les jeux à forme extensive

Sur la complexité des équilibres corrélés optimaux dans les jeux à forme extensive

2025-07-15 17:24:16

{"Vincent Cheval","Florian Horn","Soumyajit Paul","Mahsa Shirmohammadi"}

{cs.GT,cs.CC,F.2.0}

Ce document investigate la complexité computationnelle de la recherche des équilibres corrélés optimaux dans les jeux à forme extensive, en se concentrant spécifiquement sur le problème " seuil " : déterminer s'il existe un équilibre corrélé avec une valeur supérieure à un seuil donné. **Principaux résultats** : * **Complexité PSPACE pour l'NFCE** : Le document établit que le problème seuil pour les équilibres corrélés de forme normale (NFCE) est PSPACE-dure même pour les jeux à forme extensive à joueurs multiples avec un souvenir parfait et des seuils fixes. Cela implique que la recherche des NFCE optimaux est un défi computationnel, même pour les jeux avec un petit nombre de joueurs. * **Complexité NP pour l'AFCE et l'AFCCE** : Le document prouve également que le problème seuil pour les équilibres corrélés de forme agent (AFCE) et les équilibres corrélés grossiers de forme agent (AFCCE) est NP-dure, même pour les jeux à deux joueurs sans noeuds aléatoires. Cela suggère que la recherche des AFCE et des AFCCE optimaux est également difficile. * **Complexité NP-complète pour d'autres concepts d'équilibre** : Le document montre que le problème seuil pour d'autres concepts d'équilibre corrélé, tels que les équilibres corrélés de forme extensive (EFCE), les équilibres corrélés grossiers de forme extensive (EFCCE), les équilibres grossiers de forme normale (NFCCE) et les équilibres grossiers de forme agent (AFCCE), est NP-complet pour les jeux à joueurs multiples stochastiques à forme extensive avec un souvenir parfait. * **Inversion de complexité** : Le document révèle une inversion surprenante de complexité : tandis que les équilibres corrélés optimaux sont plus simples computationnellement que les équilibres Nash optimaux dans les jeux à forme normale, l'inverse est vrai dans les jeux à forme extensive. Cela contredit l'attente établie depuis longtemps que les équilibres Nash optimaux sont intrinsèquement plus complexes. **Implications** : * **Complexité de représentation** : Le document met en lumière l'importance de comprendre la complexité de représentation des équilibres corrélés optimaux dans les jeux à forme extensive. Il suggère que trouver des représentations succinctes pour les NFCE optimaux peut être un défi. * **Approches algorithmiques** : Les résultats motivent le développement d'approches algorithmiques efficaces pour calculer des équilibres corrélés approximatifs dans les jeux à forme extensive. * **Recherche further** : Le document laisse plusieurs questions ouvertes, y compris la complexité exacte du problème seuil pour l'NFCE dans les jeux à deux joueurs ou les jeux avec un nombre constant de joueurs. **Dans l'ensemble, ce document fournit des insights précieux sur la complexité computationnelle de la recherche des équilibres corrélés optimaux dans les jeux à forme extensive et contribue à une compréhension plus large de la théorie des jeux algorithmique**.