summaryrefslogtreecommitdiffstats
path: root/controle-20170419.tex
blob: 10862cf4e4468f63ee76965d89dd1ab45649b399 (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
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[english,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.

Une traduction anglaise suit l'énoncé en français.

\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

\vskip3ex

\begin{otherlanguage}{english}
{\footnotesize

\noindent\textbf{Instructions.}

The following exercises are independent.  They can be answered in any
order, but the beginning and end of each exercise should be clearly
marked.

An English translation follows the questions in French.

The use of all documents (handwritten or printed course notes,
exercise sheets, books) is permitted.

The use of electronic devices is forbidden.

Duration: 1h30

\par}
\end{otherlanguage}

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

\pagebreak


%
%
%

\exercice\label{hackenbush-exercise}

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$ ?

\begin{corrige}
Il s'agit simplement d'observer que les différentes branches de
l'arbre n'interagissent pas du tout.  Jouer à la somme de nim des jeux
de Hackenbush représentés par les arbres $T'_1,\ldots,T'_r$ revient,
si on veut, à jouer à Hackenbush sur la réunion disjointe de ces
arbres, et comme la racine n'intervient pas, cela ne change rien au
jeu de réunir leurs racines en une seule, ce qui donne l'arbre $T$.

On en déduit que $\gr(T) = \gr(T'_1) \oplus \cdots \gr(T'_r)$ où
$\gr(T)$ désigne, par abus de notation, la valeur de Grundy de la
position de Hackenbush représentée par l'arbre $T$, et où $\oplus$
désigne la somme de nim des entiers naturels.
\end{corrige}

\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'$) de $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$.

\begin{corrige}
Observons tout d'abord que la valeur de Grundy de la position $0$
de $*{:}G$ vaut $0$ puisque c'est un puits.  Montrons par induction
bien-fondée sur les sommets de $*{:}G$ que la valeur de Grundy de la
position $*{:}z$ vaut $1+\gr(z)$ où $\gr(z)$ désigne la valeur de
Grundy de la position $z$ dans $G$.  Les voisins sortants de $*{:}z$
sont $0$ et les $*{:}z'$ pour $z'$ voisin sortant de $z$ (dans $G$) ;
la définition de la valeur de Grundy assure donc que $\gr(*{:}z) =
\mex(\{0\} \cup \{\gr(*{:}z') : z'\in\outnb(z)\})$, c'est-à-dire que
la valeur de Grundy de $*{:}z$ est le plus petit ordinal qui n'est
ni $0$ ni un $\gr(*{:}z')$ pour $z'$ voisin sortant de $z$ ; mais par
hypothèse d'induction, on peut remplacer $\gr(*{:}z')$ par
$1+\gr(z')$, ce qui donne $\gr(*{:}z) = \mex(\{0\} \cup \{1+\gr(z') :
z'\in\outnb(z)\})$.  Montrons que ce $\mex$ vaut $1+\gr(z)$ : pour
cela, il suffit d'observer que (A) $1+\gr(z)$ ne vaut ni $0$ ni
$1+\gr(z')$, et (B) tout ordinal $<1+\gr(z)$ vaut soit $0$ soit
$1+\gr(z')$.  Or le (A) est clair car $1+\gr(z) > 0$ et que $\gr(z')
\neq \gr(z)$ assure $1+\gr(z') \neq 1+\gr(z)$, et le (B) est clair car
si $\beta < 1+\gr(z)$, alors soit $\beta=0$ soit $\beta = 1+\beta'$ où
$\beta' < \gr(z)$, auquel cas la définition de $\gr$ assure qu'il
existe $z'$ voisin sortant de $z$ tel que $\beta' = \gr(z')$.
\end{corrige}

\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$ ?

\begin{corrige}
Un coup dans le jeu de Hackenbush représenté par l'arbre $T'$ peut
consister soit à couper l'arbre à sa racine, c'est-à-dire couper
l'arête reliant $x$ et $y$, ce qui met fin au jeu immédiatement, soit
à jouer dans $T$ (i.e., couper une arête de celui-ci) ; c'est
précisément la définition qu'on a donnée de la
construction « $*{:}$ ».

On en déduit que $\gr(T') = 1 + \gr(T)$ (comme par ailleurs on a ici
affaire à des entiers naturels, le $+$ est commutatif, donc dans cette
question on peut aussi l'écrire $\gr(T') = \gr(T) + 1$).
\end{corrige}

\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.

\begin{corrige}
Des questions précédentes, on déduit que la valeur de Grundy d'un
arbre $T$ au Hackenbush impartial se calcule comme la somme de nim des
$\gr(T'_i) = 1+\gr(T_i)$ où les $T_i$ sont les sous-arbres partant des
fils de la racine de $T$.

On peut donc calculer la valeur de Grundy d'un arbre en calculant
celle de ses sous-arbres enracinés aux différents nœuds, des feuilles
vers la racine : dès qu'on a calculé la valeur de Grundy de tous les
sous-arbres enracinés aux fils $y_1,\ldots,y_r$ d'un nœud $x$, on en
déduit celle du sous-arbre enraciné en leur père $x$ comme la somme de
nim des valeurs en question incrémentées de $1$.
\end{corrige}

\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}

\begin{corrige}
On trouve les valeurs de Grundy suivantes en notant à côté de chaque
nœud la valeur du sous-arbre enraciné en ce nœud :
\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}
\node[anchor=east] at (P2) {$0$};
\node[anchor=west] at (P5) {$1$};
\node[anchor=east] at (P1) {$3$};
\node[anchor=east] at (P0) {$5$};
\end{tikzpicture}
\end{center}

La valeur de Grundy recherchée est donc $5$.  En étudiant les
différentes possibilités, on trouve qu'un coup gagnant possible
consiste à retirer n'importe laquelle des arêtes les plus en haut sur
le dessin (dans tous les cas, le sommet étiqueté $3$ sur la figure
ci-dessus passe à $0$ et la racine de même).
\end{corrige}

\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).

\begin{corrige}
Tout d'abord, observons que $-(*{:}G) = *{:}(-G)$ puisque la
construction « $*{:}$ » est symétrique entre bleu et rouge.

La condition $G\geq H$ signifie que le joueur bleu (Blaise) possède
une stratégie gagnante au jeu $G-H = G+(-H)$ s'il joue en second.
Montrons qu'il en possède encore une à $(*{:}G) - (*{:}H) = (*{:}G) +
(*{:}(-H))$ en considérant comment il répond à un coup de son
adversaire (Roxane).  Si Roxane joue un coup de « destruction totale »
sur l'une des composantes $(*{:}G)$ ou $(*{:}(-H))$, Blaise réplique
sur l'autre et gagne.  Si Roxane joue un coup dans une des deux
composantes $G$ ou $-H$, Blaise répond selon la stratégie qu'il est
supposé posséder.  Dans tous les cas, Blaise peut répondre à tout coup
de Roxane, donc il gagne.  Ceci montre $*{:}G \geq *{:}H$.

Comme $G\doteq H$ signifie $G\geq H$ et $G\leq H$, on a bien $*{:}G
\geq *{:}H$ et $*{:}G \leq *{:}H$ d'après ce qu'on vient d evoir,
c'est-à-dire $*{:}G \doteq *{:}H$.  (La valeur d'un jeu partisan
$*{:}G$ est donc déterminée par la valeur de $G$.)
\end{corrige}


%
%
%

\exercice\label{normal-game-exercise}

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.)

\begin{corrige}
On fait deux tableaux, l'un pour le cas où Alice joue $\mathtt{0}$,
\begin{center}
\begin{tabular}{r|cc}
$\mathtt{0}$A, $\downarrow$B, C$\rightarrow$&$\mathtt{0}$&$\mathtt{1}$\\\hline
$\mathtt{0}$&$0,0,0$&$-1,-1,+2$\\
$\mathtt{1}$&$-1,+2,-1$&$+2,-1,-1$\\
\end{tabular}
\end{center}
et l'autre pour le cas où Alice joue $\mathtt{1}$,
\begin{center}
\begin{tabular}{r|cc}
$\mathtt{1}$A, $\downarrow$B, C$\rightarrow$&$\mathtt{0}$&$\mathtt{1}$\\\hline
$\mathtt{0}$&$+2,-1,-1$&$-1,+2,-1$\\
$\mathtt{1}$&$-1,-1,+2$&$0,0,0$\\
\end{tabular}
\end{center}
Chacune des entrées doit bien sûr lister trois nombres, pour les gains
d'Alice, Bob et Charlie respectivement.
\end{corrige}

\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$.)

