summaryrefslogtreecommitdiffstats
path: root/controle-20180411.tex
blob: 08613de1dbe4c82cc242c07c2c88c7b3c4e4f573 (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
%% 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,calc}
\usepackage{hyperref}
%
%\externaldocument{notes-mitro206}[notes-mitro206.pdf]
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigskip\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\par\smallbreak\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{11 avril 2018}
\maketitle

\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 : 2h

Barème \emph{indicatif} : exercice 1 : $3$ points ; exercice 2 :
$4$ points ; exercice 3 : $10$ points ; exercice 4 : $3$ points ;
points bonus : comme indiqué.

\emph{Avertissement :} Les exercices ne sont pas tous une application
immédiate du cours ; il est parfois nécessaire de s'inspirer des
techniques ou raisonnements vus en cours pour raisonner dans des
cadres légèrement différents.

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

\pagebreak


%
%
%

\exercice

On considère le jeu à deux joueurs dans lequel les joueurs choisissent
indépendamment chacun une option parmi les quatre possibilités
« Terre », « Eau », « Air » et « Feu », et reçoivent des gains donnés
par le tableau suivant :

\begin{center}
\begin{tabular}{r|cccc}
$\downarrow$Alice, Bob$\rightarrow$&Terre&Eau&Air&Feu\\\hline
Terre&$0,0$&$-1,+1$&$+2,-2$&$+1,-1$\\
Eau&$+1,-1$&$0,0$&$-1,+1$&$+2,-2$\\
Air&$-2,+2$&$+1,-1$&$0,0$&$-1,+1$\\
Feu&$-1,+1$&$-2,+2$&$+1,-1$&$0,0$\\
\end{tabular}
\end{center}

