Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-20-1 [2018/09/08 19:33]
zielonka [Planning prévisionnel détaillé]
cours:c-2-20-1 [2019/09/15 00:35] (current)
berwanger [Bibliographie]
Line 5: Line 5:
  
  
-Responsable: W. Zielonka, professeur à Paris 7+Responsable: W. Zielonka, professeur à l'Université Paris-Diderot 
  
  
  
-==== Intervenants prévus pour 2018-2019 ====+==== Intervenants prévus pour 2019-2020 ====
  
-   * [[http://www.lsv.ens-cachan.fr/~dwb|Dietmar Berwanger]] chargé de recherche CNRS, LSV (l'ENS Cachan) [12h], +   * [[http://www.lsv.fr/~dwb|Dietmar Berwanger]] chargé de recherche CNRS, LSV (ENS Paris-Saclay) [12h], 
-   * [[http://www.irif.fr/~zielonka|Wieslaw Zielonka]] professeur, IRIF (Université Paris Diderot) [12h].+   * [[http://www.irif.fr/~serre|Olivier Serre]] directeur de recherche CNRS, IRIF (Université Paris Diderot) [12h].
 ==== Objectifs ==== ==== Objectifs ====
  
Line 19: Line 19:
 Cependant, depuis le début des années 1980, la théorie des jeux occupe une place de plus en plus importante en informatique et l'objectif de ce cours est de présenter divers modèles de jeux ainsi que des applications de cette théorie dans plusieurs domaines de l'informatique. Cependant, depuis le début des années 1980, la théorie des jeux occupe une place de plus en plus importante en informatique et l'objectif de ce cours est de présenter divers modèles de jeux ainsi que des applications de cette théorie dans plusieurs domaines de l'informatique.
  
-Une partie centrale de ce cours portera sur des jeux infinis sur des graphes finis ou infinis. Cette théorie possède des applications  +Le cours portera sur des jeux infinis sur des graphes finis ou infinis. Cette théorie possède des applications pour la théorie des automates (automates d'arbre), la vérification de programme (mu-calcul ou autres logiques).
-pour la théorie des automates (automates d'arbre), la vérification de programme (mu-calcul ou autres logiques).+
  
-Ce cours proposera également une étude approfondie de plusieurs classes de jeux (et de leurs combinaisons): jeux stochastiques, jeux muni de fonction de paiement, jeux à information imparfaite+Nous proposerons une étude approfondie de plusieurs classes de jeux (et de leurs combinaisons): jeux stochastiques, jeux muni de fonction de paiement, jeux à information imparfaite.
- +
-La théorie classique des jeux sera également abordée en donnant les grands principes des jeux sous forme normale (et des notions d'équilibre) ainsi qu'une introduction au mecanism design.+
  
  
Line 57: Line 54:
 de comportement optimal dans ces jeux et les questions algorithmiques de comportement optimal dans ces jeux et les questions algorithmiques
 associées.  associées. 
- 
- 
-=== Introduction à la théorie des jeux classique === 
- 
-Les points suivants seront abordés:  
-   * Jeux en forme stratégique et en forme extensive. 
-   * Existence d'un équilibre de Nash (théorème de Nash). 
-   * Jeux à deux joueurs à somme nulle avec un nombre fini de stratégies, théorème minimax de von Neumann. 
- 
  
  
 ==== Planning prévisionnel détaillé ==== ==== Planning prévisionnel détaillé ====
  
-Les séances d'une durée de trois heures.  +Les séances auront une durée de trois heures.  
  
-  * 13/09 (Wieslaw Zielonka)  perfect information games : finite games, combinatorial games, reachability games, Buchi games +  * 10/09 (Olivier Serre)  Introduction, reachability games 
-  * 20/09 (Wieslaw Zielonka)  multi-player games and Nash equilibriabackward induction +  * 17/09 (Olivier Serre)  Büchi games, parity games 
-  * 27/09 (Dietmar Berwangervérification and synthesis, parity games +  * 24/09 (Olivier Serre Tree automata 
-  * 04/10  (Dietmar Berwanger) parity games : application to automata theory, energy games +  * 1/10  (Nathanael Fijalkow: guest lectureQuasipolynomial time algorithms for parity games 
-  * 11/10  (Dietmar Berwanger) mean-payoff games +  * 8/10  (Dietmar Berwanger) Mean-payoff, simple stochastic games 
-  * 18/10  (Wieslaw Zielonkasimple stochastic games +  * 22/10  (Dietmar BerwangerGames for verification and synthesis 
-  * 25/10 (Wieslaw Zielonkamatrix games, concurrent reachability games +  * 29/10 (Dietmar BerwangerImperfect information I 
-  * 08/11 (Dietmar Berwanger) imperfect information games +  * 5/11 (Dietmar Berwanger) Imperfect information II 
  
  
Line 86: Line 74:
  
  
-Dietmar Berwanger donnera le cours **en anglais**. Wieslaw Zielonka donnera le cours en français.+Dietmar Berwanger donnera le cours **en anglais**. Olivier Serre et Nathana&etrema;l Fijalkow donneront le cours en français ou anglais.
  
 Les étudiants seront autorisés à rédiger leur examen en anglais ou en français. Les étudiants seront autorisés à rédiger leur examen en anglais ou en français.
Line 95: Line 83:
  
    * [[http://www.lsv.fr/~dwb/|Dietmar Berwanger]].    * [[http://www.lsv.fr/~dwb/|Dietmar Berwanger]].
-   * [[http://www.irif.fr/~zielonka|Wieslaw Zielonka]].+   * [[http://www.irif.fr/~serre|Olivier Serre]].
  
 Cela dit, il s'agira plus de notes ou de copies de transparents que d'un polycopié détaillé. Cela dit, il s'agira plus de notes ou de copies de transparents que d'un polycopié détaillé.
Line 118: Line 106:
 ==== Bibliographie ==== ==== Bibliographie ====
  
-   * Roger B. Myerson, //Game theory. Analysis of Conflict,//Harvard University Press. +   * Krzysztof R Apt and Erich Grädel, //Lectures in Game Theory for Computer Scientists,// Cambridge University Press, 2011. 
-   * Michael Maschler, Eilon Solan, Shmuel Zamir, //Game theory,//Cambridge University Press +   * Roger B. Myerson, //Game theory. Analysis of Conflict,// Harvard University Press, 1991
-   * Martin J. Osborne and Ariel Rubinstein, //A Course in Game Theory,//The MIT Press+   * Michael Maschler, Eilon Solan, Shmuel Zamir, //Game theory,// Cambridge University Press, 2013. 
-   * Drew Fudenberg and Jean Tirole//Game theory,//The MIT Press.    +   * Martin J. Osborne and Ariel Rubinstein, //A Course in Game Theory,// The MIT Press, 1994 
-   * Erich Grädel, Wolfgang Thomas, Thomas Wilke (eds.), //Automata, Logics, and Infinite Games: A Guide to Current Research//[outcome of a Dagstuhl seminarFebruary 2001], Lecture Notes in Computer Science 2500, Springer 2002. +   * Erich Grädel, Wolfgang Thomas, Thomas Wilke (eds.), // Automata, Logics, and Infinite Games: A Guide to Current Research//, LNCS 2500, Springer 2002. 
-   * Erich Grädel et al., //Finite Model Theory and Its Applications,//EATCS Texts in Theoretical Computer Science, Springer 2007.+   * Uri Zwick and Mike Paterson, //The Complexity of Mean Payoff Games on Graphs,// Theoretical Computer Science 158no. 1–2: 343–59. Springer 1996. 
  
  
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA