summaryrefslogtreecommitdiffstats
path: root/controle-20170419.tex
blob: 8529436cd6c02f10ec40e45f34b4ba8fcb215568 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
%% 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{\outnb}{\operatorname{outnb}}
\newcommand{\downstr}{\operatorname{downstr}}
\newcommand{\precs}{\operatorname{precs}}
\newcommand{\mex}{\operatorname{mex}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\limp}{\Longrightarrow}
\newcommand{\gr}{\operatorname{gr}}
\newcommand{\rk}{\operatorname{rk}}
\newcommand{\fuzzy}{\mathrel{\|}}
%
\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{19 avril 2017}
\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 totalement 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.

\medbreak

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

L'usage des appareils électroniques est interdit.

\medbreak

Durée : 1h30

\vfill
{\noindent\tiny
\immediate\write18{sh ./vc > vcline.tex}
Git: \input{vcline.tex}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pagebreak


%
%
%

\exercice

On s'intéresse dans cet exercice au jeu de \emph{Hackenbush impartial
  en arbre}, défini comme suit.  L'état du jeu est représenté par un
arbre (fini, enraciné\footnote{C'est-à-dire que la racine fait partie
  de la donnée de l'arbre, ce qui est la convention la plus
  courante.}).  Deux joueurs alternent et chacun à son tour choisit
une arête de l'arbre et l'efface, ce qui fait automatiquement
disparaître du même coup tout le sous-arbre qui descendait de cette
arête (voir figure).  Le jeu se termine lorsque plus aucun coup n'est
possible (c'est-à-dire que l'arbre est réduit à sa seule racine),
auquel cas, selon la convention habituelle, le joueur qui ne peut plus
jouer a perdu.

\begin{center}
\begin{tikzpicture}[baseline=0]
\fill [gray!50!white] (-1.5,0) rectangle (1.5,-0.2);
\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
\node (P0) at (0,0) {};
\node (P1) at (0,1) {};
\node (P2) at (-1.5,2) {};
\node (P3) at (-2.0,3) {};
\node (P4) at (-1.0,3) {};
\node (P5) at (1.5,2) {};
\node (P6) at (0.75,3) {};
\node (P7) at (1.5,3) {};
\node (P8) at (2.25,3) {};
\node (P9) at (1.75,1) {};
\end{scope}
\begin{scope}[line width=1.5pt]
\draw (P0) -- (P1);
\draw (P1) -- (P2);
\draw (P1) -- (P5);
\draw (P2) -- (P3);
\draw (P2) -- (P4);
\draw (P5) -- (P6);
\draw (P5) -- (P7);
\draw (P5) -- (P8);
\draw (P0) -- (P9);
\end{scope}
\begin{scope}[line width=3pt,red]
\draw ($0.5*(P1) + 0.5*(P5) + (-0.2,-0.2)$) -- ($0.5*(P1) + 0.5*(P5) + (0.2,0.2)$);
\draw ($0.5*(P1) + 0.5*(P5) + (-0.2,0.2)$) -- ($0.5*(P1) + 0.5*(P5) + (0.2,-0.2)$);
\end{scope}
\end{tikzpicture}
devient
\begin{tikzpicture}[baseline=0]
\fill [gray!50!white] (-1.5,0) rectangle (1.5,-0.2);
\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
\node (P0) at (0,0) {};
\node (P1) at (0,1) {};
\node (P2) at (-1.5,2) {};
\node (P3) at (-2.0,3) {};
\node (P4) at (-1.0,3) {};
\node (P9) at (1.75,1) {};
\end{scope}
\begin{scope}[line width=1.5pt]
\draw (P0) -- (P1);
\draw (P1) -- (P2);
\draw (P2) -- (P3);
\draw (P2) -- (P4);
\draw (P0) -- (P9);
\end{scope}
\end{tikzpicture}
\end{center}