(Le choix d'Alice détermine la ligne du tableau, celui de Bob
détermine la colonne ; la case correspondante indique d'abord le gain
d'Alice, puis celui de Bob.)

Montrer (c'est-à-dire, vérifier) que la stratégie optimale à ce jeu
consiste à jouer « Eau » avec probabilité $\frac{1}{2}$, et chacun de
« Terre » et « Air » avec probabilité $\frac{1}{4}$ (et ne jamais
jouer « Feu »).



%
%
%

\exercice

On considère le jeu suivant entre $N$ joueurs (où $N\geq 3$ est
fixé) : chaque joueur choisit, indépendamment des autres, une des deux
options $E$ (« égoïste ») ou $A$ (« altruiste »).  Le but de chaque
joueur est de maximiser son gain, indépendamment des autres.  Le choix
$E$ apporte un gain de $1$ point au joueur qui le fait (en plus des
gains liés aux choix $A$ des autres comme expliqué dans la phrase
suivante).  Le choix $A$ apporte un gain de $2$ points, mais ces gains
sont mutualisés entre \emph{tous} les joueurs, y compris ceux qui ont
choisi $E$.  Autrement dit, si $k$ joueurs choisissent l'option $A$,
chaque joueur gagne $\frac{2k}{N}$ à cause de ces choix (les $N-k$
joueurs qui ont choisi $E$ gagnent donc $1 + \frac{2k}{N}$ au total).

(0) Quel est le gain maximal d'un joueur dans ce jeu ?  Quel est le
gain minimal ?

(1) En supposant fixés les choix effectués par les $N-1$ autres
joueurs, exprimer le gain d'un joueur s'il choisit $E$ d'une part,
$A$ d'autre part ; calculer la différence entre ces deux gains.  Quel
est le signe de cette différence ?

(2) Expliciter tous les équilibres de Nash dans ce jeu (on indiquera
les stratégies pures ou mixtes intervenant dans l'équilibre, et le
gain espéré pour chaque joueur).

\medskip

On appelle maintenant \emph{stratégie rationnelle commune} une
stratégie mixte $s$ qui, si elle est suivie par tous les joueurs,
maximise le gain espéré de chaque joueur (il est le même pour chaque
joueur puisqu'on fait justement ici l'hypothèse qu'ils jouent tous
selon la même stratégie $s$).

(3) Expliciter la ou les stratégie(s) rationnelle(s) commune(s) au jeu
considéré ci-dessus.

(4) Commenter brièvement quant à la différence entre les réponses aux
questions (2) et (3).


%
%
%

\exercice

Considérons le graphe suivant :

\begin{center}
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (a) at (0bp,0bp) [draw,circle] {$a$};
\node (b) at (-40bp,0bp) [draw,circle] {$b$};
\node (c) at (-80bp,0bp) [draw,circle] {$c$};
\node (d) at (-20bp,-30bp) [draw,circle] {$d$};
\node (e) at (-60bp,-30bp) [draw,circle] {$e$};
\node (f) at (-100bp,-30bp) [draw,circle] {$f$};
\node (g) at (-40bp,-60bp) [draw,circle] {$g$};
\node (h) at (-80bp,-60bp) [draw,circle] {$h$};
\draw [->] (a) -- (b);  \draw [->] (b) -- (c);
\draw [->] (a) -- (d);  \draw [->] (b) -- (d);
\draw [->] (b) -- (e);  \draw [->] (c) -- (e);
\draw [->] (c) -- (f);  \draw [->] (f) -- (e);  \draw [->] (d) -- (e);
\draw [->] (d) -- (g);  \draw [->] (e) -- (g);
\draw [->] (e) -- (h);  \draw [->] (f) -- (h);
\end{tikzpicture}
\end{center}

Les questions qui suivent étudient toutes différentes variantes d'un
jeu consistant à déplacer un ou plusieurs pions sur ce graphe en
suivant les flèches.

\medskip

(1) Dans un premier temps, on considère le jeu suivant : deux joueurs
déplacent un pion (commun) sur ce graphe ; chacun, tour à tour,
déplace le pion d'un sommet du graphe vers un sommet adjacent en
suivant une flèche (i.e., vers un voisin sortant).  Suivant la
convention habituelle, celui qui ne peut pas jouer a perdu.  Indiquer,
en fonction de la position initiale du pion ($a$ à $h$), quel joueur a
une stratégie gagnante.

(2) On modifie maintenant le jeu de la manière suivante : il y a
\emph{plusieurs} pions ; chaque joueur, à son tour, peut et doit
déplacer l'un quelconque des pions, mais un seul, selon les mêmes
règles que précédemment ; plusieurs pions peuvent se trouver sur la
même case, ils n'interagissent pas.  Comme précédemment, le joueur qui
ne peut pas jouer (c'est-à-dire, si tous les pions sont bloqués dans
des puits) a perdu.  Analyser le jeu en question et expliquer comment
déterminer quel joueur a une stratégie gagnante.  Traiter l'exemple de
la situation initiale où un pion est placé en chacun des sommets
$a,b,d,e$ (soit quatre pions au total).

\smallskip

(Les questions (3), (4) et (5) sont indépendantes.)

\smallskip

(3) On modifie maintenant encore un peu le jeu : comme dans la
question (2), il y a plusieurs pions sur le graphe, mais maintenant,
au lieu de déplacer un pion, un joueur peut aussi choisir d'en retirer
un (autrement dit, il y a deux coups possibles : soit déplacer un pion
quelconque suivant une flèche, soit retirer un pion quelconque) ; les
pions n'interagissent pas.  Analyser le jeu en question et expliquer
comment déterminer quel joueur a une stratégie gagnante.  On pourra
commencer par chercher la valeur de Grundy du jeu où il n'y a qu'un
seul pion et la comparer à la valeur de Grundy du jeu non modifié.
Traiter l'exemple de la situation initiale où un pion est placé en
chacun des sommets $a,b,d,e$, soit quatre pions au total.

(4) Les joueurs s'appellent ici Gandalf et Harry (Potter).  On revient
au jeu considéré en (1) (on déplace un seul pion, commun, et on ne
peut pas le retirer), mais cette fois, si le pion arrive au sommet $g$
le joueur Gandalf gagne (indépendamment de qui l'y a amené), tandis
que si le pion arrive en $h$, c'est Harry qui gagne.  Indiquer, en
fonction de la position initiale du pion ($a$ à $h$), quel joueur a
une stratégie gagnante.

(5) On considère enfin le jeu où deux joueurs, disons Xavier et
Yvonne, ont chacun un pion : chacun, quand vient son tour, déplace son
pion indépendamment de l'autre (les deux pions peuvent se trouver sur
la même case, ils n'interagissent pas).  Comme en (1), le joueur qui
ne peut pas bouger (quand vient son tour) a perdu.  Analyser le jeu en
question et expliquer comment déterminer quel joueur a une stratégie
gagnante (en fonction des positions initiales des deux pions).


%
%
%

\exercice

On considère le jeu de solitaire (c'est-à-dire, à un seul joueur)
suivant : on joue sur une rangée de cases qui pourront être numérotées
de $0$ à $N$, et qui peuvent chacune contenir un nombre quelconque de
pierres.  Initialement, on place une seule pierre sur la case $N$.  À
chaque coup, le joueur choisit une pierre sur la case $i$, il la
retire et, si $i>0$ ajoute $k$ pierres sur la case $i-1$, où $k$ est
le numéro du coup (compté à partir de $1$ : autrement dit, le premier
coup remplace une pierre par une pierre, le second remplace une pierre
par deux pierres, le troisième remplace une pierre par trois pierres
et ainsi de suite).

Le jeu se termine quand toutes les pierres ont été retirées.
Démontrer que cela se produit effectivement en temps fini (on ne
demande pas de majorer le nombre de coups en fonction de $N$).



%
%
%

\refstepcounter{comcnt}\bigskip\noindent\textbf{Points bonus.}

(Ceci n'est pas un exercice à résoudre mais un choix à faire.)

Vous disposez de deux options : indiquez clairement sur votre copie si
vous souhaitez
\begin{itemize}
\item[(E)] obtenir $1$ point supplémentaire, qui sera ajouté à votre
  note, ou bien
\item[(A)] obtenir $2$ points, qui seront mutualisés entre tous les
  participants à l'épreuve, c'est-à-dire que $2/N$ points seront
  ajoutés à la note de chacun des $N$ participants.
\end{itemize}



%
%
%
\end{document}