Résumé technique : Nash sans nombres : Une approche de choix social pour les équilibres mixtes dans les jeux context-ordinaux

Énoncé du problème

La théorie des jeux classique repose sur l'équilibre de Nash (EN), un concept fondamentalement ancré dans la maximisation de l'utilité numérique espérée. Cependant, dans de nombreux scénarios stratégiques — tels que les élections, l'élucidation des préférences humaines et l'évaluation d'agents — les utilités cardinales précises sont indisponibles ou difficiles à obtenir. Bien que les joueurs puissent souvent fournir des classements ordinaux des résultats, la définition standard d'une « meilleure réponse » (maximisation de l'utilité espérée) devient mal définie lorsque les co-joueurs adoptent des stratégies mixtes (probabilistes). Les tentatives précédentes pour résoudre ce problème ont soit abandonné la théorie des probabilités au profit de la théorie des possibilités, soit introduit des équilibres médiatisés nécessitant un coordinateur tiers, soit restreint l'analyse aux stratégies pures. Le défi central consiste à définir un équilibre en stratégies mixtes qui repose uniquement sur des préférences ordinales, sans supposer l'accès à des utilités cardinales sous-jacentes.

Méthodologie

Les auteurs proposent un cadre de Jeu Context-Ordinal (JCO) et un Équilibre de Nash Context-Ordinal (EN-CO) correspondant.

1. Jeux Context-Ordinaux (JCO)

Contrairement aux Jeux Ordinaux (JO) traditionnels où les joueurs classent les résultats conjoints de manière globale, un JCO suppose que les joueurs ne peuvent classer leurs propres actions que conditionnellement aux actions conjointes spécifiques de leurs co-joueurs.

• Définition : Un JCO est un tuple $\langle N, A, \rho \rangle$, où $\rho_i$ associe à l'action conjointe $a_{-i}$ d'un co-joueur une relation de préférence sur les actions $A_i$ du joueur $i$.
• Meilleure réponse via le choix social : Pour définir une meilleure réponse face à une stratégie mixte $x_{-i}$, les auteurs agrègent les « votes » (classements ordinaux) générés par chaque $a_{-i}$ possible, pondérés par sa probabilité $x_{-i}(a_{-i})$. Cela crée une population de votes. Une Fonction de Choix Social Doubly Probabiliste (dpSCF) est ensuite appliquée à cette population pour déterminer l'ensemble des actions gagnantes.
• EN-CO : Un profil de stratégies $x$ est un EN-CO si la stratégie mixte de chaque joueur ne place de masse que sur des actions qui gagnent selon la dpSCF appliquée aux votes générés par les stratégies des autres joueurs.

2. Existence et régularisation

• Existence : Les auteurs prouvent l'existence d'un EN-CO mixte sous des conditions légères. Ils montrent que si la dpSCF est semi-continue supérieurement (s.c.s.), un point fixe existe via le théorème du point fixe de Kakutani. Ils identifient que de nombreuses règles de vote standard (par exemple, Borda, Loteries Maximales, règles de notation) satisfont cette condition lorsqu'elles sont considérées comme renvoyant des distributions plutôt que des gagnants uniques.
• Régularisation : Pour assurer la continuité et l'unicité (facilitant l'apprentissage), les auteurs introduisent une Meilleure réponse régularisée. Cela implique :
  1. Perturbation : Remplacer aléatoirement une fraction $p$ de la population de votes par des bulletins « usurpateurs » (où une action échantillonnée est classée première).
  2. Lissage : Appliquer une perturbation de Dirichlet à la distribution de stratégie des co-joueurs $x_{-i}$ pour gérer les discontinuités aux égalités.
     Cette régularisation garantit que l'opérateur de meilleure réponse est continu et à valeur unique, permettant l'utilisation de l'apprentissage basé sur le gradient.

3. Apprentissage et métriques d'approximation

Puisque les utilités sont absentes, les métriques traditionnelles d'exploitabilité ne peuvent pas être utilisées directement. L'article introduit :

• Distance de l'espace des stratégies : Mesurer la distance (par exemple, la distance de Wasserstein ou « Earth Mover's Distance ») entre la stratégie actuelle d'un joueur et l'ensemble des meilleures réponses.
• Taux de victoire rétrospectif : Une analyse de méta-jeu comparant la stratégie en ligne à une stratégie fixe rétrospective agrégée via la règle de vote.
• Bornes de distorsion : L'article dérive des bornes sur la sous-optimalité de l'EN-CO par rapport à un EN classique (si les utilités existaient). Il montre que la distorsion additive est bornée par la distorsion de la règle de vote elle-même, mise à l'échelle par la variation des sommes de gains à travers les différentes actions des co-joueurs.

