Théorème du minimax de von Neumann - Définition

Introduction

John von Neumann

Vers où faut-il tirer ?

Le théorème du minimax de John von Neumann (parfois appelé théorème fondamental de la théorie des jeux à deux joueurs), démontré en 1928, est un résultat important en théorie des jeux. Il assure que, pour un jeu non-coopératif synchrone à information complète opposant deux joueurs, à nombre fini de stratégies pures et à somme nulle, il existe au moins une situation d'interaction stable, à savoir 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 du théorème fondamental de la théorie des jeux à n joueurs de John Forbes Nash, démontré en 1950.

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 fortement. 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 à 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 la programmation linéaire qui va émerger dans les années 1940.

Énoncé du théorème

Théorème de von Neumann (1926) : Pour m entier strictement positif, notons Δ_m l'ensemble des vecteurs colonnes comportant m coefficients réels positifs ou nuls dont la somme vaut 1.

Soit A une matrice réelle (n,k). On a l'identité :

.

(La notation Y^T désignant le vecteur ligne transposé de Y).