--- tags: corrigé, TD --- # [IA04 / AI30] Corrigé TD n°9 : Négotiation et enchères ## Exercice 1 : Jeu séquentiel, équilibre de Nash, équilibre parfait On considère le jeu séquentiel à deux joueurs (I et II) représenté par l'arbre suivant : ![](https://i.imgur.com/4qcwtyX.png) 1. Énumérer toutes les **stratégies** pures de chacun des joueurs 2. Représenter ce jeu sous **forme normale** à l'aide d'une bimatrice de gain 3. Déterminer les correspondances de **meilleure réponse** de chacun des joueurs, puis tous les **équilibres de Nash** en stratégies pures et la valeur de chacun 4. Déterminer tous les **équilibres parfaits** en sous-jeu en stratégies pures et la valeur de chacun. Commenter. > #### Solution > 1. pour un joueur donné, une stratégie consiste à spécifier une action par noeud appartenant à ce joueur > pour le joueur I, les stratégies sont AC, AD, BC, BD > pour le joueur II, les stratégies sont ac, ad, bc, bd > 2. la bimatrice 4x4, où le joueur I joue en colonne et le joueur II joue en ligne : > > | | AC | AD | BC | BD | > |----|----|----|----|----| > | ac | 1/0|2/10| 8/3| 8/3| > | ad | 1/0|2/10| 3/8| 3/8| > | bc | 5/5| 5/5| 8/3| 8/3| > | bd | 5/5| 5/5| 3/8| 3/8| > > 3. meilleure réponse du joueur I : > * ac $\mapsto$ {BC,BD} > * ad $\mapsto$ {BC,BD} > * bc $\mapsto$ {BC,BD} > * bd $\mapsto$ {AC,AD} > > meilleure réponse du joueur II : > * AC $\mapsto$ {bc,bd} > * AD $\mapsto$ {ac,ad} > * BC $\mapsto$ {ad,bd} > * BD $\mapsto$ {ad,bd} > > Par définition, un équilibre de Nash en stratégies pures est un couple $(S_I,S_{II})$ de stratégies de chacun des joueurs tel que $S_I \in BR_I(S_{II})$ et $S_{II} \in BR_{II}(S_I)$ > Ici, NE = {(BC,ad) de valeur 3/8, (BD,ad) de valeur 3/8, (AC,bd) de valeur 5/5} > 4. la notion d'équilibre parfait est récursive. On les détermine en partant du bas de l'arbre et en remontant (*backward induction*) [c'est l'algorithme du minimax]. On trouve que les branches optimales sont D et d, puis a et enfin B, soit (ad,BD), de valeur 3/8. On remarque que dans l'équilibre de Nash (ad,BC), la menace du joueur I de jouer C n'est **pas crédible**. Il en va de même pour la menace du joueur I de jouer A dans l'équilibre de Nash (AC,bd). ## Exercice 2 : Analyse stratégique de la négotiation On se place dans le cadre vu en cours : * Les agents A et B doivent se partager un gâteau de taille 1. * L'agent A joue en premier * L'agent dont c 'est le tour propose une offre de partage, de la forme $o_1 = (x,1-x)$ avec $x\in[0,1]$ * L'autre agent peut **accepter**, et le jeu se termine, ou bien **refuser** et prendre la main au tour suivant * *tie-breaking* : lorsqu'un agent reçoit une offre, s'il est indifférent entre acceptation et refus, alors il accepte cette offre ### A. Modèle à coûts fixes Dans ce modèle, si l'offre $o_t=(x,1-x)$ est acceptée, les agents reçoivent les gains $g_A = x-(t-1)c_A$, $g_B = 1-x-(t-1) c_B$. On considère le jeu à **horizon fini**. 1. Analyser les jeux en 1, 2, 3 tours en précisant les équilibres parfaits. > #### Solution > * **jeu en 1 tour**. C est exactement le jeu de l'ultimatum. Le joueur A propose (1,0) et le joueur B accepte, car sa menace de refuser n'est pas crédible. > * **jeu en 2 tours**. On part de la fin. Au 2e/dernier tour, le joueur B propose l'ultimatum (0,1) et A l'accepte, pour un gain $(-c_A, 1-c_B)$. Par conséquent, au 1e tour, le joueur A n'a pas intérêt à proposer au joueur B une répartition $(x,1-x)$ avec $1-x \ne 1-c_B$ car : > - s'il propose $1-x < 1-c_B$, le joueur B va refuser et prendre la main, ce qui placerait A dans une position strictement moins favorable > - s'il propose $1-x > 1-c_B$, il se prive inutilement d'une partie du gâteau > Donc A propose $(c_B,1-c_B)$ au premier tour, et B accepte, pour des gains $(c_B, 1-c_B)$. > * **jeu en 3 tours**. Le raisonnement précédent reste valide en permutant les joueurs et en tenant compte des coûts de négociation. Au 3e/dernier tour, A propose (1,0) et B accepte, pour des gains $(1-2c_A, -2c_B)$. Au 2e tour, B propose $(1-c_A, c_A)$ et A accepte car il est indifférent, pour des gains $(1-2c_A, c_A-c_B)$. Au 1e tour, il est nécessaire de distinguer 2 cas suivant la **patience relative** des agents. Si A est moins patient que B (càd $c_A>c_B$ ) A propose $(1-c_A+c_B, c_A-c_B)$ de manière à ce que B soit indifférent (et il accepte donc cette offre), pour un gain $(1-c_A+c_B, c_A-c_B)$. Si A est plus patient que B, A propose (1,0) et B accepte, pour un gain (1,0). ### B. Modèle à taux d'escompte Dans ce modèle, si l'offre $o_t=(x,1-x)$ est acceptée, les agents reçoivent les gains $g_A = x\cdot\delta^{t-1}$, $g_2 = (1-x)\cdot\delta^{t-1}$, où $\delta$ est un paramètre de l'intervalle ]0,1[ > **Remarque :** les taux d'escompte des 2 joueurs sont supposés égaux, ce qui simplifie l'analyse. Ce modèle revient à considérer que la valeur du gâteau est multipliée par $\delta$ à chaque tour. > On considère le jeu à **horizon fini**. 2. Analyser les jeux en 1, 2, 3 tours en précisant les équilibres parfaits. > #### Solution > * **jeu en 1 tour**. C est exactement le jeu de l'ultimatum. Le joueur A propose (1,0) et le joueur B accepte, car sa menace de refuser n'est pas crédible. > * **jeu en 2 tours**. On part de la fin. Au 2e/dernier tour, le joueur B propose l'ultimatum (0,1) et A l'accepte, pour un gain $(0, \delta)$. Par conséquent, au 1e tour, le joueur A n'a pas intérêt à proposer au joueur B une répartition $(x,1-x)$ avec $1-x \ne \delta$ car : > - s'il propose $1-x < \delta$, le joueur B va refuser et prendre la main, ce qui placerait A dans une position strictement moins favorable > - s'il propose $1-x > \delta$, il se prive inutilement d'une partie du gâteau > Donc A propose $(\delta,1-\delta)$ au premier tour, et B accepte, pour des gains $(\delta, 1-\delta)$. > * **jeu en 3 tours**. Au 3e/dernier tour, A propose (1,0) pour des gains $(\delta^2,0)$. Au 2e tour, B propose $(\delta, 1-\delta)$ que A accepte, pour des gains $(\delta^2,\delta-\delta^2)$. Par conséquent, A propose au 1e tour $(1-\delta+\delta^2, \delta-\delta^2)$ que B accepte, pour des gains $(1-\delta+\delta^2, \delta-\delta^2)$. ### C. Pour aller plus loin Emettre une conjecture quant aux équilibres parfaits et aux valeurs de ces jeux lorsque le nombre de tours est un entier $N$ quelconque. Prouver cette conjecture par récurrence. ## Exercice 3 : Enchère de Vickrey Il s'agit du mécanisme d'enchères vu en cours : les acheteurs soumettent des offres privées, et l'objet va au plus offrant, qui paie au vendeur le prix correspondant à la seconde offre la plus élevée. Les autres acheteurs ne paient rien. Montrer que le mécanisme est sincère : pour chaque acheteur, faire une offre dont le montant correspond à sa propre évaluation de l'objet est une *stratégie faiblement dominante* (quel que soit le comportement des autres acheteurs --sincères ou non-- il n'existe pas de stratégie strictement plus profitable). > #### Solution > Il s'agit de faire une disjonction de cas rigoureuse et détaillée. > * Si la valuation réelle $v$ d'un joueur correspond à la meilleure offre, ce joueur à un gain $v-o_2\ge 0$, où $o_2$ désigne la 2e meilleure offre. Enchérir davantage que $v$ n'a aucun impact sur son gain. Enchérir entre $o_2$ et $v$ n'a aucun impact sur son gain. Enchérir moins que $o_2$ fait perdre l'enchère au joueur, et son gain devient nul, ce qui ne constitue pas une meilleure option. > * Si la valuation réelle $v$ du joueur est inférieure à la meilleure offre $o_1$, le gain du joueur est nul s'il est sincère. Enchérir moins que $v$, ou plus que $v$ mais moins que $o_1$ apporte aussi un gain nul. Enchérir davantage que $o_1$ permet au joueur de remporter l'objet, mais pour un gain $v-o_1$ négatif, ce qui ne constitue pas une meilleure option. > Dans tous les cas, exprimer une enchère différente de $v$ conduit à un gain identique ou strictement inférieur, donc la sincérité constitue bien une stratégie faiblement dominante, et le mécanisme est sincère.