\begin{corrige}
Si Alice joue $\mathtt{0}$, son espérance de gain est $-q(1-r) -
(1-q)r + 2qr$ d'après le premier tableau donné en réponse à la
question précédente, soit $4qr - q - r$.  Si Alice joue $\mathtt{1}$,
son espérance de gain vaut $2(1-q)(1-r) -q(1-r) - (1-q)r = 4qr - 3q -
3r + 2$.  Si elle joue $p$, son espérance de gain vaut $1-p$ fois $4qr
- q - r$ plus $p$ fois $4qr - 3q - 3r + 2$, ce qui vaut l'expression
$-2pq -2pr +4qr + 2p - q -r$ annoncée.
\end{corrige}

\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$.

\begin{corrige}
On cherche à quelle condition la valeur $4qr - q - r$ (qui se retrouve
en substituant $0$ à $p$ dans $-2pq -2pr +4qr + 2p - q -r$) est égale
à $4qr - 3q - 3r + 2$ (obtenue en mettant $p$ à $1$).  La différence
entre les deux vaut $2 - 2q - 2r$, qui est donc nulle si et seulement
si $q+r = 1$, comme annoncé.
\end{corrige}

\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$.

\begin{corrige}
Si $(p,q,r)$ est un équilibre de Nash en stratégies mixtes et si
$0<p<1$, c'est-à-dire si Alice pondère effectivement ses deux
stratégies pures, c'est que les gains espérés qu'elles lui apportent
sont égaux (si l'une était strictement meilleure que l'autre, Alice
aurait strictement intérêt à ne jouer que celle-là), c'est-à-dire
$q+r=1$ comme on vient de le voir.
\end{corrige}

