Le noyau : un partage dont aucun groupe ne veut sortir
Quand plusieurs personnes créent ensemble un gain, il faut le partager. Mais chaque groupe peut aussi menacer de faire bande à part. Un partage est stable si aucun groupe ne peut obtenir mieux en se retirant : c'est l'idée du noyau, définie par Donald Gillies en 1953 et déjà présente chez Edgeworth en 1881. Cette page dessine le noyau d'un jeu à trois joueurs, montre la logique implacable du marché des gants, fait jouer les coalitions qui font sécession, compare le noyau à la valeur de Shapley, et finit par un jeu où aucun partage n'est stable : le noyau est vide.
Les mots des coalitions
| Mot | Sens |
|---|---|
| Coalition | Un groupe de joueurs qui s'entendent. Sa valeur v(S) est ce qu'elle peut obtenir seule, sans les autres. |
| Partage | Une répartition de la valeur totale v(N), obtenue quand tout le monde coopère, entre les joueurs. |
| Sécession | Une coalition qui reçoit moins que sa valeur a intérêt à se retirer et à produire seule : elle bloque le partage. |
| Excès | Ce qui manque à une coalition : sa valeur moins ce qu'elle reçoit. Un excès positif signifie une menace de sécession. |
| Noyau | L'ensemble des partages qu'aucune coalition ne bloque : chaque groupe reçoit au moins sa valeur. Il peut être vide. |
Le triangle des partages et la forme du noyau
Trois associés, A, B et C, gagnent 100 ensemble. Seul, chacun ne gagne rien ; à deux, ils gagnent ce qu'indiquent les curseurs. Tous les partages de 100 tiennent dans un triangle : chaque sommet donne tout à un associé, le centre partage à égalité. La paire AB bloque tout partage qui lui donne moins que v(AB), c'est-à-dire qui donne trop à C : elle exclut un coin du triangle, autour du sommet C. Ce qui reste après les trois exclusions est le noyau. Déplacez le partage dans le triangle.
Le marché des gants : un gant de trop suffit
Des vendeurs possèdent chacun un gant gauche, d'autres un gant droit. Une paire vaut 1 ; un gant seul ne vaut rien. La valeur d'une coalition est le nombre de paires qu'elle peut former. Dans le noyau, la règle est brutale : s'il y a plus de gants droits que de gants gauches, même d'un seul, chaque possesseur d'un gant gauche reçoit toute la valeur de sa paire, et les gants droits ne reçoivent rien. Sinon, un gant droit laissé pour compte proposerait à un gant gauche un meilleur partage, et ils feraient sécession ensemble.
Les coalitions qui font sécession
Quatre communes, A, B, C et D, mettent en commun un service et économisent ensemble 10 M€. Chaque groupe de communes économiserait moins en s'associant seul (les valeurs sont dans le graphique). Partons d'un partage, puis laissons agir les menaces : à chaque étape, la coalition la plus lésée (celle dont l'excès est le plus grand) menace de partir ; pour la retenir, on lui rend ce qui lui manque, pris à parts égales aux autres. Le processus s'arrête quand plus personne ne peut menacer : le partage est entré dans le noyau.
Noyau et valeur de Shapley : pas toujours d'accord
La valeur de Shapley est-elle toujours dans le noyau ? Non. Si A possède une ressource dont B et C ont besoin, la paire AB vaut 90, la paire AC aussi, mais BC ne vaut rien. Le noyau exige que A reçoive au moins 80, alors que la valeur de Shapley ne lui donne que 63,3 : l'équité selon Shapley n'est pas stable. Lloyd Shapley a montré en 1971 que, dans les jeux convexes, où rejoindre un groupe plus grand rapporte toujours au moins autant, la valeur de Shapley est toujours dans le noyau.
Un jeu dont le noyau est vide
Trois associés gagnent 100 ensemble, et n'importe quelle paire gagne déjà 80 à elle seule. Pour retenir les trois paires, il faudrait donner au moins 80 à chacune. En additionnant les trois paires, chaque associé est compté deux fois : il faudrait donc distribuer au moins 3 × 80 / 2 = 120, alors qu'il n'y a que 100. Aucun partage n'est stable : quoi qu'on propose, une paire fait sécession, puis le laissé-pour-compte rachète l'un des deux, et ainsi de suite. Le théorème de Bondareva (1963) et Shapley (1967) généralise ce raisonnement : le noyau est vide exactement quand une famille de coalitions ainsi « pondérées » demande plus que le total.
Ce qu'il faut retenir
Stabilité
Un partage est dans le noyau si aucune coalition ne peut obtenir mieux en partant. Le noyau est une zone, pas une règle.
Concurrence
Dans le marché des gants, le noyau donne toute la valeur au camp rare, même s'il n'est rare que d'une unité.
Parfois rien
Quand des petites coalitions sont trop puissantes, aucun partage n'est stable : le noyau est vide, et les coalitions se font et se défont.
Pour aller plus loin
Les conventions de la page. Les joueurs seuls ne gagnent rien, sauf indication contraire. Le noyau à trois joueurs est calculé exactement, en découpant le triangle par les contraintes des paires. Le test de vacuité utilise le théorème de Bondareva-Shapley : la page cherche les poids λS ≥ 0 tels que chaque joueur soit couvert une fois et qui maximisent Σ λS v(S), en essayant toutes les bases du programme linéaire. Les jeux à quatre joueurs tirés au hasard sont rendus superadditifs (deux groupes séparés ne valent jamais plus que leur réunion).
Références. F. Y. Edgeworth, Mathematical Psychics (1881) ; D. B. Gillies, thèse de Princeton (1953) et « Solutions to general non-zero-sum games » (1959) ; O. Bondareva (1963) ; L. S. Shapley, « On balanced sets and cores » (1967) et « Cores of convex games » (1971) ; L. S. Shapley et M. Shubik, « On market games » (1969).
Pages voisines. La valeur de Shapley, les mariages stables (dont les appariements stables forment un noyau), le vote stratégique.