Valeur de Shapley

Lloyd Shapley

En théorie des jeux, plus précisément dans un jeu coopératif, la valeur de Shapley donne une répartition équitable des gains aux joueurs. Elle est nommée en honneur à Lloyd Shapley qui introduit le concept en 1953.

Introduction

Dans un jeu coopératif, les joueurs collaborent pour obtenir un certain gain. Le problème est alors la répartition de ce gain entre les différents acteurs. Shapley a proposé une répartition « équitable » des gains de la coalition de n joueurs. Sa solution s’applique au cas où l’utilité est transférable. Prenons le cas d’entreprises qui forment un cartel et décident des quotas de production^{[réf. nécessaire]}. On a une solution sans utilité transférable (Nash a proposé une solution dans le cas de deux joueurs). Par contre, si le but du cartel est la maximisation du profit global et ensuite la répartition de ce montant entre les membres, alors on parle de solution avec utilité transférable.

Dans les jeux coopératifs on utilise le concept de fonction caractéristique. Soit v(C) la fonction qui donne la valeur maximale de la coalition C. Cette expression est appelée la fonction caractéristique du jeu. Par exemple, si la coalition comprenant les joueurs 1 et 2 obtient un profit de 600 $, on écrit v({1,2}) = 600.

On peut décrire un jeu en indiquant les valeurs de la fonction caractéristique pour toutes les coalitions possibles, y compris celles ne comprenant qu'un seul joueur. On parle souvent du jeu v au lieu de dire un jeu ayant la fonction caractéristique v.

Dans un jeu à n personnes, il y a $2^{n}-1$ coalitions non vides et autant de valeurs de la fonction caractéristique. Par définition, la valeur de la fonction caractéristique d'une coalition vide est égale à zéro.

Si des coalitions disjointes (C et Z) sont réunies en une grande coalition, on peut admettre que la valeur de la fonction caractéristique de cette grande coalition soit au moins égale à la somme des valeurs des deux coalitions:

$v(C\cup Z)\geq v(C)+v(Z)\qquad (C\cap Z=\emptyset )$

Définition

La valeur de Shapley pour le joueur i est notée $\varphi _{i}(v)$ et est définie par :

$\varphi _{i}(v)=\sum _{Z\subseteq N \atop i\in Z}{(n-|Z|)!\,(|Z|-1)!\, \over n!\,}\times [v(Z)-v(Z\backslash \{i\})]$

où |Z| est le nombre de joueurs de la coalition Z et n le nombre total de joueurs.

Dans le cas d'un jeu à deux personnes, on a :

$\varphi _{1}(v)=0.5[v(\{1,2\})+v(\{1\})-v(\{2\})]\quad ;\quad \varphi _{2}(v)=0.5[v(\{1,2\})+v(\{2\})-v(\{1\})]$

Si les joueurs isolés obtiennent le même profit, le profit total de la coalition est réparti en parts égales entre les deux joueurs. Formellement, si $v(\{1\})=v(\{2\})$ alors $\varphi _{1}(v)=\varphi _{2}(v)=0.5\times v(\{1,2\})$.

On peut interpréter la valeur de Shapley en supposant que chaque joueur entre de manière aléatoire dans chaque coalition possible. On lui attribue la valeur de l'accroissement de gain que la coalition peut réaliser avec son entrée. La valeur de Shapley correspond à la valeur marginale moyenne, pour les différentes coalitions, du joueur i.

Exemple

Le jeu avec la fonction caractéristique suivante:

$v(1,2,3)=120\ ;\ v(1,2)=0\ ;\ v(1,3)=v(2,3)=120\ ;\ v(1)=v(2)=v(3)=0$

a un noyau correspondant au point (0,0,120). Par contre, les valeurs de Shapley sont :

$\varphi _{1}=\varphi _{2}=20\quad ;\quad \varphi _{3}=80$

et ce point n'est pas dans le noyau.

Axiomes