\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).

\begin{corrige}
Considérons un équilibre de Nash $(p,q,r)$.  On a vu en (4) que si
l'un des trois nombres n'est ni $0$ ni $1$, la somme des deux autres
vaut nécessairement $1$.

(A) Si au moins deux des trois nombres sont strictement entre $0$ et
$1$, disons sans perte de généralité que $p$ et $q$ le sont.  Alors
$q+r=1$ et $p+r=1$, ce qui donne $p=q$.  Mais le fait que $r=1-q$ avec
$0<q<1$ implique que $0<r<1$.  On a donc aussi $p+q=1$, ce qui
implique $p=q=\frac{1}{2}$ et du coup $r=\frac{1}{2}$ puisque le
raisonnement est complètement symétrique.  Or il est clair que
$(\frac{1}{2},\frac{1}{2},\frac{1}{2})$ est bien un équilibre de Nash
(toutes les options deviennent indifférentes pour tout le monde).

(B) Si un seul des trois nombres est strictement entre $0$ et $1$,
disons sans perte de généralité que $p$ l'est.  Alors $q+r=1$, et
comme $q$ et $r$ doivent valoir chacun $0$ ou $1$, les seules
possibilités sont $(p,0,1)$ et symétriquement $(p,1,0)$.  Vérifions
que $(p,0,1)$ constitue bien un équilibre de Nash, y compris si $p=0$
ou $p=1$ (le cas $(p,1,0)$ étant bien sûr symétrique) : dans
$(p,0,1)$, Alice a un gain espéré de $-1$ qui ne varie pas selon $p$ ;
Bob y a un gain espéré de $3p-1$, qui est supérieur ou égal au gain
$-3p+2$ qu'il espère obtenir en changeant d'option, et le cas de
Charlie est exactement symétrique.  On a donc bien affaire à un
équilibre de Nash.

(C) Enfin, si $p,q,r$ dont tous dans $\{0,1\}$, on a déjà vu en (B)
que si deux valent $0$ et un vaut $1$ ou le contraire, on a affaire à
un équilibre de Nash.  Reste le cas de $(0,0,0)$ ou $(1,1,1)$, et ce
ne sont certainement pas des équilibres de Nash car les trois joueurs
ont intérêt à changer unilatéralement de stratégie.

