David Madore's WebLog: Un peu de théorie mathématique du marchandage

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]

↓Entry #2817 [older| permalink|newer] / ↓Entrée #2817 [précédente| permalien|suivante] ↓

(jeudi)

Un peu de théorie mathématique du marchandage

Comme je l'avais évoqué récemment, je voudrais parler un peu de la théorie mathématique du marchandage coopératif (selon Nash).

Je me suis senti motivé, donc, une fois n'est pas coutume j'ai fait des dessins[#] (en SVG, produits avec TikZ) pour illustrer le billet, j'espère qu'ils aideront à comprendre ce que je raconte.

[#] Désolé si les étiquettes sont en anglais : à l'origine j'ai fait ça pour un petit fil BlueSky (dont ce billet est en quelque sorte la version étendue), et je n'ai pas voulu changer ensuite. Mais accessoirement, je n'ai pas trouvé de traduction française satisfaisante pour le mot settlement : j'ai écrit des choses comme accord négocié (ou point négocié) dans le corps du texte, et c'est long et lourd.

En contrepartie, il faut que je reconnaisse que, comme souvent mais peut-être encore plus que d'habitude, ce billet bordélique souffre du défaut que je ne sais pas bien à quel niveau mathématique je veux me placer : il y a des passages qui ne supposent aucune connaissance mathématique, d'autres où je suppose le lecteur familier avec des notions comme celle de partie convexe, de différentielle, ce genre de choses, et je passe de l'un à l'autre de façon pas super cohérente ; il y a des passages où j'essaie de parler de façon purement géométrique et sans aucun symbole, d'autres où je me suis trouvé obligé à écrire des formules, ce qui gâche un peu l'effort fait pour ne pas en mettre ; parfois je redis la même chose de plein de façons différentes et tout ça est mal séparé. (En plus de ça, j'avais commencé par écrire quelque chose de complètement faux[#2] : j'ai rectifié comme j'ai pu, ce qui a donné naissance à la quatrième partie du billet, mais du coup j'ai dû faire pas mal de repentirs, ce qui a certainement cassé des choses, au moins le fil de mes pensées.) Et puis, comme souvent, il y a plein de notes en bas de paragraphe qui sont destinées à apporter des éclaircissements sur tel ou tel point mais qui, peut-être, rendent la lecture d'autant plus compliquée.

[#2] À savoir que la rentabilité de la défense, que je vais définir ci-dessous, vaut toujours exactement ½, ce qui est manifestement absurde.

Bref, j'espère que c'est quand même assez compréhensible. Les lecteurs non mathématiciens peuvent sans doute sauter les passages où il y a des calculs ou des démonstrations, on doit pouvoir tirer quelque chose du reste. (La question de savoir si ce quelque chose est vraiment intéressant, en revanche, est laissé en exercice au lecteur.)

Pour ceux qui veulent une description mathématiquement plus précise que cette sorte de vulgarisation bâtarde, je renvoie principalement à l'article de Nash de 1953 Two-Person Cooperative Games (qu'on pourra aussi trouver ici), ainsi qu'à un plus ancien, The Bargaining Problem, mais aussi, par exemple, le livre de Damme, Stability and Perfection of Nash Equilibria (Springer 1991), chapitre 7 ; ce sont là mes sources essentielles pour ce que je raconte.

Plan

Description du problème

De quoi s'agit-il, donc ?

[Schéma illustrant la théorie de la négociation de Nash]La situation qu'on cherche à modéliser mathématiquement ici est la suivante : on a deux joueurs (appelons-les Alice et Bob), parfaitement égoïstes, parfaitement rationnels et parfaitement bien informés, qui cherchent à négocier quelque chose, typiquement le partage d'une ressource ou n'importe quelle forme d'accord[#3]. L'idée est la suivante : Alice et Bob vont négocier un accord, et s'ils y parviennent (l'accord doit être accepté par les deux parties), tant mieux, sinon, ils se feront la guerre. Quand j'écris ils se feront la guerre, ce n'est pas forcément à prendre au sens littéral, mais c'est une situation défavorable qui résulte de l'absence d'accord (par exemple, ça peut simplement être le fait que la ressource à partager est perdue pour les deux joueurs). La négociation se fait donc sous la menace[#4] de cette situation par défaut (la guerre). Comme j'ai supposé mes joueurs parfaitement bien informés, cela suppose notamment qu'ils connaissent l'issue espérée[#5] de la guerre pour chacun des deux. Cette issue de la guerre est supposée défavorable pour les deux joueurs (si l'un des deux joueurs a plus à gagner à faire la guerre qu'à négocier, évidemment il ne va pas négocier).

[#3] Exemple de situation qu'on peut analyser sous l'angle de la théorie évoquée dans ce billet, et qui aidera peut-être à comprendre de quoi ça cause : deux forces politiques envisagent de s'allier pour former un gouvernement (ou pour voter un budget, ou pour se présenter de façon commune à une élection). La négociation porte sur le programme commun : l'espace des programmes politiques possibles est, évidemment, extrêmement vaste, mais on ne reflète ici que sa projection sur le plan de l'utilité des deux forces en question. La « guerre » dont il est question est, alors, le fait que le pays n'ait pas de gouvernement, ou de budget, ou que d'autres partis en forment, ou encore de perdre les élections.

[#4] Les termes de menace et de guerre sont donc essentiellement interchangeables dans la suite, à ceci près que la menace est la potentialité de la guerre tandis que la guerre est sa réalisation. Mais mathématiquement, c'est juste un point sur le diagramme (représenté en rouge), et qui est crucial pour déterminer l'issue de la négociation (représenté en bleu).

[#5] Notons que la guerre n'a pas forcément une issue déterministe, mais ce n'est pas important pour ce que je raconte : si l'issue de la guerre est probabiliste, on la remplace par l'espérance de cette distribution de probabilités, ce qui est de toute façon ce qui compte pour les joueurs rationnels : donc si la guerre conduit, par exemple, à ce que les joueurs aient les gains (−2,−2) avec probabilité ½ et (0,−6) avec probabilité ½, on remplace ça par (−1,−4). (La définition d'une fonction d'utilité affine, cf. la note #6, est justement celle qui assure que le joueur rationnel est indifférent au choix entre un gain de x avec probabilité p et de y avec probabilité 1−p ou un gain certain de p·x + (1−py, et sous des hypothèses faibles on doit toujours pouvoir reparamétrer l'utilité de façon à assurer cette propriété.)

Une autre hypothèse essentielle de la théorie est que si la négociation échoue, la guerre est inévitable. Encore une fois, guerre est un terme un peu fourre-tout qui peut recouvrir plein de choses, éventuellement probabilistes comme le signale la note #5 ci-dessus, mais si les joueurs ont fait des menaces l'un envers l'autre, ils doivent mettre leur menace à exécution. Cette hypothèse est indispensable pour que l'autre joueur la prenne au sérieux lors de la négociation. Donc il faut que les joueurs aient la possibilité de prendre un engagement irrévocable d'accomplir leur menace : sans cette possibilité de se lier les mains, l'autre joueur pourra toujours leur proposer n'importe quel accord qui soit meilleur que la guerre, et ce serait rationnel d'accepter.

La bonne nouvelle — façon de parler —, c'est que la théorie du marchandage exposée ci-dessous conclut qu'il existe effectivement un accord (bien défini par la situation, c'est-à-dire à la fois par l'issue connue de la guerre et par le domaine des accords réalisables) auquel les deux joueurs devraient arriver, évitant donc la guerre. La menace de guerre est indispensable et cruciale pour définir la solution négociée (je vais y revenir, et toute la discussion va consister à voir comment l'une détermine l'autre), mais au final, la guerre n'a pas lieu (sous les hypothèses que j'ai dites…).

Venons-en au dessin ci-dessus. Les deux axes représentent la fonction d'utilité[#6] des deux joueurs, c'est-à-dire qu'Alice cherche à maximiser la coordonnée horizontale (elle cherche à trouver un accord autant que possible à droite) et que Bob cherche à maximiser la coordonnée verticale (il cherche à se placer aussi haut que possible). Chaque point représente donc une issue possible pour les deux joueurs : plus on est à droite, plus Alice est contente, plus on est haut, plus Bob est content.

[#6] Il y aurait sans doute beaucoup à dire sur cette notion d'utilité (et l'axiomatique qui la sous-tend). Dire que chaque joueur cherche à maximiser son utilité est ce que j'ai qualifié d'hypothèse d'égoïsme, mais, en fait, ce n'est pas forcément un terme très correct : ça ne signifie pas qu'Alice est indifférente à ce qui arrive à Bob, c'est juste la définition de l'utilité d'Alice (si Alice est intéressée par quelque chose qui arrive à Bob, il faut juste refléter ce fait dans la fonction d'utilité d'Alice) : par définition, les situations qui ont une plus grande utilité pour Alice sont celles qu'Alice préfère, et symétriquement pour Bob. Mais il y a une autre hypothèse que je fais implicitement, qui est que la fonction d'utilité est affine, c'est-à-dire qu'avoir une situation d'utilité x avec probabilité p et une situation d'utilité y avec probabilité 1−p équivaut à une utilité de p·x + (1−py : là aussi, cela peut sembler hautement contestable (par exemple, il ne m'est peut-être pas indifférent de recevoir 1000€ de façon certaine ou 2000€ avec probabilité ½), mais en fait des hypothèses très faibles doivent assurer la possibilité de reparamétrer l'utilité sous cette forme (rien ne dit que ce soit directement lié à l'argent : par exemple, si je préfère recevoir 1000€ de façon certaine que 2000€ avec probabilité ½, ça signifie juste que mon utilité à recevoir 1000€ est plus que la moitié de celle de recevoir 2000€).

[Schéma]Évidemment, il y a des contraintes (imposées par « la nature » ou l'environnement) sur les partages autorisés : sinon les deux joueurs choisiraient tous les deux une solution optimale pour eux et il n'y aurait aucune tension de négociation (c'est en gros ce qui est montré par le diagramme ci-contre à gauche, représentant une situation « sans conflit » où, en gros, les joueurs ne se marchent pas sur les pieds l'un de l'autre, donc chacun peut choisir sa valeur idéale). Cette région « réalisable » est grisée dans mon dessin : on ne peut négocier qu'une solution qui soit dedans. Les deux joueurs sont au courant des contours exact de cette région (hypothèse qu'ils sont parfaitement informés[#7]).

[#7] Concrètement, cela signifie, donc, que non seulement ils sont capables d'envisager tous les accords concevables, mais qu'ils savent exactement lesquels sont réalisables, et ce qu'ils en pensent (c'est-à-dire l'utilité de l'accord pour leur part) et aussi ce qu'en pense l'autre joueur.

Une remarque technique mais importante est qu'on peut supposer que cette région « réalisable » est convexe. En effet, si elle ne l'était pas, on pourrait toujours l'étendre pour qu'elle le soit : il suffit pour cela que les joueurs acceptent des solutions probabilistes : si par exemple le problème dont il s'agit est de se partager un zorglub précieux qu'il n'est pas matériellement possible de partager[#8], les joueurs peuvent convenir qu'Alice recevra le zorglub avec probabilité p et que Bob le recevra avec probabilité 1−p, ce qui réalise le segment, dans l'espace des possibles, entre les deux extrêmes Alice reçoit le zorglub et Bob reçoit le zorglub. Ceci suppose, bien sûr, que les joueurs aient accès à une source de hasard commune (ça ce n'est pas une hypothèse difficile : voir ce fil pour quoi faire si chacun dispose d'un dé mais ne fait pas confiance au dé de l'autre, par exemple), et soient prêts à accepter les solutions probabilistes (comme signalé dans la note #6 ci-dessus, ça fait partie de l'hypothèse d'une fonction d'utilité affine).

[#8] Dans la version mathématique du jugement de Salomon, au lieu de proposer de couper le bébé en deux, le roi Salomon propose de tirer au hasard qui le recevra, et l'utilité est supérieur pour chacune des deux mères au fait de couper le bébé en deux. Mais du coup, la vraie mère ne se révèle pas.

On peut aussi supposer (cette fois c'est juste pour simplifier les figures, ça n'a de toute façon aucune conséquence sur le jeu) que la région réalisable est stable par diminution de l'une ou l'autre de ses coordonnées (i.e., tout point situé à gauche et/ou en bas d'un point réalisable est lui-même réalisable) : c'est dire que les joueurs peuvent toujours, si ça les amuse, négocier un accord qui soit pire pour l'un, ou pour l'autre, ou pour les deux, qu'un accord qui est possible (i.e., ils peuvent toujours brûler gratuitement de l'utilité). Ceci explique la forme de mes régions, et aussi pourquoi le seul bord qui existe (qui est de toute manière le seul bord qui va m'intéresser) est le bord supérieur droit. Encore une fois, ça n'a pas vraiment d'importance, c'est juste pour ne pas s'embarrasser avec une partie du bord qui n'aurait de toute façon pas d'intérêt.

Il reste donc une partie convexe du plan dont le bord est constitué de l'ensemble des points « Pareto-optimaux », c'est-à-dire tels qu'il n'y ait aucun point réalisable qui soit strictement[#9] préférable pour les deux joueurs (i.e. situé à droite et/ou au-dessus et qui soit encore dans la région réalisable). Les joueurs vont évidemment négocier un accord qui soit sur ce bord, vu qu'il n'y a aucune raison[#10] de choisir un accord si on peut faire mieux pour les deux joueurs. Ce bord est représenté sur mes figures par un trait plein noir, et le but de la théorie est de déterminer quel point du bord au juste constitue le point d'accord rationnel naturel (en bleu).

[#9] On peut ergoter pour savoir si le terme Pareto-optimal fait référence à l'impossibilité de faire strictement mieux pour les deux joueurs, ou mieux pour l'un des deux et strictement mieux pour l'autre. Ce n'est pas important ici. Si vous êtes gênés par l'affirmation que les demi-droites horizontale et verticale constituant le bord de la région réalisable sont Pareto-optimales, imaginez qu'elles sont très très très légèrement penchées, tellement peu que vous ne puissiez pas le voir.

[#10] Rappelons que, dans les négociations, la seule chose qui intéresse Alice est d'optimiser sa fonction d'utilité (hypothèse d'égoïsme) : elle ne cherche pas à punir Bob, donc elle n'a aucune objection à améliorer l'utilité de Bob si ça ne change pas la sienne. Ceci est différent de la menace de guerre, par laquelle elle cherche effectivement à punir Bob en cas d'échec des négociations (c'est bien pour ça que j'ai dû faire l'hypothèse qu'en cas de guerre les joueurs doivent mettre leur menace à exécution : ce ne serait pas rationnel pour Alice de chercher à punir Bob si ça ne faisait pas partie d'une menace à laquelle elle s'est engagée).

Là-dedans, on a un « point de guerre » ou point de menace, en rouge sur mes figures, qui représente l'utilité pour les deux joueurs de la guerre en cas d'échec des négociations. Ce point est dans la région réalisable, et, vraisemblablement, profondément dedans, ce qui représente le fait que la guerre n'est pas du tout souhaitable, ni par un joueur ni par l'autre (et tout le but de la théorie est d'éviter la guerre, et de savoir comment on négocie rationnellement un accord qui l'évite ; mais la menace[#11] de guerre, et son inévitabilité en cas d'échec des négociations, est essentielle pour faire fonctionner la théorie). Les joueurs négocient, donc, sous et selon la menace que si la négociation échoue il leur en coûtera à tous les deux.

[#11] Comme je l'ai dit, c'est une devise bien connue des joueurs d'échecs, souvent attribuée (peut-être à tort) à Aron Nimzowitsch qu'une menace est plus forte que son exécution, et la théorie de Nash vise à donner à cet adage un fondement théorique. (Bon, j'exagère peut-être en disant ça, vu que les échecs sont un jeu à somme nulle, et que la théorie ici développée n'a pas de sens dans le cadre d'un jeu à somme nulle, donc peut-être que ce n'est quand même pas la même chose.)

Il va de soi que les seuls accords intéressants à considérés sont ceux qui non seulement sont situés sur le bord (Pareto-optimal) de la région réalisable, mais aussi à droite et/ou au-dessus du point de guerre. (En effet, un point situé, disons, à gauche du point de guerre, correspond à un accord pire que la guerre du point de vue d'Alice, donc Alice n'acceptera jamais un tel accord : elle préférera faire la guerre.) D'où les lignes horizontale et verticale en pointillé qui émanent du point de guerre sur mes figures : les accord réellement envisageables sont ceux situés dans la région grisée un peu plus sombre, au-dessus à droite du point de guerre, et, en fait, sur le bord Pareto-optimal de cette partie. Mais où exactement ?

Approche axiomatique

Là je n'ai fait que poser le problème. Nash y répond de la façon suivante :

✱ Théorème (Nash, 1950, 1953) : L'issue rationnelle de la négociation (présentée ci-dessous, et avec une caractérisation à définir ci-dessous) est l'unique point du bord de la région réalisable dont la tangente soit de pente opposée à la droite qui le relie au point de guerre.

Je vais essayer d'expliquer pourquoi c'est le cas (et ce que ça veut dire au juste), mais pour ce qui est des illustrations, le point négocié dont je parle est représenté en bleu sur mes figures, la tangente[#12] est aussi représentée en bleu, et j'ai essayé de montrer (par des secteurs angulaires illustrant des angles égaux) que la pente est opposée à celle de la droite qui relie le point de guerre au point négocié.

[#12] Il y a un petit point à noter quand je dis la tangente : le terme est un peu abusif parce que le bord d'un convexe n'a pas forcément une unique tangente (il a deux demi-tangentes, mais il peut être anguleux comme sur ma deuxième figure) : il s'agit donc, en fait, de l'unique point du bord tel qu'il existe une droite entre les deux demi-tangentes au point en question (ou, si on préfère, une droite passant par ce point qui soit le bord d'un demi-plan contenant le convexe). Si on préfère, on peut ajouter l'hypothèse que le bord du convexe est lisse, comme ça la tangente existe : on peut de toute façon l'approcher par un convexe lisse.

Je dois dire que je trouve assez magique qu'il y ait une solution aussi simple et géométrique au problème de la négociation !

Bon, d'accord, mais pourquoi est-ce le cas ? Et comment caractériser cette issue rationnelle ?

[Schéma]Nash donne, en fait, deux approches différentes qui conduisent à la même solution, mais avec des caractérisations différentes. Celle qui me semble la plus élégante est l'approche axiomatique. Pour la comprendre, commençons par envisager le cas particulier, représenté par la figure ci-contre à droite, où la région réalisable est un demi-plan (dont le bord est, donc, une droite). C'est, par exemple, la situation où il y a une ressource à se partager sans aucun gain intrinsèque au partage ni rendement croissant pour l'un des joueurs, i.e., une utilité affine dans le partage (par exemple, Alice et Bob gagnent 100€ s'ils arrivent à se mettre d'accord sur la manière de le partager — et s'ils n'arrivent pas à se mettre d'accord, c'est « la guerre » et aucun d'entre eux ne gagne rien — et je suppose qu'ils attribuent une utilité linéaire à l'argent).

Sur ma figure ci-contre, cette droite a pour pente −1 (i.e., un angle de 45° avec la verticale dans le sens décroissant de la gauche vers la droite) : prima facie, c'est un cas particulier, mais quand on y réfléchit un peu, on se rend compte que non : en effet, l'utilité d'Alice et l'utilité de Bob ont, en fait, des unités différentes (ça n'a pas de sens de les comparer), donc quitte à multiplier l'une par la bonne constante, on peut s'arranger pour que la droite ait pour pente −1, donc l'équation x + y = c pour une certaine constante c (la somme à partager). On peut aussi supposer, quitte à changer l'origine (arbitraire) de l'utilité de l'un et l'autre joueur, que le point de guerre ait les coordonnées (0,0) (et forcément c≥0 puisque le point de guerre doit être un partage possible). Alors pour des raisons de symétrie, s'il y a une solution rationnelle bien-définie au partage, ça ne peut être que (c/2, c/2) (projeter le point de guerre horizontalement et verticalement sur la droite limite, ce qui construit les points (c,0) et (0,c), et prendre le milieu entre ces deux projections).

La construction que je viens de donner correspond bien à la caractérisation générale que j'ai énoncée plus haut : la droite reliant le point de guerre (0,0) au point négocié (c/2, c/2) a pour pente 1, donc opposée à la pente de la droite limite.

Vous pourriez objecter qu'elle est aussi perpendiculaire, alors pourquoi je ne présente pas comme ça ? Parce que la propriété d'être perpendiculaire à la droite limite n'est pas invariante par changement d'échelle séparément sur les axes horizontal et vertical, tandis que la propriété d'avoir une pente opposée, elle, l'est — et j'ai justement utilisé un changement d'échelle séparément sur les axes horizontal et vertical pour me ramener à la pente −1. Donc l'argument que je viens de gloser a pour conclusion que, dans le cas particulier considéré pour l'instant (celui où la frontière est une droite), la caractérisation donnée par Nash est bien la seule qui peut conduire à trouver une solution à la négociation qui soit à la fois invariante par changement d'échelle et d'origine des utilités, et par échange des deux joueurs.

L'argument de Nash, maintenant, c'est qu'en fait on peut toujours se ramener à cette situation : sans entrer dans les détails, on va approcher le bord du domaine considéré, autour du point recherché, par la tangente à ce domaine, et on en conclut que la solution est la même, si tant est qu'on peut ignorer ce qui se passe loin de ce point. C'est-à-dire qu'on fait l'hypothèse suivante :

‣ Indépendance des alternatives non pertinentes : si la négociation à partir d'un ensemble réalisable conduit à un certain accord, alors toute négociation à partir d'un sous-ensemble de cette région réalisable qui contient aussi le point de cet accord et le même point de guerre, conduira à la même issue.

Autrement dit, si Alice et Bob négocient un compromis, ce compromis reste valable même si certaines possibilités deviennent impossibles, tant que le point de guerre et le compromis restent possibles. C'est assez intuitif (dans une négociation, les options qu'on a choisi de ne pas utiliser n'ont pas de pertinence, seuls comptent la menace et le résultat du compromis), mais s'il y a quelque chose qui a été critiqué dans l'analyse de Nash, c'est bien cette hypothèse-là.

Finalement, le théorème mathématique précis[#13] que démontre Nash, dans cette approche axiomatique, est le suivant. Considérons une fonction F qui à un domaine plan C⊆ℝ² (supposé ① convexe, ② fermé, ③ non vide, ④ ne contenant aucune droite horizontale ni verticale, et ⑤ stable par diminution de l'une ou de l'autre coordonnée, i.e., si (x,y)∈C et x′≤x et y′≤y alors (x′,y′)∈C) et à un point wC (le point de guerre) associe un point F(C,w)∈C (l'accord trouvé), et supposons que cette fonction F vérifie :

  • optimalité de Pareto : si (x,y)∈C est supérieur ou égal à F(C,w) sur chaque coordonnée, alors il lui est égal ;
  • invariance par transformations affines croissantes sur l'utilité de chaque joueur : si T : (x,y) ↦ (p·x+a, q·y+b) avec p,q>0, alors F(T(C), T(w)) = T(F(C,w)) ;
  • invariance par symétrie : si T : (x,y) ↦ (y,x) alors F(T(C), T(w)) = T(F(C,w)) ;
  • indépendance des alternatives non pertinentes : si wDC et F(C,w)∈D, alors F(D,w) = F(C,w) ;

alors z := F(C,w) est l'unique point du bord de C dont la tangente (enfin, une tangente, i.e., une droite passant par lui et limitant un demi-plan contenant C) a la pente opposée à celle de la droite (zw). Et inversement, cette définition donne un point unique[#14] qui vérifie les critères qu'on vient de dire.

[#13] J'espère ne pas avoir oublié d'hypothèses. La formulation que j'utilise ici n'est pas exactement celle de Nash, qui a des axiomes subtilement différents : je la prends plutôt du livre de Damme mentionné en introduction, §7.4, en changeant un petit peu les hypothèses sur C, mais je n'ai pas vérifié avec énormément de soin que je n'ai pas cassé quelque chose lors de la conversion. En tout cas, la preuve est essentiellement ce que j'ai expliqué : on utilise l'indépendance des alternatives non pertinentes pour se ramener à un petit bout autour de F(C,w), ce qui nous ramène essentiellement au cas où C est un demi-plan, et dans ce cas l'invariance par transformations affines nous ramène à une droite de pente −1 et la symétrie permet de conclure.

[#14] Le fait qu'il y ait bien un unique point vérifiant cette condition sur la pente de la tangente n'est pas difficile à prouver. Si on suppose que le bord de C est lisse, alors, par convexité, la pente de sa tangente en un point variable doit décroître continûment quand on se déplace du point situé à la verticale au-dessus du point de guerre jusqu'au point situé à l'horizontale à sa droite, et la pente de la droite reliant le point de guerre à ce point variable va décroître strictement, et en considérant ce qui se passe aux deux bouts, il est clair qu'à un moment unique les deux pentes sont opposées. Si on ne suppose plus que le bord de C est lisse, l'argument vaut encore mais il faut être plus soigneux et le dire avec des demi-tangentes et accepter le point quand la pente est entre celle des deux demi-tangentes. Je ne rentre pas dans les détails mais tout ça est assez standard et n'a pas grand rapport avec ce que je raconte.

Cette approche est assez satisfaisante en ce qu'elle est plutôt économe en moyens, mais on peut lui faire un reproche important : elle nous dit que la seule solution rationnelle possible de la négociation est la fonction décrite, mais elle ne nous dit pas vraiment[#15] que c'est effectivement une solution « rationnelle » de la négociation. (Plus exactement, s'il y a un procédé unique qui vérifie les axiomes posés, c'est forcément la construction qu'on a dite, mais comment savoir qu'il y en a effectivement un ? D'ailleurs, qu'est-ce que ça veut dire ?)

[#15] Pour dire les choses autrement, cette approche axiomatique nous dit que si Alice et Bob doivent trouver un accord pour partager 100€ (sinon ils ne gagnent rien), alors l'accord est forcément 50–50 pour des raisons de symétrie (ou, s'il s'agit de partager un zorglub précieux, l'accord consiste à le tirer à pile ou face ou toute solution équivalente). Mais c'est un peu une pétition de principe : s'il y a un moyen systématique d'arriver à un accord, c'est forcément celui-là, mais y a-t-il effectivement un moyen d'arriver à un accord ?

Construction par un jeu de négociation

Pour ça, Nash propose une autre approche.

D'abord, on va formaliser le problème comme un jeu. Le jeu (enfin, le jeu initial, parce que je vais ensuite le modifier un peu) prend la forme suivante. Dans une première phase (qui ne va pas m'intéresser dans l'analyse qui va suivre), Alice et Bob déclarent leurs menaces l'un à l'autre (et s'engagent irrévocablement à les accomplir en cas d'échec des négociations), ce qui détermine le point de guerre ; dans une seconde phase (celle que je vais considérer), la « négociation » prend la forme très simple suivante : chaque joueur choisit indépendamment et en secret une exigence, puis, si le point (x,y) correspondant aux exigences des deux joueurs est réalisable (s'il appartient à la région réalisable C), alors les joueurs gagnent respectivement x et y, sinon, c'est-à-dire si leurs exigences sont incompatibles, il se font la guerre et leurs gains sont les coordonnées du point de guerre. (Comme les deux phases sont indépendantes et que la seconde se fait en toute connaissance du point de guerre, on peut ne considérer que cette seconde phase, c'est-à-dire travailler à point de guerre fixé.)

Cette façon de « négocier » peut sembler bizarre : les joueurs ne communiquent même pas ! La raison est qu'ils sont parfaitement rationnels et parfaitement informés, donc savent très bien quelle sera l'utilité de l'autre dans une négociation, donc ils n'ont pas, en fait, besoin de négocier pour arriver à la solution optimale. Mais il est quand même essentiel que les joueurs choisissent leurs exigences en secret, car si Alice déclarait la sienne en premier, elle aurait évidemment intérêt à la prendre juste un tout petit peu en-dessous de l'abscisse du point du bord qui se trouve à la même ordonnée que le point de guerre (i.e., elle pose une exigence qui est quasiment le maximum qu'elle peut demander mais qui soit quand même préférable pour Bob que de lui faire la guerre), et Bob aura rationnellement intérêt à se plier (même si Alice a presque tout « gardé pour elle », c'est quand même mieux pour Bob d'accepter que de faire la guerre), et symétriquement si Bob choisissait en premier. Autrement dit, le joueur qui lancerait un ultimatum à l'autre aurait l'avantage. À la place, on rétablit la symétrie en disant que chacun va écrire une exigence en secret, et si ces exigences s'avèrent être incompatibles, ils sont obligés de se faire la guerre : du coup, comme ils sont rationnels, ils vont choisir des exigences compatibles, sachant comment l'autre se comportera.

Tel quel, ce jeu admet beaucoup d'équilibres de Nash (i.e., des choix possibles des deux joueurs tels que, si chacun connaît le choix de l'autre, aucun des deux n'a intérêt à changer le sien) : en fait, tous les points du bord qui sont situés à droite et au-dessus du point de guerre est un équilibre de Nash (pour la même raison qu'expliqué au paragraphe précédent). Mais pour montrer la particularité du point qui nous intéresse, Nash s'intéresse à une petite modification du jeu, dans laquelle, au lieu de passer brutalement de l'accord réussi à la guerre (dès qu'on quitte le domaine C réalisable), il y a une petite zone de transition entre les deux ; et il montre que que, quand on rend cette zone de transition de plus en plus petite, l'équilibre de Nash du jeu ainsi modifié (on peut s'arranger pour qu'il soit unique) tend forcément vers la solution décrite précédemment. Autrement dit, c'est bien lui l'équilibre pertinent, les autres ne sont que des artefacts du fait qu'on a une discontinuité au bord de C.

[Schéma]Pour arriver à cette conclusion, la première chose est de changer un peu la description du point négocié dont on cherche à montrer la particularité : au lieu de le voir comme celui dont la tangente soit de pente opposée à la droite qui le relie au point de guerre, on va le voir comme celui (ci-dessous noté (x₀,y₀)) qui maximise la quantité (xu)·(yv) où (u,v) sont les coordonnées du point de guerre (que je vais rapidement prendre égales à (0,0) pour y voir plus clair) ; comme les courbes d'équation (xu)·(yv) = constante sont des hyperboles ayant pour centre le point de guerre et ayant pour asymptotes les droites horizontale et verticale passant par lui, il est peut-être plus parlant de décrire ce point comme le point de tangence de l'unique hyperbole de cette famille qui soit tangente au domaine réalisable C (j'espère que c'est plus clair en voyant la figure ci-contre, où j'ai figuré en brun le bout d'hyperbole (xu)·(yv) = maximum). L'équivalence entre les deux descriptions vient d'une propriété géométrique standard[#16] des hyperboles équilatères (disons, ayant les axes horizontal et vertical comme asymptotes), à savoir que la pente de la tangente en un point est l'opposé de la pente de la droite reliant ce point au centre de l'hyperbole.

[#16] Analytiquement, c'est dire que la dérivée en x de la fonction xc/x vaut −c/x², ce qui est bien l'opposé de la pente de la droite reliant l'origine à (x, c/x).

L'idée, donc, c'est que, même si la solution (x₀,y₀) n'est pas le seul équilibre de Nash du jeu initial, on peut s'arranger pour que ce soit le seul équilibre de Nash d'un jeu un tout petit peu modifié, et faire « tendre vers zéro » la modification de manière que la solution du jeu modifié tende vers (x₀,y₀).

Pour rendre les choses plus concrètes, on peut décrire le jeu modifié de la façon suivante : Alice et Bob choisissent chacun une exigence (x et y), comme dans le jeu original, et comme dans le jeu original, si le point (x,y) est dans C alors ce sera leur accord (et donc les gains des deux joueurs), mais cette fois, si le point (x,y) est en-dehors de C, au lieu qu'ils se fassent forcément la guerre, il y a une certaine probabilité que cet accord soit quand même possible, cette probabilité étant extrêmement petite dès qu'on n'est pas extrêmement proche de C, mais elle varie de façon régulière (et vaut 1 sur C, donc). De façon plus imagée, pensez que la frontière de C est rendue un petit peu floue en dépassant vers l'extérieur (ce que j'ai présenté comme C est l'ensemble des accords dont on est sûr qu'ils sont mathématiquement possibles, mais on peut gratter un tout petit peu plus loin, simplement la probabilité que « ça marche » tend rapidement vers 0 dès qu'on s'éloigne de C).

Donnons quelques détails mathématiques supplémentaires, qu'on peut éventuellement sauter.

Pour fixer les notations, appelons x et y les valeurs (exigences) choisies par Alice et Bob respectivement, et on va choisir l'origine (arbitraire) de façon que le point de guerre soit en (0,0) : comme on l'a déjà fait remarquer, les joueurs choisissent évidemment des valeurs ≥0, donc on ne va s'intéresser qu'à ce quadrant. Appelons C le domaine réalisable. Dans le jeu d'origine, le gain d'Alice est alors x lorsque (x,y) est dans le domaine C réalisable, et 0 sinon, et celui de Bob est y ou 0 dans les mêmes conditions ; ou, pour dire les choses autrement, le gain (= l'utilité) d'Alice est x·g(x,y) où g est la fonction indicatrice de C (c'est-à-dire valant 1 sur C et 0 ailleurs) et celui de Bob est y·g(x,y). Maintenant, pour ε>0 (fixé pour l'instant), remplaçons la fonction discontinue g par une fonction h (à choisir), sur le quart de plan supérieur droit, qui soit suffisamment lisse, comprise entre 0 strictement et 1 au sens large, tendant « assez vite » vers 0 à l'infini, valant constamment 1 sur C (comme g), et ayant une valeur ≤ε en tout point situé à distance ≥ε de C. Remplaçons g par h dans la définition du jeu, c'est-à-dire qu'Alice choisit une exigence x, Bob une exigence y, et ils gagnent x·h(x,y) et y·h(x,y) respectivement (on peut y penser ainsi : ils obtiennent leur exigence avec probabilité h(x,y), c'est-à-dire de façon certaine si le point est dans C, et très faible dès qu'on n'en est pas très proche).

Considérons le[#17] point (x₀,y₀) de C (je parle de sa partie où x≥0 et y≥0, bien sûr) qui maximise x·y, et un point (x₁,y₁) du plan à coordonnées positives qui maximise x·y·h(x,y), où on a supposé ε < x₀·y₀. Alors par l'hypothèse faite sur h, le point (x₁,y₁) doit être à distance <ε de C (sinon, h<ε et le point (x₁,y₁) fait moins bien que (x₀,y₀)) ; mais par ailleurs, x₀·y₀ = x₀·y₀·h(x₀,y₀) ≤ x₁·y₁·h(x₁,y₁) ≤ x₁·y₁. Donc le point (x₁,y₁) est à la fois situé à distance ≤ε de C, mais en même temps au-dessus de l'hyperbole x·y = x₀·y₀, et il est alors clair que quand on rend ε arbitrairement petit, ces points (x₁,y₁) doivent tendre vers (x₀,y₀).

[#17] Le fait qu'un point de C maximisant x·y existe est une conséquence du fait que C est fermé et, puisqu'on s'est limité à x≥0 et y≥0 (et que je rappelle que C ne contient aucune droite horizontale ni verticale), borné. Le fait qu'il soit unique est un argument de convexité : si on a deux points qui réalisent le même produit, on peut montrer que leur milieu fait encore un peu mieux (géométriquement : si on prend deux points sur la même branche d'une hyperbole, leur milieu est du côté de l'hyperbole opposé au centre de celle-ci).

Or un point (x₁,y₁) qui maximise x·y·h(x,y) (et dont on vient de démontrer qu'il est proche de (x₀,y₀)) maximise, en particulier, x·h(x,y) à y constant (puisque y>0), c'est-à-dire maximise le gain d'Alice à stratégie fixée de Bob, et maximise y·h(x,y) à x constant, c'est-à-dire le gain de Bob. C'est donc un équilibre de Nash. Maintenant, il n'y a plus qu'à choisir un h tel que le jeu n'ait qu'un seul équilibre de Nash, ce qui n'est pas particulièrement difficile (Nash ne rentre pas dans les détails, mais Damme le fait[#18]).

[#18] Il montre qu'on peut prendre pour h la fonction valant 1 sur C et exp(−(s−1)²/ε) ailleurs, où s est la jauge associée à C, c'est-à-dire le plus petit t tel que le point soit dans t·C. C'est une façon assez raisonnable de rendre un peu flou le bord de C.

Concrètement, donc, si le jeu « Alice et Bob doivent se partager 100€ (chacun écrit une exigence en secret, et ils ne les obtiennent que si leur somme est ≤100€) » a toutes sortes d'équilibres de Nash, il n'en demeure qu'un si on remplace le jeu par le jeu à peine différent où chacun écrit une exigence en secret, et ils les obtiennent de façon certaine si leur somme est ≤100€, et avec probabilité exp(−(s−100€)²/(ε·100€)) si la somme est s≥100€ : un petit calcul pas compliqué montre que cet équilibre correspond à la situation où chacun des joueurs choisit 50€ · (1+ε+O(ε²)) (précisément 50€ · (1+√(1+4ε))/2). Et on peut représenter la négociation comme une convergence de stratégies vers cet unique équilibre.

Variation du point de guerre

Bref, on a montré l'existence d'une solution négociée rationnelle, soit de manière axiomatique, soit comme équilibre de Nash approché d'un jeu de négociation très légèrement modifié, et on a vu comment construire, géométriquement, la solution de cette négociation.

[Schéma]Il peut maintenant être intéressant de se demander comment varie ce point négocié en fonction de la position du point de guerre : c'est évidemment difficile de faire une analyse générale sans faire des hypothèses sur la forme de C, mais on a un feuilletage de C en demi-droites, chacune correspondant à un ensemble possible de points de guerre conduisant à une solution négociée donnée (la figure ci-contre illustre ce que je veux dire).

Le joueur qui veut améliorer le résultat des négociations a évidemment intérêt à déplacer le point de guerre dans le sens qui l'arrange, c'est-à-dire soit en améliorant son attaque (empirer l'utilité de la guerre pour son adversaire), soit sa défense (améliorer sa propre utilité de guerre), soit les deux. Quel est l'effet sur les négociations d'un petit investissement dans l'un ou l'autre ?

Je ne vois pas, là, comment éviter quelques calculs[#19] (et des formules péniblement tapées en MathML). Mettons que le bord de C soit paramétré (au moins localement) par y = h (x) avec h convexe et suffisamment régulière (disons de classe C²), et appelons (u,v) les coordonnées du point de guerre et (x,y) celles de la solution négociée. On doit donc avoir d'une part y = h (x) parce que la solution négociée est sur le bord, et, d'autre part, à cause de la condition sur la pente, h (x) = yv xu , c'est-à-dire (xu) h (x) + (yv) = 0 . En dérivant, on trouve dy = h (x) dx d'une part, et (dxdu) h (x) + (xu) h (x) dx + (dydv) = 0 , ce qui se résout en :

dx = h (x) du + dv 2 h (x) + (xu) h (x) et dy = h (x) 2 du + h (x) dv 2 h (x) + (xu) h (x)

[#19] Tout ce que je raconte ici n'est pas chez Nash, ce sont des élucubrations de ma part (enfin, ça n'a rien d'original, je prends juste la différentielle d'une fonction définie au-dessus pour essayer de comprendre comment les choses varient, donc je ne suis certainement pas le premier à faire ça, mais je veux juste dire que je n'ai pas de référence à proposer, et que les termes que j'utilise ne sont certainement pas standards).

Cette formule donne donc la variation (dx) d'utilité d'un des joueurs (Alice, mais on a évidemment la formule symétrique pour Bob) à l'issue de négociations pour un petit investissement (du) dans sa défense et un petit investissement (−dv) dans l'attaque de l'autre joueur (noter que h′ et h″ sont négatives ici). On prendra particulièrement attention à la quantité sans dimension x u = y v = h (x) 2 h (x) + (xu) h (x) que j'ai envie d'appeler rentabilité de la défense. Elle suggère de distinguer deux régimes selon le terme qui domine le dénominateur :

  • le régime de menace proche, lorsque xu est petit devant 2 h (x) h (x)  : dans ce cas, la rentabilité de la défense est proche de (mais inférieure ou égale à) ½, et on a approximativement dx = 12 du + 1 2 h (x) dv  ; et
  • le régime de menace lointaine, lorsque xu est grand devant 2 h (x) h (x)  : dans ce cas, la rentabilité de la défense est petite, et on a approximativement dx = h (x) (xu) h (x) du + 1 (xu) h (x) dv .

Les termes utilisés sont de moi et ne sont peut-être pas idéaux (parce que la menace proche pourrait aussi être qualifiée de faible et la menace lointaine de forte). Ici le calcul est fait du point de vue d'Alice, mais comme ∂x/∂u est égal à ∂y/∂v, le régime est le meme pour les deux joueurs.

Géométriquement, la question est, en gros, de savoir si le point de guerre est loin par rapport à la distance de courbure[#20] du bord de lu domaine réalisable. La deuxième et la troisième figure illustrant ce billet correspondent aux cas de menace « infiniment lointaine » et « infiniment proche » respectivement (sur l'une, on est de toute façon sur un point anguleux, bouger le point de guerre ne change rien à la solution négociée ; sur l'autre, le bord est complètement droit c'est-à-dire que h″ est nul). On peut voir ça comme une mesure de l'antagonisme des joueurs : le régime de menace proche est un régime où ils sont proches de la guerre, et en antagonisme à peu près complet, tandis que le régime de menace lointaine est un régime où ils peuvent mettre à profit mutuel la courbure du bord. Sur ma toute première figure, la rentabilité de la défense vaut environ 0.19, on est dans un régime de menace « plutôt lointaine ».

[#20] Il y a certainement une jolie interprétation géométrique, mais je ne l'ai pas trouvée. L'expression h′(x)/h″(x) correspond à la distance horizontale de l'axe (vertical) de la parabole (de direction asymptotique verticale) osculatrice à la courbe au point négocié. Donc en gros la question est de savoir si le point de guerre est plus ou moins loin, horizontalement, de l'axe de cette parabole. Mais dit comme ça ce n'est pas symétrique en les deux joueurs, donc ce n'est pas satisfaisant.

Dans le régime de menace proche, investir dans la défense est rentable comme si la probabilité de guerre était quasiment ½ (je répète ce que j'ai déjà dit : au final, la guerre n'a pas lieu, mais l'issue prévisible de celle-ci est cruciale pour déterminer la solution négociée, et je dis que le déplacement de l'issue de la guerre selon un axe se retrouve pour moitié dans le déplacement du point négocié selon cet axe). Cette rentabilité de la défense ne peut en aucun cas valoir plus que ½, et elle est petite dans le régime de menace lointaine. J'insiste sur le fait qu'elle est toujours la même pour les deux joueurs.

La rentabilité de l'attaque, bien sûr, est plus compliquée à formuler parce que c'est une quantité qui a une dimension[#21] (étant, disons, le changement de l'utilité d'Alice dans la solution négociée pour une petite variation de l'utilité de Bob dans la guerre), contrairement à la rentabilité de la défense. Mais de toute façon le rapport des deux rentabilités est toujours égal (au signe près) à la pente qui a servi de critère pour définir le point négocié.

[#21] L'utilité de chaque joueur a sa propre dimension (voir ce billet passé pour une longue explication sur la notion de dimension, mais ce que je veux dire concrètement, ici, c'est que toutes les constructions doivent rester invariantes par changement d'échelle séparément sur chaque axe : c'était mon point d'invariance par transformations affines sur chaque utilité dans la présentation axiomatique).

Et dans le monde réel ?

Bon, voilà pour l'analyse mathématique.

A-t-elle des leçons à nous apporter pour le monde réel ? Comme je l'ai dit dans le billet précédent, l'idée de ce genre d'analyse de modèles extrêmement simplifiés par rapport à la réalité consiste à les utiliser, non pas comme représentant la réalité, mais comme points de départ pour comprendre les comportements possibles de la réalité et chercher ensuite comment la réalité peut différer de ces modèles. Un peu comme parler de l'énergie cinétique ne permet pas de comprendre toute la subtilité des accidents routiers (c'est juste un nombre…), mais fournit un point de départ pour leur discussion.

Déjà, c'est une conclusion intéressante (et satisfaisante) que les acteurs rationnels et parfaitement bien informés ne se font pas la guerre. Comme de toute évidence la guerre existe dans la réalité, il est intéressant de se demander quelle hypothèse échoue (ou quelle hypothèse échoue principalement, parce que probablement toutes échouent). Mais il y a d'autres hypothèses un peu plus cachées dans ce modèle, par exemple le fait qu'une fois la solution négociée elle soit réellement appliquée (enfin, ça fait partie de l'hypothèse de parfaite information que les acteurs savent quelles seront les conséquences réelles de ce qu'ils négocient), ou qu'il y a exactement deux[#22] joueurs. Globalement parlant, quand même, on peut dire que la guerre résulte non pas d'un simple antagonisme d'intérêts, mais soit d'une divergence d'évaluation entre les parties sur l'issue de la guerre soit d'un choix idéologique de la faire.

[#22] Je n'ai pas du tout réfléchi à la façon intelligente de poser le problème s'il y a trois joueurs ou plus, ni cherché à lire la littérature (que j'imagine abondante) sur ce sujet.

Néanmoins, l'autre grande leçon de la théorie, c'est que la menace est cruciale pour déterminer l'issue des négociations. Et c'est un peu le paradoxe de la négociation : la guerre n'est pas rationnelle, elle est défavorable aux deux parties, et pourtant les parties doivent s'engager irrévocablement à la faire pour avoir une menace crédible comme base des négociations ; on souligne parfois qu'une partie qui en menace une autre va à l'encontre de ses propres intérêts, et de fait, si la menace se réalise, ce sera à l'encontre de ses intérêts, mais le fait de menacer et que la menace soit crédible est dans ses intérêts dans la négociation. Les acteurs rationnels et bien informés ne se feront pas la guerre, mais ils doivent néanmoins être prêts à la faire et engagés dans ce sens.

Et l'issue prévisible de cette guerre (prévisible car on suppose les acteurs parfaitement informés, mais je répète ce que j'ai déjà dit : ça ne signifie pas qu'elle soit déterministe — elle peut parfaitement faire intervenir le hasard), cette menace détermine l'issue des négociations aussi bien que le bord de l'espace matériellement réalisable : ce sont les deux ingrédients de la théorie de Nash pour déterminer la solution négociée.

Notamment, le fait de proférer des menaces qui soient gratuitement punitives (i.e., qui rendent très mauvaise l'utilité de l'autre joueur sans pour autant améliorer la sienne propre) est justifié par la théorie présentée ici : dans la phase de menace (que je n'ai quasiment pas analysée ici, mais elle le mériterait), les joueurs sont essentiellement dans la situation d'un jeu à somme nulle. (C'est peut-être triste sur le plan moral, mais les maths sont ce qu'elles sont.)

Symétriquement, investir pour sa propre défense peut être rentable. Ce que j'ai montré ci-dessus est que la rentabilité de la défense, définie comme le gain d'utilité sur la solution négociée pour un petit gain d'utilité sur le point de guerre, est la même pour les deux joueurs, et vaut au maximum ½, et est proche de ½ en situation de « menace proche », et beaucoup plus petite en situation de « menace lointaine ». Cette valeur de ½ ne doit sans doute pas être prise trop au sérieux dans le monde réel, mais elle dit en quelque sorte que même si on va éviter la guerre parce qu'on est parfaitement rationnel et informé et l'autre joueur aussi, il faut traiter l'investissement dans la défense comme si la guerre allait se produire avec une probabilité non nulle, certes inférieure à ½ mais qui peut aller jusqu'à cette valeur, et généralement non-négligeable à moins qu'on soit dans le régime de « menace lointaine ».

La signification de ces régimes de « menace proche » et de « menace lointaine » m'échappe assez, je dois le reconnaître (d'autant plus que j'avais commencé à écrire ce billet sans comprendre cette distinction). Donc je pose notamment la question de les caractériser, à la fois géométriquement, mais aussi de proposer des façons de reconnaître si une situation du monde réel se rattache plutôt à l'un ou l'autre régime[#23].

[#23] En gros, pour définir ces notions sans présupposer toute la théorie que j'ai exposée, l'idée est d'imaginer la rentabilité de la défense r : si je dépense pour améliorer l'issue de la guerre de du, j'en retire r·du à l'issue des négociations (donc je dois « faire comme si » la guerre allait se produire avec probabilité r) : lorsque r est petit (disons r≤¼) je suis en situation de menace lointaine, et lorsque r est grand (disons r≥¼, sachant que la théorie affirme r≤½ dans tous les cas), je suis en situation de menace proche. Bon, mais qu'est-ce que ça signifie un peu plus concrètement ?

↑Entry #2817 [older| permalink|newer] / ↑Entrée #2817 [précédente| permalien|suivante] ↑

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]