- Valeur de Shapley
-
En théorie des jeux, la valeur de Shapley permet une répartition équitable des gains dans un jeu coopératif.
Sommaire
Introduction
Dans un jeu coopératif, le problème le plus difficile à résoudre est la répartition des gains de la coopération. 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. 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 maximum 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 a n personnes, il y a 2n − 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:
La solution de Shapley
Shapley a développé une série d'axiomes qui conduisent à une solution unique dans le cas d'un jeu avec utilité transférable.
Les axiomes utilisés par Shapley sont les suivants:
(1) Symétrie
Pour toute permutation π et
, on a:φπ(i)(πv) = φi(v)
où φi(v) est appelé la valeur de Shapley et N est l’ensemble des joueurs (i=1,2,…,n). Si l'on permute les joueurs et le joueur i devient le joueur j, alors la valeur de Shapley pour le joueur i dans le jeu initial doit être égale à celle du joueur j dans le nouveau jeu. C’est dans ce sens que la solution est « équitable ».
(2) Optimalité de Pareto
La somme des valeurs des membres de la coalition doit être égale à ce que la coalition peut obtenir:
(3) Additivité
Soit un joueur i qui participe à deux jeux ayant les mêmes joueurs et dont les fonctions caractéristiques sont v et w. Si l'on considère ces deux jeux comme un seul (r=v+w), on aura une valeur φi(r). Cet axiome dit que:
Comme le jeu r aura sa propre structure et ses équilibres, cette restriction est moins plausible que les autres.
Shapley a montré que ces axiomes suffisent à déterminer une valeur unique pour tout jeu à n personnes. La valeur de Shapley est donnée par l'expression suivante:
![\varphi_{i} (v) = \sum_{ Z \subset N \atop i\in Z} {(n-z) !\, (z-1) !\, \over n ! \,} [ v(Z) - v(Z \backslash \{i\})]](f/8df730f57161dd35e8474253b4cc3e24.png)
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} = 0.5 [v(1,2)+ v(1)-v(2)] \quad ; \quad \varphi_{2} = 0.5 [v(1,2)+v(2)-v(1)]](2/a72df5ed58f2f8535ea9714e2852c9f8.png)
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:
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.
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.
Exemple
Le jeu avec la fonction caractéristique suivante:
a un noyau correspondant au point (0,0,120). Par contre, les valeurs de Shapley sont :
et ce point n'est pas dans le noyau.
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:
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).
Banzhaf a proposé un autre indice qui a 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
Lien externe
(en) Eyal Winter, The Shapley Value
-
![SSi(v) = \sum_{i\in S\geq N} \frac{(s-1)!(n-s)!}{n!} [v(S)-v(S-{i})]](e/90e603f2391462cd990abbd4fff2e6c6.png)
Wikimedia Foundation. 2010.
