Courses on Game Theory and Types
(year 2008-2009, 1rst semester)
Pierre Lescanne
The Internet is an equilibrium we just have to identify the game.
Scott Shenker (U. of California, Berkeley) cited by Papadimitriou in Algorithmic Game Theory p. xiv
Goal
The goal of the course is to introduce
- game theory à la Nash and von Neumann, i.e. equilibria known as Nash equilibria
- a new extension called CP games i.e. games with conversion and preference,
- computer assisted proofs for games, especially sequential games, we will use the proof assistant COQ.
The course will be taught in English.
In the following section we will see:
Description
Teaching
The first part of the course will be interactive, aka reading group.
- Students will be assigned a paper or a chapter in a book for each class.
- Students shall read this paper/chapter.
- The paper/chapter will be commented in the next class.
- In general we skip exercises, except if mention one explicitly. Students are advised to make them anyway.
As a consequence the group of students will be restricted to 12-15 students with priority to M2 students.
The second part of the course will be presentations of papers by the students.
The evaluation will be
- by the participation to the reading in the first part,
- by the quality of the student presentation (oral and written), in the second part
Four reference books:
- GTE: Herbert Gintis "Game Theory Evolving", Princeton University Press, 2000
- MOGT: Martin Osborne "Introduction to Gamer Theory", Oxford University Press, 2004.
- ORCGT: M. J. Osborne and A. Rubinstein, "A Course in Game Theory", The MIT Press, 1994.
- Coq'Art: Yves
Bertot, Pierre Castéran, "Interactive Theorem Proving and
Program Development Coq'Art: The Calculus of Inductive
Constructions", 2004, XXV, 469 p., Hardcover , ISBN: 3-540-20854-2
Structure of the course
Planning
- 19/09/08: reading of GTE chap1
- 26/09/08: reading of GTE end of Chap1 beginning of Chap 2, beginning of MOGT Chap2.
- 10/10/08: no class
- 17/10/08: read MOGT Chap 5 + MOGT 177.2.
- 31/10/08: class by Stéphane Le Roux
- Wednesday 12/11/08: seminar at IXXI on Games theory at 10h30,
especially "Reasoning in infinite extensive games" (talk in French,
slights in English
Course 1, Introduction to Game Theory
Read
Course 2, Nash Equilibrium Theory
Read
Course 3, Nash Equilibrium Theory
Read
- We will continue reading MOGT Chap 2 (in directory MOGT)
- Exercises 3.3 (p. 28-29) in GTE, (Competition on Main Street)
- Exercise MOGT 34.1 (Guessing two third of the average)
Course 4, Extensive Games
Read
- MOGT, Chap 5 (see also directory MOGT)
- Exercises 3.13 (p. 35-36) in GTE (The Illogic of Conflict Escalation), read also this
- Exercise MOGT 177.2 (The Rotten kids theorem)
Course 5, CP Games
Read
Course 6, Abstract games in trees and in graphs (October 31)
This course will be delivered by Stéphane Le Roux.
Two parts will compose the 2-hour class.
I) Multi-player games in trees
- a) Definitions: abstraction of sequential games.
- b) Results: necessary and sufficient condition for every
sequential game to have a Nash equilibrium. (This is a generalisation
of Kuhn's theorem.)
II) Uni-player games in graphs
- a) Definitions: dalographs and their equilibria, etc.
- b) Results: necessary/sufficient conditions for every dalograph to have anequilibrium.
Part I corresponds to chapter 4 in my thesis.
Part II corresponds to chapter 6 in my thesis.
To prepare the class, you may read the main definitions and results of
both chapters. No need to read the proofs or any other detail. Chapter
4, no need to read section 4.4 and the Coq-related formalism. Chapter
6, you may skip section 6.5, and even sections 6.3 and 6.6 if you do
not have time.
Do not hesitate to ask questions at stephane.le.roux at ens-lyon.fr
Course 7, Bayesian games and Mixed Strategies
Read
- MOGT, Chap 4 (available also in directory MOGT)
Course 6, Infinite Games
Read
Course 7, Games and Common Knowledge
Read
- Aumann theorem after Lescanne, Onno et Vestergaard
Notes
Assignment of papers
Classification
During the next class you will be asked to choose among the following
alphabetically ordered keywords in order for me to assign you a paper.
- application to biology
- application of computational game theory to the Internet
- computational game theory
- economics
- experimental approach to games,
- game and rationality
- history of game theory
- others
Rules of the game
Each student is assigned to present the paper. He (she) should read how to do.
The note by Ian Parberry is a useful guide.
He (she) writes a presentation. Another (other) student (s) is (are) asked to
evaluate (referee) the written and the oral presentation using a
prepared form in pdf and in tex
Assignments
This file contains the lists of assigned papers.
Papers
Last modified: Sat October 20 2008