Jeu Blotto
Un jeu Blotto, un jeu Colonel Blotto ou 'un jeu diviser un dollar est un type de jeu à somme nulle pour deux personnes dans lequel les joueurs sont chargés de distribuer simultanément des ressources limitées sur plusieurs objets (ou champs de bataille). Dans la version classique du jeu, le joueur qui consacre le plus de ressources à un champ de bataille gagne ce champ de bataille et le gain (ou gain) est alors égal au nombre total de champs de bataille gagnés.
Le jeu Colonel Blotto a été proposé et résolu par Émile Borel[1] en 1921, à titre d'exemple de jeu dans lequel « la psychologie des joueurs compte ». Il a été étudié après la Seconde Guerre mondiale par des spécialistes de la recherche opérationnelle et est devenu un classique de la théorie des jeux[2] . Il a été démontré que la recherche d’un équilibre Min-Max, c’est-à-dire que les stratégies optimales de ce jeu est réalisable par calcul[3],[4].
Le jeu est nommé d'après le colonel fictif du papier de Gross et Wagner datant de 1950[5] . Le colonel avait pour tâche de trouver la répartition optimale de ses soldats sur N champs de bataille en sachant que :
- Sur chaque champ de bataille, le parti qui a attribué le plus grand nombre de soldats à la bataille va gagner.
- Aucune des parties ne sait combien de soldats la partie adverse affectera de soldats à chaque champ de bataille.
- Les deux parties cherchent à maximiser le nombre de champs de bataille qu’elles s’attendent à gagner.
Exemple
modifierÀ titre d’exemple de jeu Blotto, considérons le jeu dans lequel deux joueurs écrivent chacun trois nombres entiers positifs dans un ordre non décroissant et s’additionnant jusqu’à un nombre prédéfini S. Par la suite, les deux joueurs s’échangent leurs écrits afin de comparer les chiffres correspondants. Le joueur qui a deux numéros plus élevés que ceux de l'adversaire correspondant remporte la partie.
Pour S = 6, seuls trois choix de nombres sont possibles: (2, 2, 2), (1, 2, 3) et (1, 1, 4). Il est facile de voir que:
- Tout triplé contre lui-même est un match nul
- (1, 1, 4) contre (1, 2, 3) est un match nul
- (1, 2, 3) contre (2, 2, 2) est un match nul
- (2, 2, 2) bat (1, 1, 4)
Il s’ensuit que la stratégie optimale est (2, 2, 2), dans la mesure où elle ne fait pas pire que de casser même contre toute autre stratégie tout en battant une autre stratégie. Il existe cependant plusieurs équilibres de Nash. Si les deux joueurs choisissent la stratégie (2, 2, 2) ou (1, 2, 3), aucun d’entre eux ne peut battre l’autre en changeant de stratégie. Chaque paire de stratégies de ce type est donc un équilibre de Nash .
Pour les grands joueurs, le jeu devient de plus en plus difficile à analyser. Pour S = 12, on peut montrer que (2, 4, 6) représente la stratégie optimale, alors que pour S> 12, les stratégies déterministes ne sont pas optimales. Pour S = 13, choisir la stratégie (3, 5, 5), (3, 3, 7) et (1, 5, 7) avec une probabilité de 1/3 est la stratégie probabiliste optimale.
Le jeu de Borel est similaire à l'exemple ci-dessus pour les très gros S, mais les joueurs ne se limitent pas à des entiers ronds. Ils ont ainsi un nombre infini de stratégies pures disponibles, voire un continuum.
Ce concept est également mis en œuvre dans une histoire de Sun Bin lorsque vous regardez une course de chars avec trois courses différentes concurrentes. Dans les courses, chaque groupe avait la possibilité d’avoir une équipe de chars dans chaque course et chacun choisissait d’utiliser une stratégie de 1, 2, 3 (3 étant le char le plus rapide et 1 le plus lent) pour déployer leurs chars entre les trois. courses créant des victoires serrées dans chaque course et peu de résultats sûrs sur les gagnants. Lorsqu'on lui a demandé comment gagner, Sun Bin a conseillé au propriétaire du char de changer son déploiement en celui de 2, 3, 1. Bien qu'il soit sûr de perdre la course contre les chars les plus rapides (les 3 chars); il gagnerait chacune des autres races, avec ses 3 chars battant facilement 2 chars et ses 2 chars battant les 1 chars.
Application
modifierCe jeu est couramment utilisé comme métaphore de la compétition électorale, deux partis politiques consacrant de l'argent ou des ressources pour attirer le soutien d'un nombre déterminé d'électeurs[6],[7]. Chaque électeur est un "champ de bataille" qui peut être gagné par l'un ou l'autre parti. Le même jeu trouve également une application dans la théorie des enchères où les enchérisseurs doivent faire des offres simultanées[8].
Jean-François Laslier[9] Brian Roberson[10], Dmitriy Kvasov, a résolu plusieurs variantes du jeu original[11].
Notes et références
modifier- The Theory of Play and Integral Equations with Skew Symmetric Kernels (1953 translation from the French paper "La théorie du jeu et les équations intégrales à noyau symétrique gauche")
- Guillermo Owen, Game Theory, Academic Press (1968)
- mewright, « UMD-led Team First to Solve Well-known Game Theory Scenario », College of Computer, Mathematical, and Natural Sciences (consulté le )
- (en) Auteur inconnu, « [1] », .erreur modèle {{Lien arXiv}} : renseignez un paramètre «
|eprint»erreur modèle {{Lien arXiv}} : renseignez un paramètre «|titre» - A Continuous Colonel Blotto Game
- R. Myerson "Incentives to cultivate favored minorities under alternative electoral systems" American Political Science Review 87(4):856—869, 1993
- Laslier et Picard, « Distributive politics and electoral competition », Journal of Economic Theory, vol. 103, , p. 106–130 (DOI 10.1006/jeth.2000.2775)
- Szentes et Rosenthal, « Three-object, Two-Bidder Simultaneous Auctions: Chopsticks and Tetrahedra », Games and Economic Behavior, vol. 44, , p. 114–133 (DOI 10.1016/s0899-8256(02)00530-4)
- J.-F. Laslier, "Party objectives in the `divide a dollar’ electoral competition" in: Social Choice and Strategic Decisions, Essays in Honor of Jeff Banks, edited by D. Austen–Smith and J. Duggan, Springer, p. 113–130 (2005)
- B. Roberson, The Colonel Blotto game
- Kvasov, « Contests with Limited Resources », Journal of Economic Theory, vol. 136, , p. 738–748 (DOI 10.1016/j.jet.2006.06.007)