path: root/controle-20160421.tex

%% 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{xr-hyper}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{matrix,calc}
\usepackage{hyperref}
%
\externaldocument{notes-mitro206}[notes-mitro206.pdf]
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\id}{\operatorname{id}}
\newcommand{\Frac}{\operatorname{Frac}}
\newcommand{\degtrans}{\operatorname{deg.tr}}
\newcommand{\Frob}{\operatorname{Frob}}
\newcommand{\alg}{\operatorname{alg}}
\newcommand{\sep}{\operatorname{sep}}
\newcommand{\Gal}{\operatorname{Gal}}
\newcommand{\Fix}{\operatorname{Fix}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\Divis}{\operatorname{Div}}
\newcommand{\divis}{\operatorname{div}}
\newcommand{\Pic}{\operatorname{Pic}}
\newcommand{\ord}{\operatorname{ord}}
%
\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}}
%
\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
%
\begin{document}
\ifcorrige
\title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des jeux}}
\else
\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théorie des jeux}}
\fi
\author{}
\date{21 avril 2016}
\maketitle

%% {\footnotesize
%% \immediate\write18{sh ./vc > vcline.tex}
%% \begin{center}
%% Git: \input{vcline.tex}
%% \end{center}
%% \immediate\write18{echo ' (stale)' >> vcline.tex}
%% \par}

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

Les exercices sont complètement indépendants.  Ils pourront être
traités dans un ordre quelconque, mais on demande de faire apparaître
de façon très visible dans les copies où commence chaque exercice.

Il n'est pas nécessaire de faire des réponses longues.

L'usage de tous les documents (notes de cours manuscrites ou
imprimées, feuilles d'exercices, livres) est autorisé.

L'usage des calculatrices électroniques est interdit.

Durée : 3h

\pagebreak


%
%
%

\exercice

Alice joue contre Bob un jeu dans lequel elle choisit une option parmi
deux possibles appelées U et V, et Bob choisit une option parmi deux
appelées X et Y (les modalités du choix varient selon les questions
ci-dessous) : les gains d'\emph{Alice} (c'est-à-dire, la fonction
qu'elle cherche à maximiser) sont donnés par le tableau ci-dessous, en
fonction de son choix (colonne de gauche) et de celui de Bob (ligne du
haut) :

\begin{center}
\begin{tabular}{r|ccc}
$\downarrow$A, B$\rightarrow$&X&Y\\\hline
U&$3$&$1$\\
V&$0$&$4$\\
\end{tabular}
\end{center}

\smallbreak

(1) On suppose que Bob fait son choix \emph{après} Alice, et en
connaissant le choix d'Alice, et qu'il cherche à minimiser le gain
d'Alice (i.e., le gain de Bob est l'opposé de celui d'Alice).  Comment
Alice a-t-elle intérêt à jouer et comment Bob répondra-t-il ?  Quelle
est le gain d'Alice dans ce cas ?

\begin{corrige}
Si Alice choisit U, Bob répondra par Y et le gain d'Alice sera $1$ ;
si Alice choisit V, Bob répondra par X et le gain d'Alice sera $0$.
Comme Alice veut maximiser son gain, elle a intérêt à choisir U, et
Bob répondra par Y, et le gain d'Alice sera $1$ dans ce cas.
\end{corrige}

\smallbreak

(2) On suppose maintenant que Bob fait son choix \emph{avant} Alice,
et qu'Alice connaîtra le choix de Bob ; on suppose toujours que Bob
cherche à minimiser le gain d'Alice.  Que fera Bob et comment Alice
répondra-t-elle ?  Quelle est le gain d'Alice dans ce cas ?

\begin{corrige}
Si Bob choisit X, Alice répondra par U et le gain d'Alice sera $3$ ;
si Bob choisit Y, Alice répondra par V et le gain d'Alice sera $4$.
Comme Bob veut minimiser le gain d'Alice, il a intérêt à choisir X, et
Alice répondra par U, et le gain d'Alice sera $3$ dans ce cas.
\end{corrige}

\smallbreak

(3) On suppose qu'Alice et Bob font leur choix séparément, sans
connaître le choix de l'autre, et toujours que Bob cherche à minimiser
le gain d'Alice.  Comment ont-ils intérêt à faire leurs choix ?  Quel
est le gain (espéré) d'Alice dans ce cas ?