Shapley a énoncé une série d'axiomes qui admettent pour unique solution les valeurs de Shapley dans le cas d'un jeu avec utilité transférable. Un jeu coopératif est la donné d'un ensemble fini de joueurs N et d'une fonction caractéristique v, qui à tout sous-ensemble de joueurs C, associe v(C), le gain de C. Dans la suite on suppose que N = {1, 2, ..., n}.

Les axiomes utilisés par Shapley sont les suivants :

(1) Efficacité. la somme des valeurs attribués aux joueurs doit être égale à ce que la coalition de tous les joueurs peut obtenir :

$\sum _{i\in N}\varphi _{i}(v)=v(N)$

(2) Symétrie. Si deux joueurs peuvent se substituer dans chaque coalition, alors ils perçoivent le même gain :

Si $v(S\cup \{i\})=v(S\cup \{j\})$ pour tout sous-ensemble S de joueurs qui ne contient ni i, ni j, alors $\varphi _{i}(v)=\varphi _{j}(v)$.

(3) Additivité (aussi appelé linéarité). Soit un joueur i qui participe à deux jeux ayant les mêmes joueurs et dont les fonctions caractéristiques sont v et w. L'axiome suivant lie la somme des valeurs de Shapley dans les deux jeux et la valeur de Shapley dans le jeu défini à partir de la somme des gains des deux jeux (v + w) :

$\varphi _{i}(v+w)=\varphi _{i}(v)+\varphi _{i}(w)$

(4) Joueur nul. Un joueur i est nul pour $v$ si $v(S\cup \{i\})=v(S)$ pour toute coalition $S$. Pour tout joueur i nul pour $v$, on a $\varphi _{i}(v)=0$.

Harsanyi a développé un modèle plus général qui comprend, comme cas particulier, la solution coopérative de Nash et la valeur de Shapley.

L’indice de pouvoir de Shapley-Shubik

Dans une assemblée législative, il y a plusieurs possibilités de coalition entre les partis. Si l’on attribue une valeur de 1 aux coalitions gagnantes et 0 aux autres, alors la valeur de Shapley est une mesure du pouvoir des partis. Pour le joueur i, la formule de l'indice est :

$SSi(v)=\sum _{S\subset N \atop i\in S}{(n-|S|)!\,(|S|-1)!\, \over n!\,}\times [v(S)-v(S\backslash \{i\})]$

où S est une coalition, |S| est la taille de la coalition gagnante (c'est-à-dire le nombre d'individus dans la coalition), n le nombre de joueurs total du jeu et un joueur i a du pouvoir si v(S)=1 et v(S-{i})=0.

Prenons l’exemple du Conseil de sécurité des Nations unies. Il y a 5 membres permanents qui ont droit de veto et 10 autres membres. Une résolution doit obtenir 9 voix et aucun veto pour être acceptée. L’indice de Shapley-Shubik nous dit que le pouvoir d’un membre permanent est beaucoup plus fort que celui d’un membre non permanent (0,1963 contre 0,00186).

Le cas du Conseil de l'Union européenne est encore plus intéressant. De 1958 à 1973, la majorité qualifiée était de 17 voix. Or, le Luxembourg avait une voix et aucun pouvoir car aucune coalition ne pouvait devenir gagnante avec sa voix. Avec l’entrée de nouveaux pays, son pouvoir passe à 0,95 % en 1973 et à 3,02 % en 1981 (comme le Danemark qui a une population dix fois plus grande).

De nombreux autres théoriciens, dont Banzhaf, ont proposé des indices de pouvoir, plus ou moins adaptés à d'autres contextes et avec des propriétés similaires.

Bibliographie

• J.F. Banzhaf, Weighted voting doesn't work: A mathematical analysis, Rutgers Law Review, 19, 1965, p. 317-343
• J.F. Nash, The Bargaining Problem, Econometrica, 18, 1950, p. 155-162
• L. S. Shapley, « A Value for n-Person Games », in H. Kuhn and A. Tucker (Eds.), Contribution to the Theory of Games, vol. II, Princeton, 1953, p. 303-317
• L.S. Shapley, L.S. and M. Shubik, A Method for Evaluating the Distribution of Power in a Committee System, American Political Science Review, 48, 1954, p. 787-792