MPRI: Modèle de Jeux et de mécanismes

20/01/06: Introduction au modèle des jeux et des Mécanismes

Modèle pour l'étude de protocoles informatiques: étant donné un jeu, on cherche un équilibre, ou étant donné un équilibre on recherche jeu (mécanisme) dont l'équilibre est celui qui est donné.

Jeux Matriciels, Exemple de mécanismes (Enchères, Anti-Spam)
Equilibres de Nash: exemples de jeux associés à MaxSAT et MaxCut.
Jeux à somme nulle: dualité, MaxMin=MinMax.
Rappels de programmation linéaire et de dualité (.ppt), (.pdf)
Cours 1 (.ppt), (.pdf)

Exercice: stratégie optimale pour le jeu de Morra, et le jeu Nord-Est pour certains cas.

27/01/06: Existence d'équilibres

Le problème est NP et coNP.

Existence:
Lemme de Sperner,
Theoremes de Brouwer, Kakutani,
Nash,
Cours 2 (.ppt),(.pdf)

03/02/06: Calculs d'équilibres

Calcul: algorithme Lemke-Howson
Classes PPA et PPAD
Approximation d'équilibres (Lipton)
Cours 3 (.ppt),(.pdf)

10/02/06: Jeux sous forme extensive et Approximation

Approximation d'équilibres: Lipton, Vempala, Joueur fictif
Equilibres Arrow-Debreu
Autres Equilibres (.pdf)
Jeux sous forme extensive et logique Cours 4 (.pdf)

Cours global: Game theory: proofs, testing and equilibria.