summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
blob: c8d954c64a8910438e333284bf4dd4f186ddfb26 (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
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
%% 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}
%
\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}
\newtheorem{scho}[comcnt]{Scholie}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\outnb}{\operatorname{outnb}}
\newcommand{\downstr}{\operatorname{downstr}}
\newcommand{\mex}{\operatorname{mex}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\limp}{\Longrightarrow}
%
\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}}

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



%
%
%

\section{Introduction et typologie}

\subsection{La notion de jeu mathématique : généralités}

\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 ou \textbf{positions} 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).  Une stratégie
est dite \textbf{gagnante} si le joueur qui l'utilise gagne le jeu
(supposé avoir une notion de « joueur gagnant ») quels que soient les
coups choisis par l'autre joueur.

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 situation 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 à plusieurs 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é.  La question \ref{question-preposing-moves} est
cependant plus intéressante.

\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 (= états possibles), 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 $\{\mathtt{0},\mathtt{1}\}$), si le XOR de ces deux
bits vaut $\mathtt{0}$ alors Alice gagne, s'il vaut $\mathtt{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).

\begin{center}
\begin{tabular}{r|cc}
$\downarrow$Alice, Bob$\rightarrow$&$\mathtt{0}$/« gagne »&$\mathtt{1}$/« perd »\\\hline
$\mathtt{0}$/« Alice »&$+1,-1$&$-1,+1$\\
$\mathtt{1}$/« Bob »&$-1,+1$&$+1,-1$\\
\end{tabular}
\end{center}

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 la « battle of wits » du film \textit{Princess
  Bride} à ce sujet.)

\thingy\label{rock-paper-scissors} 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 situation complètement symétrique.

\begin{center}
\begin{tabular}{r|ccc}
$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux\\\hline
Pierre&$0,0$&$-1,+1$&$+1,-1$\\
Papier&$+1,-1$&$0,0$&$-1,+1$\\
Ciseaux&$-1,+1$&$+1,-1$&$0,0$\\
\end{tabular}
\end{center}

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

\begin{center}
\begin{tabular}{r|cccc}
$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Puits\\\hline
Pierre&$0,0$&$-1,+1$&$+1,-1$&$-1,+1$\\
Papier&$+1,-1$&$0,0$&$-1,+1$&$+1,-1$\\
Ciseaux&$-1,+1$&$+1,-1$&$0,0$&$-1,+1$\\
Puits&$+1,-1$&$-1,+1$&$+1,-1$&$0,0$\\
\end{tabular}
\end{center}

\thingy\label{prisonners-dilemma} Le \textbf{dilemme du prisonnier} :
Alice et Bob choisissent simultanément une option parmi « coopérer »
ou « faire défaut ».  Les gains sont déterminés par la matrice
suivante :

\begin{center}
\begin{tabular}{r|cc}
$\downarrow$Alice, Bob$\rightarrow$&Coopère&Défaut\\\hline
Coopère&$2,2$&$0,4$\\
Défaut&$4,0$&$1,1$\\
\end{tabular}
\end{center}

Ou plus généralement, en remplaçant $4,2,1,0$ par quatre nombres
$T$ (tentation), $R$ (récompense), $P$ (punition) et
$S$ (\textit{sucker}) tels que $T>R>P>S$.  Ces inégalités font que
chaque joueur a intérêt à faire défaut, quelle que soit l'option
choisie par l'autre joueur : on se convaincra facilement que le seul
équilibre de Nash
(cf. \ref{definition-best-response-and-nash-equilibrium}) pour ce jeu
est celui où Alice et Bob font tous deux défaut ; pourtant, tous les
deux reçoivent moins dans cette situation que s'ils coopèrent
mutuellement.

Ce jeu a été énormément étudié du point de vue économique,
psychologique, politique, philosophique, etc., pour trouver des cadres
d'étude justifiant que la coopération est rationnelle, pour expliquer
en quoi le jeu itéré (=répété) diffère du jeu simple, ou pour montrer
que la notion d'équilibre de Nash est perfectible.

\thingy\label{dove-or-hawk} Le jeu du \textbf{trouillard}, ou de la
\textbf{colombe et du faucon}, obtenu en modifiant les gains du
dilemme du prisonnier pour pénaliser le double défaut (maintenant
appelé rencontre faucon-faucon) plus lourdement que la coopération
(colombe) face au défaut.  Autrement dit :

\begin{center}
\begin{tabular}{r|cc}
$\downarrow$Alice, Bob$\rightarrow$&Colombe&Faucon\\\hline
Colombe&$2,2$&$0,4$\\
Faucon&$4,0$&$-4,-4$\\
\end{tabular}
\end{center}

Ou plus généralement, en remplaçant $4,2,0,-4$ par quatre nombres
$W$ (\textit{win}), $T$ (\textit{truce}), $L$ (\textit{loss}) et
$X$ (\textit{crash}) tels que $W>T>L>X$.  Ces inégalités font que
chaque joueur a intérêt à faire le contraire de ce que fait l'autre
(si Bob joue faucon, Alice a intérêt à jouer colombe, et si Bob joue
colombe, Alice a intérêt à jouer faucon).

(Pour justifier le nom de « jeu du trouillard », on peut évoquer le
scénario d'une course de voitures vers une falaise, à la façon du film
\textit{La Fureur de vivre} : jouer colombe, c'est arrêter sa voiture
avant d'arriver à la falaise, et jouer faucon, c'est ne pas s'arrêter
sauf si l'autre s'est arrêté : celui qui s'arrête passe pour un
trouillard et perd le jeu, mais si aucun ne s'arrête, les deux
voitures tombent dans la falaise, ce qui est pire que de passer pour
un trouillard.)

Ce jeu présente par exemple un intérêt en biologie, notamment pour ce
qui est de l'évolution des comportements.

On pourra se convaincre que ce jeu a trois équilibres de Nash
(cf. \ref{definition-best-response-and-nash-equilibrium} ; en gros, il
s'agit d'une situation dans laquelle aucun des joueurs n'améliorerait
son gain en changeant \emph{unilatéralement} la stratégie employée) :
l'un où Alice joue colombe et Bob joue faucon, un deuxième où c'est le
contraire, et un troisième où chacun joue colombe ou faucon avec les
probabilités respectives $\frac{L-X}{W-T + L-X}$ et $\frac{W-T}{W-T +
  L-X}$ (avec les valeurs ci-desssus : $\frac{2}{3}$ et
$\frac{1}{3}$), pour un gain espéré de $\frac{LW - TX}{W-T + L-X}$
(avec les valeurs ci-dessus : $\frac{4}{3}$).

\thingy\label{battle-of-sexes} La \textbf{guerre des sexes}.  Alice et
Bob veulent faire du sport ensemble : Alice préfère l'alpinisme, Bob
préfère la boxe, mais tous les deux préfèrent faire quelque chose avec
l'autre que séparément.  D'où les gains suivants :

\begin{center}
\begin{tabular}{r|cc}
$\downarrow$Alice, Bob$\rightarrow$&Alpinisme&Boxe\\\hline
Alpinisme&$2,1$&$0,0$\\
Boxe&$0,0$&$1,2$\\
\end{tabular}
\end{center}

Ou plus généralement, en remplaçant $2,1,0$ par trois nombres
$P$ (préféré), $Q$ (autre), $N$ (nul) tels que $P>Q>N$.

Ce jeu présente par exemple un intérêt en sociologie, notamment pour
ce qui est de la synchronisation aoutour d'une ressource commune (par
exemple l'adoption d'un standard).

On pourra se convaincre que ce jeu a trois équilibres de Nash
(cf. \ref{definition-best-response-and-nash-equilibrium}) : l'un où
les deux joueurs vont à l'alpinisme, un deuxième où les deux vont à la
boxe, et un troisième où chacun va à son activité préférée avec
probabilité $\frac{P-N}{P+Q-2N}$ et à l'autre avec probabilité
$\frac{Q-N}{P+Q-2N}$ (avec les valeurs ci-dessus : $\frac{2}{3}$ et
$\frac{1}{3}$), pour un gain espéré de $\frac{PQ-N^2}{P+Q-2N}$ (avec
les valeurs ci-dessus : $\frac{2}{3}$).  Remarquablement, ce gain
espéré est inférieur à $Q$.