\begin{corrige}
On a affaire à un jeu à somme nulle écrit en forme normale :
l'algorithme \ref{zero-sum-games-by-linear-programming-algorithm} nous
indique qu'on obtient la stratégie optimale d'Alice en résolvant le
problème de programmation linéaire suivant :
\[
\left\{
\begin{aligned}
\text{maximiser\ }v&\text{\ avec}\\
p_U \geq 0\;, \;\; p_V \geq 0&\\
p_U + p_V &= 1\\
v - 3p_U - 1p_V &\leq 0\;\;\text{(X)}\\
v - 0p_U - 4p_V &\leq 0\;\;\text{(Y)}\\
\end{aligned}
\right.
\]
On peut l'écrire sous forme normale en réécrivant $v = v_+ - v_-$ avec
$v_+,v_- \geq 0$, mais on gagne un petit peu en remarquant que $v$
sera forcément positif puisque tous les gains du tableau le sont, donc
on peut ajouter la contrainte $v \geq 0$.  Une application de
l'algorithme du simplexe donne finalement l'optimum $v = 2$ atteint
pour $p_U = \frac{2}{3}$ et $p_V = \frac{1}{3}$, avec pour le dual
$q_X = \frac{1}{2}$ et $q_Y = \frac{1}{2}$ (les inégalités (X) et (Y)
sont toutes saturées).

Autrement dit, Alice joue les options U et V avec probabilités
$\frac{1}{3}$ et $\frac{2}{3}$, Bob réplique avec les options X et Y
de façon équiprobable, et le gain espéré d'Alice est $2$, qui est la
valeur du jeu à somme nulle en forme normale considéré ici.
\end{corrige}

\smallbreak

(4) On suppose maintenant que Bob cherche à \emph{maximiser} le gain
d'Alice (i.e., il n'est plus son adversaire comme dans les questions
(1), (2) et (3), mais son allié).  On cherche à déterminer quels sont
les équilibres de Nash possibles.  On notera $(p_U,p_V, q_X,q_Y)$ un
profil de stratégies mixtes général, où $p_U,p_V$ (positifs de
somme $1$) sont les poids des trois options d'Alice (=probabilités
qu'elle les joue), et $q_X,q_Y$ (positifs, également de somme $1$) les
poids des trois options de Bob.  On va discuter selon le support des
stratégies (i.e., selon les ensembles d'options qui ont un poids
strictement positif).\spaceout (a) Pour commencer, quels sont les
équilibres de Nash évidents en stratégies pures ?  Expliquer pourquoi
ce sont bien les seuls équilibres de Nash où l'un des deux joueurs a
une stratégie pure.\spaceout (b) Calculer ce que doivent valoir $p_U$
et $p_V$ dans un équilibre de Nash où $q_X > 0$ et $q_Y > 0$ (i.e.,
les options X et Y de Bob sont dans le support), et ce que dovient
valoir $q_X$ et $q_Y$ dans un équilibre de Nash où $p_U > 0$ et $p_V >
0$ (i.e., les options U et V d'Alice sont dans le support).  Ces
contraintes donnent-elles effectivement un équilibre de
Nash ?\spaceout (c) Conclure quant à l'ensemble des équilibres de Nash
du jeu considéré.

\begin{corrige}
(a) Deux équilibres de Nash sont évidents : si Alice joue (purement) U
  et Bob joue (purement) X, aucun n'a intérêt à changer puisque $3$
  est maximum sur la ligne et sur la colonne ; si Alice joue
  (purement) V et Bob joue (purement) Y, aucun n'a intérêt à changer
  puisque $4$ est maximum sur la ligne et sur la colonne.  Les gains
  d'Alice (et de Bob) dans chacun de ces trois cas sont donc $3$
  et $4$ respectivement.

Il s'agit là de l'ensemble des équilibres de Nash où l'un des deux
joueurs a une stratégie pure : par exemple, si Alice joue purement U,
Bob ne peut que répondre par purement X puisque le gain $3$ est
strictement plus grand que tout autre gain sur la ligne (i.e., donner
un poids non nul à une autre option de Bob ne pourrait que diminuer le
gain).

(b) Si $q_X > 0$ et $q_Y > 0$, les stratégies pures X et Y de Bob
donnent forcément le même gain, car si l'une d'elle donnait un gain
strictement supérieure à l'autre, Bob aurait intérêt à augmenter le
poids $q$ correspondant et améliorerait ainsi strictement sa réponse.
Autrement dit, l'espérance de gain contre la stratégie pure X,
c'est-à-dire $6 p_U$, est égale à l'espérance de gain contre la
stratégie pure Y, soit $p_U + 4 p_V$.  On a donc $3 p_U = p_U + 4
p_V$, et comme aussi $p_U + p_V = 1$ on trouve $(p_U, p_V) =
(\frac{1}{3}, \frac{2}{3})$ en résolvant le système (soit la même
stratégie mixte que trouvée en (3), ce qui n'est pas un hasard vu que
le signe des gains de Bob n'est pas du tout intervenu dans le
raisonnement).  De même, si $p_U > 0$ et $p_V > 0$, on a $3 q_X + q_Y
= 4 q_Y$, et comme aussi $q_X + q_Y = 1$ on trouve $(q_X, q_Y) =
(\frac{1}{2}, \frac{1}{2})$ en résolvant le système (même remarque).

Bref, on a un équilibre de Nash \emph{potentiel} donné par $(p_U,p_V,
q_X,q_Y) = (\frac{2}{3}, \frac{1}{3}, \frac{1}{2}, \frac{1}{2})$,
c'est-à-dire exactement le même profil que dans la question (3) quand
les joueurs étaient adversaires.  Pourtant, aucun des deux joueurs n'a
(strictement) intérêt à changer unilatéralement sa stratégie puisque
les deux options qui se présentent à lui sont indifférentes (elles ont
le même gain espéré) compte tenu du comportement de l'autre.  On a
donc bien trouvé un troisième équilibre de Nash.

(c) Pour résumer, on a trois équilibres de Nash récapitulés par le
tableau (triés par ordre de gain espéré décroissant) :
\begin{center}
\begin{tabular}{cc|cc|c}
$p_U$&$p_V$&$q_X$&$q_Y$&gain\\\hline
$0$&$1$&$0$&$1$&$4$\\
$1$&$0$&$1$&$0$&$3$\\
$\frac{2}{3}$&$\frac{1}{3}$&$\frac{1}{2}$&$\frac{1}{2}$&$2$\\
\end{tabular}
\end{center}
et on a prouvé que c'étaient bien les seuls.
\end{corrige}


%
%
%

\exercice

On considère le jeu suivant : une position du jeu consiste en un
certain nombre (fini) de jetons placés sur un damier transfini dont
les cases étiquetées par un couple $(\alpha,\beta)$ d'ordinaux (on
dira que $\alpha$ est [le numéro de] la ligne de la case et $\beta$
[le numéro de] la colonne).

