title: Jeu du pirate
text: # Jeu du pirate
  
  Le jeu du pirate est un jeu mathématique simple. Il illustre comment, si le comportement des participants humains est conforme au modèle homo economicus, l'aboutissement d'un jeu peut être surprenant. C'est une version multijoueur du jeu de l'ultimatum.
  
  ## Jeu
  
  Il y a cinq pirates rationnels, A, B, C, D et E. Ils trouvent cent pièces d'or. Ils doivent décider comment les répartir.
  
  Les pirates ont une hiérarchie stricte selon l'ancienneté : A est le supérieur de B, qui est le supérieur de C, qui est le supérieur de D, qui est le supérieur de E.
  
  Les règles de répartitions dans le monde des pirates sont les suivantes : le plus ancien pirate propose une répartition. Les pirates, y compris celui qui a fait la proposition, votent ensuite pour savoir s'ils acceptent cette répartition. Dans le cas d'une égalité, celui qui a fait la proposition tranche. Si la répartition est acceptée, les pièces sont distribuées, et le jeu se termine. Sinon, celui qui a fait la proposition est jeté par-dessus bord et meurt, et le plus ancien pirate après lui fait une nouvelle proposition, et le système commence une nouvelle fois.
  
  Les pirates basent leur décision sur trois facteurs. En premier, les pirates veulent survivre. En second, et tant qu'ils survivent, chaque pirate veut maximiser le nombre de pièces d'or qu'il reçoit. En troisième, chaque pirate préfère jeter un autre pirate par-dessus bord, s'il y a égalité des gains entre les autres possibilités de jeu. Les pirates ne se font pas confiance entre eux, et ne feront ni ne tiendront jamais de promesses entre pirates autre que le plan de répartition des pièces qui donne à chaque pirate un nombre entier de pièces d'or.
  
  ## Résultat
  
  Intuitivement, on pourrait s'attendre à ce que le pirate A n'alloue peu, voire pas du tout, de pièces d'or à A par peur que son plan de répartition soit rejeté par les autres pirates pour qu'il y ait moins de pirates avec qui partager. Cependant, c'est plutôt éloigné du résultat théorique.
  
  Cela apparait si on raisonne de la fin vers le début : si tout le monde à part D et E a été jeté par-dessus bord, D propose 100 pour D et 0 pour E. D a le dernier mot, donc c'est la répartition qui est acceptée.
  
  S'il en reste trois (C, D et E) C sait que D va offrir 0 à E au prochain tour; c'est pourquoi, C doit offrir 1 pièce à E à ce tour pour gagner le vote de E, et ainsi faire gagner sa répartition. Ainsi, quand il n'en reste que 3, l'allocation est C:99, D:0, E:1.
  
  S'il reste B, C, D et E, B prend en considération le fait qu'il risque d'être jeté par-dessus bord en proposant son plan de répartition des pièces. Pour éviter d'être jeté par-dessus bord, B peut simplement offrir 1 à D. Comme B a le dernier mot, le vote de D est suffisant. Donc B propose B:99, C:0, D:1, E:0. On pourrait envisager de proposer B:99, C:0, D:0, E:1, étant donné que E sait que cela ne sera pas possible pour lui d'avoir plus de pièces, s'il en a seulement, si E vote pour jeter B par-dessus bord. Mais, comme chaque pirate est avide de jeter les autres par-dessus bord, E va préférer tuer B, pour avoir le même nombre de pièces que C.
  
  En assumant que A sait toutes ces choses, A peut compter sur le support de C et E pour la répartition suivante, qui est la solution définitive :
  
  * A: 98 pièces
  * B: 0 pièces
  * C: 1 pièce
  * D: 0 pièces
  * E: 1 pièce
  
  Aussi, A:98, B:0, C:0, D:1, E:1 ou les autres variantes ne sont pas correctes, puisque D va préférer jeter A par-dessus bord pour avoir le même nombre de pièces d'or que B.
  
  ## Extension
  
  La solution suit le même schéma général pour des nombres différents de pirates et/ou de pièces. Cependant, le jeu change de nature si on pousse jusqu'à avoir deux fois plus de pirates que de pièces d'or. Ian Stewart a écrit à propos de l'ajout d'un nombre arbitraire de pirates dans l'édition de mai 1999 de Scientific American et décrit le schéma plutôt complexe qui apparait dans la solution.
  
  Supposons qu'il n'y a que cent pièces d'or, alors :
  
  * Le pirate $n^o$ 201 en tant que capitaine ne peut rester en vie que s'il offre une pièce à chacun des pirates ayant un numéro inférieur et impair, n'en gardant aucune pour lui-même.
  * Le pirate $n^o$ 202 en tant que capitaine ne peut rester en vie qu'en ne prenant aucune pièce d'or, et en offrant une pièce d'or à chacun des 100 pirates qui n'en recevrait pas du pirate $n^o$ 201. C'est pourquoi, il y a 101 destinataires possibles de ces parts d'une pièce d'or, et ce sont les 100 pirates ayant un numéro pair jusqu'à 200 et le pirate $n^o$ 201.
  * Le pirate $N^o$ 203 en tant que capitaine n'aura pas assez de pièces d'or pour obtenir la majorité lors du vote et sera donc jeté par-dessus bord.
  * Le pirate $n^o$ 204 en tant que capitaine aura le vote du pirate $n^o$ 203 sans avoir à lui donner de pièces d'or: $n^o$ 203 ne peut survivre que si $n^o$ 204 survit lui aussi. Donc $n^o$ 204 peut survivre grâce au vote de 102 pirates en distribuant à 100 pirates une pièce d'or chacun. Cela a plus de chances de marcher en distribuant aux pirates ayant un numéro pair, et en incluant optionnellement $n^o$ 202, qui n'obtiendrait rien du $n^o$ 202. Cependant, c'est aussi possible de distribuer aux autres à la place étant donné qu'ils n'ont que 100/101 chances de se voir offrir une pièce d'or par le pirate $n^o$ 202.
  * Avec 205 pirates, tous les pirates à part $n^o$ 205 préfèrent tuer $n^o$ 205 à moins qu'on leur propose de l'or, donc $n^o$ 205 en tant que capitaine est condamné.
  * De la même manière, avec 206 ou 207 pirates, seulement les votes de $n^o$ 205 jusqu'à $n^o$ 206/7 sont assurés sans pièces d'or ce qui est insuffisant, donc $n^o$ 206 et $n^o$ 207 sont eux aussi condamnés.
  * Pour 208 pirates, les votes de survies de $n^o$ 205, $n^o$ 206 et $n^o$ 207 sans pièce d'or sont suffisants pour permettre $n^o$ 208 d'atteindre 104 votes et de survivre.
  
  En général, si G est le nombre de pièces d'or et N (> 2G) le nombre de pirates, alors
  
  * Tous les pirates dont le nombre est inférieur ou égal à 2G + M survivront, avec M la plus grande puissance de 2 qui n'excède pas N - 2G.
  * Tous les pirates dont le nombre est supérieur à 2G + M vont mourir.
  * Tous les pirates dont le nombre est supérieur à 2G + M/2 ne recevront pas d'or.
  * Il n'y a pas une unique solution quant à qui va recevoir une pièce d'or et qui ne va pas en recevoir si le nombre de pirates est 2G+2 ou plus. Une solution simple est de donner une pièce d'or aux numéros impair ou pair jusqu'à 2G suivant que M est une puissance paire ou impaire de 2.
  
  Une autre façon de voir ça est de réaliser que tous les pirates n°M vont recevoir le vote de tous les pirates M/2 jusqu'à M pour leurs propres survies étant donné que leur survie n'est possible qu'avec la survie du n°M. Étant donné que le pirate le plus haut peut trancher en cas d'égalité, le capitaine n'a besoin des votes que de la moitié des pirates au-dessus de 2G, ce qui ne se produit qu'à chaque fois que (2G + une puissance de 2) est atteinte.
  
  