Logique et Jeux : 2008-2009
Michel de Rougemont
Le cours présente plusieurs notions de jeux, liées à des
notions logiques et à des notions de
complexité. Ces notions éclairent différents modèles de calcul dans lesquels on
peut analyser des algorithmes et comprendre leurs limites.
La première partie concerne les jeux E/A, où un jour E
(Exists) et un joueur A (pour tout) sont opposés. Le joueur E essaye de montrer
que une formule alternée est vraie sur une structure.
La deuxième partie concerne les jeux d’Ehrenfeucht-Fraisse
dans le contexte de la définissabilité logique. Ces jeux à information complète
permettent de montrer des résultats négatifs pour différentes logiques et certains résultats de complexité.
La troisième partie est consacrée aux Preuves Interactives,
à PCP et aux Testeurs.
Dans la quatrième
partie, on présente les jeux matriciels à N joueurs et les équilibres de
Nash. On montre que la recherche d’un optimum local dans un problème
d’optimisation est équivalente à la recherche d’un équilibre de Nash. On
généralise aux jeux itérés, sous forme extensive et sous forme logique. Dans ce
cadre on explicite la complexité des stratégies et on décrit les équilibres
restreints à des joueurs dont la capacité de calcul est limitée. On s’intéresse
enfin aux mécanismes : ce sont des
protocoles qui déterminent des jeux à N joueurs pour lesquels on recherche des
équilibres d’un certain type. La
régulation des réseaux, la sécurité informatique et plus généralement
l’informatique distribuée décrivent des mécanismes. La logique et la complexité
permettent de comprendre les limitations des mécanismes et les langages pour
les définir.
Partie 1 : Jeux E/A (Exists/for All)
- QSAT
est PESPACE complet, ainsi que SSAT.
- Jeu
Géographie est PESPACE complet.
Partie 2 : Jeux d’Ehrenfeucht-Fraisse
- Logique
du 1er ordre
- Logique
du point fixe, :Games for Formula length, Dynamic Complexity
- Logique
Monadique du 2nd ordre
- Structures de mots d’arbres et de graphes.
Automates d’arbres :Automata
on Tree-like structures ,Query Automata,
Walking Automata, Queries
in XML
- Structures compressées : Definability and Compression, Automata on compressed structures
Partie 3 : Protocoles
Interactifs
- Classes
probabilistes : PP, BPP, RP. Exemples d’algorithmes probabilistes :
marche aléatoire et couplage parfait.
- Preuves
Interactives : IP=PESPACE
- PCP PCP by GAP
amplification
- Testeurs : : Regular words, Regular
trees, Equivalence testing
Partie 4 : Equilibres de Nash et Mécanismes
- Programmation
linéaire et dualité, Notes de Williamson
- Jeux
à somme nulle. Théorème Minmax: transparents (.ppt)
ou (.pdf)
- Jeux
matriciels, stratégies, Equilibres. transparents
(.ppt) ou (.pdf)
- Le
lemme de Sperner, les théorème de Brouwer et Kakutani. Les équilibres de
Nash et de Arrow-Debreu:
Notes de Papadimitriou,
Non-calculabilité de l'équilibre (Richter et Wong),
Calcul P d'un équilibre Arrow-Debreu, Williamson
chapitres 14 et 15
Calcul P d'un équilibre Arrow-Debreu, Algorithme
Devanur et al. (Transparents)
- Nash
et l’optimisation locale. Approximation de Nash et de problèmes d’optimisation.
transparents (.ppt) ou (.pdf),
Lipton 2003
- Jeux
itérés, sous forme extensive (transparents) et
logique. Complexité des stratégies et des équilibres.Exemple
: jeu NE
- Autres équilibres (Corréles, Séquentiels, Bayes)
(transparents)
- Mécanismes
véraces, transparents :Mécanismes
de Vickrey, Enchères combinatoires, D. Lehmann
- Stratégies
pour Enchères combinatoires,Stratégies informatiques, T. Sandholm,
Enchères combinatoires, N. Nisan,
Addwords
de Google
- R.
Lassaigne et M. de Rougemont , Logique et Complexité, Springer 2003
2. M.J. Osborne and A.
Rubinstein, A Course in Game theory, MIT Press, 1994 (ISBN
0-262-65040-1)
3. MAS-COLLEL, A., M.D.
WHINSTON and J.R. GREEN, Microeconomic Theory, Oxford University Press,
1996.
Projets :
Site du DEA de Logique, Paris VII