vignette|John von Neumann.
Le théorème du minimax de von Neumann (parfois appelé théorème fondamental de la théorie des jeux à deux joueurs et à somme nulle) est un résultat important de la théorie des jeux dont la démonstration a été publiée en 1928 par John von Neumann. Il assure que, pour un jeu non-coopératif synchrone à information complèteCes termes sont définis dans la suite de l'article. opposant deux joueurs, à nombre fini de stratégies pures et à somme nulle, il existe au moins une situation d'interaction stable : une situation dans laquelle aucun des deux joueurs n'a intérêt à changer sa stratégie mixte si l'autre ne la change pas. Ce théorème est un cas particulier de l'équilibre de Nash, théorème démontré en 1950 par John Forbes Nash.
Le théorème du minimax fournit une méthode rationnelle de prise de décision dans un contexte bien précis : celui où s'affrontent deux adversaires (des entreprises concurrentes ou des États en guerre par exemple) lorsqu'on suppose qu'ils doivent prendre leurs décisions simultanément et que tout gain de l'un est perte de l'autre. Cette seconde hypothèse, rarement remplie dans la réalité, limite cependant beaucoup son intérêt pratique.
Un exemple de situation qu'il modélise bien est, au football, le duel entre un tireur de penalty et le gardien de but adverse. Le premier doit choisir où diriger son tir, le second quel secteur de sa cage protéger. En fonction du couple de décisions prises, les chances du tireur de marquer varient fortementLes données empiriques figurent au tableau 4, dans . La pratique des joueurs est bien sûr de faire leurs choix de façon aléatoire et imprévisible. La théorie du minimax justifie cette méthode et détermine les probabilités qu'il est bon de donner à chacune des stratégies possibles ; les mesures effectuées sur les matchs de Bundesliga la valident : les probabilités constatées sont proches de celles que le théorème de von Neumann recommande.
Historiquement, le mathématicien Émile Borel a formalisé l'énoncé du théorème et est l'auteur de démonstrations parcellaires. La première preuve complète, un peu plus tardive, est l'œuvre de von Neumann.
La pertinence du modèle de von Neumann a été mise en cause. Outre l'inadéquation à la réalité de l'hypothèse de « somme nulle », des critiques ont été articulées contre la théorie sous-jacente de l'utilité bâtie par von Neumann et l'économiste Oskar Morgenstern pour donner un sens à la mesure du gain en situation d'incertitude ; le paradoxe d'Allais en est une des plus célèbres.
Si on fait abstraction de son utilisation en théorie de la décision, le théorème de von Neumann n'en demeure pas moins un résultat remarquable de mathématiques pures. En analyse fonctionnelle, c'est le premier d'une longue chaîne de théorèmes du minimax; sa deuxième démonstration de 1937 par von Neumann, qui utilise un théorème de point fixe, a sans doute guidé les travaux ultérieurs de John Forbes Nash sur les jeux à plus de deux joueurs et somme non nulle ; sa démonstration de 1938 par Jean Ville, qui met en relief la relation avec la convexité et la théorie des inégalités, ouvre un pont vers la théorie de l'optimisation linéaire qui va émerger dans les années 1940.
Énoncé du théorème
Théorème de von Neumann (1926) : Pour entier strictement positif, notons l'ensemble des vecteurs colonnes comportant coefficients réels positifs ou nuls dont la somme vaut .
Soit une matrice réelle . On a l'identité :
.
(La notation désignant le vecteur ligne transposé de ).
Le modèle économique sous-jacent
thumb|Pierre thumb|Feuille thumb|Ciseaux
On suppose que deux protagonistes, Xavier et Yvette, s'affrontent dans un contexte qui peut être un « jeu », au sens commun du terme (ainsi le pierre-feuille-ciseaux), mais aussi une compétition militaire ou économique. On en trouvera deux exemples (des plus primaires) à l'article Jeu à somme nulle.
Chacun dispose d'un nombre fini de coups possibles, appelés des « stratégies pures ». On note « k » le nombre de stratégies pures disponibles pour Xavier et « n » le nombre de stratégies pures disponibles pour Yvette. On numérote de à les stratégies à la disposition de Xavier et de à celles d'Yvette. Dans l'exemple du jeu de pierre-feuille-ciseaux, le formalisme sera le même pour Xavier et pour Yvette : , « 1 » codant « jouer pierre », « 2 » codant « jouer feuille » et « 3 » codant « jouer ciseaux » (on prendra garde que cet exemple peut être trompeur : on ne suppose pas le jeu symétrique et les deux joueurs n'ont pas nécessairement les mêmes stratégies pures à leur disposition, ni même le même nombre de stratégies pures.)
On suppose que les deux joueurs connaissent sans ambiguïté la règle du jeu, en particulier les gains ou pertes qui seront applicables pour chaque couple de choix de stratégies (le jeu est dit « à information complète »), et qu'à chaque coup ils jouent simultanément (le jeu est dit « synchrone » — on peut aussi utiliser l'expression « jeu à information complète imparfaite » pour exprimer ce synchronisme). Il leur est interdit de se concerter préalablementCette définition d'un jeu « non coopératif » est exagérément simplificatrice ; Robert Aumann (parlant du dilemme du prisonnier mais cela s'adapte aussi ici) souligne que ce qui est important, ce n'est pas tant d'interdire aux joueurs de se concerter que de supposer qu'aucun mécanisme n'est prévu pour sanctionner qui trahirait ses engagements. (« Game theory », dans Collected papers, MIT Press, 2000 , ) : le jeu est dit « non coopératif ».
Pour chaque choix d'une stratégie pure numérotée « » par Xavier et d'une stratégie pure numérotée « » par Yvette, les règles du jeu (bien connues des deux participants) définissent un gain remporté par Xavier, qui est un nombre réel. Une valeur positive signifie que Xavier est bénéficiaire de ce nombre réel, un gain négatif qu'il en est perdant. Ces gains peuvent être regroupés en un tableau carré, appelé matrice (les lignes correspondant aux stratégies d'Yvette et les colonnes à celles de Xavier). Dans l'exemple de « pierre-feuille-ciseaux » avec ses règles les plus usuelles, la matrice représentant les gains de Xavier serait ainsi :
Xavier joue « pierre » Xavier joue « feuille » Xavier joue « ciseaux » Yvette joue « pierre » 0 1 -1 Yvette joue « feuille » -1 0 1 Yvette joue « ciseaux » 1 -1 0
On pourrait définir de même le gain « » pour Yvette et la matrice représentant ces gains, mais ce ne sera pas nécessaire car on fait une dernière hypothèse : celle que le jeu est « à somme nulle », ce qui signifie que la société formée des deux joueurs ne gagne ni ne perd rien au jeu dans sa globalité, que tout ce que perd Xavier, Yvette le gagne et réciproquement. La matrice des gains d'Yvette est donc la matrice et il n'est pas utile de lui donner un nouveau nom.
Points-selles dans les matrices de gain thumb|Représentation graphique de la matrice .Le point-selle est en vert.
Soit l'exemple d'un jeu à trois stratégies pour chaque joueur où la matrice A des gains de Xavier est la suivante :
Xavier joue sa stratégie 1 Xavier joue sa stratégie 2 Xavier joue sa stratégie 3 Yvette joue sa stratégie 1 -1000 2 2000 Yvette joue sa stratégie 2 1010 2 -3000 Yvette joue sa stratégie 3 0 1 0
Considérant la règle du jeu, Xavier se dit : « Si je joue 1, je risque de perdre 1000 unités, et si je joue 3 d'en perdre 3000 ; mais si je joue 2, je gagne une unité dans le pire des cas. »
Yvette, pour sa part, se dit : « Si je joue 1, je risque de perdre 2000 unités, et si je joue 2 d'en perdre 1010 ; mais si je joue 3 mes pertes sont limitées à une unité dans le pire des cas.
Xavier peut poursuivre son raisonnement : « J'ai reconstitué le raisonnement d'Yvette, qui lui donne de bonnes raisons de choisir sa stratégie 3. Si elle le fait comme je m'y attends, la lecture de la ligne de la matrice me montre que la stratégie 2 est le meilleur choix pour moi. Excellente raison de m'y tenir. »
Et symétriquement, après avoir observé la colonne de la matrice, Yvette se sent confortée dans son choix pour la stratégie 3.
Finalement tout ceci mène à penser que le choix conjoint du coup pour Xavier, du pour Yvette est plus rationnel que les autres, qu'il est le bon choix en un sens qui reste à préciser. Il est à cet égard instructif de considérer deux règles de décision inappropriées qui pourraient tenter Xavier : en premier lieu, il pourrait chercher à maximiser la moyenne d'une colonne, en l'interprétant comme le gain moyen que lui rapporterait le choix de la stratégie correspondante, et il jouerait alors son coup ; en second lieu, il pourrait être attiré par le « maximax », le gain le plus élevé figurant sur le tableau (ici c'est 2000), ce qui le conduirait à jouer son coup. Dans les deux cas, il y perdrait, puisqu'Yvette — si elle joue bien — s'en tiendrait tout de même à jouer son coup numéro 3 et le seul résultat de la gourmandise de Xavier serait qu'il ne toucherait rien au lieu de gagner le modeste 1 que la meilleure stratégie lui garantit.
Comparons à la situation suivante, variante minime du jeu de « pierre-feuille-ciseaux » (on a modifié de quelques centimes les enjeux pour éviter des situations d'indifférence entre stratégies qui n'apportent rien à la compréhension) :
Xavier joue « pierre » Xavier joue « feuille » Xavier joue « ciseaux » Yvette joue « pierre » 0 1,05 -1,07 Yvette joue « feuille » -1,03 0 1,04 Yvette joue « ciseaux » 1,02 -1,01 0
Xavier et Yvette peuvent commencer à raisonner comme dans l'exemple précédent : si Xavier veut minimiser la somme qu'il devra verser à Yvette, le coup à jouer est « feuille » où il ne perdra au pire que 1,01 unité. De même Yvette va dans un premier temps être tentée par jouer « ciseaux » où dans le pire des cas sa perte se limite à 1,02 unité. Mais lorsqu'il considère qu'Yvette a des raisons sérieuses de jouer « ciseaux » Xavier, au lieu d'être conforté dans son choix initial de « feuille », s'aperçoit qu'il serait alors perdant et qu'il vaut bien mieux bifurquer sur « pierre ». Yvette, qui reconstitue mentalement les anticipations de Xavier, anticipe qu'il jouera « pierre » et déplace son projet de coup vers « feuille ». À son tour Xavier modifie ses anticipations... Rien ne se stabilise et aucun choix de stratégies pures n'arrive à s'imposer.
Où se situe la différence entre les deux exemples ? C'est que dans la première matrice, contrairement à la deuxième, figure ce qu'on peut appeler un point-selle, ou équilibre de Nash : une entrée qui est à la fois la plus petite de sa colonne et la plus grande de sa ligne.
Proposition : Les points-selles étant définis comme ci-dessus, une matrice de réels possède un point-selle si et seulement si
En tout point-selle de la matrice, l'entrée correspondante du tableau est égale à ce minimax.
Supposons l'égalité du minimax et du maximin, et montrons l'existence d'un point-selle.
Notons un indice pour lequel , et symétriquement un indice pour lequel .
Vu l'hypothèse d'égalité du maximin et du minimax, on en déduit l'égalité : .
On va vérifier que la position correspond à un point-selle. Soit une autre position dans la même colonne. On écrit : : l'entrée en cette nouvelle position est plus grande que celle en . On vérifierait de même l'autre propriété requise des points-selles.
Remarquons préalablement que l'inégalité
est vérifiée pour n'importe quelle matrice , qu'elle contienne ou non des points-selles.
Soit en effet un indice pour lequel , et symétriquement un indice pour lequel .
Comme , il en découle que le maximin est plus petit que le minimax.
Supposons qu'une position corresponde à un point-selle.
Alors par définition d'un point-selle, (c'est la plus petite entrée de sa colonne) et (c'est la plus grande entrée de sa ligne).
On en déduit que et donc -puisqu'on connaît déjà l'inégalité dans l'autre sens- l'égalité du maximin et du minimax, qui sont de surcroît tous deux égaux à l'entrée de la matrice au point-selle.