Mini-projet : Pizza-Bot, déploiement et données

Un jeu sous forme normale se décrit par trois choses : les joueurs, leurs stratégies, et les gains de chacun pour chaque combinaison de stratégies. À deux joueurs et deux stratégies, c'est un tableau : chaque case contient le couple (gain du joueur des lignes ; gain du joueur des colonnes).

Un équilibre de Nash est une case où aucun joueur n'a intérêt à changer seul de stratégie, celle de l'autre restant fixée. En notant $u_{PB}$ et $u_{MA}$ les gains de Pizza-Bot et de Mamma-Auto, la case $(s_{PB}^*, s_{MA}^*)$ est un équilibre si, pour toute stratégie $s_{PB}$ de Pizza-Bot et toute stratégie $s_{MA}$ de Mamma-Auto :

La première inégalité fixe la colonne et fait varier la ligne ; la seconde fixe la ligne et fait varier la colonne. Seul : on ne compare jamais deux cases où les deux joueurs auraient changé ensemble. Les inégalités sont larges : un joueur peut être indifférent, il suffit qu'il ne gagne rien à changer.

La méthode des soulignements applique la définition mot pour mot : colonne par colonne, souligner le meilleur gain du joueur des lignes ; ligne par ligne, celui du joueur des colonnes. Les cases soulignées deux fois sont les équilibres.

Exemple résolu, sur un autre jeu, entre deux joueurs A et B :

• Dans la colonne Campus, le meilleur gain de A est 5, sur la ligne Gare ; dans la colonne Gare, c'est 1, encore sur la ligne Gare.
• Sur la ligne Campus, le meilleur gain de B est 5, dans la colonne Gare ; sur la ligne Gare, c'est 1, encore dans la colonne Gare.
• Seule la case (Gare, Gare) est soulignée deux fois : c'est l'unique équilibre, alors que (Campus, Campus) rapporterait 3 à chacun.

Une stratégie est dominante pour un joueur si elle lui rapporte strictement plus que toute autre, quoi que fasse l'adversaire.

Les flèches de déviation dessinent le test case par case : de chaque case part une flèche vers la case voisine chaque fois qu'un joueur gagne strictement à y aller seul, verticale pour le joueur des lignes, horizontale pour celui des colonnes. Un équilibre est une case d'où ne part aucune flèche : un puits. Quand aucune comparaison ne tombe sur une égalité, un jeu 2 × 2 appartient à l'une de quatre familles :

• un seul équilibre : toutes les flèches mènent à un même coin. C'est un dilemme du prisonnier si les deux joueurs ont une stratégie dominante et que le coin opposé est meilleur pour tous les deux ;
• coordination : deux puits, sur les cases où les deux joueurs font le même choix ;
• anti-coordination : deux puits, sur les cases où ils font des choix différents ;
• pile ou face : aucun puits, les flèches tournent en cycle.

