David Madore's WebLog: 2025-02

Vous êtes sur le blog de David Madore, qui, comme le reste de ce site web, parle de tout et de n'importe quoi (surtout de n'importe quoi, en fait), des maths à la moto et ma vie quotidienne, en passant par les langues, la politique, la philo de comptoir, la géographie, et beaucoup de râleries sur le fait que les ordinateurs ne marchent pas, ainsi que d'occasionnels rappels du fait que je préfère les garçons, et des petites fictions volontairement fragmentaires que je publie sous le nom collectif de fragments littéraires gratuits. • Ce blog eut été bilingue à ses débuts (certaines entrées étaient en anglais, d'autres en français, et quelques unes traduites dans les deux langues) ; il est maintenant presque exclusivement en français, mais je ne m'interdis pas d'écrire en anglais à l'occasion. • Pour naviguer, sachez que les entrées sont listées par ordre chronologique inverse (i.e., la plus récente est en haut). Cette page-ci rassemble les entrées publiées en février 2025 : il y a aussi un tableau par mois à la fin de cette page, et un index de toutes les entrées. Certaines de mes entrées sont rangées dans une ou plusieurs « catégories » (indiqués à la fin de l'entrée elle-même), mais ce système de rangement n'est pas très cohérent. Le permalien de chaque entrée est dans la date, et il est aussi rappelé avant et après le texte de l'entrée elle-même.

You are on David Madore's blog which, like the rest of this web site, is about everything and anything (mostly anything, really), from math to motorcycling and my daily life, but also languages, politics, amateur(ish) philosophy, geography, lots of ranting about the fact that computers don't work, occasional reminders of the fact that I prefer men, and some voluntarily fragmentary fictions that I publish under the collective name of gratuitous literary fragments. • This blog used to be bilingual at its beginning (some entries were in English, others in French, and a few translated in both languages); it is now almost exclusively in French, but I'm not ruling out writing English blog entries in the future. • To navigate, note that the entries are listed in reverse chronological order (i.e., the most recent is on top). This page lists the entries published in February 2025: there is also a table of months at the end of this page, and an index of all entries. Some entries are classified into one or more “categories” (indicated at the end of the entry itself), but this organization isn't very coherent. The permalink of each entry is in its date, and it is also reproduced before and after the text of the entry itself.

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

Entries published in February 2025 / Entrées publiées en février 2025:

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

(mercredi)

Une tentative pour vulgariser les bases de la calculabilité

