Jeu du mille-pattes
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.
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.
Explications
Depuis que l'expérience a produit des résultats qui contredisent la théorie traditionnelle de l'analyse des équilibres, beaucoup d'explications de ce comportement ont été données. Rosenthal (1981) a suggéré que si un joueur a des raisons de penser que l'autre allait dévier de l'équilibre de Nash, il pouvait être avantageux de ne pas prendre le pot immédiatement.
L'une des raisons pour lesquelles un autre joueur pourrait dévier de l'équilibre de Nash est l'altruisme. Le principe est que si vous jouez contre un altruiste, comme ce joueur va toujours coopérer, vous avez intérêt à attendre la dernière occasion de prendre le pot pour maximiser vos gains. Si le nombre d'altruistes est suffisamment important, le prix de départ est au pire le prix à payer pour savoir si votre adversaire est altruiste. Nagel et Tang ont soumis cette explication.
Une autre explication possible est l'erreur. S'il y a une possibilité significative d'erreur, par exemple parce que l'autre joueur n'a pas complètement raisonné par induction à rebours, il peut être avantageux, et rationnel, de coopérer pendant les premiers tours.
Cependant, Parco, Rapoport et Stein (2002) ont mis en évidence que le niveau d'incitations financières peut avoir un effet important sur le résultat dans un jeu à trois : la propension à apprendre au cours d'un exercice répété afin de jouer selon l'équilibre de Nash augmente avec les incitations à la déviation.
Palacios-Huerta et Volij (2009) montrent que les experts des échecs jouent différemment des étudiants. Quand le classement Elo augmente, la probabilité de continuer le jeu décline ; tous les grands maîtres de l'expérience ont arrêté à la première étape. Ils en conclurent que les joueurs d'échecs étaient familiers de l'induction à rebours, et qu'ils avaient besoin de moins de temps pour trouver l'équilibre de Nash.
Sources
- (en) R. Aumann, « Backward Induction and Common Knowledge of Rationality », Games and Economic Behavior, vol. 8, no 1, , p. 6–19 (DOI 10.1016/S0899-8256(05)80015-6).
- (en) R. Aumann, « A Reply to Binmore », Games and Economic Behavior, vol. 17, no 1, , p. 138–146 (DOI 10.1006/game.1996.0099).
- (en) K. Binmore, Natural Justice, New York, Oxford University Press, , 207 p. (ISBN 0-19-517811-4, lire en ligne).
- (en) K. Binmore, « A Note on Backward Induction », Games and Economic Behavior, vol. 17, no 1, , p. 135–137 (DOI 10.1006/game.1996.0098).
- (en) R. McKelvey et T. Palfrey, « An experimental study of the centipede game », Econometrica, vol. 60, no 4, , p. 803–836 (DOI 10.2307/2951567).
- (en) R. Nagel et F. F. Tang, « An Experimental Study on the Centipede Game in Normal Form: An Investigation on Learning », Journal of Mathematical Psychology, vol. 42, nos 2–3, , p. 356–384 (DOI 10.1006/jmps.1998.1225).
- (en) I. Palacios-Huerta et O. Volij, « Field Centipedes », American Economic Review, vol. 99, no 4, , p. 1619–1635 (DOI 10.1257/aer.99.4.1619).
- (en) J. E. Parco, A. Rapoport et W. E. Stein, « Effects of financial incentives on the breakdown of mutual trust », Psychological Science, vol. 13, no 3, , p. 292–297 (DOI 10.1111/1467-9280.00454).
- (en) A. Rapoport, W. E. Stein, J. E. Parco et T. E. Nicholas, « Equilibrium play and adaptive learning in a three-person centipede game », Games and Economic Behavior, vol. 43, no 2, , p. 239–265 (DOI 10.1016/S0899-8256(03)00009-5).
- (en) R. Rosenthal, « Games of Perfect Information, Predatory Pricing, and the Chain Store », Journal of Economic Theory, vol. 25, no 1, , p. 92–100 (DOI 10.1016/0022-0531(81)90018-1).