Quand un jeu a plusieurs équilibres, la définition ne dit pas lequel sera joué. Quatre critères aident à trancher : l'efficacité (un équilibre meilleur pour les deux, au sens de Pareto), la prudence (celui où l'on risque le moins si l'autre se trompe), le point focal (celui qui saute aux yeux), et l'ordre de jeu (celui qui s'engage le premier impose l'équilibre qui l'avantage).

Exemple résolu, sur le jeu précédent : la Gare rapporte plus à A quoi que fasse B (5 contre 3, puis 1 contre 0), et de même à B ; c'est une stratégie dominante pour chacun. Toutes les flèches mènent à (Gare, Gare), et le coin opposé, (Campus, Campus), est meilleur pour les deux : c'est un dilemme du prisonnier.

Une enseigne ne tire pas au sort l'emplacement d'un distributeur. L'équilibre mixte se lit autrement : chacune ignore ce que fera l'autre, et raisonne sur une croyance, la probabilité qu'elle attribue à chaque choix de l'autre. Une enseigne n'hésite entre ses deux emplacements que s'ils lui rapportent autant en moyenne ; sinon, elle prendrait le meilleur à coup sûr. La croyance portée sur un joueur se lit donc sur les gains de l'autre : c'est celle qui rend l'autre indifférent.

Exemple résolu, sur pile ou face : A gagne 1 si les deux pièces tombent du même côté et perd 1 sinon ; B, l'inverse. Si A croit que B joue Pile avec la probabilité $p$, Pile rapporte à A en moyenne $p - (1 - p) = 2p - 1$, et Face $1 - 2p$. A n'est indifférent que si $2p - 1 = 1 - 2p$, soit $p = 1/2$.

Quand un joueur voit le choix de l'autre avant de décider, le jeu est séquentiel et se représente par un arbre : chaque nœud porte le joueur qui décide, chaque branche une action, chaque feuille le couple de gains. On le résout par induction à rebours, en trois gestes :

1. Se placer au dernier nœud de décision. Le joueur qui y décide garde la branche qui maximise son propre gain.
2. Remplacer ce nœud par le couple de gains de la branche retenue.
3. Recommencer un cran plus haut, jusqu'à la racine.

Le premier joueur ne compare donc pas les feuilles : il compare ce qui remonte de chaque branche, une fois que l'autre y a répondu au mieux.

Exemple résolu, sur le jeu de l'exemple de la partie 1, B jouant le premier comme Mamma-Auto, et les gains restant dans l'ordre (A ; B). Si B prend le Campus, A répond Gare (5 contre 3), et B finit avec 0 ; s'il prend la Gare, A répond Gare (1 contre 0), et B finit avec 1. B prend donc la Gare, et la partie s'achève en (Gare, Gare), à (1 ; 1). Les gains de B sur la ligne Campus, 3 et 5, ne comptent pas : A n'y resterait pas.

Un jeu est à information incomplète quand un joueur ignore une caractéristique de l'adversaire lui-même : son coût, son positionnement, sa politique. On suppose alors que l'adversaire est d'un type $t$ parmi plusieurs, et l'on attribue une probabilité $P(t)$ à chacun : c'est la croyance. Le gain espéré d'une décision $g$ est la moyenne des gains contre chaque type, pondérée par la croyance :

L'adversaire inconnu est remplacé par une loterie entre plusieurs adversaires connus, et l'on choisit la décision d'espérance la plus grande.

Exemple résolu. Contre un adversaire de type A, une décision rapporte 0 ; contre un type B, 10. Une autre rapporte 4 dans les deux cas. Avec $P(B) = 0{,}5$, la première vaut en moyenne $0{,}5 \times 0 + 0{,}5 \times 10 = 5$, la seconde 4 : on prend la première.

Si l'on pouvait connaître le type de l'adversaire avant de décider, on prendrait contre chaque type la meilleure décision. L'espérance de ce choix informé, moins celle de la meilleure décision prise sans savoir, est la valeur de l'information parfaite : le prix maximal qu'il vaut la peine de payer pour connaître le type.

Exemple résolu, sur l'exemple du rappel, avec $P(B) = 0{,}5$ : informé, on prend 4 contre A et 10 contre B, soit $0{,}5 \times 4 + 0{,}5 \times 10 = 7$ en moyenne ; sans information, la meilleure décision rapporte 5. L'information vaut $7 - 5 = 2$.

Une file d'attente se décrit d'abord par deux rythmes. Le rythme d'arrivée $\lambda$ (lambda) est le nombre moyen de clients qui se présentent par unité de temps. Le rythme de service $\mu$ (mu) est le nombre moyen de clients qu'un serveur peut traiter par unité de temps ; la durée moyenne d'un service vaut $1/\mu$. Les deux se comptent dans la même unité, et une durée se convertit en rythme avant tout calcul : un service de 4 minutes, c'est $\mu = 15$ par heure, et non 4.

Le taux d'occupation est leur rapport :

C'est la fraction du temps où le serveur travaille. La file n'est stable que si $\rho < 1$ : à $\rho = 1$ déjà, elle grossit sans fin, parce que le moindre à-coup des arrivées ne se rattrape jamais.

Exemple résolu. Un guichet reçoit 12 appels par heure, de 4 minutes chacun. Son rythme de service est $\mu = 60 / 4 = 15$ appels par heure, et $\rho = 12 / 15 = 0{,}8$ : 48 minutes de travail par heure, soit 80 % du temps.

La loi de Little relie le nombre moyen de clients présents $L$, le rythme d'arrivée et le séjour moyen $W$ d'un client :

Elle ne suppose qu'un système stable, observé assez longtemps.

Quand les clients arrivent au hasard, indépendamment les uns des autres, et que la durée du service est elle aussi très variable (le modèle sans mémoire à un serveur, qu'on écrit M/M/1), deux formules donnent le reste :

$L$ compte les clients présents, celui qu'on sert compris ; $W$ est le temps passé en tout, attente et service. L'attente en file, avant d'être servi, vaut $W_q = W - 1/\mu$. Le dénominateur est ce qui compte : quand la charge approche la capacité, il tend vers zéro, et l'attente explose.

Exemple résolu, sur le guichet : $L = 0{,}8 / 0{,}2 = 4$ appels présents en moyenne ; $W = 1 / (15 - 12) = 1/3$ d'heure, soit 20 minutes, dont $20 - 4 = 16$ minutes d'attente en file. La loi de Little le confirme : $12 \times 1/3 = 4$.

Le modèle sans mémoire suppose des services de durée très variable. Quand ce n'est pas le cas, la formule approchée de Kingman donne l'attente en file d'un serveur :

où $c_a$ et $c_s$ sont les coefficients de variation, écart-type divisé par moyenne, des intervalles entre arrivées et des durées de service. Des arrivées au hasard ont $c_a = 1$ ; un service sans mémoire a $c_s = 1$, et l'on retrouve alors le modèle M/M/1 ; un service parfaitement régulier a $c_s = 0$, ce qui divise l'attente en file par deux.

Avec deux serveurs derrière une file commune, le taux d'occupation de chacun devient $\rho = \lambda / (2\mu)$. Dans le modèle sans mémoire, la probabilité qu'un client trouve les deux occupés, et doive attendre, vaut $2\rho^2 / (1 + \rho)$ ; l'attente en file moyenne s'en déduit en divisant cette probabilité par la marge de capacité : $W_q = P_{\text{attendre}} / (2\mu - \lambda)$.

Exemple résolu, sur le guichet. Si chaque appel durait exactement 4 minutes, $c_s = 0$, et l'attente en file tomberait à $4 \times \frac{1 + 0}{2} \times 4 = 8$ minutes, au lieu de 16. Avec deux guichets à 15 appels par heure chacun, pour 24 appels par heure, $\rho = 24 / 30 = 0{,}8$, la probabilité d'attendre vaut $2 \times 0{,}64 / 1{,}8 \approx 0{,}71$, et $W_q \approx 0{,}71 / (30 - 24)$ heure, soit environ 7 minutes.

Chaque jour est un couple $(x_i, y_i)$ : c'est une série double. On note $N$ le nombre de couples, $\bar{x}$ et $\bar{y}$ les moyennes, $G(\bar{x}, \bar{y})$ le point moyen. On divise par $N$, puisqu'on décrit les journées observées :

avec $\sigma(X) = \sqrt{V(X)}$. La seconde écriture de chaque ligne, « la moyenne des carrés moins le carré de la moyenne », évite de calculer chaque écart à la main.

La covariance est positive si les deux grandeurs montent ensemble, négative si l'une descend quand l'autre monte ; elle porte le produit des deux unités et ne se lit pas seule. $r$, sans unité, est compris entre $-1$ et $1$ et dit à quel point les points sont alignés. Son carré $r^2$ est la part de la variance de $Y$ expliquée par la relation linéaire.

Exemple résolu, sur quatre points : $x$ = 1, 2, 3, 4 et $y$ = 1, 3, 2, 4. On a $\sum x_i = 10$, $\sum x_i^2 = 30$, $\sum x_i y_i = 1 + 6 + 6 + 16 = 29$, donc $\bar{x} = 2{,}5$, $V(X) = 30/4 - 2{,}5^2 = 1{,}25$ et $\operatorname{cov}(X, Y) = 29/4 - 2{,}5 \times 2{,}5 = 1$. Les $y$ ont la même moyenne et la même variance que les $x$, d'où $r = 1 / (\sqrt{1{,}25} \times \sqrt{1{,}25}) = 0{,}8$.

La droite $y = ax + b$ qui rend la plus petite possible la somme des carrés des écarts verticaux entre les points et la droite a pour coefficients

La seconde formule dit que la droite passe par le point moyen ; $a$ et $r$ ont le même signe, puisqu'ils partagent le numérateur $\operatorname{cov}(X, Y)$. La pente se lit en unités de $y$ par unité de $x$.

Une droite ne vaut que sur la plage observée. Prédire à l'intérieur de cette plage est une interpolation ; au-dehors, une extrapolation, et rien ne garantit que la relation s'y prolonge.

Exemple résolu, sur les quatre points : $a = 1 / 1{,}25 = 0{,}8$ et $b = 2{,}5 - 0{,}8 \times 2{,}5 = 0{,}5$. En $x = 3{,}5$, la droite prévoit $3{,}3$ : une interpolation, puisque les $x$ observés vont de 1 à 4. En $x = 10$, elle prévoit $8{,}5$ : une extrapolation, que rien ne garantit.

Une corrélation mesure une association, pas une cause. Trois situations la produisent : $x$ agit sur $y$ ; $y$ agit sur $x$ ; ou une troisième variable, un facteur de confusion, agit sur les deux. Une corrélation suffit à prévoir ; seule une cause permet d'agir.

Exemple résolu. La consommation de gaz d'une chaufferie et les ventes de boissons chaudes de la cafétéria voisine sont fortement corrélées. Aucune ne cause l'autre : le froid agit sur les deux. Les ventes de boissons prévoient très bien la facture de gaz, mais fermer la cafétéria ne la ferait pas baisser.

Une grandeur qui résulte de la somme de nombreux petits effets indépendants (humidité du fromage, température, vibrations de la machine) suit approximativement une loi normale $N(\mu, \sigma^2)$ : la courbe en cloche, symétrique autour de sa moyenne $\mu$, d'autant plus étalée que son écart-type $\sigma$ est grand. Pour elle, et pour elle seule :

• environ 68 % des valeurs tombent dans $[\mu - \sigma ; \mu + \sigma]$ ;
• 95,45 % dans $[\mu - 2\sigma ; \mu + 2\sigma]$, si bien que 4,55 % en sortent ;
• 99,73 % dans $[\mu - 3\sigma ; \mu + 3\sigma]$, si bien que 0,27 % en sortent.

Le z-score d'une valeur $x$ dit de combien d'écarts-types elle s'éloigne de la moyenne :

Une valeur sort de $[\mu - 2\sigma ; \mu + 2\sigma]$ exactement quand $|z| > 2$.

Exemple résolu, sur une buse de moyenne 100 g et d'écart-type 2 g. Une pesée de 103 g a pour z-score $(103 - 100) / 2 = 1{,}5$ : elle est dans la dispersion ordinaire de la buse, même si elle dépasse la dose de 3 %. Une pesée de 105 g a pour z-score 2,5 : elle sort de l'intervalle à deux écarts-types.

Les 50 pesées ne sont pas la série qu'on décrit, comme les seize journées de ventes : ce sont un échantillon dont on se sert pour estimer le comportement de la buse, et juger des pesées qu'on n'a pas encore vues. On estime alors l'écart-type en divisant par $N - 1$ :

Les écarts sont mesurés à une moyenne calculée sur ces mêmes valeurs, qui colle un peu trop à l'échantillon : diviser par $N$ sous-estimerait la dispersion réelle. Sur de grands échantillons, la différence s'efface.

Exemple résolu, sur 2, 4 et 6 : la moyenne vaut 4, les écarts $-2$, 0 et 2, la somme de leurs carrés 8. En divisant par $N - 1 = 2$, $\sigma = \sqrt{4} = 2$ ; en divisant par $N = 3$, on trouverait $\sqrt{8/3} \approx 1{,}63$.

Un seuil se règle en fausses alertes par jour, pas en sigmas : la part des pesées saines qui sortent de l'intervalle, multipliée par le nombre de pesées d'une journée. Pour en réduire le nombre sans monter le seuil, le levier le plus employé est la persistance : n'agir qu'après plusieurs anomalies consécutives. Un pic isolé disparaît, une dérive qui dure passe. Son prix est double : l'arrêt vient plus tard, et un incident plus bref que la persistance n'est plus signalé du tout.

Exemple résolu, sur une machine qui fait 1 000 pesées par jour. À deux écarts-types, une buse saine déclenche $1\,000 \times 0{,}0455 \approx 45$ fausses alertes par jour. Trois dépassements de suite sont bien plus rares, de l'ordre de $1\,000 \times 0{,}0455^3 \approx 0{,}09$ par jour, une fois tous les dix jours environ : une persistance de trois fait taire presque toutes les fausses alertes, mais aussi tout défaut qui ne toucherait qu'une seule dose.