Finalement, on a trouvé comme équilibre de Nash : le point isolé
$(\frac{1}{2},\frac{1}{2},\frac{1}{2})$, et l'hexagone formé des
segments paramétrés par $(p,0,1)$, $(1,0,r)$, $(1,q,0)$, $(p,1,0)$,
$(0,1,r)$ et $(0,q,1)$ où la seule variable prend une valeur
quelconque dans $[0;1]$ (intuitivement, ce sont des équilibres où deux
joueurs sont en position de gagner, et le troisième, qui est en
position de « faiseur de roi », ne peut pas gagner mais choisit au
hasard lequel des deux autres gagne).
\end{corrige}

\smallbreak

(6) Dans cette question, on modifie le jeu : plutôt que faire leurs
choix indépendamment, les joueurs les font et les déclarent
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.

\begin{corrige}
(a) Si Alice choisit $\mathtt{0}$, Bob a bien sûr intérêt à
  choisir $\mathtt{1}$ (car s'il choisit lui-même $\mathtt{0}$,
  Charlie choisira $\mathtt{1}$ et Bob a le pire gain possible
  de $-1$).  Charlie sera alors dans la situation de choisir qui
  d'Alice ou de Bob gagne sans pouvoir gagner lui-même (il est
  « faiseur de roi »).  La situation est complètement symétrique si
  Alice choisit $\mathtt{1}$, et le choix d'Alice est complètement
  indifférent puisque les deux options sont équivalentes de son point
  de vue.

