Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

JEUX SOUS FORME NORMALE par Tristan Tomala Table des matières 1. Préliminaires.

JEUX SOUS FORME NORMALE par Tristan Tomala Table des matières 1. Préliminaires. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Jeux à somme nulle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3. Jeux à somme non nulle. . . . . . . . . . . . . . . . . . . . . . . . . . 15 4. Jeux ﬁnis et stratégies mixtes. . . . . . . . . . . . . . . . . . . . 19 5. Jeux à information parfaite. . . . . . . . . . . . . . . . . . . . . . . 22 1. Préliminaires On appelle jeu sous forme normale ou jeu sous forme stratégique la donnée d’un ensemble N de joueurs, d’une famille d’ensembles de stratégies (ou d’actions) (Ai)i∈N et d’une famille de fonctions de paie- ments (gi)i∈N avec gi : Q j∈N Aj →R. L’ensemble des joueurs sera toujours supposé ﬁni et non-vide. Les ensembles d’actions seront tou- jours supposés non vides et on parlera de jeu ﬁni lorsque Ai est ﬁni pour tout i. Un jeu sous forme normale représente une interaction entre joueurs rationnels : chaque joueur i ∈N choisit une action ai ∈Ai, les choix étant simultanés, et si a = (ai)i∈N est le proﬁl d’actions choisi, le joueur i reçoit le paiement gi(a). Tous les joueurs connaissent le jeu et le but du joueur i est d’obtenir un paiement le plus grand possible. 6 T. TOMALA Un jeu à un joueur est donc simplement un problème de maximisa- tion. Dès qu’il y a au moins deux joueurs, le joueur i ne contrôle que partiellement son paiement et la notion de bonne stratégie n’est pas claire. Les exemples usuels suivants permettent de s’en convaincre. Les matrices ci-dessous représentent des jeux à deux joueurs dans les- quels le joueur 1 choisit la ligne, le joueur 2 la colonne et l’entrée de la matrice est le couple de paiements (g1, g2). Le Dilemme du Prisonnier. — Deux criminels sont arrêtés et inter- rogés dans des pièces séparées. Ils ont le choix entre dénoncer leur complice (D) où se taire et donc coopérer avec leur complice (C). Un criminel dénoncé par son complice se verra inﬂiger une lourde peine et une peine légère dans le cas contraire. De plus le fait de dénoncer l’autre permet d’obtenir une remise de peine, que l’on soit soi-même dénoncé ou pas. Chaque joueur classe les issues du jeu par préférence décroissante selon l’ordre suivant : (ne pas être dénoncé et dénoncer), (ne pas être dénoncé et ne pas dénoncer), (être dénoncé et dénoncer), (être dénoncé et ne pas dénoncer). Attribuant des paiements numé- riques à ces alternatives, nous formalisons cette situation par le jeu suivant : C D C D 3, 3 0, 4 4, 0 1, 1 Un jeu de coordination. — Deux amis veulent se rencontrer au lieu (A) ou au lieu (B). Leurs paiements sont égaux et valent 1 s’ils se rencontrent eﬀectivement et 0 sinon. Ceci se représente par le jeu : A B A B 1, 1 0, 0 0, 0 1, 1 Le jeu « Matching Pennies ». — Chaque joueur possède une pièce de monnaie et choisit secrètement de la mettre sur Pile (P) ou sur Face (F). Le joueur 1 gagne si son choix est le même que celui du joueur 2 et, dans ce cas, le joueur 2 perd. Dans le cas contraire c’est 2 qui gagne et 1 qui perd. Ceci se représente par le jeu : P F P F 1, −1 −1, 1 −1, 1 1, −1 JEUX SOUS FORME NORMALE 7 Commençons par donner quelques notions simples de bonne stra- tégie. Nous adopterons les notations suivantes. Pour tout joueur i, −i désigne l’ensemble des autres joueurs N ∖{i}. Si (Ei)i∈N est une famille d’ensembles indexée par N, nous notons E = Q i∈N Ei, E−i = Q j̸=i Ei. Un élément e de E pourra se noter e = (e1, . . . , en) = (ei)i∈N = (ei, e−i) cette dernière notation étant utilisée lorsque l’on veut séparer le joueur i des autres. Déﬁnition 1.1 – Une stratégie ai ∈Ai du joueur i est dominée si ∃bi ∈Ai, ∀a−i ∈A−i, gi(ai, a−i) ⩽gi(bi, a−i). – Une stratégie ai ∈Ai du joueur i est faiblement dominée si ∃bi ∈Ai, ( ∀a−i ∈A−i, gi(ai, a−i) ⩽gi(bi, a−i) et ∃a−i ∈A−i, gi(ai, a−i) < gi(bi, a−i). – Une stratégie ai ∈Ai du joueur i est strictement dominée si ∃bi ∈Ai, ∀a−i ∈A−i, gi(ai, a−i) < gi(bi, a−i). – Une stratégie ai ∈Ai du joueur i est dominante si ∀bi ∈Ai, ∀a−i ∈A−i, gi(ai, a−i) ⩾gi(bi, a−i). – Une stratégie ai ∈Ai du joueur i est faiblement dominante si ∀bi ∈Ai, ( ∀a−i ∈A−i, gi(ai, a−i) ⩾gi(bi, a−i) et ∃a−i ∈A−i, gi(ai, a−i) > gi(bi, a−i). – Une stratégie ai ∈Ai du joueur i est strictement dominante si ∀bi ∈Ai, ∀a−i ∈A−i, gi(ai, a−i) > gi(bi, a−i). Un joueur rationnel ne jouera jamais de stratégie strictement do- minée, jouera à coup sur une stratégie strictement dominante si elle existe (et alors elle est unique) et ne perd rien à jouer une stratégie dominante. On peut remarquer que dans le jeu du Dilemme du Pri- sonnier, la stratégie D est strictement dominante pour chaque joueur, l’issue rationnelle du jeu est donc (D, D). Lorsque tous les joueurs sont rationnels et savent que leurs ad- versaires le sont, chacun peut supprimer ses propres stratégies stric- tement dominées et s’attendre à ce que les autres fassent de même. 8 T. TOMALA De nouvelles stratégies strictement dominées peuvent alors apparaître dans le jeu réduit. On est donc conduit à itérer cette opération. Procédure d’élimination itérée des stratégies strictement dominées (EISSD). — Pour tout jeu G = (N, (Ai)i∈N, (gi)i∈N) et tout joueur i, on note SDi(G) l’ensemble des stratégies du joueur i strictement dominées dans G. Partons d’un jeu G0 = (N, (Ai 0)i∈N, (gi)i∈N). – Pour tout i ∈N, on pose Ai 1 = Ai 0 ∖SDi(G0) et G1 = (N, (Ai 1)i∈N, (gi)i∈N), jeu dans lequel les fonctions de paiement sont déﬁnies par restriction. – Pour tout entier k > 1 et tout i ∈N, on pose Ai k = Ai k−1 ∖SDi(Gk−1) et Gk = (N, (Ai k)i∈N, (gi)i∈N). – Pour tout i ∈N on pose enﬁn Ai ∞= \ k Ai k et G∞= (N, (Ai ∞)i∈N, (gi)i∈N). On dit que G0 est résoluble par EISSD si pour tout joueur i, la restriction de gi à Q i∈N Ai ∞est une application constante. Le jeu de concurrence de Cournot. — Deux entreprises produisent le même bien et choisissent la quantité à produire. Le prix de vente est une fonction décroissante de la somme des quantités, le bénéﬁce de chaque entreprise s’écrit comme la diﬀérence entre ses recettes et le coût total de production. Prenons des paramètres α, β, γ > 0 avec α > γ et déﬁnissons le jeu suivant : G = (A1, A2, g1, g2) dans lequel A1 = A2 = R+ et pour chaque joueur i et paire de stratégies (a1, a2) : gi(a1, a2) = ai(α −β(a1 + a2))+ −γai Ce jeu est résoluble par EISSD et on montre que, pour i = 1, 2, Ai ∞= n α−γ 3β o . Deviner le demi-moyenne. — Un autre exemple est le jeu à n joueurs dans lequel chacun choisit un réel entre 0 et 100, le but étant d’être JEUX SOUS FORME NORMALE 9 le plus proche possible de la demi-moyenne : gi(a) = − ai −1 2n n X j=1 aj Ce jeu est résoluble par EISSD et on a, pour tout i ∈N, Ai ∞= {0}. Comme le montrent les jeux de coordination et Matching Pennies ci- dessus, bon nombre de jeux ne sont pas résolubles par cette simple méthode. Les deux parties suivantes donnent des notions de solutions pour lesquels on dispose de théorèmes d’existence relativement géné- raux. Nous commençons par traiter les jeux à somme nulle. 2. Jeux à somme nulle Un jeu à somme nulle est un jeu à deux joueurs G = (A1, A2, g1, g2) tel que pour tous (a1, a2) ∈A, g1(a1, a2) + g2(a1, a2) = 0. Pour cette partie posons, A1 = S, A2 = T, g1 = g. Ainsi, un jeu à somme nulle est déterminé par une application g : S × T →R. Dans la suite, par souci de simplicité, nous supposerons g bornée. 2.1. Notions de solutions Déﬁnition 2.1 – Le joueur 1 garantit le paiement d ∈R si : ∃s ∈S, ∀t ∈T, g(s, t) uploads/Sports/ xups-06.pdf