Pour les jeux à somme nulle finis à deux joueurs, les différents concepts de solution de la théorie des jeux que sont l’équilibre de Nash, le minimax et le maximin donnent tous la même solution. Si les joueurs sont autorisés à jouer une stratégie mixte, le jeu a toujours un équilibre.
ExempleEdit
|
Bleu
Rouge
|
A | B | C |
|---|---|---|---|
| 1 |
-30
30
|
10
-10
|
-20
20
|
| 2 |
10
-10
|
-20
20
|
20
-20
|
La matrice des gains d’un jeu est une représentation pratique. Considérons par exemple le jeu à somme nulle à deux joueurs illustré à droite ou ci-dessus.
L’ordre du jeu se déroule comme suit : Le premier joueur (rouge) choisit en secret l’une des deux actions 1 ou 2 ; le second joueur (bleu), ignorant le choix du premier joueur, choisit en secret l’une des trois actions A, B ou C. Ensuite, les choix sont révélés et le total de points de chaque joueur est affecté en fonction du gain pour ces choix.
Exemple : Rouge choisit l’action 2 et Bleu choisit l’action B. Lorsque le payoff est attribué, Rouge gagne 20 points et Bleu perd 20 points.
Dans cet exemple de jeu, les deux joueurs connaissent la matrice des payoffs et tentent de maximiser le nombre de leurs points. Rouge pourrait raisonner comme suit : « Avec l’action 2, je peux perdre jusqu’à 20 points et ne peux en gagner que 20, et avec l’action 1, je ne peux perdre que 10 mais je peux en gagner jusqu’à 30, donc l’action 1 semble bien meilleure. » Avec un raisonnement similaire, Bleu choisirait l’action C. Si les deux joueurs font ces actions, Rouge gagnera 20 points. Si Bleu anticipe le raisonnement de Rouge et son choix de l’action 1, Bleu peut choisir l’action B, afin de gagner 10 points. Si Rouge, à son tour, anticipe ce tour et opte pour l’action 2, cela fait gagner 20 points à Rouge.
Émile Borel et John von Neumann ont eu l’intuition fondamentale que les probabilités permettent de sortir de cette énigme. Au lieu de décider d’une action précise à entreprendre, les deux joueurs attribuent des probabilités à leurs actions respectives, puis utilisent un dispositif aléatoire qui, en fonction de ces probabilités, choisit une action pour eux. Chaque joueur calcule les probabilités de manière à minimiser la perte de points maximale attendue, indépendamment de la stratégie de l’adversaire. Cela conduit à un problème de programmation linéaire avec les stratégies optimales pour chaque joueur. Cette méthode minimax peut calculer des stratégies probablement optimales pour tous les jeux à somme nulle à deux joueurs.
Pour l’exemple donné ci-dessus, il s’avère que Rouge doit choisir l’action 1 avec une probabilité de 4/7 et l’action 2 avec une probabilité de 3/7, et que Bleu doit attribuer les probabilités 0, 4/7 et 3/7 aux trois actions A, B et C. Rouge gagnera alors 20/7 points en moyenne par partie.
RésolutionEdit
L’équilibre de Nash pour un jeu à somme nulle à deux joueurs peut être trouvé en résolvant un problème de programmation linéaire. Supposons qu’un jeu à somme nulle ait une matrice de gain M où l’élément Mi,j est le gain obtenu lorsque le joueur minimisant choisit la stratégie pure i et le joueur maximisant choisit la stratégie pure j (c’est-à-dire que le joueur essayant de minimiser le gain choisit la ligne et le joueur essayant de maximiser le gain choisit la colonne). Supposons que chaque élément de M est positif. Le jeu aura au moins un équilibre de Nash. L’équilibre de Nash peut être trouvé (Raghavan 1994, p. 740) en résolvant le programme linéaire suivant pour trouver un vecteur u:
Minimiser : ∑ i u i {\displaystyle \sum _{i}u_{i}} Sous réserve des contraintes : u ≥ 0 M u ≥ 1.
La première contrainte dit que chaque élément du vecteur u doit être non négatif, et la deuxième contrainte dit que chaque élément du vecteur M u doit être au moins égal à 1. Pour le vecteur u résultant, l’inverse de la somme de ses éléments est la valeur du jeu. En multipliant u par cette valeur, on obtient un vecteur de probabilité, donnant la probabilité que le joueur maximisateur choisisse chacune des stratégies pures possibles.
Si la matrice du jeu n’a pas tous les éléments positifs, il suffit d’ajouter une constante à chaque élément qui est assez grand pour les rendre tous positifs. Cela augmentera la valeur du jeu par cette constante, et n’aura aucun effet sur les stratégies mixtes d’équilibre pour l’équilibre.
La stratégie mixte d’équilibre pour le joueur minimisant peut être trouvée en résolvant le dual du programme linéaire donné. Ou bien, on peut la trouver en utilisant la procédure ci-dessus pour résoudre une matrice de gains modifiée qui est la transposée et la négation de M (en ajoutant une constante pour qu’elle soit positive), puis en résolvant le jeu résultant.
Si toutes les solutions du programme linéaire sont trouvées, elles constitueront tous les équilibres de Nash pour le jeu. Inversement, tout programme linéaire peut être converti en un jeu à deux joueurs et à somme nulle en utilisant un changement de variables qui le met sous la forme des équations ci-dessus. Donc de tels jeux sont équivalents à des programmes linéaires, en général.
Solution universelleEdit
Si éviter un jeu à somme nulle est un choix d’action avec une certaine probabilité pour les joueurs, éviter est toujours une stratégie d’équilibre pour au moins un joueur à un jeu à somme nulle. Pour tout jeu à somme nulle à deux joueurs où un tirage zéro est impossible ou non crédible après le début du jeu, comme au poker, il n’y a pas d’autre stratégie d’équilibre de Nash que d’éviter le jeu. Même s’il existe un tirage zéro-zéro crédible après le début d’un jeu à somme nulle, il n’est pas meilleur que la stratégie d’évitement. Dans ce sens, il est intéressant de trouver que la récompense dans le calcul du choix optimal prévaut sur tous les jeux à somme nulle à deux joueurs en ce qui concerne le fait de commencer le jeu ou non.
L’exemple le plus commun ou le plus simple du sous-domaine de la psychologie sociale est le concept de « pièges sociaux ». Dans certains cas, la poursuite d’un intérêt personnel individuel peut améliorer le bien-être collectif du groupe, mais dans d’autres situations, toutes les parties poursuivant un intérêt personnel aboutissent à un comportement mutuellement destructeur.
ComplexitéEdit
Il a été théorisé par Robert Wright dans son livre Nonzero : The Logic of Human Destiny, que la société devient de plus en plus à somme nulle à mesure qu’elle devient plus complexe, spécialisée et interdépendante.