\thingy Le \textbf{jeu du partage} ou \textbf{de l'ultimatum} : Alice
et Bob ont $10$ points à se partager : Alice choisit un $k$ entre $0$
et $10$ entier (disons), la partie qu'elle se propose de garder pour
elle, \emph{puis} Bob choisit, en fonction du $k$ proposé par Alice,
d'accepter ou de refuser le partage : s'il accepte, Alice reçoit le
gain $k$ et Bob reçoit le gain $10-k$, tandis que si Bob refuse, les
deux reçoivent $0$.  Cette fois, il ne s'agit pas d'un jeu à somme
nulle !

Variante : Alice choisit $k$ et \emph{simultanément} Bob choisit
$\varphi \colon \{0,\ldots,10\} \to \{\textrm{accepte},\penalty0
\textrm{refuse}\}$.  Si $\varphi(k) = \textrm{accepte}$ alors Alice
reçoit $k$ et Bob reçoit $10-k$, tandis que si $\varphi(k) =
\textrm{refuse}$ alors Alice et Bob reçoivent tous les deux $0$.  Ceci
revient (cf. \ref{question-preposing-moves}) à demander à Bob de
préparer sa réponse $\varphi(k)$ à tous les coups possibles d'Alice
(notons qu'Alice n'a pas connaissance de $\varphi$ quand elle
choisit $k$, les deux sont choisis simultanément).  On se convainc
facilement que si Bob accepte $k$, il devrait aussi accepter tous
les $k'\leq k$, d'où la nouvelle :

Variante : Alice choisit $k$ entre $0$ et $10$ (la somme qu'elle
propose de se garder) et \emph{simultanément} Bob choisit $\ell$ entre
$0$ et $10$ (le maximum qu'il accepte qu'Alice garde pour elle) : si
$k\leq \ell$ alors Alice reçoit $k$ et Bob reçoit $10-k$, tandis que
si $k>\ell$ alors Alice et Bob reçoivent tous les deux $0$.

Ce jeu peut sembler paradoxal pour la raison suivante : dans la
première forme proposée, une fois $k$ choisi, on il semble que Bob ait
toujours intérêt à accepter le partage dès que $k<10$ (il gagnera
quelque chose, alors que s'il refuse il ne gagne rien) ; pourtant, on
a aussi l'impression que refuser un partage pour $k>5$ correspond à
refuser un chantage (Alice dit en quelque sorte à Bob « si tu
n'acceptes pas la petite part que je te laisse, tu n'auras rien du
tout »).

Dans la troisième forme, qui est censée être équivalente, on verra
qu'il existe plusieurs équilibres de Nash, ceux où $\ell=k$ (les deux
joueurs sont d'accord sur le partage) et celui où $k=10$ et $\ell=0$
(les deux joueurs demandent tous les deux la totalité du butin, et
n'obtiennent rien).

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

\thingy\label{introduction-graph-game} Le jeu d'un graphe : soit $G$
un graphe orienté (cf. \ref{definitions-graphs} ci-dessous pour la
définition) et $x_0$ un sommet de $G$.  Partant de $x_0$, Alice et Bob
choisissent tour à tour une arête à emprunter pour arriver dans un
nouveau sommet (c'est-à-dire : Alice choisit un voisin sortant $x_1$
de $x_0$, puis Bob un voisins ortant $x_2$ de $x_1$, puis Alice $x_3$
de $x_2$ et ainsi de suite).  \emph{Le perdant est celui qui ne peut
  plus jouer}, et si ceci ne se produit jamais (si on définit un
chemin infini $x_0, x_1, x_2, x_3,\ldots$) alors la partie est
déclarée nulle (ceci ne peut pas se produire lorsque le graphe $G$ est
« bien-fondé »).  On verra qu'il s'agit là du cadre général dans
lequel on étudie la théorie combinatoire des jeux impartiaux à
information parfaite
(cf. \ref{definition-impartial-combinatorial-game}), et qu'un des
joueurs a forcément une stratégie gagnante ou bien les deux joueurs
une stratégie assurant le nul (si le nul est possible)
(cf. \ref{determinacy-of-perfect-information-games}).

Dans une variante du jeu, celui qui ne peut plus jouer gagne au lieu
de perdre : on parle alors de la variante « misère » du jeu.

On peut aussi considérer un graphe dont les arêtes peuvent être
coloriées de trois couleurs possibles : des arêtes rouges, qui ne
peuvent être suivies que par Alice, des arêtes bleues, qui ne peuvent
être suivies que par Bob, et des arêtes vertes (équivalentes à une
arête rouge \emph{et} une arête bleue entre les mêmes deux sommets),
qui peuvent être suivies par l'un ou l'autre joueur (le cas précédent
est donc équivalent à celui d'un graphe entièrement vert).  Il s'agira
là du cadre général dans lequel on étudie la théorie combinatoire des
jeux \emph{partiaux} à information parfaite : on verra que, si le nul
est rendu impossible, quatre cas sont possibles (Alice a une stratégie
gagnante qui que soit le joueur qui commence, ou Bob en a une, ou le
premier joueur a une stratégie gagnante, ou le second en a une).

\thingy\label{introduction-nim-game} Le \textbf{jeu de nim} : un
certain nombre d'allumettes sont
arrangées en plusieurs lignes ; chacun leur tour, Alice et Bob
retirent des allumettes, au moins une à chaque fois, et autant qu'ils
veulent, mais \emph{d'une ligne seulement} ; le gagnant est celui qui
retire la dernière allumette (de façon équivalente, le perdant est
celui qui ne peut pas jouer).  Autrement dit, une position du jeu de
nim est une suite finie $(n_1,\ldots,n_r)$ d'entiers naturels
(représentant le nombre d'allumettes de chaque ligne), et un coup
possible à partir de cette position consiste à aller vers l'état
$(n'_1,\ldots,n'_r)$ où $n'_i = n_i$ pour tout $i$ sauf exactement un
pour lequel $n'_i < n_i$.  Il s'agit ici d'un jeu à deux joueurs
impartial à connaissance parfaite (un cas particulier du jeu général
défini en \ref{introduction-graph-game}).  On verra que la théorie de
Grundy permet de décrire exactement la stratégie gagnante : en
anticipant sur la suite, il s'agit de calculer le XOR (= « ou
  exclusif », appelé aussi \textit{somme de nim} dans ce contexte des
nombres $n_i$ d'allumettes des différentes lignes (écrits en
binaire) : ce XOR s'appelle la \textit{fonction de Grundy} de la
position, et le jeu est gagnable par le second joueur (c'est-à-dire,
celui qui \emph{vient de} jouer) si et seulement cette fonction de
Grundy vaut $0$.  (À titre d'exemple, la position de départ la plus
courante du jeu de nim est $(1,3,5,7)$, et comme $\mathtt{001} \oplus
\mathtt{011} \oplus \mathtt{101} \oplus \mathtt{111} = \mathtt{000}$
en binaire, en notant $\oplus$ pour le XOR, le second joueur a une
stratégie gagnante.)

On peut aussi jouer à la variante « misère » du jeu : celui qui prend
la dernière allumette a perdu (cf. le film \textit{L'année dernière à
  Marienbad}) ; néanmoins, elle se ramène assez facilement à la
variante « normale » (où celui qui prend la dernière allumette a
gagné), cette dernière ayant plus d'intérêt mathématique.

Le jeu de nim apparaît sous différents déguisements.  On peut par
exemple évoquer le suivant, complètement équivalent à ce qu'on vient
de dire : on place $r$ jetons sur un plateau formé d'une seule ligne
dont les cases sont numérotées $0,1,2,3,\ldots$ (de la gauche vers la
droite, pour fixer les idées).  Chacun tour à tour déplace un jeton
vers la gauche ; plusieurs jetons ont le droit de se trouver sur la
même case, et ils peuvent passer par-dessus l'un l'autre.  Le perdant
est celui qui ne peut plus jouer (parce que tous les jetons sont sur
la case la plus à gauche, $0$).  Il s'agit exactement du jeu de nim,
en considérant que la position où les jetons sont sur les cases
$n_1,\ldots,n_r$ correspond à celle du jeu de nim où il y a
$n_1,\ldots,n_r$ allumettes sur les différentes lignes.  C'est ce
point de vue qui suggère le type de jeux suivant :

\thingy Jeux de \textbf{retournement de pièces}.  Ici une position est
une rangée de pièces (qui pourront être numérotées, de la gauche vers
la droite, de $0$ à $N-1$ ou de $1$ à $N$, selon la commodité du jeu),
chacune en position « pile vers le haut » (qu'on notera $\mathtt{0}$)
ou « face vers le haut » ($\mathtt{1}$).  Chaque joueur tour à tour va
retourner certaines pièces selon des règles propres au jeu, avec
toujours la règle générale que \textit{au moins une pièce est
  retournée, et la plus à droite à être retournée doit passer de face
  à pile} (d'autres pièces peuvent passer de pile à face, et d'autres
pièces plus à droite peuvent rester sur pile ou rester sur face, mais
la plus à droite parmi les pièces qui se font retourner devait être
face avant le mouvement et devient du coup pile).  Cette règle
générale assure que le nombre binaire formé de l'ensemble des pièces,
lues de la droite vers la gauche, diminue strictement à chaque coup,
et donc que le jeu termine forcément en temps fini.  Le joueur qui ne
peut plus jouer a perdu.

Il faut bien sûr mettre des règles supplémentaires restreignant les
retournements possibles, sinon le jeu n'a aucun intérêt (le premier
joueur met toutes les pièces à montrer pile et gagne immédiatement).
Quelques exemples de telles règles peuvent être :
\begin{itemize}
\item On ne peut retourner qu'une pièce à chaque coup.  Dans ce cas,
  seul importe le nombre de pièces montrant face, et les joueurs n'ont
  essentiellement aucun choix dans le coup à jouer : peu importe la
  pièce retournée (qui passe forcément de face à pile) ; si le nombre
  de pièces montrant face est pair, le second joueur gagne, tandis que
  s'il est impair, c'est le premier qui gagne.  Ce jeu est très peu
  intéressant.
\item On retourne exactement deux pièces à chaque coup (toujours avec
  la règle générale que la plus à droite des deux passe de face à
  pile).  Il s'agit de nouveau du jeu de nim déguisé (mais un peu
  mieux) : si les pièces sont numérotées à partir de $0$ (la plus à
  gauche), retourner les pièces $n$ et $n'<n$ peut se comprendre comme
  faire passer une ligne d'allumettes de $n$ à $n'$ allumettes, avec
  la différence que deux lignes identiques disparaissent mais on peut
  montrer que cette différence n'a aucun impact sur le jeu de nim
  (essentiellement parce que deux lignes identiques s'« annulent » :
  si un joueur prend des allumettes de l'une, l'autre peut faire le
  même coup sur l'autre).
\item On retourne \emph{une ou deux} pièces (toujours avec la règle
  générale que la plus à droite des deux passe de face à pile).  Il
  s'agit encore une fois de nim déguisé, mais cette fois en numérotant
  les pièces à partir de $1$ (retourner une seule pièce revient à
  vider une ligne de nim, en retourner deux revient à diminuer le
  nombre de pièces d'une ligne).
\item On retourne \emph{au plus trois} pièces (toujours avec la règle
  générale).  On peut décrire la stratégie gagnante dans ce jeu en
  rapport avec le code de parité binaire.  Plus généralement, les jeux
  où on retourne au plus $s$ pièces peuvent, pour les petites valeurs
  de $s$, être reliés à des codes correcteurs remarquables.
\item On retourne n'importe quel nombre de pièces, mais elles doivent
  être consécutives (et toujours avec la règle générale que la pièce
  retournée la plus à droite passe de face à pile).  Il est assez
  facile de décrire la stratégie gagnante de ce jeu.
\end{itemize}

On peut aussi considérer des jeux de retournement de pièces
bidimensionnels : une position est alors un damier, par exemple avec
$M$ lignes et $N$ colonnes (qu'on peut donc repérer comme
$\{0,\ldots,M-1\} \times \{0,\ldots,N-1\}$) avec une pièce à chaque
case, qui peut montrer pile ou face.  Donnons juste un exemple de tel
jeu : chaque joueur peut retourner soit une seule pièce, soit
exactement deux pièces de la même ligne, soit exactement deux pièces
de la même colonne, soit exactement quatre pièces formant les quatre
sommets d'un rectangle (i.e., définies par l'intersection de deux
lignes et de deux colonnes), avec la contrainte supplémentaire que
dans chaque cas la pièce la plus en bas à droite de celles retournées
doit passer de face à pile.

\thingy Le jeu de \textbf{chomp} ou de la tablette de chocolat (ou
gaufre) empoisonnée.

On part d'une « tablette de chocolat » de taille $m\times n$,
c'est-à-dire le produit $\{0,\ldots,m-1\} \times \{0,\ldots,n-1\}$
dont les éléments (les couples $(i,j)$ avec $0\leq i<m$ et $0\leq
j<n$) sont appelés les « carrés » de la tablette ; un état général du
jeu sera un sous-ensemble de ce produit (l'ensemble des carrés restant
à manger).  Le carré $(0,0)$ est empoisonné et le but est de ne pas le
manger.  Un coup consiste à choisir un carré $(i,j)$ où mordre dans la
tablette, ce qui fait disparaître tous les carrés $(i',j')$ avec
$i'\geq i$ et $j'\geq j$.  Chaque joueur, tour à tour, effectue un
coup de la sorte, et le premier à mordre dans la case empoisonnée
$(0,0)$ a perdu (de façon équivalente, on ne peut pas mordre dedans,
ce qui se ramène au formalisme général où le premier qui ne peut pas
jouer a perdu).

On ne sait pas décrire la stratégie gagnante en général, mais on peut
montrer que, partant d'une tablette rectangulaire (ou carrée) $m\times
n$ (par opposition à une forme irrégulière quelconque), le
\emph{premier joueur} a forcément une stratégie gagnante.  En effet,
en admettant provisoirement
(cf. \ref{determinacy-of-perfect-information-games}) qu'un des deux
joueurs a une stratégie gagnante, montrons qu'il s'agit forcément du
premier ; pour cela, supposons par l'absurde que le second joueur ait
une stratégie gagnante, et considérons la réponse $(i,j)$ préconisée
par cette stratégie si le premier joueur joue en mordant la case
$(m-1,n-1)$ opposée à la case empoisonnée : à partir de l'état obtenu
en jouant cette réponse (i.e., toutes les cases $(i',j')$ avec $i'\geq
i$ et $j'\geq j$ ont été mangées), le joueur qui vient de jouer est
censé avoir une stratégie gagnante ; mais si le premier joueur jouait
directement en mordant en $(i,j)$, il se ramènerait à cet état, les
rôles des joueurs étant inversés, donc il aurait une stratégie
gagnante, et cela signifie qu'il en a une dès le premier tour.

\thingy\label{introduction-hackenbush} Le jeu de \textbf{Hackenbush}
impartial, bicolore, ou tricolore.

Dans ce jeu, l'état est défini par un dessin, plus précisément un
graphe non orienté, pouvant avoir des arêtes multiples et des arêtes
reliant un sommet à lui-même, dont certains sommets sont « au sol »
(graphiquement représentés en les plaçant sur une droite horizontale
en bas du dessin).  Chaque sommet et chaque arête doit être « relié au
  sol », c'est-à-dire atteignable depuis un sommet au sol par une
succession d'arêtes.  De plus, dans le cas de Hackenbush bicolore,
chaque arête est coloriée rouge ou bleue, dans le cas de Hackenbush
tricolore elle peut aussi être verte, et dans le cas de Hackenbush
impartial il n'y a pas de couleur, ou, si on préfère, toutes les
arêtes sont vertes.

\begin{center}
\begin{tikzpicture}
\draw[very thin] (-0.5,0) -- (3.5,0);
\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
\node (P0) at (0,0) {};
\node (P1) at (1.5,0) {};
\node (P2) at (0.75,1) {};
\node (P3) at (0.75,2.5) {};
\node (P4) at (0,2) {};
\node (P5) at (1.5,2) {};
\node (Q0) at (3,0) {};
\node (Q1) at (3,1.5) {};
\node (Q2) at (3,3) {};
\end{scope}
\begin{scope}[line width=1.5pt]
\draw[color=green] (P0) -- (P2);
\draw[color=green] (P1) -- (P2);
\draw[color=green] (P2) -- (P3);
\draw[color=green] (P3) -- (P4);
\draw[color=green] (P3) -- (P5);
\draw[color=green] (P3) .. controls (1.0,2.75) and (1.0,3.0) .. (0.75,3.0) .. controls (0.5,3.0) and (0.5,2.75) .. (P3);
\draw[color=red] (Q0) -- (Q1);
\draw[color=blue] (Q1) -- (Q2);
\end{scope}
\end{tikzpicture}
\\{\footnotesize (Un état possible de Hackenbush.)}
\end{center}

Alice et Bob jouent tour à tour, chacun efface une arête du dessin, ce
qui fait disparaître du même coup toutes les arêtes et tous les
sommets qui ne sont plus reliés au sol.  (Par exemple, dans le dessin
représenté ci-dessus, si on efface l'arête rouge, l'arête bleue
au-dessus disparaît immédiatement ; si on efface l'une des deux arêtes
vertes reliées au sol, les « jambes » du « bonhomme » vert, rien de
particulier ne se passe mais si on efface la deuxième, toutes les
arêtes vertes disparaissent.)  Dans le jeu de Hackenbush impartial,
n'importe quel joueur peut effacer n'importe quelle arête ; dans le
jeu bicolore, seule Alice peut effacer les arêtes rouges et seul Bob
peut effacer les arêtes bleues ; dans le jeu tricolore, les arêtes
vertes sont effaçables par l'un ou l'autre joueur (mais dans tous les
cas, la disparition des arêtes non reliées au sol est automatique).
Le jeu se termine quand un joueur ne peut plus jouer, auquel cas il a
perdu (au Hackenbush impartial, cela signifie que le jeu se termine
quand un joueur finit de faire disparaître le dessin, auquel cas il a
gagné ; au Hackenbush bicolore ou tricolore, il se peut bien sûr qu'il
reste des arêtes de la couleur du joueur qui vient de jouer).

Le jeu de Hackenbush impartial possède une stratégie gagnante soit par
le premier soit par le second joueur (le dessin formé uniquement des
arêtes vertes ci-dessus, par exemple, est gagnable par le premier
joueur, le seul coup gagnant consistant à effacer le « corps » du
« bonhomme » pour ne laisser que ses jambes).  Le jeu de Hackenbush
bicolore possède une stratégie gagnante soit pour Alice, soit pour
Bob, soit pour le second joueur, mais jamais pour le premier (le
dessin formé par les arêtes rouge et bleue ci-dessus, par exemple, est
gagnable par Alice).  Le jeu de Hackenbush tricolore possède une
stratégie gagnante soit pour Alice, soit pour Bob, soit pour le
premier joueur, soit pour le second (l'ensemble du dessin ci-dessus,
par exemple, est gagnable par Alice).

\thingy Le \textbf{jeu de l'hydre} : Hercule essaie de terrasser
l'hydre.  Le joueur qui joue l'hydre commence par dessiner (i.e.,
choisir) un arbre (fini, enraciné), la forme initiale de l'hydre.
Puis Hercule choisit une \emph{tête} de l'hydre, c'est-à-dire une
feuille $x$ de l'arbre, et la décapite en la supprimant de l'arbre.
L'hydre se reproduit alors de la façon suivante : soit $y$ le nœud
parent de $x$ dans l'arbre, et $z$ le nœud parent de $y$ (grand-parent
de $x$, donc) : si l'un ou l'autre n'existe pas, rien ne se passe
(l'hydre passe son tour) ; sinon, l'hydre choisit un entier naturel
$n$ (aussi grand qu'elle veut) et attache à $z$ autant de nouvelles
copies de $y$ (mais sans la tête $x$ qui a été décapitée) qu'elle le
souhaite.  Hercule gagne s'il réussit à décapiter le dernier nœud de
l'hydre ; l'hydre gagnerait si elle réussissait à survivre
indéfiniment.

\begin{center}
\begin{tikzpicture}[baseline=0]
\draw[very thin] (-1.5,0) -- (1.5,0);
\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,2) {};
\node (P3) at (0,2) {};
\node (P4) at (1,2) {};
\node (P5) at (0.5,3) {};
\node (P6) at (1.5,3) {};
\end{scope}
\begin{scope}[line width=1.5pt]
\draw (P0) -- (P1);
\draw (P1) -- (P2);
\draw (P1) -- (P3);
\draw (P1) -- (P4);
\draw (P4) -- (P5);
\draw (P4) -- (P6);
\end{scope}
\begin{scope}[line width=3pt,red]
\draw ($(P6) + (-0.2,-0.2)$) -- ($(P6) + (0.2,0.2)$);
\draw ($(P6) + (-0.2,0.2)$) -- ($(P6) + (0.2,-0.2)$);
\end{scope}
\node[anchor=west] at (P6) {$x$};
\node[anchor=west] at (P4) {$y$};
\node[anchor=west] at (P1) {$z$};
\end{tikzpicture}
devient
\begin{tikzpicture}[baseline=0]
\draw[very thin] (-1.5,0) -- (1.5,0);
\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,2) {};
\node (P3) at (0,2) {};
\node (P4) at (0.8,2) {};
\node (P5) at (0.6,3) {};
\node (P4b) at (1.2,2) {};
\node (P5b) at (1.2,3) {};
\node (P4c) at (1.7,2) {};
\node (P5c) at (1.7,3) {};
\node (P4d) at (2.2,2) {};
\node (P5d) at (2.2,3) {};
\end{scope}
\begin{scope}[line width=1.5pt]
\draw (P0) -- (P1);
\draw (P1) -- (P2);
\draw (P1) -- (P3);
\draw (P1) -- (P4);
\draw (P4) -- (P5);
\draw[blue] (P1) -- (P4b);
\draw[blue] (P4b) -- (P5b);
\draw[blue] (P1) -- (P4c);
\draw[blue] (P4c) -- (P5c);
\draw[blue] (P1) -- (P4d);
\draw[blue] (P4d) -- (P5d);
\end{scope}
\end{tikzpicture}
\end{center}

Ce jeu est particulier en ce que, mathématiquement, non seulement
Hercule possède une stratégie gagnante, mais en fait Hercule gagne
\emph{toujours}, quoi qu'il fasse et quoi que fasse l'hydre.
Pourtant, en pratique, l'hydre peut facilement s'arranger pour
survivre un temps inimaginablement long.

\thingy Le \textbf{jeu topologique de Choquet} : soit $X$ un espace
métrique (ou topologique) fixé à l'avance.  Uriel et Vania choisissent
tour à tour un ouvert non vide de ($X$ contenu dans) l'ouvert
précédemment choisi : i.e., Uriel choisit $\varnothing \neq U_0
\subseteq X$, puis Vania choisit $\varnothing \neq V_0 \subseteq U_0$,
puis Uriel choisit $\varnothing \neq U_1 \subseteq V_0$ et ainsi de
suite.  Le jeu continue pendant un nombre infini de tours indicés par
les entiers naturels.  À la fin, on a bien sûr $\bigcap_{n=0}^{\infty}
U_n = \bigcap_{n=0}^{\infty} V_n$ : on dit qu'Uriel gagne le jeu si
cette intersection est vide, Vania le gagne si elle est non-vide.  On
peut se convaincre que si $X = \mathbb{Q}$, alors Uriel possède une
stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vania qui en
a une.

\thingy Les \textbf{jeux de Gale-Stewart} : soit $A$ une partie de
$\mathbb{N}^{\mathbb{N}}$ ou de $\{0,1\}^{\mathbb{N}}$ ou de $[0,1]$.
Alice et Bob choisissent tour à tour un élément de $\mathbb{N}$ (dans
le premier cas) ou de $\{0,1\}$ (dans les deux suivants).  Ils jouent
un nombre infini de tours, « à la fin » desquels la suite de leurs
coups définit un élément de $\mathbb{N}^{\mathbb{N}}$ ou de
$\{0,1\}^{\mathbb{N}}$ ou, en les considérant comme la suite des
chiffres binaires d'un réel commençant par $0.$, de $[0,1]$ : si cet
élément appartient à $A$, Alice gagne, sinon c'est Bob (la partie
n'est jamais nulle).  \emph{Il n'est pas vrai} qu'un des deux joueurs
possède forcément une stratégie gagnante.


\subsection{Remarques}

\thingy\label{question-preposing-moves} La question suivante mérite
l'attention : supposons que, dans un jeu, deux joueurs aient à jouer
deux coups successifs, disons que le joueur $A$ choisit une option $x$
parmi un certain ensemble $E$ (typiquement fini), \emph{puis} le
joueur $B$ choisit, en connaissant le $x$ choisi par $A$, une option
$y$ parmi un certain ensemble $F$ (typiquement fini).  Revient-il au
même de demander de choisir \emph{simultanément} pour $A$ un élément
de $E$ et pour $B$ un élément de l'ensemble $F^E$ des fonctions de $E$
dans $F$ ?  L'idée étant que $B$ choisit la fonction $\varphi$ qui,
selon le coup $x \in E$ joué par $A$, déterminera le coup $y :=
\varphi(x) \in F$ qu'il joue en réponse.  Au moins si $E$ est fini, on
peut imaginer que $B$ considère mentalement tous les coups que $A$
pourra jouer et choisit la réponse qu'il y apporterait, déterminant
ainsi la fonction $\varphi$ (si on préfère, $\varphi$ est une
stratégie locale pour le prochain coup de $B$).

En principe, les jeux ainsi considérés (le jeu initial, et celui où on
a demandé à $B$ d'anticiper son choix en le remplaçant par une
fonction du choix de $A$) devraient être équivalents.  En pratique, il
se peut qu'on les analyse différemment pour différentes raisons.

Notons que si on permet ou oblige $B$ à communiquer à $A$ la fonction
$\varphi$ qu'il a choisie, i.e., à s'\emph{engager} irrévocablement
sur le coup $y$ qu'il jouerait selon le coup $x$ de $A$, on peut
véritablement changer le jeu.


\subsection{Plan}

La section \ref{section-games-in-normal-form} concerne les jeux en
forme normale et la notion d'équilibre de Nash : on gardera donc à
l'esprit les exemples tels que le dilemme du
prisonnier (\ref{prisonners-dilemma}), le
trouillard (\ref{dove-or-hawk}) et la bataille des
sexes (\ref{battle-of-sexes}).  On évoque plus particulièrement les
jeux à somme nulle en \ref{zero-sum-games} : on pensera alors à des
jeux comme pierre-papier-ciseaux (cf. \ref{rock-paper-scissors}).

La section \ref{section-well-founded-induction} introduit la notion de
graphe bien-fondée et d'induction bien-fondée qui est essentielle pour
la suite.

La section \ref{section-combinatorial-impartial-games} concerne la
théorie, dite « combinatoire », des jeux impartiaux à information
parfaite, dont le modèle est décrit en \ref{introduction-graph-game}
(sans coloriage) et dont l'archétype est le jeu de nim
(cf. \ref{introduction-nim-game}) ou le Hackenbush impartial (=vert)
(cf. \ref{introduction-hackenbush}).

On parlera ensuite des jeux \emph{partiaux} à information parfaite,
dont l'archétype est le Hackenbush bicolore ou tricolore, et de la
théorie des nombres de Conway.

Enfin, on évoquera quelques jeux en vrac et des liens avec la logique.


%
%
%

\section{Jeux en forme normale}\label{section-games-in-normal-form}

\subsection{Généralités}

\begin{defn}\label{definition-game-in-normal-form}
Un \textbf{jeu en forme normale} à $N$ joueurs est la donnée de $N$
ensembles finis $A_1,\ldots,A_N$ et de $N$ fonctions
$u_1,\ldots,u_N\colon A \to \mathbb{R}$ où $A := A_1 \times \cdots
\times A_N$.

Un élément de $A_i$ s'appelle une \textbf{option} ou \textbf{stratégie
  pure} pour le joueur $i$.  Un élément de $A := A_1 \times \cdots
\times A_N$ s'appelle un \textbf{profil de stratégies pures}.  La
valeur $u_i(a)$ de la fonction $u_i$ sur un $a\in A$ s'appelle le
\textbf{gain} du joueur $i$ selon le profil $a$.
\end{defn}

Le jeu doit se comprendre de la manière suivante : chaque joueur
choisit une option $a_i \in A_i$ indépendamment des autres, et chaque
joueur reçoit un gain égal à la valeur $u_i(a_1,\ldots,a_n)$ définie
par le profil $(a_1,\ldots,a_n)$ des choix effectués par tous les
joueurs.  Le but de chaque joueur est de maximiser son propre gain.

On utilisera le terme « option » ou « stratégie pure » selon qu'on
veut souligner que le joueur $i$ choisit effectivement $a_i$ ou décide
a priori de faire forcément ce choix-là.  Cette différence vient du
fait que les joueurs peuvent également jouer de façon probabiliste, ce
qui amène à introduire la notion de stratégie mixte :

\begin{defn}\label{definition-mixed-strategy-abst}
Donné un ensemble $B$ fini d'« options », on appelle \textbf{stratégie
  mixte} sur $B$ une fonction $s\colon B\to\mathbb{R}$ telle que
$s(b)\geq 0$ pour tout $b\in B$ et $\sum_{b\in B} s(b) = 1$ :
autrement dit, il s'agit d'une distribution de probabilités sur $B$.

Le \textbf{support} de $s$ est l'ensemble des options $b\in B$ pour
lesquelles $s(b) > 0$.

Parfois, on préférera considérer la stratégie comme la combinaison
formelle $\sum_{b\in B} s(b)\cdot b$ (« formelle » signifiant que le
produit $t\cdot b$ utilisé ici n'a pas de sens intrinsèque : il est
défini par son écriture ; l'écriture $\sum_{b\in B} s(b)\cdot b$ est
donc une simple notation pour $s$).  Autrement dit, ceci correspond à
voir une stratégie mixte comme une combinaison convexe d'éléments
de $B$, i.e., un point du simplexe affine dont les sommets sont les
éléments de $B$.  En particulier, un élément $b$ de $B$ (stratégie
pure) sera identifié à l'élément de $S_B$ qui affecte le poids $1$
à $b$ et $0$ à tout autre élément.

En tout état de cause, l'ensemble $S_B$ des stratégies mixtes sur $B$
sera vu (notamment comme espace topologique) comme le fermé de
$\mathbb{R}^B$ défini par l'intersection des demi-espaces de
coordonnées positives et de l'hyperplan défini par la somme des
coordonnées égale à $1$.
\end{defn}

\begin{defn}\label{definition-mixed-strategy-game}
Pour un jeu comme défini en \ref{definition-game-in-normal-form}, une
stratégie mixte pour le joueur $i$ est donc une fonction $s\colon A_i
\to\mathbb{R}$ comme on vient de le dire.  On notera parfois $S_i$
l'ensemble des stratégies mixtes du joueur $i$.  Un \textbf{profil de
  stratégies mixtes} est un élément du produit cartésien $S := S_1
\times \cdots \times S_N$.

Plus généralement, si $I \subseteq \{1,\ldots,N\}$ est un ensemble de
joueurs, un élément du produit $S_I := \prod_{j\in I} S_j$ s'appellera
un profil de stratégies mixtes pour l'ensemble $I$ de joueurs ; ceci
sera notamment utilisé si $I = \{1,\ldots,N\}\setminus\{i\}$ est
l'ensemble de tous les joueurs sauf le joueur $i$, auquel cas on
notera $S_{?i} := \prod_{j\neq i} S_j$ l'ensemble des profils.
Naturellement, si chaque composante est une stratégie pure, on pourra
parler de profil de stratégies pures.
\end{defn}

\thingy Il va de soi qu'un profil de stratégies mixtes, i.e., un
élément de $S := S_1 \times \cdots \times S_N$, i.e., la donnée d'une
distribution de probabilité sur chaque $A_i$, n'est pas la même chose
qu'une distribution de probabilités sur $A := A_1 \times \cdots \times
A_N$.  Néanmoins, on peut voir les profils de stratégies mixtes comme
des distributions particulières sur $A$, à savoir celles pour
lesquelles les marginales (i.e., les projections sur un des $A_i$)
sont indépendantes.  Concrètement, ceci signifie que donné
$(s_1,\ldots,s_N) \in S$, on en déduit un $s\colon A\to\mathbb{R}$,
aussi une distribution de probabilité, par la définition suivante :
$s(a_1,\ldots,a_N) = s_1(a_1)\cdots s_N(a_N)$ (produit des
$s_i(a_i)$).  On identifiera parfois abusivement l'élément
$(s_1,\ldots,s_N) \in S$ à la distribution $s\colon A\to\mathbb{R}$
qu'on vient de décrire (ce n'est pas un problème car $s_i$ se déduit
de $s$ : précisément, $s_i(b) = \sum_{a: a_i = b} s(a)$ où la somme
est prise sur les $a \in A$ tels que $a_i = b$).

Ceci conduit à faire la définition suivante :

\begin{defn}
Donné un jeu en forme normale comme
en \ref{definition-game-in-normal-form}, si $s := (s_1,\ldots,s_N) \in
S_1 \times \cdots \times S_N$ est un profil de stratégies mixtes, on
appelle \textbf{gain [espéré]} du joueur $i$ selon ce profil la
quantité
\[
u_i(s) := \sum_{a\in A} s_1(a_1)\cdots s_N(a_N)\,u_i(a)
\]
(ceci définit $u_i$ comme fonction de $S_1\times\cdots \times S_N$
vers $\mathbb{R}$).
\end{defn}

Selon l'approche qu'on veut avoir, on peut dire qu'on a défini
$u_i(s)$ comme l'espérance de $u_i(a)$ si chaque $a_j$ est tiré selon
la distribution de probabilité $s_i$ ; ou bien qu'on a utilisé
l'unique prolongement de $u_i$ au produit des simplexes $S_i$ qui soit
affine en chaque variable $s_i$.



\subsection{Équilibres de Nash}

\begin{defn}\label{definition-best-response-and-nash-equilibrium}
Donné un jeu en forme normale comme
en \ref{definition-game-in-normal-form}, si $1 \leq i \leq N$ et si
$s_? := (s_1,\ldots,s_{i-1},s_{i+1},\ldots,s_N) \in S_1 \times \cdots
\times S_{i-1} \times S_{i+1} \times \cdots \times S_N$ est un profil
de stratégies mixtes pour tous les joueurs autres que le joueur $i$,
on dit que la stratégie mixte $s_! \in S_i$ est une \textbf{meilleure
  réponse} (resp. la meilleure réponse stricte) contre $s_?$ lorsque
pour tout $t \in S_i$ on a $u_i(s_?,s_!) \geq u_i(s_?,t)$
(resp. lorsque pour tout $t \in S_i$ différent de $s_!$ on a
$u_i(s_?,s_!) > u_i(s_?,t)$), où $(s_?,t)$ désigne l'élément de
$S_1\times \cdots \times S_N$ obtenu en insérant $t \in S_i$ comme
$i$-ième composante entre $s_{i-1}$ et $s_{i+1}$.

Un profil de stratégies mixtes $s = (s_1,\ldots,s_N)$ (pour l'ensemble
des joueurs) est dit être un \textbf{équilibre de Nash} (resp., un
équilibre de Nash \emph{strict}) lorsque pour tout $1\leq i \leq N$,
la stratégie $s_i$ pour le joueur $i$ est une meilleure réponse
(resp. la meilleure réponse stricte) contre le profil $s_{?i}$ pour
les autres joueurs obtenu en supprimant la composante $s_i$ de $s$.
\end{defn}

\begin{prop}\label{stupid-remark-best-mixed-strategies}
Donné un jeu en forme normale comme
en \ref{definition-game-in-normal-form}, si $1 \leq i \leq N$ et si
$s_?$ est un profil de stratégies mixtes pour tous les joueurs autres
que le joueur $i$, il existe une meilleure réponse pour le joueur $i$
qui est une stratégie pure.  Et même, si $s_!$ (stratégie mixte) est
une meilleure réponse, alors il existe une meilleure réponse qui est
une stratégie pure appartenant au support de $s_!$.

En particulier, une meilleure réponse stricte est nécessairement une
stratégie pure.
\end{prop}
\begin{proof}
Il suffit de se rappeler que $u_i(s_?,t)$ est une fonction affine
de $t \in S_i$, c'est-à-dire que sa valeur est combinaison convexe, à
coefficients les $t(a)$ pour $a\in S_i$, des $u_i(s_?,a)$.  Comme une
combinaison convexe est majorée par la plus grande des valeurs
combinée (ici, des $u_i(s_?,a)$), il est clair que le maximum des
$u_i(s_?,t)$ existe et est égal au maximum des $u_i(s_?,a)$ ; les
autres affirmations sont tout aussi faciles.
\end{proof}

\begin{thm}[John Nash, 1951]\label{theorem-nash-equilibria}
Pour un jeu en forme normale comme
en \ref{definition-game-in-normal-form}, il existe un équilibre de
Nash.
\end{thm}

Pour démontrer le théorème en question, on utilise (et on admet) le
théorème du point fixe de Brouwer, qui affirme que :

\begin{thm}[L. E. J. Brouwer, 1910]\label{brouwer-fixed-point-theorem}
Si $K$ est un convexe compact de $\mathbb{R}^m$, et que $T \colon K
\to K$ est continue, alors il existe $x\in K$ tel que $T(x) = x$ (un
\emph{point fixe} de $T$, donc).
\end{thm}

L'idée intuitive de la démonstration suivante est : partant d'un
profil $s$ de stratégies, on peut définir continûment un nouveau
profil $s^\sharp$ en donnant plus de poids aux options qui donnent un
meilleur gain au joueur correspondant — si bien que $s^\sharp$ sera
différent de $s$ dès que $s^\sharp$ n'est pas un équilibre de Nash.  Comme
la fonction $T \colon s \to s^\sharp$ doit avoir un point fixe, ce point
fixe sera un équilibre de Nash.

\begin{proof}[Démonstration de \ref{theorem-nash-equilibria}]
Si $s \in S$ et $1\leq i\leq N$, convenons de noter $s_{?i}$
l'effacement de la composante $s_i$ (c'est-à-dire le profil pour les
joueurs autres que $i$).  Si de plus $b \in A_i$, notons
$\varphi_{i,b}(s) = \max(0,\; u_i(s_{?i},b) - u_i(s))$ l'augmentation
du gain du joueur $i$ si on remplace sa stratégie $s_i$ par la
stratégie pure $b$ en laissant le profil $s_{?i}$ des autres joueurs
inchangé (ou bien $0$ s'il n'y a pas d'augmentation).  On remarquera
que $s$ est un équilibre de Nash si et seulement si les
$\varphi_{i,b}(s)$ sont nuls pour tout $1\leq i\leq N$ et tout $b\in
A_i$ (faire appel à la proposition précédente pour le « si »).  On
remarquera aussi que chaque $\varphi_{i,b}$ est une fonction continue
sur $S$.

Définissons maintenant $T\colon S\to S$ de la façon suivante : si $s
\in S$, on pose $T(s) = s^\sharp$, où $s^\sharp =
(s^\sharp_1,\ldots,s^\sharp_N)$ avec $s^\sharp_i$ le barycentre de
$s_i$ avec coefficient $1$ et des $a_i$ avec les coefficients
$\varphi_{i,a}(s)$, autrement dit :
\[
\begin{aligned}
s^\sharp_i(a) &= \frac{s_i(a) + \varphi_{i,a}(s)}{\sum_{b\in A_i}(s_i(b) + \varphi_{i,b}(s))}\\
&= \frac{s_i(a) + \varphi_{i,a}(s)}{1 + \sum_{b\in A_i}\varphi_{i,b}(s)}
\end{aligned}
\]
(L'important est que $s^\sharp_i$ augmente strictement le poids des options
$a\in A_i$ telles que $u_i(s_{?i},a) > u_i(s)$ ; en fait, on pourrait
composer $\varphi$ à gauche par n'importe quelle fonction $\mathbb{R}
\to \mathbb{R}$ croissante, continue, nulle sur les négatifs et
strictement positive sur les réels strictement positifs, on a choisi
l'identité ci-dessus pour rendre l'expression plus simple à écrire,
mais elle peut donner l'impression qu'on commet une « erreur
  d'homogénéité » en ajoutant un gain à une probabilité.)

D'après la première expression donnée, il est clair qu'on a bien
$s^\sharp_i \in S_i$, et qu'on a donc bien défini une fonction
$T\colon S\to S$.  Cette fonction est continue, donc admet un point
fixe $s$ d'après \ref{brouwer-fixed-point-theorem}.  On va montrer que
$s$ est un équilibre de Nash.

Si $1\leq i\leq N$, il existe $a \in A_i$ tel que $u_i(s_{?i},a) \leq
u_i(s)$ (car, comme dans la preuve
de \ref{stupid-remark-best-mixed-strategies}, $u_i(s)$ est combinaison
convexe des $u_i(s_{?i},a)$ dont est supérieur au plus petit d'entre
eux) : c'est-à-dire $\varphi_{i,a}(s) = 0$.  Pour un tel $a$, la
seconde expression $s^\sharp_i(a) = s_i(a) / \big(1 + \sum_{b\in
  A_i}\varphi_{i,b}(s)\big)$ montre, en tenant compte du fait que
$s^\sharp_i = s_i$ puisque $s$ est un point fixe, que $\sum_{b\in A_i}
\varphi_{i,b}(s) = 0$, donc $\varphi_{i,b}(s) = 0$ pour tout $b$.  On
vient de voir que les $\varphi_{i,b}(s)$ sont nuls pour tout $i$ et
tout $b$, et on a expliqué que ceci signifie que $s$ est un équilibre
de Nash.
\end{proof}

\textcolor{red}{Dire quelque chose sur l'algorithme de Lemke-Howson ?}



\subsection{Jeux à somme nulle : le théorème du minimax}\label{zero-sum-games}

\begin{thm}[« du minimax », von Neumann, 1928]\label{theorem-minimax}
Soient $C$ et $C'$ deux convexes compacts dans des espaces affines
réels de dimension finie, et $u\colon C\times C' \to \mathbb{R}$
une application bi-affine (c'est-à-dire, affine en chaque variable
séparément).  Alors
\[
\max_{x\in C} \min_{y\in C'} u(x,y) =
\min_{y\in C'} \max_{x\in C} u(x,y)
\]
\end{thm}
\begin{proof}
Tout d'abord, l'inégalité dans un sens est évidente : on a
\[
\max_{x\in C} \min_{y\in C'} u(x,y)
= \min_{y\in C'} u(x_*,y)
\leq u(x_*,y_*) \leq \max_{x\in C} u(x,y_*) =
\min_{y\in C'} \max_{x\in C} u(x,y)
\]
où $x_* \in C$ est un point où $\max_{x\in C} \min_{y\in C'}
u(x,y)$ est atteint et $y_* \in C'$ un point où $\min_{y\in C'}
\max_{x\in C} u(x,y)$ l'est.  Il s'agit donc de prouver
l'inégalité de sens contraire.

Commençons par supposer que $C$ est l'enveloppe convexe d'un nombre
fini de points $(x_i)_{i\in I}$ et $C'$ de $(y_j)_{j\in J}$, et on
expliquera plus loin comment se ramener à ce cas (même si c'est le
seul qui servira dans le cadre de la théorie des jeux).  Lorsque cette
hypothèse est vérifiée, on va définir une fonction $T\colon C\times C'
\to C\times C'$ de la façon suivante.  Donnons-nous $(x,y) \in C\times
C'$.  Pour chaque $i\in I$, on définit $\varphi_i(x,y) = \max (0,\;
u(x_i,y)-u(x,y))$, et de même on pose $\psi_j(x,y) = \max (0,\;
u(x,y)-u(x,y_j))$.  Posons enfin $T(x,y) = (x^\sharp,y^\sharp)$ où
$x^\sharp$ et $y^\sharp$ (qui dépendent tous les deux de $x$ et $y$ à
la fois, malgré la notation) sont définis comme suit.  On appelle
$x^\sharp$ le barycentre de $x$ affecté du coefficient $1$ et des
$x_i$ (pour $i\in I$) affectés des coefficients respectifs
$\varphi_i(x,y)$, c'est-à-dire $x^\sharp = \frac{x + \sum_{i\in I}
  \varphi_i(x,y)\,x_i}{1 + \sum_{i\in I} \varphi_i(x,y)}$ ; et soit de
même $y^\sharp$ le barycentre de $y$ avec coefficient $1$ et des $y_i$
avec les coefficients $\psi_i(x,y)$.  Clairement, $x^\sharp$ et
$y^\sharp$ sont dans $C$ et $C'$ respectivement (il s'agit de
barycentres à coefficients positifs, c'est-à-dire de combinaisons
convexes).  La fonction $T\colon C\times C' \to C\times C'$ définie
par $T(x,y) = (x^\sharp,y^\sharp)$ est continue.  Par ailleurs, on a
$x^\sharp = x$ si et seulement si $x$ réalise $\max_{\tilde x\in C}
u(\tilde x,y)$ (un sens est évident, et pour l'autre il suffit de se
convaincre que s'il existe $\tilde x$ tel que $u(\tilde x,y) > u(x,y)$
alors il y a un $i$ tel que ceci soit vrai en remplaçant $\tilde x$
par $x_i$, et on a alors $\varphi_i(x,y)>0$ donc $u(x^\sharp,y) >
u(x,y)$) ; et on a un résultat analogue pour $y$.  La fonction $T$
continue du compact convexe $C\times C'$ vers lui-même y admet
d'après \ref{brouwer-fixed-point-theorem} un
point fixe $(x_0,y_0)$, vérifiant donc $(x_0^\sharp, y_0^\sharp) =
(x_0,y_0)$, c'est-à-dire que $u (x_0,y_0) = \max_{x\in C} u(x,y_0) =
\min_{y\in C'} u(x_0, y)$.  On a donc maintenant
\[
\max_{x\in C} \min_{y\in C'} u(x,y)
\geq \min_{y\in C'} u(x_0,y) = u(x_0,y_0)
= \max_{x\in C} u(x,y_0) \geq
\min_{y\in C'} \max_{x\in C} u(x,y)
\]
ce qu'on voulait.

Pour se ramener au cas où $C$ et $C'$ sont enveloppes convexes d'un
nombre fini de points, on observe que pour tout $\varepsilon>0$ il
existe $\Sigma$ et $\Sigma'$ des enveloppes convexes d'un nombre fini
de points (= polytopes) contenues dans $C$ et $C'$ respectivement et
telles que pour tout $x\in C$ on ait $\min_{y\in C'} u(x,y) >
\min_{y\in\Sigma'} u(x,y)-\varepsilon$ et $\max_{x\in C} u(x,y) <
\max_{x\in\Sigma} u(x,y)+\varepsilon$ (explication : il est trivial
que pour chaque $x$ il existe un $\Sigma'$ vérifiant la condition
demandée, le point intéressant est qu'un unique $\Sigma'$ peut
convenir pour tous les $x$ ; mais pour chaque $\Sigma'$ donné,
l'ensemble des $x$ pour lesquels il convient est un ouvert de $C$, qui
est compact, donc un nombre fini de ces ouverts recouvrent $C$, et on
prend l'enveloppe convexe de la réunion des $\Sigma'$ en question ; on
procède de même pour $\Sigma$).  On a alors $\max_{x\in C} \min_{y\in
  C'} u(x,y) > \max_{x\in \Sigma} \min_{y\in \Sigma'} u(x,y) -
\varepsilon$ et une inégalité analogue pour l'autre membre : on en
déduit l'inégalité recherchée à $2\varepsilon$ près, mais comme on
peut prendre $\varepsilon$ arbitrairement petit, on a ce qu'on
voulait.
\end{proof}

\begin{cor}
Soit $C$ un convexe compact dans un espace affine réel de dimension
finie, et $u\colon C^2 \to \mathbb{R}$ une application bi-affine
antisymétrique (i.e., $u(y,x) = -u(x,y)$).  Alors il
existe $x\in C$ tel que pour tout $y\in C$ on ait $u(x,y)\geq 0$
(et la valeur commune des deux membres de l'égalité du
théorème \ref{theorem-minimax} est $0$).
\end{cor}
\begin{proof}
On applique le théorème : il donne $\max_{x\in C}\penalty0 \min_{y\in
  C} u(x,y) = \min_{y\in C}\penalty0 \max_{x\in C} u(x,y)$.  Mais
puisque $u$ est antisymétrique ceci s'écrit encore $\min_{y\in C}y
\max_{x\in C} (-u(y,x))$, soit, en renommant les variables liées,
$\min_{x\in C}\penalty0 \max_{y\in C} (-u(x,y)) = -\max_{x\in
  C}\penalty0 \min_{y\in C} u(x,y)$.  Par conséquent, $\max_{x\in
  C}\penalty0 \min_{y\in C} u(x,y) = 0$ (il est son propre opposé), et
en prenant un $x$ qui réalise ce maximum, on a $\min_{y\in C} u(x,y) =
0$, ce qu'on voulait prouver.
\end{proof}

Avec les hypothèses et notations du corollaire, l'ensemble des $x$
tels que $u(x,y)\geq 0$ pour tout $y\in C$ est un convexe
compact $C_0 \neq \varnothing$ inclus dans $C$.


%
%
%

\section{Théorie de l'induction bien-fondée}\label{section-well-founded-induction}

Le but de cette section est de présenter les outils fondamentaux sur
les graphes orientés bien-fondés (cf. \ref{definitions-graphs})
permettant utiles à la théorie combinatoire des jeux impartiaux.  Il
s'agit notamment de la théorie de l'induction bien-fondée
(cf. \ref{scholion-well-founded-induction}
et \ref{scholion-well-founded-definition}).

\subsection{Graphes orientés bien-fondés}

\begin{defn}\label{definitions-graphs}
Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et
d'une partie $E$ de $G^2$ ne rencontrant pas la diagonale (i.e., un
ensemble de couples $(x,y)$ avec $x\neq y$) : si on préfère, il s'agit
d'un ensemble $G$ muni d'une relation $E$ irreflexive.  Les éléments
de $G$ s'appellent \textbf{sommets} et les éléments de $E$
\textbf{arêtes} de $G$, et si $(x,y) \in E$, on dit qu'il y a une
arête allant du sommet $x$ au sommet $y$, ou arête de source $x$ et de
cible $y$, ou encore que $y$ est \textbf{atteint} par une arête de
source $x$, ou encore que $y$ est un \textbf{voisin sortant} de $x$,
et on notera $\outnb(x) = \{y : (x,y) \in E\}$ l'ensemble des voisins
sortants de $x$.  Un sommet qui n'a pas de voisin sortant est
appelé \textbf{puits} dans $G$.

Un tel graphe est dit \textbf{fini} lorsque $G$ est fini (il est clair
que $E$ l'est alors aussi).  Il est dit \textbf{acyclique} lorsqu'il
n'existe pas de suite finie (« cycle ») $x_0,\ldots,x_{n-1}$ de
sommets telle que $(x_i,x_{i+1})$ soit une arête pour chaque $0\leq
i\leq n-1$, où on convient que $x_n = x_0$.

Un graphe orienté (possiblement infini) est dit \textbf{bien-fondé}
lorsqu'il n'existe pas de suite $x_0,x_1,x_2,\ldots$ de sommets telle
que $(x_i,x_{i+1})$ soit une arête pour tout $i\in\mathbb{N}$ (i.e.,
aucun cycle ni chemin infini, cf. ci-dessous).
\end{defn}

\thingy Il est évident que tout graphe bien-fondé est acyclique (s'il
existe un cycle $x_0,\ldots,x_{n-1}$, on en déduit une suite infinie
en posant $x_i = x_{i\mod n}$) ; pour un graphe \emph{fini}, la
réciproque est vraie : en effet, s'il existe une suite infinie
$x_0,x_1,x_2,\ldots$ avec une arête de $x_i$ à $x_{i+1}$ pour
chaque $i$, il doit exister $n$ tel que $x_n = x_0$, et on obtient
alors un cycle $x_0,\ldots,x_{n-1}$.  En général, cependant, les
notions sont distinctes, l'exemple le plus évident étant sans doute
celui de $\mathbb{N}$ dans lequel on fait pointer une arête de $i$
à $i+1$ pour chaque $i$.

\begin{defn}\label{definition-accessibility-downstream}
Si $G$ est un graphe orienté on appelle \textbf{relation
  d'accessibilité} la clôture réflexive-transitive de la relation
donnée par les arêtes de $G$ : autrement dit, on dit que $y$ est
accessible à partir de $x$ lorsqu'il existe $x {=}
x_0,x_1,\ldots,x_{n-1},x_n {=} y$ tels que pour chaque $i$ le sommet
$x_{i+1}$ soit voisin sortant de $x_i$ (on autorise $n=0$,
c'est-à-dire que chaque sommet est toujours accessible à partir de
lui-même).

L'ensemble des sommets accessibles à partir d'un sommet $x$
s'appellera aussi l'\textbf{aval} de $x$ et pourra se noter
$\downstr(x)$ (c'est donc la plus petite partie $P$ de $G$ telle que
$x\in P$ et $y\in P \limp \outnb(y)\subseteq P$,
cf. \ref{definition-downstream-closed-inductive}).  On peut considérer
l'aval de $x$ comme un sous-graphe induit de $G$ (c'est-à-dire,
considérer le graphe dont l'ensemble des sommets est l'aval de $x$ et
dont les arêtes sont celles qui partent d'un tel sommet).  On
remarquera la convention faite que $x$ appartient à son propre aval.
\end{defn}

\thingy On peut remarquer que la relation d'accessibilité sur $G$ est
antisymétrique (i.e., est une relation d'ordre partiel) si et
seulement si $G$ est acyclique.  Lorsque $G$ est bien-fondé, la
relation d'accessibilité est elle-même bien-fondée (au sens où le
graphe qu'elle définit est bien-fondé).

\begin{defn}\label{definition-downstream-closed-inductive}
Si $G$ est un graphe orienté, on dira qu'un ensemble $P$ de sommets de
$G$ est \textbf{aval-clos} lorsqu'il vérifie la propriété suivante :
« si $x$ est dans $P$ alors tout voisin sortant de $x$ est dans $P$ »
(soit $x\in P \limp \outnb(x)\subseteq P$ ; ou de façon équivalente,
« tout sommet accessible à partir d'un sommet de $P$ est encore
  dans $P$ »,).

Réciproquement, on dira qu'un ensemble $P$ de sommets de $G$ est
\textbf{aval-inductif} lorsqu'il vérifie la propriété suivante : « si
  $x \in G$ est tel que tout voisin sortant de $x$ appartient à $P$,
  alors $x$ lui-même appartient à $P$ » (i.e. « $P$ contient tout
  sommet dont tous les voisins sortants sont dans $P$ »,
soit $\outnb(x)\subseteq P \limp x\in P$).
\end{defn}

\thingy\label{trivial-remark-downstream} Il est clair qu'une
intersection ou réunion quelconque d'ensembles aval-clos est encore
aval-close.  L'aval de $x$ (ensemble des sommets accessibles
depuis $x$) est toujours aval-clos, c'est même la plus petite partie
aval-close contenant $x$, et il est facile de se convaincre qu'un
ensemble de sommets est aval-clos si et seulement si il est une
réunion d'avals.

Pour ce qui est des ensembles aval-inductifs, il est clair qu'une
intersection quelconque d'ensembles aval-inductifs est aval-inductive.
Leur nature, au moins dans un graphe bien-fondé, va être précisée dans
ce qui suit, et ceci justifiera le terme d'« aval-inductif ».

\begin{prop}[induction bien-fondée]\label{well-founded-induction}
Pour un graphe orienté $G$, les affirmations suivantes sont
équivalentes :

\begin{itemize}
\item[(*)]$G$ est bien-fondé.
\item[(\dag)]Tout ensemble \emph{non vide} $N$ de sommets de $G$
  contient un sommet $x \in N$ qui est un puits pour $N$,
  c'est-à-dire qu'il n'existe aucune arête $(x,y)$ de $G$ avec $y \in
  N$ (i.e., aucun voisin sortant de $x$ n'appartient à $N$).
\item[(\ddag)]Si une partie $P\subseteq G$ vérifie la propriété
  suivante « si $x \in G$ est tel que tout voisin sortant de $x$
    appartient à $P$, alors $x$ lui-même appartient à $P$ » (i.e.,
  « $P$ est aval-inductif »,
  cf. \ref{definition-downstream-closed-inductive}), alors $P = G$.
\end{itemize}
\end{prop}
\begin{proof}
L'équivalence entre (\dag) et (\ddag) est complètement formelle : elle
s'obtient en posant $P = G\setminus N$ ou réciproquement $N =
G\setminus P$, en passant à la contraposée, et en passant aussi à la
contraposée à l'intérieur de la propriété d'être aval-inductif (entre
guillemets dans (\ddag)), et encore une fois dans la prémisse de cette
propriété (« tout voisin sortant de $x$ appartient à $P$ » équivaut à
« aucun voisin sortant de $x$ n'appartient à $N$ », i.e., « $x$ est un
  puits pour $N$ »).

Pour montrer que (\dag) implique (*), il suffit d'appliquer (\dag) à
l'ensemble $N := \{x_0,x_1,x_2,\ldots\}$ des sommets d'une suite telle
qu'il y ait une arête de $x_i$ à $x_{i+1}$.

Pour montrer que (*) implique (\dag), on suppose que $N$ est un
ensemble non-vide de sommets sans puits [i.e., puits pour $N$] : comme
$N$ est non-vide, on choisit $x_0 \in N$, et comme $x_0$ n'est pas un
puits on peut choisir $x_1 \in N$ atteignable à partir de $x_0$ par
une arête, puis $x_2 \in N$ atteignable à partir de $x_1$ et ainsi de
suite — par récurrence (et par l'axiome du choix [dépendants]), on
construit ainsi une suite $(x_i)$ de sommets telle qu'il y ait une
arête de $x_i$ à $x_{i+1}$.
\end{proof}

La définition (*) choisie pour un graphe bien-fondé est la plus
compréhensible, mais en un certain sens la définition (\ddag) est « la
  bonne » (en l'absence de l'axiome du choix, il faut utiliser (\dag)
ou (\ddag), et en mathématiques constructives il faut
utiliser (\ddag)).  En voici une traduction informelle :

\begin{scho}\label{scholion-well-founded-induction}
Pour montrer une propriété $P$ sur les sommets d'un graphe bien-fondé,
on peut supposer (comme « hypothèse d'induction »), lorsqu'il s'agit
de montrer que $x$ a la propriété $P$, que cette propriété est déjà
connue de tous les voisins sortants de $x$.
\end{scho}

Exactement comme le principe de récurrence sur les entiers naturels,
le principe d'induction bien-fondée peut servir non seulement à
démontrer des propriétés sur les graphes bien-fondés, mais aussi à
définir des fonctions dessus :

\begin{thm}[définition par induction bien-fondée]\label{well-founded-definition}
Soit $G$ un graphe orienté bien-fondé et $Z$ un ensemble quelconque.
Notons $\outnb(x) = \{y : (x,y) \in E\}$ l'ensemble des
voisins sortants d'un sommet $x$ de $G$ (i.e., des $y$ atteints par une
arête de source $x$).

Appelons $\mathscr{F}$ l'ensemble des couples $(x,f)$ où $x\in G$ et
$f$ une fonction de l'ensemble des voisins sortants de $x$ vers $Z$
(autrement dit, $\mathscr{F}$ est $\bigcup_{x \in G} \big(\{x\}\times
Z^{\outnb(x)}\big)$).  Soit enfin $\Phi\colon \mathscr{F} \to Z$
une fonction quelconque.  Alors il existe une unique fonction $f\colon
G \to Z$ telle que pour tout $x \in G$ on ait
\[
f(x) = \Phi(x,\, f|_{\outnb(x)})
\]
\end{thm}
\begin{proof}
Montrons d'abord l'unicité : si $f$ et $f'$ vérifient toutes les deux
la propriété anoncée, soit $P$ l'ensemble des sommets $x$ de $G$ tels
que $f(x) = f'(x)$.  Si $x \in G$ est tel que $\outnb(x)
\subseteq P$, c'est-à-dire que $f|_{\outnb(x)} =
f'|_{\outnb(x)}$, alors $f(x) = \Phi(x,\,
f|_{\outnb(x)}) = \Phi(x,\, f'|_{\outnb(x)}) = f'(x)$,
autrement dit, $x\in P$.  La phrase précédente affirme précisément que
$P$ vérifie la propriété entre guillemets dans (\ddag)
de \ref{well-founded-induction}, et d'après la proposition en
question, on a donc $P = G$, c'est-à-dire $f = f'$.  Ceci montre
l'unicité.

Pour montrer l'existence, on considère l'ensemble $\mathfrak{E}$ des
fonctions $e\colon H\to Z$ définies sur une partie aval-close $H
\subseteq G$ et telles que pour tout $e(x) = \Phi(x, e|_{\outnb(x)})$
pour tout $x\in H$.  Si $e,e' \in \mathfrak{E}$ alors $e$ et $e'$
coïncident là où toutes deux sont définies, comme le montre l'unicité
qu'on a montrée (appliquée à $e$ et $e'$ sur l'ensemble aval-clos $H
\cap H'$ de définition commun de $e$ et $e'$).  En particulier, la
réunion [des graphes] de tous les $e\in\mathfrak{E}$ définit encore un
élément $f$ de $\mathfrak{E}$, maximal pour le prolongement.  Soit $P$
l'ensemble des $x \in G$ où $f$ est définie.  Si $P$ contient (i.e.,
$f$ est définie sur) tous les voisins sortants d'un certain $x\in G$,
alors $f$ est nécessairement définie aussi en $x$, sans quoi on
pourrait l'y prolonger par $f(x) = \Phi(x,\, f|_{\outnb(x)})$, ce qui
contredirait la maximalité de $f$.  Par induction bien-fondée, on en
conclut $P = G$, c'est-à-dire que $f$ est définie sur $G$ tout entier.
C'est ce qu'on voulait.
\end{proof}

Ce théorème est difficile à lire.  En voici une traduction
informelle :

\begin{scho}\label{scholion-well-founded-definition}
Pour définir une fonction $f$ sur un graphe bien-fondé, on peut
supposer, lorsqu'on définit $f(x)$, que $f$ est déjà défini (i.e.,
connu) sur tous les voisins sortants de $x$ : autrement dit, on
peut librement utiliser la valeur de $f(y)$ sur chaque sommet $y$
voisin sortant de $x$, dans la définition de $f(x)$.
\end{scho}

Voici un exemple d'application de la définition par induction
bien-fondée :

\begin{defn}
Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a
qu'un nombre fini de voisins sortants.  En utilisant le
théorème \ref{well-founded-definition}, on définit alors une fonction
$\rho\colon G \to \mathbb{N}$ par $\rho(x) = \max\{\rho(y) :
y\in\outnb(x)\} + 1$ où il est convenu que $\max\varnothing = -1$ ;
formellement, c'est-à-dire qu'on pose $\Phi(x, r) = \max\{r(y) :
y\in\outnb(x)\} + 1$ avec $\Phi(x, r) = 0$ si $x$ est un puits, et
qu'on appelle $\rho$ la fonction telle que $\rho(x) = \Phi(x,
\rho|_{\outnb(x)})$ dont l'existence et l'unicité sont garanties par
le théorème.  Cette fonction $\rho$ s'appelle la \textbf{fonction
  rang} sur $G$, on dit que $\rho(x)$ est le rang (ou rang bien-fondé)
d'un sommet $x$.
\end{defn}

\thingy Autrement dit, un sommet de rang $0$ est un puits,
un sommet de rang $1$ est un sommet non-puits dont tous les
voisins sortants sont terminaux, un sommet de rang $2$ est un sommet dont
tous les voisins sortants sont de rang $\leq 1$ mais et au moins un est de
rang exactement $1$, et ainsi de suite.

Il revient au même de définir le rang de la manière suivante : le rang
$\rho(x)$ d'un sommet $x$ d'un graphe orienté bien-fondé est la plus
grande longueur possible d'un chemin orienté partant de $x$,
c'est-à-dire, le plus grand $n$ tel qu'il existe une suite
$x_0,x_1,\ldots,x_n$ telle que $x_0 = x$ et que pour chaque $i$ le
sommet $x_{i+1}$ soit atteint par une arête de source $x_i$.

Voici un autre exemple de définition par induction bien-fondée :

\begin{defn}\label{definition-grundy-function}
Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a
qu'un nombre fini de voisins sortants.  En utilisant le
théorème \ref{well-founded-definition}, on définit alors une fonction
$\gamma\colon G \to \mathbb{N}$ par $\gamma(x) = \mex\{\gamma(y) :
y\in\outnb(x)\}$ où, si $S\subseteq\mathbb{N}$, on note $\mex S
:= \mathbb{N}\setminus S$ pour le plus petit entier naturel
\emph{n'appartenant pas} à $S$ ; formellement, c'est-à-dire qu'on pose
$\Phi(x, g) = \mex\{g(y) : y\in\outnb(x)\}$ et qu'on appelle
$\gamma$ la fonction telle que $\gamma(x) = \Phi(x,
\gamma|_{\outnb(x)})$ dont l'existence et l'unicité sont
garanties par le théorème.  Cette fonction $\gamma$ s'appelle la
\textbf{fonction de Grundy} sur $G$, on dit que $\gamma(x)$ est la
valeur de Grundy d'un sommet $x$.
\end{defn}

\thingy En particulier, un sommet de valeur de Grundy $0$ est un
sommet qui n'a que des sommets de valeur de Grundy $>0$ comme voisins
sortants (ceci inclut le cas particulier d'un puits), tandis qu'un
sommet de valeur de Grundy $>0$ est un sommet ayant au moins un sommet
de valeur de Grundy $0$ comme voisin sortant.

On verra que la notion de fonction de Grundy, et particulièrement le
fait que la valeur soit nulle ou pas, a énormément d'importance dans
l'étude de la théorie des jeux impartiaux.  On verra aussi comment la
définir sans l'hypothèse que chaque sommet n'a qu'un nombre fini de
voisins sortants (mais ce ne sera pas forcément un entier naturel).
En attendant, peut se passer de cette hypothèse pour définir isolément
l'ensemble des sommets de valeur de Grundy $0$ :

\begin{defn}\label{definition-grundy-kernel}
Soit $G$ un graphe orienté bien-fondé.  En utilisant le
théorème \ref{well-founded-definition}, on définit alors une partie $P
\subseteq G$ telle que $x \in P$ ssi $\outnb(x) \cap P =
\varnothing$ ; formellement, c'est-à-dire que pour $f\colon \outnb(x)
\to \{0,1\}$ on définit $\Phi(x, f)$ comme valant $1$ si $f$ prend la
valeur $0$ et $0$ si $f$ vaut constamment $1$, et qu'on appelle $f$ la
fonction telle que $f(x) = \Phi(x, f|_{\outnb(x)})$ dont l'existence
et l'unicité sont garanties par le théorème, et enfin on pose $P = \{x
\in G : f(x) = 0\}$.

Les éléments de $P$ seront appelés les \textbf{P-sommets} (ou
P-positions) de $G$, tandis que les éléments du complémentaire
$G\setminus P$ seront appelés \textbf{N-sommets} (ou N-positions)
de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous les voisins
  sortants sont des N-sommets, et un N-sommet est un sommet qui a au
  moins un P-sommet pour voisin sortant}.
\end{defn}

On va voir que dans le jeu exposé en \ref{introduction-graph-game}, si
le graphe est bien-fondé, les P-sommets sont les positions du jeu à
partir desquelles le joueur précédent a une stratégie gagnante, tandis
que les N-sommets sont celles à partir desquelles le joueur suivant
(`N' comme « Next ») a une stratégie gagnante (consistant, justement,
à jouer vers un P-sommet).


\subsection{Généralisations aux graphes non nécessairement bien-fondés}

\begin{defn}\label{definition-wfpart}
L'ensemble des sommets d'un graphe orienté dont l'aval est bien-fondé,
autrement dit, l'ensemble des sommets $x$ tels qu'il n'existe pas de
suite $x_0,x_1,x_2,\ldots$ de sommets où $x_0 = x$ et où pour
chaque $i$ le sommet $x_{i+1}$ est atteint par une arête de
source $x_i$, est appelé la \textbf{partie bien-fondée} du graphe.
\end{defn}

\thingy\label{trivial-remark-wfpart} Il sera utile pour la suite de
remarquer que la partie bien-fondée de $G$ est à la fois aval-close et
aval-inductive (car on peut construire une suite infinie $x_0, x_1,
x_2\ldots$, avec $x_{i+1}$ voisin sortant de $x_i$, commençant par un
$x_0$ donné si et seulement si on peut le faire en commençant pour un
certain voisin sortant $x_1$ de ce $x_0$).

\begin{prop}\label{wfpart-is-smallest-inductive}
Si $G$ est un graphe orienté non supposé bien-fondé, la partie
bien-fondée de $G$ est la plus petite (pour l'inclusion) partie $P$
aval-inductive de $P$ (i.e., vérifiant la propriété « si $x \in
  G$ est tel que tout voisin sortant de $x$ appartient à $P$, alors
  $x$ lui-même appartient à $P$ »,
cf. \ref{definition-downstream-closed-inductive}).
\end{prop}
\begin{proof}
La plus petite partie aval-inductive de $G$ a bien un sens, car
l'intersection de toutes les parties aval-inductives est encore
aval-inductive (cf. \ref{trivial-remark-downstream}).

Si $x$ est un sommet de $G$ et $\downstr(x)$ désigne son aval
(considéré comme sous-graphe induit de $G$), il est clair que pour
toute partie $P$ aval-inductive de $G$, la partie $P \cap \downstr(x)$
de $\downstr(x)$ est aval-inductive dans ce dernier (le point
important étant que les voisins sortants d'un sommet de $\downstr(x)$
dans ce dernier sont les mêmes que ceux dans $G$).  En particulier, si
$\downstr(x)$ est bien-fondé (c'est-à-dire, si $x$ appartient à la
partie bien-fondée de $G$), alors $x$ appartient à toute partie
aval-inductive de $G$.

Mais réciproquement, la partie bien-fondée de $G$ est elle-même
aval-inductive (car si $\downstr(y)$ est bien-fondé pour tout voisin
sortant de $x$, il est clair que $\downstr(x)$ est aussi bien-fondé,
cf. \ref{trivial-remark-wfpart}), donc un sommet qui appartient à
toute partie aval-inductive de $G$ est, en particulier, dans la partie
bien-fondée de $G$.
\end{proof}

\thingy Pour pouvoir énoncer le théorème suivant, on aura besoin de
faire les rappels, définitions et remarques suivants.  Une
\textbf{fonction partielle} $A \dasharrow Z$, où $A$ est un ensemble
quelconque, n'est rien d'autre qu'une fonction définie $D \to Z$ sur
une partie $D\subseteq A$ de $Z$ (appelée \textbf{ensemble de
  définition} de la partie).  Si $f,g\colon A \dasharrow Z$ sont deux
fonctions partielles, on dit que $f$ \textbf{prolonge} $g$ et on note
$f \supseteq g$ ou $g\subseteq f$, lorsque l'ensemble de définition
$D_f$ de $f$ contient celui $D_g$ de $g$ et que $f$ et $g$ coïncident
sur $D_f$ (ceci signifie bien que $f \supseteq g$ en tant qu'ensembles
si on identifie une fonction avec son graphe).  Il s'agit bien sûr là
d'un ordre partiel (sur l'ensemble des fonctions partielles $A
\dasharrow Z$).

Enfin, si $\Phi$ est une fonction partielle elle-même définie sur
l'ensemble des fonctions partielles $A \dasharrow Z$ (cet ensemble est
$\bigcup_{D\subseteq A} Z^D$, si on veut), on dit que $\Phi$ est
\textbf{cohérente} lorsque $\Phi(f) = \Phi(g)$ à chaque fois que $f$
prolonge $g$ et que $\Phi(g)$ est définie (autrement dit, une fois que
$\Phi$ est définie sur une fonction partielle $g$, elle est définie
sur tout prolongement de $g$ et y prend la même valeur que sur $g$ ;
intuitivement, il faut s'imaginer que si $g$ apporte assez
d'information pour décider la valeur de $\Phi(g)$, toute information
supplémentaire reste cohérente avec cette valeur).

\begin{thm}\label{non-well-founded-definition}
Soit $G$ un graphe orienté et $Z$ un ensemble quelconque.
Notons $\outnb(x) = \{y : (x,y) \in E\}$ l'ensemble des
voisins sortants d'un sommet $x$ de $G$ (i.e., des $y$ atteints par une
arête de source $x$).

Appelons $\mathscr{F}$ l'ensemble des couples $(x,f)$ où $x\in G$ et
$f$ une fonction \emph{partielle} de l'ensemble des voisins sortants
de $x$ vers $Z$ (autrement dit, $\mathscr{F}$ est $\bigcup_{x \in G}
\bigcup_{D \subseteq \outnb(x)} \big(\{x\}\times Z^D\big)$).  Soit
enfin $\Phi\colon \mathscr{F} \dasharrow Z$ une fonction partielle
cohérente en la deuxième variable, c'est-à-dire telle que $\Phi(x,f) =
\Phi(x,g)$ dès que $f \supseteq g$ et que $\Phi(x,g)$ est définie.
Alors il existe une plus petite (au sens du prolongement) fonction
partielle $f\colon G \dasharrow Z$ telle que pour tout $x \in G$ on
ait
\[
f(x) = \Phi(x,\, f|_{\outnb(x)})
\]
(au sens où chacun des deux membres est défini ssi l'autre l'est, et
dans ce cas ils ont la même valeur).

Si $\Phi(x,g)$ est défini à chaque fois que $g$ est totale, alors la
fonction $f$ qu'on vient de décrire est définie \emph{au moins} sur la
partie bien-fondée de $G$.
\end{thm}
\begin{proof}
Soit $\mathscr{D}$ l'ensemble des fonctions partielles $f \colon G
\dasharrow Z$.  Pour $f \in \mathscr{D}$, on définit $\Psi(f)$ comme
la fonction partielle $x \mapsto \Phi(x, f|_{\outnb(x)})$.  Remarquons
que si $f$ prolonge $g$ dans $\mathscr{D}$ alors $\Psi(f)$
prolonge $\Psi(g)$ (c'est une traduction de la cohérence supposée
sur $\Phi$).  Le lemme suivant (appliqué à $X=G$, les autres notations
étant inchangées) permet de conclure à l'existence de $f$.

Pour ce qui est de la dernière affirmation, on procède par induction
bien-fondée sur la partie bien-fondée de $G$ : si $f|_{\outnb(x)}$ est
totale, i.e., si $f$ est définie sur chaque voisin sortant de $x$,
alors l'hypothèse faite sur $\Phi$ assure que $f(x)$ est définie, et
l'induction bien-fondée ((\ddag) de \ref{well-founded-induction}
appliqué à l'intersection $P$ de la partie bien-fondée de $G$ et de
l'ensemble de définition de $f$) montre alors que $f$ est définie
partout sur la partie bien-fondée de $G$.
\end{proof}

La démonstration du théorème repose crucialement sur le lemme suivant,
dont on va donner deux démonstrations :
\begin{lem}
Soient $X$ et $Z$ deux ensembles quelconques : notons $\mathscr{D}$
l'ensemble des fonctions partielles $X\dasharrow Z$, qu'on verra comme
des parties de $X\times Z$ ne contenant jamais deux couples $(x,z_1)$
et $(x,z_2)$ avec la même première coordonnée.  (Lorsque $f\supseteq
g$, on dit que « $f$ prolonge $g$ ».)

Soit $\Psi \colon \mathscr{D} \to \mathscr{D}$ une fonction (totale !)
vérifiant : $\Psi$ est \emph{croissante} pour l'inclusion,
c'est-à-dire que si $f$ prolonge $g$, alors $\Psi(f)$
prolonge $\Psi(g)$.  Alors il existe une plus petite (au sens du
prolongement) fonction partielle $f \in \mathscr{D}$ telle que
$\Psi(f) = f$.
\end{lem}
\begin{proof}[Première démonstration]
Montrons d'abord que \emph{si} il existe une fonction partielle $f \in
\mathscr{D}$ telle que $\Psi(f) = f$, ou même simplement $\Psi(f)
\subseteq f$, alors il en existe une plus petite.  Pour cela, il
suffit de considérer l'intersection $h$ de toutes les $f$ telles que
$\Psi(f) \subseteq f$ (considérées comme des parties de $X\times Z$) :
dès lors qu'il existe au moins un $f \in \mathscr{D}$ tel que $\Psi(f)
\subseteq f$, cette intersection $h$ est bien définie et est bien un
élément de $\mathscr{D}$.  Si $\Psi(f) \subseteq f$ alors $h \subseteq
f$ (puisque $h$ est l'intersection des $f$), donc $\Psi(h) \subseteq
\Psi(f)$ (par croissance de $\Psi$), donc $\Psi(h) \subseteq f$ (par
transitivité), et comme ceci est vrai pour tous les $f$ dont
l'intersection est $h$, on a finalement $\Psi(h) \subseteq h$ ; mais
la croissance de $\Psi$ donne alors aussi $\Psi(\Psi(h)) \subseteq
\Psi(h)$, et du coup $\Psi(h)$ fait partie des $f$ qu'on a
intersectées pour former $h$, et on a ainsi $h \subseteq \Psi(h)$ ;
bref, $\Psi(h) = h$, et $h$ est à la fois le plus petit élément $f \in
\mathscr{D}$ vérifiant $\Psi(f) \subseteq f$ (de par sa construction)
et le plus petit vérifiant $\Psi(f) = f$ (puisqu'il vérifie cette
propriété).

Reste à montrer qu'il existe bien une fonction partielle $f$ telle que
$\Psi(f) = f$, ou même simplement $\Psi(f) \subseteq f$.  Pour cela,
on introduit l'ensemble $\mathscr{E}$ des $f \in \mathscr{D}$ qui
vérifient $\Psi(f) \supseteq f$ (inclusion dans le sens opposé du
précédent !).  Notons que $\mathscr{E}$ n'est pas vide puisque
$\varnothing \in \mathscr{E}$ (où $\varnothing$ est la fonction vide,
définie nulle part).

Soit maintenant $\mathfrak{M}$ l'ensemble des applications (totales !)
$T\colon\mathscr{E}\to\mathscr{E}$ qui vérifient (i) $T(f) \supseteq
f$ pour tout $f\in \mathscr{E}$ et (ii) si $f \supseteq g$ alors $T(f)
\supseteq T(g)$.  Ainsi $\id_{\mathscr{E}} \in \mathfrak{M}$
(trivialement) et $\Psi \in \mathfrak{M}$ (par définition de
$\mathscr{E}$ et par croissance de $\Psi$) ; et si $T, T' \in
\mathfrak{M}$ on a $T'\circ T \in \mathfrak{M}$ (en notant $T'\circ T$
la composée).  L'observation suivante sera cruciale : si $g \in
\mathscr{E}$ et $T, T' \in \mathfrak{M}$, alors on a à la fois
$(T'\circ T)(g) \supseteq T(g)$ (d'après (i) pour $T'$) et $(T'\circ
T)(g) \supseteq T'(g)$ (d'après (i) pour $T$ et (ii) pour $T'$).

Affirmation : si $g \in \mathscr{E}$ alors la réunion des $T(g)$ pour
tous les $T\in\mathfrak{M}$ est, en fait, une fonction partielle.  En
effet, l'observation faite ci-dessus montre que si $T, T' \in
\mathfrak{M}$ alors les fonctions partielles $T(g)$ et $T'(g)$ sont
toutes deux restrictions d'une même fonction partielle $(T'\circ
T)(g)$, donc il ne peut pas y avoir de conflit entre leurs valeurs (au
sens où si toutes les deux sont définies en un $x\in X$, elles y
coïncident) — c'est exactement ce qui permet de dire que la réunion
est encore une fonction partielle.  Notons $U(g) :=
\bigcup_{T\in\mathfrak{M}} T(g)$ cette réunion.  On a au moins $U(g)
\in \mathscr{D}$.  Mais en fait, comme $U(g)$ prolonge tous les
$T(g)$, la croissance de $\Psi$ assure que $\Psi(U(g))$ prolonge tous
les $\Psi(T(g))$, qui prolongent eux-mêmes les $T(g)$ (puisque $T(g)
\in \mathscr{E}$), bref $\Psi(U(g)) \supseteq U(g)$ et ainsi $U(g) \in
\mathscr{E}$.

Mais alors $U \in \mathfrak{M}$ (on vient de voir que $U$ est une
fonction $\mathscr{E}\to\mathscr{E}$, et les propriétés (i) et (ii)
sont claires).  En particulier, $\Psi\circ U \in \mathfrak{M}$, donc
$(\Psi\circ U)(g)$ fait partie des $T(g)$ dont $U(g)$ est la réunion,
et on a donc $(\Psi\circ U)(g) \subseteq U(g)$, l'inclusion réciproque
ayant déjà été vue (et de toute façon on n'en a pas besoin).  On a
donc bien trouvé une fonction partielle $f := U(\varnothing)$ telle
que $\Psi(f) \subseteq f$ (même $\Psi(f) = f$).
\end{proof}

\begin{proof}[Seconde démonstration]
On utilise la notion d'ordinaux.  On pose $f_0 = \varnothing$, et par
induction sur l'ordinal $\alpha$ on définit $f_{\alpha+1} =
\Psi(f_\alpha)$ et si $\delta$ est un ordinal limite alors $f_\delta =
\bigcup_{\gamma<\delta} f_\gamma$.  On montre simultanément par
induction sur $\alpha$ que $f_\alpha$ est bien définie, est une
fonction partielle, et, grâce à la croissance de $\Psi$, prolonge
$f_\beta$ pour chaque $\beta<\alpha$ (c'est ce dernier point qui
permet de conclure que $\bigcup_{\gamma<\delta} f_\gamma$ est une
fonction partielle lorsque $\delta$ est un ordinal limite : la réunion
d'une famille totalement ordonnée pour l'inclusion de fonctions
partielles est encore une fonction partielle).  Les inclusions
$f_\beta \subseteq f_\alpha$ pour $\beta<\alpha$ ne peuvent pas être
toutes strictes sans quoi on aurait une surjection d'un ensemble sur
la classe des ordinaux.  Il existe donc $\tau$ tel que $f_{\tau+1} =
f_\tau$, c'est-à-dire $\Psi(f_\tau) = f_\tau$.  D'autre part, si
$\Psi(h) = h$, alors par induction sur $\alpha$ on montre $f_\alpha
\subseteq h$ pour chaque $\alpha$ (l'étape successeur étant que si
$f_\alpha \subseteq h$ alors $f_{\alpha+1} = \Psi(f_\alpha) \subseteq
\Psi(h) = h$), donc en particulier $f_\tau \subseteq h$, et $f_\tau$
est bien le plus petit $f$ tel que $\Psi(f) = f$.
\end{proof}



\subsection{Écrasement transitif}

\begin{defn}\label{definition-transitive-collapse}
Soit $G$ un graphe orienté bien-fondé.  En utilisant le
théorème \ref{well-founded-definition} (modulo la remarque qui suit),
on définit alors une fonction $f$ sur $G$ par $f(x) = \{f(y) :
y\in\outnb(x)\}$.  L'image $f(G)$ de $G$ par la fonction $f$ (c'est-à-dire
l'ensemble des $f(x)$ pour $x\in G$) s'appelle l'\textbf{écrasement
  transitif} ou \textbf{écrasement de Mostowski} de $G$, tandis que
$f$ s'appelle la fonction d'écrasement, et la valeur $f(x)$ (qui n'est
autre que l'écrasement transitif de l'aval de $x$ vu comme un graphe
orienté) s'appelle l'écasement transitif du sommet $x$.

On considérera l'écrasement $f(G)$ de $G$ comme un graphe orienté, en
plaçant une arête de $u$ vers $v$ lorsque $v \in u$ ; autrement dit,
lorsque $v = f(y)$ et $u = f(x)$ pour certains $x,y$ de $G$ tels qu'il
existe une arête de $x$ vers $y$.
\end{defn}

\thingy En particulier, un puits a pour écrasement $\varnothing$, un
sommet qui n'a pour voisins sortants que des sommets terminaux a pour
écrasement $\{\varnothing\}$, un sommet qui n'a pour voisins sortants
que de tels sommets a pour écrasement $\{\{\varnothing\}\}$ tandis que
s'il a aussi des sommets terminaux pour voisins sortants ce sera
$\{\varnothing,\penalty0 \{\varnothing\}\}$, et ainsi de suite.

La terminologie « transitif » fait référence au fait qu'un ensemble
$E$ est dit transitif lorsque $v \in u\in E$ implique $v \in E$ (de
façon équivalente, $E \subseteq \mathscr{P}(E)$ où $\mathscr{P}(E)$
est l'ensemble des parties de $E$) : c'est le cas de $f(G)$ ici.

Il y a une subtilité ensembliste dans la définition ci-dessus, c'est
qu'on ne peut pas donner \textit{a priori} un ensemble $Z$ dans lequel
$f$ prend sa valeur : il faut en fait appliquer une généralisation
de \ref{well-founded-definition} où $Z$ est remplacé par l'univers de
tous les ensembles : nous ne rentrerons pas dans ces subtilités, et
admettrons qu'il existe bien une unique fonction $f$ sur $G$ qui
vérifie $f(x) = \{f(y) : y\in\outnb(x)\}$ pour chaque $x\in G$.

\begin{defn}
Un graphe orienté $G$ est dit \textbf{extensionnel} lorsque deux
sommets $x$ et $x'$ ayant le même ensemble de voisins sortants ($\outnb(x)
= \outnb(x')$) sont égaux.
\end{defn}

Pour bien comprendre et utiliser la définition ci-dessus, il est
pertinent de rappeler que \emph{deux ensembles sont égaux si et
  seulement si il sont les mêmes éléments} (\textbf{axiome
  d'extensionalité}).

\begin{prop}\label{extensional-iff-collapse-injective}
Un graphe orienté bien-fondé est extensionnel si et seulement si sa
fonction d'écrasement $f$ définie
en \ref{definition-transitive-collapse} est injective.
\end{prop}
\begin{proof}
Si $f$ est injective et si $\outnb(x) = \outnb(x')$ alors en
particulier $f(x) = f(x')$ (puisque $f(x)$ est définie comme l'image
par $f$ de $\outnb(x)$), donc $x = x'$.  Ceci montre que $G$ est
extensionnel.

Réciproquement, $G$ extensionnel et montrons que $f$ est injective,
c'est-à-dire que $f(x) = f(x')$ implique $x = x'$.  On va procéder par
induction bien-fondée sur le graphe $G^2$ dont les sommets sont les
couples $(x,x')$ de sommets de $G$, avec une arête de $(x,x')$ vers
$(y,y')$ lorsqu'il y en a de $x$ vers $y$ \emph{et} de $x'$
vers $y'$ : il est clair que $G^2$ est bien-fondé ; soit $P$
l'ensemble des sommets $(x,x')$ de $G^2$ tels que $f(x) = f(x')$
implique $x=x'$ (autrement dit, l'ensemble des sommets tels que
$(x,x')$ tels que $x=x'$ \emph{ou bien} $f(x) \neq f(x')$).  Soit
$(x,x')$ un sommet de $G^2$ dont tous les voisins sortants vérifient
l'hypothèse d'induction (i.e., appartiennent à $P$) : on suppose $f(x)
= f(x')$ et on veut montrer $x = x'$ pour pouvoir conclure $P = G^2$.
Or $f(x) \subseteq f(x')$ signifie que tout $f(y) \in f(x)$ appartient
à $f(x')$, c'est-à-dire que pour tout voisin sortant $y$ de $x$ il
existe un voisin sortant $y'$ de $x'$ pour lequel $f(y) = f(y')$, et
l'hypothèse d'induction montre alors $y = y'$ : ainsi, $\outnb(x)
\subseteq \outnb(x')$, et par symétrie, $f(x) = f(x')$ montre
$\outnb(x) = \outnb(x')$ donc, par extensionalité de $G$, on a $x =
x'$ comme on le voulait.
\end{proof}

\thingy Si $G$ est un graphe orienté (non nécessairement bien-fondé),
et si $\sim$ est une relation d'équivalence sur l'ensemble des sommets
de $G$, on peut définir un \emph{graphe quotient} $G/\sim$ dont les
sommets sont les classes d'équivalences pour $\sim$ de sommets de $G$
et dont les arêtes sont les couples $(\bar x,\bar y)$ de classes
telles qu'il existe une arête $(x,y)$ (i.e., de $x$ vers $y$) dans $G$
avec $\bar x$ classe de $x$ et $\bar y$ celle de $y$ ; si ce graphe
est extensionnel, on peut dire abusivement que $\sim$ l'est :
concrètement, cela signifie que pour tous $x,x' \in G$, si pour chaque
voisin sortant $y$ de $x$ il existe un voisin sortant $y'$ de $x'$
avec $y \sim y'$ et que la même chose vaut en échangeant $x$ et $x'$,
alors $x \sim x'$.  Une intersection quelconque de relations
d'équivalence extensionnelles sur $G$ est encore une relation
d'équivalence extensionnelle, donc il existe une plus petite relation
d'équivalence extensionnelle $\equiv$ sur $G$, c'est-à-dire un plus
grand quotient $G/\equiv$ de $G$ qui soit extensionnel (« plus grand »
au sens où tout quotient de $G$ par une relation d'équivalence se
factorise à travers ce quotient $G/\equiv$).

Le contenu essentiel de la
proposition \ref{extensional-iff-collapse-injective} est que
l'écrasement transitif $f(G)$ d'un graphe $G$ bien-fondé réalise ce
plus grand quotient extensionnel $G/\equiv$ : la relation $f(x) =
f(x')$ sur $G$ est précisément la plus petite relation d'équivalence
extensionnelle $\equiv$ sur $G$ (en effet, la relation $f(x) = f(x')$
est évidemment extensionnelle, donc contient $\equiv$ par définition
de celle-ci, mais l'écrasement de $G/\equiv$ est le même que celui
de $G$, et comme la fonction d'écrasement est injective sur
$G/\equiv$, on a bien $f(x) = f(x')$ ssi $x\equiv x'$).


%
%
%

\section{Théorie combinatoire des jeux impartiaux à information parfaite}\label{section-combinatorial-impartial-games}

\subsection{Généralités}

\begin{defn}\label{definition-impartial-combinatorial-game}
Un jeu \textbf{impartial à information parfaite} est un graphe
orienté $G$ muni d'un sommet $x_0$ appelé \textbf{position initiale}
et vérifiant de plus :
\begin{itemize}
\item pour un jeu « court » : $G$ est fini acyclique (ou de façon
  équivalente, fini et bien-fondé) ;
\item pour un jeu « terminant » : $G$ est bien-fondé ;
\item pour un jeu « fini à boucles » : $G$ est fini.
\item pour un jeu « non nécessairement terminant » : (aucune
  hypothèse).
\end{itemize}
On supposera de plus que tout sommet de $G$ est accessible à partir
de $x_0$ (si ce n'est pas le cas, il reviendra au même de supprimer
tous les sommets inaccessibles, assurant du coup cette hypothèse).
\end{defn}

La terminologie est malheureusement peu standardisée : la plupart des
auteurs font implicitement une des deux hypothèses
(« bien-fondé »=« terminant », et/ou « fini ») sur le jeu $G$, le cas
« court » étant la conjonction des deux.  Ici, on fera le plus souvent
l'hypothèse que $G$ est terminant ; on attire l'attention sur le fait
que cela signifie que $x_0$ appartient à la partie bien-fondée
(cf. \ref{definition-wfpart}) du graphe $G$.

\begin{defn}
Pour un jeu $G$ comme
en \ref{definition-impartial-combinatorial-game}, une
\textbf{stratégie} est une fonction partielle $\varsigma\colon G
\dasharrow G$ telle que $\varsigma(x)$ soit, s'il est défini, un
voisin sortant de $x$ (s'il n'est pas défini, il faut comprendre que
le joueur est forfait).

Une \textbf{partie} de $G$ est une suite finie ou infinie $(x_i)$ de
sommets de $G$ telle que $x_0$ soit la position initiale et que pour
chaque $i$ pour lequel $x_{i+1}$ soit défini, ce dernier soit un
voisin sortant de $x_i$.  Lorsque le dernier $x_i$ défini l'est pour
un $i$ pair, on dit qu'Alice \textbf{perd} et que Bob \textbf{gagne},
tandis que lorsque le dernier $x_i$ défini l'est pour un $i$ impair,
on dit qu'Alice gagne et que Bob perd ; enfin, lorsque $x_i$ est
défini pour tout entier naturel $i$ (ce qui ne peut pas se produire si
$G$ est bien-fondé), on dit que la partie est nulle ou que les deux
joueurs \textbf{survivent} sans gagner.  Lorsque de plus
$\varsigma(x_i) = x_{i+1}$ pour chaque $i$ pair pour lequel $x_i$ est
défini, on dit qu'Alice a joué la partie selon la stratégie
$\varsigma$ ; tandis que si $\tau(x_i) = x_{i+1}$ pour chaque $i$
impair pour lequel $x_i$ est défini, on dit que Bob a joué la partie
selon la stratégie $\tau$.

Si $\varsigma$ et $\tau$ sont deux stratégies, on définit $\varsigma
\ast \tau$ comme la partie jouée lorsque Alice joue $\varsigma$ et Bob
joue $\tau$ : autrement dit, $x_0$ est la position initiale du jeu,
et, si $x_i$ est défini, $x_{i+1}$ est défini par $\varsigma(x_i)$ si
$i$ est pair et $\tau(x_i)$ si $i$ est impair (si $x_{i+1}$ n'est pas
défini, la suite s'arrête là).

La stratégie $\varsigma$ est dite \textbf{gagnante pour Alice} lorsque
Alice gagne toute partie où elle joue selon $\varsigma$.  La stratégie
$\tau$ est dite \textbf{gagnante pour Bob} lorsque Bob gagne toute
partie où il joue selon $\tau$.  On définit de même une stratégie
survivante (c'est-à-dire, permettant d'assurer au moins le nul) pour
Alice, resp. Bob.
\end{defn}

\begin{thm}\label{determinacy-of-perfect-information-games}
Soit $G$ un jeu impartial à information parfaite : exactement l'une
des trois affirmations suivantes est vraie :
\begin{itemize}
\item Alice possède une stratégie gagnante,
\item Bob possède une stratégie gagnante,
\item Alice et Bob possèdent une stratégie survivante — ce cas ne
  pouvant pas se produire si $G$ est terminant.
\end{itemize}
\end{thm}
\begin{proof}
\textcolor{red}{...}
\end{proof}

%
%
%
\end{document}