From 2a7dd09cfbbf531850ebff054878db01f64c090e Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 25 Nov 2015 16:31:15 +0100 Subject: Start writing course notes. --- notes-mitro206.tex | 302 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 302 insertions(+) create mode 100644 notes-mitro206.tex (limited to 'notes-mitro206.tex') 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} -- cgit v1.2.3