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 ?
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−p)·y
, 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 arrivé, é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−p)·y
: 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€).
É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
?