Jeu du mille-pattes
From Wikipedia, the free encyclopedia
Les informations figurant dans cet article ou cette section doivent être reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » ().
En théorie des jeux, le jeu du mille-pattes, introduit par Robert W. Rosenthal en 1981, est un jeu sous forme extensive dans lequel deux joueurs choisissent à chaque tour de prendre une somme légèrement plus importante dans un pot croissant lentement, ou bien de donner le pot à l'autre joueur. Les gains sont déterminés de sorte que si le joueur A donne le pot à son adversaire, et si l'adversaire prend le pot au tour suivant, le joueur A recevra légèrement moins que s'il avait pris le pot dès ce tour. Tandis que la version traditionnelle du jeu du mille pattes avait 100 tours (le nom du « mille-pattes » est centipede en anglais), chaque jeu avec cette structure mais un nombre différent de tours est encore appelé « jeu du mille-pattes ». Ce qui est particulièrement intéressant, c'est que l'unique équilibre parfait en sous-jeux (et chaque équilibre de Nash) de ce jeu indique que le premier joueur prend le pot dès le premier tour du jeu; cependant, expérimentalement, relativement peu de joueurs jouent ainsi, et obtiennent un meilleur résultat que celui qui est prédit par l'analyse de la théorie des équilibres. Ces résultats servent à montrer que les équilibres parfaits en sous-jeux et les équilibres de Nash échouent dans la prédiction du comportement humain dans certaines circonstances. Le jeu du mille-pattes est souvent utilisé en introduction des cours de théorie des jeux pour mettre en lumière le concept d'induction à rebours et d'élimination itérée des stratégies dominées, qui permettent de donner une solution au jeu.
Une version possible de ce jeu est la suivante :
«
Considérons deux joueurs : Alice et Bob. Alice commence. Au début, Alice a deux piles de pièces en face d'elle : l'une en contient quatre et l'autre une seule. Chaque joueur a deux mouvements possibles : soit « prendre » la plus grosse pile de pièces et donner la plus petite à l'autre joueur, soit « pousser » les deux piles vers l'autre joueur. Chaque fois que les piles de pièces traversent la table, la quantité de pièces dans chaque pile double. Par exemple, supposons qu'Alice choisisse de « pousser » les piles pour commencer : Bob aura devant lui une pile de deux pièces et une pile de huit. Bob peut maintenant jouer pour prendre la pile de huit pièces et donner deux pièces à Alice, ou il peut « pousser » à nouveau les deux piles à Alice, ce qui augmentera à nouveau la taille des piles jusqu'à quatre et seize pièces. Le jeu continue pour un nombre déterminé de tours, ou jusqu'à ce qu'un joueur décide de mettre fin au jeu en prenant le pot.
»
L'ajout de pièces est effectué par une externalité, et n'est donc pas payée par l'autre joueur.
Une deuxième version possible de ce jeu est représentée par le diagramme ci-dessus : dans cette version, passer le pot est représenté par le mouvement ‘R’ et prendre le pot par le mouvement ‘D’. Les nombres ‘1’ et ‘2’ en haut du diagramme montrent l'alternance des joueurs notés 1 et 2, et le nombre en dessous de chaque branche montre le gain pour les joueurs 1 et 2 respectivement.
Analyse de l'équilibre et induction à rebours
Les outils de la théorie des jeux standard prévoient que le joueur 1 va prendre le pot dès le premier tour. Au jeu du mille-pattes, une stratégie pure consiste en un ensemble d'actions (une pour chaque situation où il faut faire un choix, même si certains de ces endroits ne seront jamais atteintes) et une stratégie mixte est une distribution de probabilités sur les stratégies pures possibles. Il y a plusieurs stratégies pures qui sont des équilibres de Nash dans le jeu du mille-pattes et une infinité de stratégies mixtes sont également de tels équilibres. Cependant, il y a seulement un équilibre parfait en sous-jeux (un raffinement courant du concept d'équilibre de Nash).
Dans l'unique équilibre parfait en sous-jeux, chaque joueur choisit de prendre le pot à chaque opportunité. Ainsi, le premier joueur prend évidemment le pot dès le début. Dans les équilibres de Nash, cependant, les joueurs peuvent choisir la coopération dans les actions suivantes (même si elles ne seront jamais effectuées puisque le premier joueur aura pris le pot).
La prise du pot par le premier joueur est indiquée par l'unique équilibre parfait par sous-jeu et par chaque équilibre de Nash. Elle peut être établie par induction à rebours. Supposons deux joueurs qui atteignent le tour final du jeu. Le deuxième joueur ne pourra faire mieux qu'en prenant le pot. Comme le deuxième joueur va prendre le pot, le premier joueur fera mieux en prenant lui-même le pot à l'avant dernier tour. Mais sachant cela, le deuxième joueur prendra le pot au tour d'avant. Ce raisonnement continue récursivement jusqu'à conclure que le meilleur choix pour le premier joueur est de prendre le pot dès le premier tour.
Résultats expérimentaux
Plusieurs études ont démontré que les équilibres de Nash (et l'équilibre parfait en sous-jeux) est rarement observé. Au contraire, les sujets choisissent souvent la coopération partielle, et jouent ‘R’ pour plusieurs mouvements avant de choisir ‘D’. Il est aussi rare que les sujets coopèrent tout au long du jeu. Voyez par exemple McKelvey et Palfrey (1992) et Nagel et Tang (1998) : comme dans de nombreuses autres expériences, lorsque les enjeux augmentent, le jeu réel des joueurs s'approche de l'équilibre de Nash.