Contributions clés

1. Généralisation de l'équilibre de Nash : L'article fournit la première définition d'un équilibre de Nash en stratégies mixtes probabilistes qui opère uniquement sur des préférences ordinales, généralisant l'EN classique.
2. Existence théorique : Il établit l'existence de tels équilibres sous des conditions standard sur les fonctions de choix social, faisant le pont entre la théorie des jeux et la théorie du choix social.
3. Cadre algorithmique : Il développe des règles d'apprentissage (spécifiquement « Follow the Regularized Leader », FTRL) et des techniques de régularisation pour calculer ces équilibres, répondant aux défis computationnels posés par les règles de vote discontinues.
4. Analyse de complexité : Les auteurs démontrent que le calcul d'un EN-CO n'est généralement pas soluble en temps polynomial (NP-dur dans certains contextes), ce qui contraste avec des travaux antérieurs cherchant des équilibres en P en sacrifiant la structure factorisée traditionnelle.
5. Analyse de distorsion : Il quantifie le coût de l'utilisation d'informations ordinales plutôt que d'utilités cardinales, fournissant des bornes théoriques sur la perte d'optimalité.

Résultats et applications

Les auteurs valident leur théorie à travers deux applications distinctes :

1. Évaluation générale d'agents (Atari) :

   • Configuration : Évaluation d'agents IA face à un ensemble de tâches utilisant une matrice de performance où les agents et les tâches sont des joueurs.
   • Méthode : Les agents et les tâches sont traités comme des joueurs dans un JCO. Les « gains » sont remplacés par des classements ordinaux (par exemple, des notes basées sur des quartiles).
   • Résultat : En utilisant FTRL avec des Fonctions de Notation Sociale (SGF) et des comptes Borda, les auteurs calculent un EN-CO. Les résultats montrent que l'agent « Rainbow » émerge comme le plus fort même sous des distributions de tâches adverses, démontrant une robustesse. Les courbes d'apprentissage indiquent une convergence et une faible exploitabilité.

2. Données électorales humaines (Perdu en mer) :

   • Configuration : Analyse de données humaines issues d'une tâche de sélection de leader « Perdu en mer » impliquant 460 participants répartis en 115 groupes. Les participants soumettent un score de volonté de diriger et un classement de leurs coéquipiers.
   • Méthode : Le mécanisme électoral est modélisé comme un JCO stochastique. Les auteurs analysent si le comportement humain constitue un EN-CO.
   • Résultat : Environ 30 % des élections ont présenté des profils d'équilibre de Nash de loteries maximales pures. Dans les 70 % restants, les humains ont montré des incitations à dévier (par exemple, réduire stratégiquement les scores de volonté de diriger pour manipuler le scrutin). Les auteurs ont calculé avec succès un Équilibre Logit Limité (LLE) pour des élections spécifiques, révélant des comportements stratégiques (par exemple, un joueur se retirant d'une course pour orienter le résultat vers un candidat préféré) qui s'alignent avec la théorie de l'EN-CO.

Importance et affirmations

L'article affirme fournir une généralisation de l'équilibre de Nash directement applicable aux préférences élucidées, qui constituent les données fondamentales des interactions humaines. En remplaçant la maximisation de l'utilité espérée par une agrégation de choix social, le cadre permet une analyse d'équilibre dans des contextes où les utilités numériques sont inconnues ou inexistantes.

Les auteurs soulignent que leur approche :

• Ne nécessite pas la découverte d'utilités cardinales sous-jacentes.
• Maintient la structure factorisée des stratégies mixtes traditionnelles (contrairement aux équilibres médiatisés).
• Est robuste à la mauvaise spécification des utilités, tant que le classement ordinal reste cohérent.
• Offre une boîte à outils théorique et pratique pour analyser le comportement stratégique dans les élections et évaluer les agents IA sans recourir à un score numérique arbitraire.

Ce travail se positionne comme une approche de « mathématiques sans nombres » pour la théorie des jeux, s'appuyant sur des siècles de théorie du choix social pour résoudre le problème de l'équilibre dans les contextes ordinaux.