Méta : J'étais initialement parti pour écrire un billet sur la calculabilité d'ordre supérieur (il aurait eu pour titre calculabilité d'ordre supérieur : comment un programme peut-il interroger un autre programme ?). Mais en commençant à écrire l'introduction pour la rendre aussi compréhensible que possible, je me suis dit que, tant qu'à faire, ce serait plus intéressant d'essayer de faire un billet autonome sur les bases de la calculabilité, en cherchant à le rendre à peu près accessible au grand public[#]. Après tout, ce sont des notions que j'enseigne à Télécom Paris, ça peut être intéressant d'essayer d'isoler, de façon moins mathématique, les messages principaux que j'essaie de communiquer aux étudiants.

[#] La notion de grand public est, évidemment, assez mal définie. Par exemple, on m'a affirmé que si je fais une phrase avec une subordonnée, l'immense majorité des gens ne savent plus lire. Bon, c'est peut-être vrai, mais je pense que de toute façon cette immense majorité ne sera en aucun cas intéressé par faire l'effort de concentration minimal pour comprendre une tentative de vulgarisation d'un sujet scientifique, même si cette vulgarisation est optimalement faite ; et de toute façon, elle ne lira jamais mon blog vu que, même sur un sujet qui n'a rien de technique, j'ai tendance à faire des phrases à la Proust. Donc disons que je parle à des gens capables de lire une phrase de plus que quelques mots sans perdre le fil de leurs pensées, et qui acceptent de faire un peu d'efforts de concentration. En revanche, j'essaie de ne présupposer du lecteur aucune connaissance préalable en maths ni en informatique. (Ce n'est pas toujours évident, parce que parfois on utilise un terme technique sans s'en rendre compte, et ça a évidemment pu m'échapper.)

(Plan :)

☞ Qu'est-ce qu'un algorithme ?

Bref, de quoi s'agit-il ?

La théorie de la calculabilité, c'est l'étude mathématique de ce que peut, en théorie, faire un ordinateur ou un programme informatique, ou plus exactement, de ce que peut faire un algorithme en l'absence de toute considération d'efficacité.

Avant toute chose, il faut donc que j'explique un peu ce qu'est un algorithme.

Si je dois tenter une définition d'algorithme ce sera quelque chose comme ceci : un plan précis d'exécution d'étapes simples et mécaniques de calcul ou de traitement de données, pouvant être réalisé sans aucune réflexion pour aboutir à un résultat bien défini, et qui est donc, en particulier, réalisable par un ordinateur (ou, en principe, par un humain suffisamment patient).

Première difficulté de la vulgarisation, ici, que mon ami David Monniaux a souvent montrée du doigt : à cause de la manière dont beaucoup de journalistes ont utilisé le mot, de manière volontiers péjorative, comme une boîte noire dont on ne comprend pas pas le fonctionnement, et/ou dont le résultat n'est pas bien spécifié, le grand public a en tête une notion de ce qu'est un algorithme possiblement très différente de son sens technique. La définition que je propose de plan précis d'exécution d'étapes simples et mécaniques de calcul ou de traitement de données, pouvant être réalisé sans aucune réflexion pour aboutir à un résultat bien défini, et qui est donc, en particulier, réalisable par un ordinateur (ou, en principe, par un humain suffisamment patient) est peut-être trop longue pour être vraiment parlante (cf. ce fil Bluesky pour une discussion).

D'autres gens proposent de dire des choses plus courtes pour définir algorithme, par exemple une recette de cuisine ou ensemble d'étapes permettant de réaliser une action : c'est peut-être plus clair mais néanmoins exagérément vague pour essayer d'en parler ensuite de façon précise. (Le problème avec recette de cuisine ou plan pour réaliser une action c'est que ① ça ne limite pas le domaine au traitement de l'information, or je ne dirais pas que, disons, un plan pour faire un coup d'état est un algorithme, et ② une recette de cuisine, normalement, n'implique pas de boucles — même si ça peut impliquer d'attendre que quelque chose se produise —, encore moins de récursion[#2].) Donc c'est un peu réducteur. Un algorithme au sens utilisé ici est constitué d'étapes extrêmement simples et très précisément définies, mais au final on peut être amené à faire des choses immensément compliquées avec, parce qu'on peut les combiner de façon très complexe.

[#2] On ne va jamais être amené à se demander est-ce que cette recette de cuisine termine ? alors que c'est, justement, une des questions cruciales qu'on peut être amené à se poser (et à ne pas savoir répondre) pour un algorithme.

☞ La calculabilité n'est pas l'étude des ordinateurs

Néanmoins, il me semble important de souligner qu'un algorithme n'est pas forcément quelque chose qui va être exécuté par un ordinateur. Il s'agit juste d'exécuter mécaniquement des étapes très simples, sans jamais se tromper, en suivant les instructions fournies (celles qui constituent l'algorithme). En principe, donc, n'importe quel algorithme peut être suivi par un humain comme il peut l'être par un ordinateur (et tout ce que peut faire un ordinateur peut aussi être fait par un humain) : il s'agira « juste » de disposer d'une patience infinie, d'un temps illimité, et d'une quantité illimitée de papier, et d'une capacité incroyable à ne jamais se tromper, chose pour laquelle les ordinateurs sont extrêmement bons et les humains extrêmement mauvais, mais je veux vraiment souligner que les ordinateurs ne peuvent rien faire qui ne soit pas, en principe, aussi faisable par un humain dans ces conditions (patience infinie, etc.).

Ce que je dis là n'est pas purement théorique : il y a vraiment des algorithmes utilisables par des humains, et d'ailleurs utilisés par des humains[#3]. J'espère qu'on apprend encore à l'école à poser une multiplication : c'est bien un algorithme qui est enseigné, et on devrait être convaincu qu'il permet, en principe, à un humain assez motivé, sans calculatrice, de savoir combien vaut 96 889 010 407 × 94 143 178 827, même si ça va être long et fastidieux (et si on pose la question à l'ordinateur, il va utiliser un algorithme qui n'est pas substantiellement différent, au moins pour des nombres de cette taille, de celui qu'on a appris à l'école).

[#3] Ou du moins, qui l'ont été : le nombre de situations où des humains calculent des multiplications de grands nombres à la main doit maintenant être minuscule ; mais historiquement, il y avait des gens dont c'était le métier. Par exemple, quand Urbain Le Verrier (connu pour sa découverte de la planète Neptune) prend la tête de l'Observatoire de Paris en 1853, puis l'amiral Mouchez en 1887, les tâches ingrates de calcul numérique sont déléguées à des « calculatrices » (ce sont essentiellement des femmes, mal rémunérées et très peu considérées). Toutes les tables de logarithmes publiées avant le 20e siècle ont aussi, bien sûr, été calculées par des humains appliquant des algorithmes longs et fastidieux (qui prennent maintenant une fraction de seconde à un ordinateur). Dans la nouvelle The Feeling of Power (1957) (disponible en ligne ici), Asimov imagine un monde dans lequel plus personne ne sait faire de calculs autrement que sur un ordinateur, et quelqu'un redécouvre qu'on peut les faire à la main.

La calculabilité n'a donc pas vraiment à voir avec les ordinateurs, ou comme le dit un adage (attribué sans doute à tort à E. W. Dijkstra), l'informatique n'est pas plus l'étude des ordinateurs que l'astronomie n'est l'étude des télescopes.

☞ Entrées, sorties, programme et extension

Un algorithme, donc, prend quelque chose en entrée (on peut aussi parler des arguments passés à l'algorithme), par exemple deux nombres à multiplier, et renvoie un certain résultat en sortie, par exemple le résultat de la multiplication. (Les entrées et les sorties seront toutes des « données finies », terme sur lequel je vais revenir ci-dessous.) Ce qu'on a fait, c'est calculer une certaine fonction au sens mathématique.

La différence entre la fonction mathématique et l'algorithme qui la calcule, c'est qu'il peut y avoir toutes sortes de façons de calculer la même fonction (par exemple, différentes façons de poser une multiplication, qui aboutissent au même résultat) : la fonction, c'est l'opération abstraite qui associe un résultat à des arguments, alors que l'algorithme, c'est le plan d'exécution par lequel on est arrivé à ce résultat. Il y a des fonctions mathématiques qui sont plus ou moins difficiles à calculer par un algorithme, et certaines qui sont même impossibles à calculer algorithmiquement (elles sont non-calculables), mais qui n'en ont pas moins un sens mathématique.

On peut aussi utiliser les termes d'extension et d'intention (ou intension ? cf. ce billet au sujet de ce mot) : l'extension, c'est la fonction mathématique qu'on calcule, tandis que l'intenſion (quelle que soit la manière dont on l'écrit), c'est l'algorithme, c'est-à-dire la manière dont on calcule cette fonction.

Autre difficulté : est-ce qu'algorithme est synonyme de programme ? En calculabilité, les deux mots sont utilisés de façon essentiellement interchangeables. Mais il y a au moins des différences d'usage, au moins dans le contexte de l'informatique plus large[#4]. Le terme d'algorithme est plus abstrait et fait souvent référence au plan de fonctionnement débarrassé de ses détails relatifs à l'usage, par exemple, d'un langage de programmation particulier (on parle d'implémentation pour l'écriture concrète d'un algorithme dans un système informatique particulier), mais la limite entre l'algorithme et son implémentation est un peu floue. On parle plus volontiers d'algorithme, par exemple, quand on ne s'intéresse qu'à la partie proprement calculatoire ; alors qu'un programme peut faire intervenir une interface utilisateur, des lectures et écritures sur écran, clavier ou disque, ce genre de choses. En outre, on peut considérer (ou pas…) qu'un algorithme doit répondre à un problème bien posé[#5] alors qu'un programme est simplement une suite d'instruction données à un ordinateur. (Et évidemment, programme sous-entend un contexte informatique alors qu'un algorithme est, comme je le souligne ci-dessus, théoriquement applicable par un humain.) Convenons, néanmoins, d'ignorer ces subtilités et que, dans ce qui suit, puisque je veux parler de calculabilité, et même si ce n'est pas vraiment l'usage habituel, programme signifie la même chose qu'algorithme, et que j'utiliserai ci-dessous ces termes de façon essentiellement interchangeable[#6].

[#4] J'aurais du mal à dire, par exemple, qu'un navigateur comme Firefox est un algorithme. C'est un programme. Ce programme utilise toutes sortes d'algorithmes à différents endroits (par exemple, pour organiser les marque-page il y a certainement des algorithmes de tri), mais il n'est pas un algorithme dans l'usage normal du mot (ne serait-ce que parce qu'il n'arrête pas d'avoir des nouvelles versions, alors qu'un algorithme est quelque chose de plus abstrait). A contrario, la manière dont on fait une multiplication à l'école primaire est un algorithme, je ne qualifierais pas ça de programme (ne serait-ce que parce qu'il n'y a pas d'ordinateur en vue).

[#5] Ce que je veux dire, c'est que, selon cette distinction terminologique (avec laquelle je ne suis pas forcément d'accord), un algorithme doit avoir une spécification : il prend en entrée certaines données et produit un certain résultat qui doit répondre à un certain problème mathématiquement bien défini (la spécification de l'algorithme) ; et on est censé prouver mathématiquement que l'algorithme correspond bien à sa spécification. Dans ce sens, ChatGPT n'est pas un algorithme (même s'il y a des algorithmes utilisés pour, par exemple, calculer ses paramètres à partir d'un corpus d'entraînement, ou pour produire la sortie à partir de ses poids), parce qu'on ne peut pas dire qu'il réponde à une quelconque spécification. En quelque sorte, cette distinction terminologique cherche à refléter la distinction entre les méthodes formelles/rigoureuses et heuristiques en informatique, en réservant le terme d'algorithme pour les premières.

[#6] Dans la mesure où je fais une différence (et elle ne sera pas forcément systématique), c'est que quand un programme prend en entrée un autre programme (situation qui va jouer un rôle important dans la suite), j'ai du mal à appeler le deuxième un algorithme (en effet, il doit être écrit dans un cadre bien précis, avec des instructions bien précises, et il ne vient pas avec une sorte de spécification ou de mode d'emploi, et justement on va voir que c'est difficile de l'analyser, donc toutes ces raisons suggèrent que le terme de programme est plus approprié).

Encore une autre difficulté est de savoir si un algorithme a le droit de faire appel au hasard. En calculabilité, la réponse est implicitement non (le hasard n'est pas calculable, il s'oppose même au calculable[#7] en un sens bien précis), mais dans d'autres branches de l'informatique, la notion d'algorithme faisant intervenir le hasard (algorithme « randomisé ») est légitime.

[#7] Ce qui ne veut pas dire qu'il n'y ait pas toutes sortes de questions fascinantes de calculabilité à se poser sur ce qu'on peut faire si on dispose d'une source de hasard (peut-on faire avec le hasard des choses qu'on ne peut pas faire sans hasard ? essentiellement non, mais ça dépend de l'interprétation précise de la question que je viens de dire de façon trop vague ; pour une référence précise, voir le fact ① sous cette question).

Bref, le domaine de la calculabilité a pour but d'étudier ce que, de façon théorique, un algorithme peut ou ne peut pas faire, et donc, pour commencer, de proposer une définition mathématiquement acceptable de ce qu'un algorithme signifie.

☞ Sans préoccupations de ressources !

Mais une autre précision importante est que la calculabilité ne s'intéresse pas aux « ressources » consommées par l'algorithme lors de son exécution, c'est-à-dire : le temps qu'il met, la mémoire qu'il utilise, ou toute autre ressource (l'énergie consommée sur un ordinateur réel). On suppose qu'il dispose de ressources (temps, mémoire, etc.) « finies à chaque instant, mais illimitées a priori », et c'est ce qui rend le sujet assez théorique. (Certains des algorithmes considérés par la calculabilité sont tout à fait inapplicables sur un ordinateur réel, en ce qu'ils prendraient bien plus que la durée de vie de l'Univers à s'exécuter sur une entrée modeste : pour autant, on dira bien que le résultat est calculable en fonction de l'entrée.) En cela, la calculabilité s'oppose à d'autres domaines de l'informatique, tels que :

  • l'algorithmique, qui est l'art d'écrire des algorithmes (de préférence, efficaces) pour résoudre des problèmes bien posés,
  • la complexité, qui est l'étude mathématique des ressources (principalement : temps, mémoire) consommées par un algorithme lors de son exécution, et de ce que peut faire un algorithme disposant de telles ressources limitées.

La complexité est une discipline beaucoup plus soigneuse que la calculabilité : elle ne cherche pas juste à savoir si des choses sont « en principe possible, avec assez de temps et de mémoire », mais combien ça va effectivement[#8] coûter en temps et en mémoire. La calculabilité se moque de ces questions d'efficacité, elle ne cherche à faire dans la dentelle[#9], donc c'est une discipline assez théorique.

[#8] Bon, effectivement avec des pincettes, quand même, parce que c'est généralement une complexité asymptotique, c'est-à-dire « à l'infini », donc ça reste assez théorique.

[#9] Par exemple, sur la question de savoir décider si un nombre n est premier, la calculabilité peut très bien dire oui, c'est une question décidable [=calculable], parce qu'on peut tester tous les produits i×j pour 2≤in et 2≤jn, et voir si l'un d'entre eux est égal à n : c'est une façon ridiculement inefficace de savoir si un nombre est premier, mais pour la calculabilité, c'est un algorithme qui marche, c'est tout ce qui compte.

Par exemple, on pourra dire en calculabilité que les décimales du nombre π sont calculables (il existe un programme qui, quand on lui donne n, renvoie les n premières décimales — ou juste la n-ième, pour la calculabilité ça ne change rien), mais évidemment, si vous voulez les calculer vraiment, il vaut mieux regarder un peu plus finement quel algorithme utiliser pour que ce soit efficace. (Et, dans le monde réel, il est peu vraisemblable qu'on arrive jamais à calculer la 101000000-ième décimale de π, alors que pour ce qui est de la calculabilité, il n'y a pas de problème particulier.)

À cause de ces ressources illimitées données aux algorithmes, les résultats positifs de la calculabilité (telle ou telle chose est calculable) sont plus faibles que ceux de la complexité (telle ou telle chose est calculable en temps ceci-cela ou en mémoire ceci-cela) ; mais symétriquement, les résultats négatifs de la calculabilité sont d'autant plus forts : quand on montre que quelque chose n'est pas calculable au sens de la calculabilité, c'est que ce n'est pas possible d'y arriver (de manière systématique), même si on n'a aucune contrainte sur le temps ou la mémoire. Et c'est sans doute pour cette raison qu'on s'intéresse beaucoup, en calculabilité, aux résultats négatifs (je vais notamment démontrer, ci-dessous, l'indécidabilité du problème de l'arrêt, qui est l'exemple fondamental dans ce sens).

☞ La « thèse » de Church-Turing

Mais la première chose avant d'étudier les algorithmes, c'est d'essayer de définir précisément ce qu'est un algorithme, pour pouvoir espérer raisonner[#10] mathématiquement dessus.

[#10] L'algorithmique n'a pas vraiment besoin de définir exactement ce qu'est un algorithme, puisqu'elle cherche juste à en construire : on peut se contenter de savoir, en pratique, reconnaître qu'on a bien construit des algorithmes. Mais pour espérer prouver des résultats négatifs du type aucun algorithme ne peut faire ceci-cela, il faut forcément une définition mathématiquement robuste.

Une des constatations importantes de la théorie de la calculabilité est la thèse de Church-Turing, qui affirme, grosso modo, que toute approche raisonnable pour définir la notion calculabilité algorithmique (déterministe, finitiste) aboutit à la même notion. Expliquons un peu ce que ça veut dire.

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

↓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 ?

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

Continue to older entries. / Continuer à lire les entrées plus anciennes.


Entries by month / Entrées par mois:

2025 Jan 2025 Feb 2025
2024 Jan 2024 Feb 2024 Mar 2024 Apr 2024 May 2024 Jun 2024 Jul 2024 Aug 2024 Sep 2024 Oct 2024 Nov 2024 Dec 2024
2023 Jan 2023 Feb 2023 Mar 2023 Apr 2023 May 2023 Jun 2023 Jul 2023 Aug 2023 Sep 2023 Oct 2023 Nov 2023 Dec 2023
2022 Jan 2022 Feb 2022 Mar 2022 Apr 2022 May 2022 Jun 2022 Jul 2022 Aug 2022 Sep 2022 Oct 2022 Nov 2022 Dec 2022
2021 Jan 2021 Feb 2021 Mar 2021 Apr 2021 May 2021 Jun 2021 Jul 2021 Aug 2021 Sep 2021 Oct 2021 Nov 2021 Dec 2021
2020 Jan 2020 Feb 2020 Mar 2020 Apr 2020 May 2020 Jun 2020 Jul 2020 Aug 2020 Sep 2020 Oct 2020 Nov 2020 Dec 2020
2019 Jan 2019 Feb 2019 Mar 2019 Apr 2019 May 2019 Jun 2019 Jul 2019 Aug 2019 Sep 2019 Oct 2019 Nov 2019 Dec 2019
2018 Jan 2018 Feb 2018 Mar 2018 Apr 2018 May 2018 Jun 2018 Jul 2018 Aug 2018 Sep 2018 Oct 2018 Nov 2018 Dec 2018
2017 Jan 2017 Feb 2017 Mar 2017 Apr 2017 May 2017 Jun 2017 Jul 2017 Aug 2017 Sep 2017 Oct 2017 Nov 2017 Dec 2017
2016 Jan 2016 Feb 2016 Mar 2016 Apr 2016 May 2016 Jun 2016 Jul 2016 Aug 2016 Sep 2016 Oct 2016 Nov 2016 Dec 2016
2015 Jan 2015 Feb 2015 Mar 2015 Apr 2015 May 2015 Jun 2015 Jul 2015 Aug 2015 Sep 2015 Oct 2015 Nov 2015 Dec 2015
2014 Jan 2014 Feb 2014 Mar 2014 Apr 2014 May 2014 Jun 2014 Jul 2014 Aug 2014 Sep 2014 Oct 2014 Nov 2014 Dec 2014
2013 Jan 2013 Feb 2013 Mar 2013 Apr 2013 May 2013 Jun 2013 Jul 2013 Aug 2013 Sep 2013 Oct 2013 Nov 2013 Dec 2013
2012 Jan 2012 Feb 2012 Mar 2012 Apr 2012 May 2012 Jun 2012 Jul 2012 Aug 2012 Sep 2012 Oct 2012 Nov 2012 Dec 2012
2011 Jan 2011 Feb 2011 Mar 2011 Apr 2011 May 2011 Jun 2011 Jul 2011 Aug 2011 Sep 2011 Oct 2011 Nov 2011 Dec 2011
2010 Jan 2010 Feb 2010 Mar 2010 Apr 2010 May 2010 Jun 2010 Jul 2010 Aug 2010 Sep 2010 Oct 2010 Nov 2010 Dec 2010
2009 Jan 2009 Feb 2009 Mar 2009 Apr 2009 May 2009 Jun 2009 Jul 2009 Aug 2009 Sep 2009 Oct 2009 Nov 2009 Dec 2009
2008 Jan 2008 Feb 2008 Mar 2008 Apr 2008 May 2008 Jun 2008 Jul 2008 Aug 2008 Sep 2008 Oct 2008 Nov 2008 Dec 2008
2007 Jan 2007 Feb 2007 Mar 2007 Apr 2007 May 2007 Jun 2007 Jul 2007 Aug 2007 Sep 2007 Oct 2007 Nov 2007 Dec 2007
2006 Jan 2006 Feb 2006 Mar 2006 Apr 2006 May 2006 Jun 2006 Jul 2006 Aug 2006 Sep 2006 Oct 2006 Nov 2006 Dec 2006
2005 Jan 2005 Feb 2005 Mar 2005 Apr 2005 May 2005 Jun 2005 Jul 2005 Aug 2005 Sep 2005 Oct 2005 Nov 2005 Dec 2005
2004 Jan 2004 Feb 2004 Mar 2004 Apr 2004 May 2004 Jun 2004 Jul 2004 Aug 2004 Sep 2004 Oct 2004 Nov 2004 Dec 2004
2003 May 2003 Jun 2003 Jul 2003 Aug 2003 Sep 2003 Oct 2003 Nov 2003 Dec 2003

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