Probabilités et applications à l’algorithmique

TD numéro 13 : le principe de Yao

Natacha Portier lundi 13 mai 2002

Nous allons montrer le principe de Yao : la complexité du meilleur algorithme déterministe sur la pire distribution d’entrées est égale à la complexité du meilleur algorithme aléatoire sur la pire entrée.

On considère des jeux pour lesquels les joueurs ont une information totale : règles du jeu, probabilités de réussite pour chaque coup. On dispose d’une fonction de gain. Un joueur peut choisir ses coups selon une distribution de probabilités qu’il choisit (stratégie mixte).

On considère un jeu à deux joueurs et à somme nulle (toute négociation est alors inutile : jeu non coopératif). Un jeu fini est représenté par une matrice A. Si Marianne joue la stratégie pure i et Jacques la stratégie pure j alors le gain de Marianne est a_{i,j} et celui de Jacques est −a_{i,j} (la perte de Jacques est a_{i,j}).

Question 1,1

Si Marianne joue i quel est son gain minimum ? Quelle stratégie pure i doit-elle adopter pour maximiser ce gain minimal, appelé gain plancher et noté v′_{I} ?

Question 1,2

Si Jacques joue j quel est sa perte maximale ? Quelle stratégie pure j doit-il adopter pour minimiser cette perte maximale, appelée perte plafond et notée v′_{II} ?

Question 1,3

Donner la relation entre v′_{I} et v′_{II}. Quels sont les cas d’égalité ?

Application : pierre/ciseau/feuille

Lorsqu’il n’existe pas de point selle on considère les stratégies mixtes. Une stratégie mixte pour Marianne est une distribution de probabilité x = (x_{i}) sur les lignes et une stratégie mixte pour Jacques est une distribution de probabilité y = (y_{j}) sur les colonnes (x_{i} ≥ 0, y_{j} ≥ 0, ∑_{i} x_{i} = 1 et ∑_{j} y_{j} = 1). L’espérance du gain de Marianne est alors xAy^{t}.

Question 2

Si Marianne joue x quel est le minimum de l’espérance de son gain ? Montrer qu’il est atteint pour une stratégie pure de Jacques (c’est le lemme de Loomis). Quelle stratégie x doit-elle adopter pour maximiser cette espérance notée v_{I} ? Cet extremum est-il atteint ?

Même question pour la perte v_{II} de Jacques.

Question 3

Nous allons montrer le théorème du minimax (Von Neumann 1928) : v_{I} = v_{II}. C’est un cas particulier de l’équilibre de Nash : chaque joueur a la meilleure stratégie

si on considère celles des autres comme fixées.

Question 3,1

Montrer le théorème suivant : Soit B un convexe fermé de l’espace euclidien de dimension n et soit x = (x_{1}, ..., x_{n}) un point n’appartenant pas à B. Alors il existe des réels

p_{1}...p_{n+1} tels que ∑_{i=1}^{n} p_{i}x_{i} = p_{n+1} et pour tout y dans B ∑_{i=1}^{n} p_{i}y_{i} > p_{n+1}.

Indications : montrer qu’il existe un point z de B qui minimise la distance à x. Définir les p_{i} en fonction de ce point. Montrer qu’alors on a bien la deuxième inégalité en pensant à utiliser toutes les hypothèses.

Question 3,2

En déduire le lemme suivant : Soit A une matrice m × n. Elle vérifie alors une des propriétés suivantes :

(i) Le point 0 de l’espace de dimension m appartient à l’enveloppe convexe des m + n points : les colonnes a_{1} ... a_{n} de la matrice A et les vecteurs e_{1} = (1, 0, ..., 0), ..., e_{m} de la base canonique.

(ii) Il existe des réels x_{1}, ..., x_{m} strictement positifs et de somme 1 tels que pour

tout entier j compris entre 1 et n on ait ∑_{i=1}^{m} a_{i,j}x_{i} > 0

Question 3,3

Preuve du minimax : en utilisant le lemme précédent montrer qu’il est impossible d’avoir v_{I} ≤ 0 < v_{II}. En prenant k quelconque et en modifiant le jeu montrer qu’il est également impossible d’avoir v_{I} ≤ k < v_{II}. Conclure.

La valeur commune de v_{I} = v_{II} est appelée valeur du jeu. Une paire de stratégies optimales (x, y) est une solution du jeu.

Question 3,4

Quelle est la valeur d’un jeu symétrique, i.e. dont la matrice est antisymétrique ?

Question 4 Montrer le principe de Yao. Pour un entier n on considèrera un majorant t(n) à la fois du temps de calcul du meilleur algorithme déterministe sur la pire distribution d’entrées de taille n et du temps de calcul du meilleur algorithme aléatoire sur la pire entrée.

Remarques

Jeu coopératif : le dilemne du prisonnier, la bataille des sexes