Un coup du jeu consiste à faire l'opération suivante : le joueur qui
doit jouer choisit un jeton du jeu, disons qu'il soit sur la case
$(\alpha,\beta)$, et il choisit aussi $\alpha' < \alpha$ et $\beta' <
\beta$, il retire le jeton choisi de la case $(\alpha,\beta)$ et le
remplace par \emph{trois} jetons, sur les cases $(\alpha',\beta)$,
$(\alpha,\beta')$ et $(\alpha',\beta')$.  (À titre d'exemple, si le
jeu comporte un seul jeton sur la case $(42,7)$, un coup valable
consiste à le remplacer par trois jetons, sur les cases $(18,7)$,
$(42,5)$ et $(18,5)$.)  Le nombre de jetons présents augmente donc
de $2$ à chaque coup joué.

On remarquera que les jetons sur la ligne ou la colonne $0$ ne peuvent
plus être retirés ou servir de quelque manière que ce soit : on pourra
dire que cette ligne et cette colonne $0$ sont la « défausse » des
jetons.  Le jeu se termine lorsque chacun des jetons est sur la ligne
ou la colonne $0$ (=dans la défausse), car il n'est alors plus
possible de jouer.  Les joueurs (Alice et Bob) jouent à tour de rôle
et celui qui ne peut plus jouer a perdu.

(0) Décrire brièvement le jeu complètement équivalent dans lequel il
n'y a pas de ligne ou de colonne $0$ (on fait démarrer la numérotation
à $1$) et il n'y a pas de défausse (les jetons disparaissent plutôt
qu'être défaussés) : quels sont les types de coups possibles à ce
jeu ?

\begin{corrige}
Les jetons défaussés ne jouant aucun rôle dans le jeu, on peut les
ignorer et obtenir un jeu équivalent.  Les lignes et les colonnes sont
alors numérotés par des ordinaux non nuls, c'est-à-dire $\geq 1$.  Les
quatre types de coups possibles dans ce jeu, selon que $\alpha'$ et/ou
$\beta'$ vaut $0$, sont alors :
\begin{itemize}
\item simplement retirer un jeton de la case $(\alpha,\beta)$ [cas où
  $\alpha' = 0$ et $\beta' = 0$],
\item déplacer un jeton de la case $(\alpha,\beta)$ vers une case
  $(\alpha,\beta')$ plus à gauche (i.e., $\beta' < \beta$) dans la
  ligne [cas où $\alpha' = 0$ et $\beta' \neq 0$],
\item déplacer un jeton de la case $(\alpha,\beta)$ vers une case
  $(\alpha',\beta)$ plus haut (i.e., $\alpha' < \alpha$) dans la
  colonne [cas où $\alpha' \neq 0$ et $\beta' = 0$],
\item remplacer un jeton de la case $(\alpha,\beta)$ par un jeton sur
  une case $(\alpha,\beta')$ plus à gauche dans la ligne, un autre sur
  une case $(\alpha',\beta)$ plus haut dans la colonne, et un
  troisième sur la case $(\alpha',\beta')$ à l'intersection de la
  nouvelle ligne et de la nouvelle colonne, comme dans le jeu
  d'origine [cas où $\alpha' \neq 0$ et $\beta' \neq 0$].
\end{itemize}
\end{corrige}



%
%
%
\end{document}