Start writing course notes.

1 files changed, 302 insertions, 0 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
new file mode 100644
index 0000000..59fdba9
--- /dev/null
+++ b/notes-mitro206.tex
@@ -0,0 +1,302 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{matrix}
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}[subsection]
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
+\newtheorem{defn}[comcnt]{Définition}
+\newtheorem{prop}[comcnt]{Proposition}
+\newtheorem{lem}[comcnt]{Lemme}
+\newtheorem{thm}[comcnt]{Théorème}
+\newtheorem{cor}[comcnt]{Corollaire}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+\DeclareFontFamily{U}{manual}{} 
+\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+%
+%
+\begin{document}
+\title{Théorie(s) des jeux\\(notes provisoires)}
+\author{David A. Madore}
+\maketitle
+
+\centerline{\textbf{MITRO206}}
+
+
+%
+%
+%
+
+\section{Introduction et typologie}
+
+\subsection{La notion de jeu mathématique}
+
+\thingy Il n'est pas possible de donner une définition générale
+précise de la notion de « jeu mathématique ».  On verra plus loin des
+définitions précises de certains types de jeux (p. ex., les jeux
+impartiaux à information parfaite), mais il n'existe pas de définition
+générale utile qui s'applique à tous ces types, et à partir de
+laquelle on pourrait développer une théorie intéressante.
+
+Pire, différentes disciplines se sont développées sous le nom de
+« théorie des jeux », chacune donnant une définition différente de ce
+qu'est un « jeu ».  Par exemple, l'étude des jeux « en forme normale »
+(=jeux définis par des matrices de gains), la théorie combinatoire des
+jeux (jeux à information parfaite), la théorie des jeux logiques, la
+théorie des jeux différentiels, etc.  Il n'existe donc pas une mais
+plusieurs théories des jeux.
+
+Ces différentes théories des jeux intersectent différentes branches
+des mathématiques ou d'autres sciences : probabilités,
+optimisation/contrôle, combinatoire, logique, calculabilité,
+complexité, analyse/EDP ou encore (en-dehors ou en marge des
+mathématiques), économie, cryptographie, physique quantique,
+cybernétique, biologie, sociologie, linguistique, philosophie.
+
+Il va de soi qu'on ne pourra dans ce cours donner qu'un aperçu de
+quelques unes de ces théories des jeux.
+
+
+\thingy Une tentative pour approcher la notion de jeu mathématique :
+le jeu possède un \textbf{état}, qui évolue dans un ensemble (fini ou
+infini) d'états possibles ; un certain nombre de \textbf{joueurs}
+choisissent, simultanément ou consécutivement, un \textbf{coup} à
+jouer parmi différentes \textbf{options}, en fonction de l'état
+courant, ou peut-être seulement d'une fonction de l'état courant ; ce
+coup peut éventuellement faire intervenir un aléa (hasard voulu par le
+joueur) ; l'état du jeu évolue en fonction des coups des joueurs et
+éventuellement d'un autre aléa (hasard intrinsèque au jeu) ; au bout
+d'un certain nombre de coups (fini ou infini), la règle du jeu
+attribue, en fonction de l'état final, ou de son évolution complète,
+un \textbf{gain} à chaque joueur, ce gain pouvant être un réel (gain
+numérique), l'étiquette « gagné » / « perdu », ou encore autre chose,
+et chaque joueur cherche en priorité à maximiser son gain (i.e., à
+gagner le plus possible, ou à gagner tout court), ou dans le cas
+probabiliste, son espérance de gain.
+
+Mais même cette définition très vague est incomplète !, par exemple
+dans le cas des jeux différentiels, les coups n'ont pas lieu tour à
+tour mais continûment.
+
+Une \textbf{stratégie} d'un joueur est la fonction par laquelle il
+choisit son coup à jouer en fonction de l'état du jeu (ou de la
+fonction de l'état qui lui est présentée), et d'aléa éventuel.  On
+peut ainsi résumer le jeu en : chaque joueur choisit une stratégie, et
+la règle du jeu définit alors un gain pour chaque joueur.  Les
+stratégies peuvent être contraintes de différentes manières (par
+exemple : être calculables par une machine de Turing).
+
+Il faut aussi se poser la question de si les joueurs peuvent
+communiquer entre eux (et si oui, s'ils peuvent prouver leur honnêteté
+ou s'engager irrévocablement quant au coup qu'ils vont jouer, etc.).
+Dans certains cas, on peut aussi être amené à supposer que les joueurs
+ne connaissent pas toute la règle du jeu (voir « information
+  complète » ci-dessous).
+
+
+\subsection{Quelques types de jeux}
+
+\thingy Le \textbf{nombre de joueurs} est généralement $2$.  On peut
+néanmoins étudier des jeux multi-joueurs, ce qui pose des questions
+d'alliances et compliquer la question des buts (un joueur peut être
+incapable de gagner lui-même mais être en position de décider quel
+autre joueur gagnera : on parle de « kingmaker »).  On peut aussi
+étudier des jeux à un seul joueur (jouant contre le hasard), voire à
+zéro joueurs (systèmes dynamiques), mais ceux-ci relèvent plutôt
+d'autres domaines.  Dans ce cours, on s'intéressera (presque
+uniquement) aux jeux à deux joueurs.
+
+\thingy Les joueurs peuvent avoir \textbf{des intérêts communs,
+  opposés, ou toute situation intermédiaire}.
+
+Le cas d'intérêts communs est celui où tous les joueurs ont le même
+gain.  Si les joueurs peuvent parfaitement communiquer, on est alors
+essentiellement ramené à un jeu à un seul joueur : on s'intéresse donc
+ici surtout aux situations où la communication est imparfaite.
+
+Le cas de deux joueurs d'intérêts opposés est le plus courant : dans
+le cas de gains numériques, on le modélise en faisant des gains d'un
+joueur l'opposé des gains de l'autre — on parle alors de \textbf{jeu à
+  somme nulle} ; ou bien la règle fera qu'un et un seul joueur aura
+gagné et l'autre perdu (mais parfois, elle peut aussi admettre le
+match nul).
+
+Toute autre situation intermédiaire est possible.  Mais on conviendra
+bien que le but de chaque joueur est de maximiser son propre gain,
+sans considération des gains des autres joueurs.
+
+\thingy Le jeu peut être \textbf{partial/partisan ou impartial}.  Un
+jeu impartial est un jeu où tous les joueurs sont traités de façon
+équivalente par la règle (le sens de « équivalent » étant à définir
+plus précisément selon le type de jeu).
+
+\thingy\label{intro-simultaneous-or-sequential} Les coups des joueurs
+peuvent avoir lieu \textbf{simultanément ou séquentiellement}.
+
+(Formellement, il s'agit seulement d'une différence de présentation.
+On peut toujours ramener des coups séquentiels à des coups simultanés
+en n'offrant qu'une seule option à tous les joueurs sauf l'un, et
+réciproquement, on peut ramener des coups simultanés à des coups
+séquentiels en cachant à chaque joueur l'information de ce que l'autre
+a joué.)
+
+\thingy Le jeu peut être à \textbf{information parfaite} ou non.  Un
+jeu à information parfaite est un jeu dont la règle ne fait pas
+intervenir le hasard et où chaque joueur joue séquentiellement en
+ayant la connaissance complète de l'état du jeu et de tous les coups
+effectués antérieurement par tous les autres joueurs.
+
+(Cette notion est parfois distinguée de la notion plus faible
+d'\textbf{information complète}, qui souligne que les joueurs ont
+connaissance complète de la \emph{règle} du jeu, i.e., des gains
+finaux et des options disponibles à chaque joueur.  Néanmoins, on peut
+formellement ramener un jeu à information incomplète en jeu à
+information complète en regroupant toute l'inconnue sur les règles du
+jeu dans des coups d'un joueur appelé « la nature ».  Dans ce cours,
+on ne considérera que des jeux à information complète [et toute
+  occurrence des mots « information complète » sera probablement un
+  lapsus pour « information parfaite »].)
+
+\thingy Le nombre de positions, comme le nombre d'options dans une
+position donnée, ou comme le nombre de coups, peut être \textbf{fini
+  ou infini}.  Même si l'étude des jeux finis (de différentes
+manières) est la plus intéressante pour des raisons pratiques, toutes
+sortes de jeux infinis peuvent être considérés, par exemple en logique
+(voir plus loin sur l'axiome de détermination).  Pour un jeu à durée
+infinie, le gagnant pourra être déterminé, par exemple, par toute la
+suite des coups effectués par les deux joueurs ; on peut même
+introduire des coups après un nombre infini de coups, etc.
+
+De même, l'ensemble des positions, des options ou des temps peut être
+\textbf{discret ou continu}.  Dans ce cours, on s'intéressera presque
+exclusivement au cas discret (on écartera, par exemple, la théorie des
+jeux différentiels).
+
+
+\subsection{Quelques exemples en vrac}
+
+\thingy Le jeu de \textbf{pile ou face} entre Pauline et Florian.  On
+tire une pièce non-truquée : si elle tombe sur pile, Pauline gagne, si
+c'est face, c'est Florian.  Aucun des joueurs n'a de choix à faire.
+Chacun a une probabilité $\frac{1}{2}$ de gagner, ou une espérance de
+$0$ si les gains sont $+1$ au gagnant et $-1$ au perdant (il s'agit
+donc d'un jeu à somme nulle).
+
+Variante entre Alice et Bob : maintenant, Alice choisit « pile » ou
+« face » avant qu'on (Bob) tire la pièce.  Si Alice a bien prévu, elle
+gagne, sinon c'est Bob.  Ici, seule Alice a un choix à faire.
+Néanmoins, il n'y a pas de stratégie intéressante : la stratégie
+consistant à choisir « pile » offre la même espérance que celle
+consistant à choisir « face », et il n'existe pas de stratégie
+(c'est-à-dire, de stratégie mesurable par rapport à l'information dont
+dispose Alice) offrant une meilleure espérance.
+
+\thingy Variante : Alice choisit « pile » ou « face », l'écrit dans
+une enveloppe scellée sans la montrer à Bob (elle s'\emph{engage} sur
+son choix), et Bob, plutôt que tirer une pièce, choisit le côté qu'il
+montre.  Si Alice a bien deviné le choix de Bob, Alice gagne, sinon
+c'est Bob.  Variante : Bob choisit une carte dans un jeu de 52 cartes
+sans la montrer à Bob, et Alice doit deviner si la carte est noire ou
+rouge.
+
+Variante équivalente : Alice choisit « Alice » ou « Bob » et Bob
+choisit simultanément « gagne » ou « perd ».  Si la phrase obtenue en
+combinant ces deux mots est « Alice gagne » ou « Bob perd », alors
+Alice gagne, si c'est « Alice perd » ou « Bob gagne », alors Bob
+gagne.  Encore une variante : Alice et Bob choisissent simultanément
+un bit (élément de $\{0,1\}$), si le XOR de ces deux bits vaut $0$
+alors Alice gagne, s'il vaut $1$ c'est Bob.  Ce jeu est impartial
+(même s'il n'est pas parfaitement symétrique entre les joueurs) :
+Alice n'a pas d'avantage particulier sur Bob (ce qui est assez évident
+sur ces dernières variantes).
+
+La notion de coups simultanés peut se convertir en coups engagés dans
+une enveloppe scellée (cf. \ref{intro-simultaneous-or-sequential}).
+
+On verra, et il est assez facile de comprendre intuitivement, que la
+meilleure stratégie possible pour un joueur comme pour l'autre,
+consiste à choisir l'une ou l'autre des deux options offertes avec
+probabilité $\frac{1}{2}$ (ceci assure une espérance de gain nul quoi
+que fasse l'autre joueur).
+
+(En pratique, si on joue de façon répétée à ce jeu, il peut être
+intéressant d'essayer d'exploiter le fait que les humains ont des
+générateurs aléatoires assez mauvais, et d'arriver à prédire leurs
+coups pour gagner.  Ceci est particulièrement amusant avec des petits
+enfants.  Voir aussi le film \textit{Princess Bride} à ce sujet.)
+
+\thingy Le jeu de \textbf{pierre-papier-ciseaux} : Alice et Bob
+choisissent simultanément un élément de l'ensemble
+$\{\textrm{pierre},\penalty0 \textrm{papier},\penalty0
+\textrm{ciseaux}\}$.  S'ils ont choisi le même élément, le jeu est
+nul ; sinon, papier gagne sur pierre, ciseaux gagne sur papier et
+pierre gagne sur ciseaux (l'intérêt étant qu'il s'agit d'un « ordre »
+cyclique, totalement symétrique entre les options).  Il s'agit
+toujours d'un jeu à somme nulle (disons que gagner vaut $+1$ et perdre
+vaut $-1$), et cette fois les deux joueurs sont en position
+complètement symétrique.  On verra que la meilleure stratégie possible
+consiste à choisir chacune des options avec probabilité $\frac{1}{3}$
+(ceci assure une espérance de gain nul quoi que fasse l'autre joueur).
+
+Ce jeu s'appelle aussi papier-ciseaux-puits, qui est exactement le
+même si ce n'est que « pierre » s'appelle maintenant « puits » (donc
+ciseaux gagne sur papier, puits gagne sur ciseaux et papier gagne sur
+puits) : la stratégie optimale est évidemment la même.  Certains
+enfants, embrouillés par l'existence des deux variantes, jouent à
+pierre-papier-ciseaux-puits, qui permet les quatre options, et où on
+convient que la pierre tombe dans le puits : quelle est alors la
+stratégie optimale ? il est facile de se convaincre qu'elle consiste à
+ne jamais jouer pierre (qui est strictement « dominée » par puits), et
+jouer papier, ciseaux ou puits avec probabilité $\frac{1}{3}$ chacun
+(cette stratégie garantit un gain au moins nul quoi que fasse l'autre
+adversaire, et même strictement positif s'il joue pierre avec
+probabilité strictement positive).
+
+\thingy Un jeu idiot : Alice et Bob choisissent simultanément chacun
+un entier naturel.  Celui qui a choisi le plus grand gagne (en cas
+d'égalité, on peut déclarer le nul, ou décider arbitrairement qu'Alice
+gagne — ceci ne changera rien au problème).  Ce jeu résiste à toute
+forme d'analyse intelligente, il n'existe pas de stratégie gagnante
+(ni d'équilibre de Nash, cf. plus bas), on ne peut rien en dire
+d'utile.
+
+Cet exemple sert à illustrer le fait que dans l'étude des jeux sous
+forme normale, l'hypothèse de finitude des choix sera généralement
+essentielle.
+
+
+%
+%
+%
+\end{document}