(b) On peut donc dire que Charlie est désavantagé par le fait de jouer
  en dernier : il ne pourra pas gagner, seulement choisir lequel des
  deux autres joueurs gagne.  (Ceci est un peu paradoxal quand on se
  rappelle que dans un jeu à \emph{deux} joueurs à somme nulle, on ne
  peut qu'être avantagé par le fait d'avoir connaissance de l'option
  choisie par l'adversaire.)
\end{corrige}


%
%
%

\begin{otherlanguage}{english}

\bigbreak

\centerline{\hbox to2truein{\hrulefill}}
\centerline{\textbf{English translation}}

\footnotesize

(This translation is provided to help understand the French version,
but the latter remains the official text and should be referred to in
case of ambiguity or doubt, as this translation has not been checked
as carefully.)

\medbreak

\textbf{Exercise \ref{hackenbush-exercise}.}

This exercise concerns the game of \emph{impartial tree Hackenbush},
defined as follows.  The state of the game is represented by a
(finite, rooted\footnote{Meaning that the root is part of the tree
  datum, which the usual convention.}) tree.  Two players alternate,
each in turn chooses an edge of the tree and removes it, which
automatically causes the entire subtree from this edge to disappear
(see figure in French version).  The game ends when no move is
possible (meaning that the tree is reduced to its root), at which
point, following the usual convention, the player who can no longer
play loses.

\smallbreak

(1) Explain why a position in this game can be considered as a nim sum
of different games of the same type.  More precisely, let $T$ be a
tree with root $x$, let $y_1,\ldots,y_r$ be the children of $x$, let
$T_1,\ldots,T_r$ be the subtrees having $y_1,\ldots,y_r$ as roots, and
let $T'_1,\ldots,T'_r$ be the trees rooted at $x$ where $T'_i$
consists of $x$ and $T_i$ (along with an edge between $x$ and $y_i$):
explain why the position represented by the tree $T$ is the nim sum of
those represented by $T'_1,\ldots,T'_r$.  What can we deduce about the
Grundy value (=nim value) of the position $T$?

\smallbreak

\centerline{* * *}

Independently of the above, we consider a new operation on games: if
$G$ is an impartial combinatorial game, considered as a (well-founded)
oriented graph, we define a new game noted $*{:}G$ defined by adding a
unique new position $0$ to $G$ as follows.  For each position $z$
of $G$, there is a position $*{:}z$ of $*{:}G$, and there is a unique
extra position, written $0$, in $*{:}G$; for each edge $z \to z'$
of $G$, there is an edge $*{:}z\, \to \, *{:}z'$ in $*{:}G$, and
additionally there are edges $*{:}z\, \to 0$ in $*{:}G$ for each $z$
(on the other hand, $0$ is a sink, meaning that it has no outgoing
edge); the initial position of $*{:}G$ is $*{:}z_0$ where $z_0$ is
that of $G$.  Informally, to play the game $*{:}G$, each player can
either make a normal move ($*{:}z\, \to \, *{:}z'$) from $G$, or apply
the ``total destruction'' move $*{:}z\, \to 0$ which terminates tha
game immediately (and the one who plays it wins\footnote{Considered
  alone, this game is therefore not very fun because there is always
  this possibility of winning immediately.}).

\smallbreak

(2) Show by well-founded induction that if $G$ is a (well-founded)
impartial combinatorial game with Grundy value $\alpha$, then $*{:}G$
has Grundy value $1+\alpha$.

\smallbreak

(3) We now return to impartial tree Hackenbush.  Let $T$ be a tree
with root $y$ and $T'$ the tree obtained by adding a new root $x$
to $T$, meaning that the vertices of $T'$ are those of $T$ plus $x$,
which is the root, with an edge between $x$ and $y$.  Explain why the
Hackenbush game represented by $T'$ is obtained, by means of the
``$*{:}$'' construction considered in (2), from that represented
by $T$.  What can we deduce about the Grundy value of the
position $T'$ with respect to that of $T$?

\smallbreak

(4) Use the previous questions to propose a method to compute the
Grundy value of an arbitrary position of impartial tree Hackenbush.

\smallbreak

(5) What is the Grundy value of the position represented in the French
version of the question?  (It is identical to the one used to show an
example of a possible move.)  What move would you prescribe in this
situation?

\smallbreak

(6) Note that the $*{:}G$ construction defined just before
question (2) can be defined in an identical way when $G$ is a partizan
game, by giving an edge $*{:}z\, \to \, *{:}z'$ the same color as
$z\to z'$, and an edge $*{:}z\, \to 0$ the color green (which means:
both blue and red).  By describing a strategy, show that if $G \geq H$
then we also have $*{:}G \geq *{:}H$, and deduce that if $G\doteq H$
then $*{:}G \doteq *{:}H$ (where $\doteq$ denotes equality in the
sense of Conway of partizan games).

\bigbreak

\textbf{Exercise \ref{normal-game-exercise}.}

We consider the following normal form game: \emph{three} players
(Alice, Bob and Charlie, say) each choose, independently of one
another, an element of the set $\{\mathtt{0},\mathtt{1}\}$:
\begin{itemize}
\item if they all choose the same option, they all receive a payoff
  of $0$;
\item whereas if one chooses an option different from the two others,
  whoever chooses this option gets a payoff of $2$ and the two others
  receive $-1$ each.
\end{itemize}

It is worth noting that the players have a completely symmetric rôle,
and that the options are likewise symmetric.

(Warning: even though the sum of the payoffs of the three players is
always $0$, this is not a ``zero-sum game'' in the classical sense,
because the latter are defined only for \emph{two} players.)

\smallbreak

(1) Write the payoff matrix for the game under consideration.  (Choose
a reasonable way to present a table with three entries, for example as
several two-entry tables put side by side.)

\smallbreak

If $p \in [0;1]$, we simply write $p$ for the mixed strategy for some
player consisting of choosing option $\mathtt{1}$ with
probability $p$, and option $\mathtt{0}$ with probability $1-p$.

(2) Check that the expected payoff for Alice if she plays following
the mixed strategy $p$ while Bob plays following the mixed
strategy $q$ and Charlie following the mixed strategy $r$ is: $-2pq
-2pr +4qr + 2p - q -r$.  (Here, $p,q,r$ are three real numbers between
$0$ and $1$.)

\smallbreak

(3) We now ask ourselves under what condition on the mixed strategy
$q$ used by Bob and the mixed strategy $r$ used by Charlie the two
options $\mathtt{0}$ and $\mathtt{1}$ for Alice are indifferent to her
(meaning that they provide her with the same expected payoff).  Show
that this is the case if and only if $q + r = 1$.

\smallbreak

(4) Deduce from question (3) that if mixed strategy profile $(p,q,r)$
is a Nash equilibrium and if $0<p<1$ then $q+r=1$.

\smallbreak

(5) Use the previous questions to find all Nash equilibria $(p,q,r)$
in the game (one might discuss various cases according as $p=0$, $p=1$
or $0<p<1$, and similarly for $q$ and $r$; the use of symmetry can
simplify the task).

\smallbreak

(6) In this question, the game is altered: instead of making their
choices independently, the players make them and declare them
successively (Alice, then Bob, then Charlie).  (a) What will Bob do if
Alice chooses $\mathtt{0}$?  (b) Explain informally who is favored or
disfavored by this alteration of the rule.

\end{otherlanguage}




%
%
%
\end{document}