(1) Expliquer pourquoi une position de ce jeu peut être considérée
comme une somme de nim de différents jeux du même type.  Plus
exactement, soit $T$ un arbre de racine $x$, soient $y_1,\ldots,y_r$
les fils de $x$, soient $T_1,\ldots,T_r$ les sous-arbres ayant pour
racines $y_1,\ldots,y_r$ et soient $T'_1,\ldots,T'_r$ les arbres de
racine $x$ où $T'_i$ est formé de $x$ et de $T_i$ (avec une arête
entre $x$ et $y_i$) : expliquer pourquoi la position (représentée par
l'arbre) $T$ est la somme de nim de (celles représentées par)
$T'_1,\ldots,T'_r$.  Qu'en déduit-on sur la valeur de Grundy de la
position $T$ ?

\smallbreak

\centerline{* * *}

Indépendamment de ce qui précède, on va considérer une nouvelle
opération sur les jeux : si $G$ est un jeu combinatoire impartial, vu
comme un graphe orienté (bien-fondé), on définit un jeu noté $*{:}G$
défini en ajoutant une unique position $0$ à $G$ comme on va l'expliquer.
Pour chaque position $z$ de $G$ il y a une position notée $*{:}z$ de
$*{:}G$, et il y a une unique autre position, notée $0$,
dans $*{:}G$ ; pour chaque arête $z \to z'$ de $G$, il y a une arête
$*{:}z\, \to \, *{:}z'$ dans $*{:}G$, et il y a de plus une arête
$*{:}z\, \to 0$ dans $*{:}G$ pour chaque $z$ (en revanche, $0$ est un
puits, c'est-à-dire qu'aucune arête n'en part) ; la position initiale
de $*{:}G$ est $*{:}z_0$ où $z_0$ est celle de $G$.  De façon plus
informelle, pour jouer au jeu $*{:}G$, chaque joueur peut soit faire
un coup normal ($*{:}z\, \to \, *{:}z'$) dans $G$, soit appliquer un
coup « destruction totale » $*{:}z\, \to 0$ qui fait terminer
immédiatement le jeu (et celui qui l'applique a gagné\footnote{Ce jeu
  considéré tout seul n'est donc pas très amusant puisqu'on a toujours
  la possibilité de gagner instantanément.}).

\smallbreak

(2) Montrer par induction bien-fondée que si $G$ est un jeu
combinatoire impartial (bien-fondé) de valeur de Grundy $\alpha$,
alors $*{:}G$ a pour valeur de Grundy $1+\alpha$.

\smallbreak

(3) On revient au jeu de Hackenbush impartial en arbre.  Soit $T$ un
arbre de racine $y$ et $T'$ l'arbre obtenu en ajoutant une nouvelle
racine $x$ à $T$, c'est-à-dire que les sommets de $T'$ sont ceux de
$T$ plus $x$, qui en est la racine, avec une arête entre $x$ et $y$.
Expliquer pourquoi le jeu de Hackenbush représenté par $T'$ s'obtient
par la construction « $*{:}$ » considérée en (2) à partir de celui
représenté par $T$.

Qu'en déduit-on sur la valeur de Grundy de la position $T'$ par
rapport à celle de $T$ ?

\smallbreak

(4) Déduire des questions précédentes une méthode pour calculer la
valeur de Grundy d'une position quelconque au Hackenbush impartial en
arbre.

\smallbreak

(5) Quelle est la valeur de Grundy de la position représentée
ci-dessous ?  (Il s'agit de la position utilisée en exemple plus
haut.)  Quel coup préconiseriez-vous dans cette situation ?

\begin{center}
\begin{tikzpicture}[baseline=0]
\fill [gray!50!white] (-1.5,0) rectangle (1.5,-0.2);
\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
\node (P0) at (0,0) {};
\node (P1) at (0,1) {};
\node (P2) at (-1.5,2) {};
\node (P3) at (-2.0,3) {};
\node (P4) at (-1.0,3) {};
\node (P5) at (1.5,2) {};
\node (P6) at (0.75,3) {};
\node (P7) at (1.5,3) {};
\node (P8) at (2.25,3) {};
\node (P9) at (1.75,1) {};
\end{scope}
\begin{scope}[line width=1.5pt]
\draw (P0) -- (P1);
\draw (P1) -- (P2);
\draw (P1) -- (P5);
\draw (P2) -- (P3);
\draw (P2) -- (P4);
\draw (P5) -- (P6);
\draw (P5) -- (P7);
\draw (P5) -- (P8);
\draw (P0) -- (P9);
\end{scope}
\end{tikzpicture}
\end{center}

\smallbreak

(La question qui suit est indépendante des questions précédentes.)

(6) On remarque que la construction $*{:}G$ définie avant la
question (2) peut se définir de façon identique lorsque $G$ est un jeu
partisan, en donnant à une arête $*{:}z\, \to \, *{:}z'$ la même
couleur que $z\to z'$, et à une arête $*{:}z\, \to 0$ la couleur verte
(ce qui signifie : à la fois bleue et rouge).  En décrivant une
stratégie, montrer que si $G \geq H$ on a aussi $*{:}G \geq *{:}H$, et
en déduire que si $G\doteq H$ alors $*{:}G \doteq *{:}H$ (où $\doteq$
désigne l'égalité au sens de Conway des jeux partisans).


%
%
%

\exercice

On considère le jeu en forme normale suivant : \emph{trois} joueurs
(Alice, Bob et Charlie, par exemple) choisissent indépendamment les
uns des autres un élément de l'ensemble $\{\mathtt{0},\mathtt{1}\}$ :
\begin{itemize}
\item s'ils ont tous les trois choisi la même option, ils gagnent
  tous $0$,
\item si l'un d'entre eux a choisi une option différente des deux
  autres, celui qui a choisi cette option gagne $2$ et chacun des deux
  autres gagne $-1$.
\end{itemize}

Il sera utile de remarquer que les joueurs ont des rôles complètement
symétriques, et que les options sont également symétriques.

(Attention, même si la somme des gains des trois joueurs vaut
toujours $0$, ce n'est pas un « jeu à somme nulle » au sens classique,
car ces derniers ne sont définis que pour \emph{deux} joueurs.)

\smallbreak

(1) Écrire le tableau des gains du jeu considéré.  (On choisira une
façon raisonnable de présenter un tableau à trois entrées, par exemple
comme plusieurs tableaux à deux entrées mis côte à côte.)

\smallbreak

Si $p \in [0;1]$, on notera simplement $p$ la stratégie mixte d'un
joueur qui consiste à choisir l'option $\mathtt{1}$ avec
probabilité $p$, et l'option $\mathtt{0}$ avec probabilité $1-p$.

(2) Vérifier que l'espérance de gain d'Alice si elle joue selon la
stratégie mixte $p$ tandis que Bob joue selon la stratégie mixte $q$
et Charlie selon la stratégie mixte $r$ vaut : $-2pq -2pr +4qr + 2p -
q -r$.  (Ici, $p,q,r$ sont trois réels entre $0$ et $1$.)

\smallbreak

(3) On se demande à quelle condition sur la stratégie mixte $q$ jouée
par Bob et la stratégie mixte $r$ jouée par Charlie les options
$\mathtt{0}$ et $\mathtt{1}$ d'Alice sont indifférentes pour elle
(c'est-à-dire, lui apportent la même espérance de gain).  Montrer que
c'est le cas si et seulement si $q + r = 1$.

\smallbreak

(4) Déduire de la question (3) que si un profil $(p,q,r)$ de
stratégies mixtes est un équilibre de Nash et que $0<p<1$ alors
$q+r=1$.

\smallbreak

(5) En déduire tous les équilibres de Nash $(p,q,r)$ du jeu (on pourra
distinguer des cas selon que $p=0$, $p=1$ ou $0<p<1$ et de même pour
$q$ et $r$ ; la symétrie doit permettre de simplifier le travail).

\smallbreak

(6) Dans cette question, on modifie le jeu : plutôt que faire leurs
choix indépendamment, les joueurs le font successivement (Alice, puis
Bob, puis Charlie).  (a) Que va faire Bob si Alice
choisit $\mathtt{0}$ ?  (b) Informellement, expliquer qui est avantagé
ou désavantagé par cette modification de la règle.




%
%
%
\end{document}