Bernard Salanié
Département d'Economie
salanie@ensae.fr -
Robert Cori
cori@lix.polytechnique.fr
La valeur de Shapley est un concept de solution couramment employé dans la théorie des jeux coopératifs [1]. On considère un ensemble N constitué de n joueurs qui doivent se partager un surplus (une certaine somme d'argent, par exemple). Ces joueurs peuvent se regrouper pour former des coalitions (ce sont des sous-ensembles S de N) qui s'approprient une partie du surplus et le redistribuent entre leurs membres. On suppose données les forces de chaque coalition, sous la forme de la fonction caractéristique v. Si S est une coalition quelconque, v(S) représente la part de surplus que S peut obtenir sans recourir à un accord avec les autres joueurs (qui sont membres de la coalition complémentaire N-S). La question à résoudre est la suivante : comment doit-on partager le surplus entre les n joueurs ? Divers concepts de solution ont été proposés. On retiendra ici l'un des plus populaires, qui a été introduit par Lloyd Shapley en 1953. La valeur de Shapley du joueur i dans le jeu donné par la fonction caractéristique v est la part du surplus qu'il convient de lui attribuer. Elle est donnée par la formule suivante :
On remarquera que 
est la contribution
marginale du joueur i à la coalition S. La valeur de Shapley est
donc une moyenne pondérée des contributions du joueur i à
chacune des coalitions possibles. Ce concept présente plusieurs
avantages :
On considère une classe particulière de jeux de vote, il s'agit
d'une assemblée où le joueur 
dispose de
votes. Les décisions se prennent à une majorité
qualifiée de M votes. La fonction caractéristique du jeu
coopératif sous-jacent est donc très simple, puisqu'elle est
donnée par
Le travail demandé est divisé en deux parties, la première
consiste à calculer la valeur de Shapley à l'aide de différentes
méthodes, la seconde à réaliser un algorithme qui teste de
l'équivalence entre deux systèmes de votes. Plus précisément
les méthodes de calcul des 
suggérées sont les
suivantes :
coalitions
S en déterminant le v(S) correspondant.
ud correspond à une coalition
non majoritaire (la somme des votes est inférieure à M) et
dont les feuilles représentent des coalitions majoritaires
grâce à un seul joueur. 
Deux systèmes de votes 
et auxquels sont attribuées les
majorités M et M' sont équivalents si les coalitions
majoritaires sont les mêmes dans les deux systèmes. On vous
demande de réaliser une procédure aussi efficace que possible qui
teste l'équivalence de deux systèmes de vote.
Vous comparerez l'efficacité des méthodes de calcul des coefficients de Shapley en utilisant des exemples arbitraires à 20 ou 25 joueurs. Vous pourrez aussi examiner l' exemple suivant:
Les élections législatives de mars 1996 en Espagne ont donné les résultats suivants (en agrégeant les plus petits partis) :