{"id":6682,"date":"2014-06-02T00:01:15","date_gmt":"2014-06-01T22:01:15","guid":{"rendered":"http:\/\/sciencetonnante.wordpress.com\/?p=6682"},"modified":"2014-06-02T00:01:15","modified_gmt":"2014-06-01T22:01:15","slug":"deux-strategies-revolutionnaires-en-theorie-des-jeux-1","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2014\/06\/02\/deux-strategies-revolutionnaires-en-theorie-des-jeux-1\/","title":{"rendered":"Deux strat\u00e9gies r\u00e9volutionnaires en th\u00e9orie des jeux (1\/2)"},"content":{"rendered":"<p style=\"text-align:justify;\"><a href=\"https:\/\/scienceetonnante.com\/2014\/06\/poker-chips.jpg\"><img decoding=\"async\" class=\"alignleft size-medium wp-image-6689 lazyload\" data-src=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2014\/06\/poker-chips.jpg?w=300\" alt=\"poker chips\" width=\"300\" height=\"200\" src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" style=\"--smush-placeholder-width: 300px; --smush-placeholder-aspect-ratio: 300\/200;\" \/><\/a>La th\u00e9orie des jeux est un domaine des math\u00e9matiques qui \u00e9tudie &#8230; les jeux ! Enfin certains types de jeux. Cette discipline a \u00e9t\u00e9 invent\u00e9e \u00e0 l&rsquo;origine non pas pour s&rsquo;amuser, mais pour comprendre la mani\u00e8re dont des individus aux objectifs diff\u00e9rents pouvaient se mettre \u00e0 collaborer (ou pas).<\/p>\n<p style=\"text-align:justify;\">On pensait depuis longtemps que l&rsquo;on avait fait le tour des questions int\u00e9ressantes concernant les jeux les plus simples, et que plus rien ne restait \u00e0 d\u00e9couvrir. Eh bien \u00e7a n&rsquo;est pas le cas !<\/p>\n<p style=\"text-align:justify;\">Dans ce billet et le suivant, je vais vous parler de deux strat\u00e9gies r\u00e9volutionnaires pour \u00ab\u00a0gagner\u00a0\u00bb \u00e0 ce jeu qu&rsquo;on appelle <strong>le dilemme du prisonnier<\/strong>. La premi\u00e8re est assez anecdotique et nous vient d&rsquo;un jeu t\u00e9l\u00e9vis\u00e9. La deuxi\u00e8me est beaucoup plus s\u00e9rieuse et pourrait bien \u00eatre en train de bouleverser le domaine.<!--more--><\/p>\n<h3 style=\"text-align:justify;\">Golden Balls<\/h3>\n<p style=\"text-align:justify;\">Non, <em>Golden Balls<\/em> n&rsquo;est pas le nom du prochain <span style=\"text-decoration:line-through;\">James Bond<\/span> Austin Powers, mais celui d&rsquo;un jeu t\u00e9l\u00e9vis\u00e9 diffus\u00e9 en Grande Bretagne entre 2007 et 2009. Le jeu est compos\u00e9 de plusieurs phases, mais la plus int\u00e9ressante est la derni\u00e8re : il ne reste que <strong>deux joueurs qui doivent se partager un magot<\/strong>, qui vaut en g\u00e9n\u00e9ral quelques dizaines de milliers de \u00a3.<\/p>\n<p style=\"text-align:justify;\"><a href=\"https:\/\/scienceetonnante.com\/2014\/06\/golden-balls.png\"><img decoding=\"async\" class=\"alignright size-medium wp-image-6692 lazyload\" data-src=\"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2014\/06\/golden-balls.png?w=300\" alt=\"golden balls\" width=\"300\" height=\"188\" src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" style=\"--smush-placeholder-width: 300px; --smush-placeholder-aspect-ratio: 300\/188;\" \/><\/a>Pour effectuer le partage, chaque candidat dispose de deux boules : sur l&rsquo;une est inscrit \u00ab\u00a0SPLIT\u00a0\u00bb (partager) et sur l&rsquo;autre \u00ab\u00a0STEAL\u00a0\u00bb (voler). Chacun des candidats choisit secr\u00e8tement une de ses deux boules :<\/p>\n<ul style=\"text-align:justify;\">\n<li>Si les deux choisissent SPLIT, le magot est partag\u00e9 \u00e9quitablement entre eux deux;<\/li>\n<li>Si l&rsquo;un choisit SPLIT et l&rsquo;autre STEAL, celui qui a choisit STEAL (voler) prend tout le magot (et l&rsquo;autre se retrouve Gros-Jean comme devant)<\/li>\n<li>Si les deux choisissent STEAL, ils repartent tous les deux les mains vides<\/li>\n<\/ul>\n<p style=\"text-align:justify;\">Bien s\u00fbr en moyenne, il vaudrait mieux que les joueurs collaborent et choisissent SPLIT tous les deux. Mais il y a la tentation de trahir pour empocher tout le magot !<\/p>\n<p style=\"text-align:justify;\">Le plus dr\u00f4le dans l&rsquo;affaire, c&rsquo;est qu&rsquo;avant de faire leur choix, les joueurs disposent de quelques minutes pour discuter. \u00c9videmment, <strong>chacun essaye de convaincre l&rsquo;autre qu&rsquo;il va choisir SPLIT.<\/strong> Les candidats jurent leurs grands dieux, ou sur la t\u00eate de leur caniche, que jamais \u00f4 grand jamais il ne vont trahir et choisir STEAL. De temps en temps, \u00e7a fonctionne et les deux choisissent de partager, mais \u00e7a arrive r\u00e9guli\u00e8rement que l&rsquo;un entube l&rsquo;autre, comme sur l&rsquo;exemple ci-dessous :<\/p>\n<p style=\"text-align:justify;\">[youtube=http:\/\/www.youtube.com\/watch?v=p3Uos2fzIJ0&amp;start=160]<\/p>\n<h3 style=\"text-align:justify;\">Une nouvelle strat\u00e9gie<\/h3>\n<p style=\"text-align:justify;\">Tout cela fonctionnait selon le plan pr\u00e9vu (par le producteur TV) jusqu&rsquo;\u00e0 ce qu&rsquo;un petit malin trouve un moyen de hacker le jeu. Ce petit malin s&rsquo;appelle Nick, et il s&rsquo;est retrouv\u00e9 un jour dans la phase finale du jeu contre un autre joueur appel\u00e9 Ibrahim. Quand la phase de n\u00e9gociation (avant le choix des boules) a commenc\u00e9, Nick a d&#8217;embl\u00e9e annonc\u00e9 :<\/p>\n<p style=\"text-align:justify;\"><strong>Nick :<\/strong> <em>&#8211; Ibrahim, je veux que tu me fasses confiance, \u00e0 100%, je vais choisir la boule STEAL (voler)<\/em><\/p>\n<p style=\"text-align:justify;\"><strong>Ibrahim interloqu\u00e9 :<\/strong> <em>&#8211; Pardon ? Tu vas prendre la boule\u2026<\/em><\/p>\n<p style=\"text-align:justify;\"><strong>Nick :<\/strong> <em>&#8211; Je vais prendre la boule STEAL.<\/em><\/p>\n<p style=\"text-align:justify;\">Puis Nick explique sa strat\u00e9gie : <em>&#8211; Je vais prendre la boule STEAL, je veux que tu prennes la boule SPLIT, et je te promets que je partagerai l&rsquo;argent avec toi apr\u00e8s.<\/em><\/p>\n<p style=\"text-align:justify;\">Ibrahim est incr\u00e9dule. Le public rigole. Le pr\u00e9sentateur TV semble nerveux.<\/p>\n<p style=\"text-align:justify;\">Puis Nick pr\u00e9cise son id\u00e9e. Il soutient mordicus que quoi qu&rsquo;il arrive, il choisira de toute fa\u00e7on STEAL. Si Ibrahim choisit aussi STEAL ils repartiront tous les deux sans rien. Donc la seule chose raisonnable que puisse faire Ibrahim, c&rsquo;est de choisir SPLIT, de laisser Nick empocher tout le magot, et de lui faire confiance pour que celui-ci partage apr\u00e8s la fin du jeu.<\/p>\n<p style=\"text-align:justify;\">S&rsquo;ensuit une n\u00e9gociation interminable, et largement coup\u00e9e au montage, mais qui para\u00eet-il aurait dur\u00e9 45 minutes.<\/p>\n<p style=\"text-align:justify;\">Et voici ce qui arriva \u00e0 la fin \u2026 (Nick est \u00e0 droite, Ibrahim \u00e0 gauche)<\/p>\n<p style=\"text-align:justify;\">[youtube=http:\/\/www.youtube.com\/watch?v=S0qjK3TWZE8&amp;start=280]<\/p>\n<p style=\"text-align:justify;\">Sous la contrainte, Ibrahim a choisi de suivre le raisonnement de Nick, et a choisi SPLIT. Quant \u00e0 Nick, &#8230; il a choisi SPLIT \u00e9galement ! Bien jou\u00e9, non ?<\/p>\n<h3 style=\"text-align:justify;\">Les jeux \u00e0 somme non-nulle<\/h3>\n<p style=\"text-align:justify;\">La phase finale de <em>Golden Balls<\/em> est un cas de ce qu&rsquo;on appelle \u00ab\u00a0<strong>les jeux \u00e0 somme non-nulle<\/strong>\u00ab\u00a0. Un jeu normal (comme disons le poker) est un jeu \u00e0 somme nulle en ce sens que tout ce qui est gagn\u00e9 par X est perdu par Y et r\u00e9ciproquement. Il n&rsquo;y a donc pas d&rsquo;int\u00e9r\u00eat \u00e0 collaborer. Dans la phase finale de <em>Golden Balls<\/em>, la somme d&rsquo;argent totale distribu\u00e9e d\u00e9pend des choix respectifs des joueurs, <strong>il y a donc int\u00e9r\u00eat \u00e0 s&rsquo;entendre pour collaborer<\/strong>.<\/p>\n<p style=\"text-align:justify;\">Les jeux de ce genre ont \u00e9t\u00e9 tr\u00e8s \u00e9tudi\u00e9s par les math\u00e9maticiens, les \u00e9conomistes et m\u00eame les biologistes, car ils permettent de mieux comprendre dans quelles circonstances les individus peuvent se mettre \u00e0 collaborer, ou au contraire \u00e0 avoir un comportement \u00e9go\u00efste.<\/p>\n<p style=\"text-align:justify;\">Le jeu le plus classique s&rsquo;appelle <strong>le dilemme du prisonnier <\/strong>(voir <a title=\"Le dilemme du prisonnier\" href=\"https:\/\/scienceetonnante.com\/blog\/2010\/10\/13\/le-dilemme-du-prisonnier\/\">mon billet sur le sujet<\/a> pour l&rsquo;explication) et ressemble tr\u00e8s fortement \u00e0 <em>Golden Balls<\/em>. Mais dans les d\u00e9tails, il y a une petite diff\u00e9rence dans les valeurs des gains. Ainsi si <em>Golden Balls<\/em> mimait v\u00e9ritablement le dilemme du prisonnier, on devrait avoir quelque chose comme<\/p>\n<ul style=\"text-align:justify;\">\n<li>Si les 2 joueurs choisissent SPLIT, ils prennent chacun 50% du magot;<\/li>\n<li>Si l&rsquo;un choisit SPLIT et l&rsquo;autre STEAL, ce dernier repart avec 80% du magot (et l&rsquo;autre rien du tout);<\/li>\n<li>Si les deux choisissent STEAL, ils repartent chacun avec 10% du magot.<\/li>\n<\/ul>\n<p style=\"text-align:justify;\">Cette r\u00e9partition des gains ob\u00e9it \u00e0 deux conditions qu&rsquo;on ne retrouve pas dans <em>Golden Balls<\/em> : d&rsquo;une part <strong>la collaboration est en moyenne strictement avantageuse<\/strong> (100% du magot est distribu\u00e9 contre 80% en cas de trahison par l&rsquo;un des deux); d&rsquo;autre part on gagne plus en faisant deux STEAL\u00a0(10%) qu&rsquo;en se faisant entuber (0%).<\/p>\n<p style=\"text-align:justify;\">Je vous laisse y r\u00e9fl\u00e9chir, mais vous voyez que <strong>ces deux conditions invalident la strat\u00e9gie de Nick<\/strong> ! Son argumentaire ne tient plus car d&rsquo;une part le \u00ab\u00a0je prends tout et on partage apr\u00e8s\u00a0\u00bb est moins avantageux qu&rsquo;une collaboration directe; d&rsquo;autre part si Ibrahim est s\u00fbr que Nick va voler, il a int\u00e9r\u00eat \u00e0 voler aussi pour au moins repartir avec 10% du magot. <strong>La strat\u00e9gie de Nick fonctionne donc parce que <em>Golden Balls<\/em> n&rsquo;est pas un vrai dilemme du prisonnier<\/strong>, mais seulement une forme dite faible. Cette strat\u00e9gie ne fonctionnerait pas avec la forme normale du jeu.<\/p>\n<h3 style=\"text-align:justify;\">Le dilemme du prisonnier r\u00e9p\u00e9t\u00e9<\/h3>\n<p style=\"text-align:justify;\">Dans <em>Golden Balls<\/em>, on ne joue \u00e9videmment qu&rsquo;une seule fois. L\u00e0 o\u00f9 les jeux comme le dilemme du prisonnier deviennent v\u00e9ritablement int\u00e9ressants, c&rsquo;est quand on joue plusieurs tours d&rsquo;affil\u00e9, voire un grand nombre de tours, ce qu&rsquo;on appelle <strong>le dilemme du prisonnier r\u00e9p\u00e9t\u00e9<\/strong> (ou it\u00e9r\u00e9). C&rsquo;est en effet ainsi qu&rsquo;on peut voir dans quelle mesure les gens se font confiance, se trahissent, se punissent sur le long terme, et mettent en place des strat\u00e9gies de coop\u00e9ration.<\/p>\n<p style=\"text-align:justify;\">C&rsquo;est dans ce contexte que la th\u00e9orie des jeux a \u00e9t\u00e9 largement \u00e9tudi\u00e9e par les biologistes, et notamment les sp\u00e9cialistes de l&rsquo;\u00e9volution qui se demandaient <strong>comment des individus d&rsquo;une m\u00eame esp\u00e8ce pouvaient se mettre \u00e0 collaborer<\/strong>, si trahir l&rsquo;autre \u00e9tait toujours plus avantageux \u00e0 court terme.<\/p>\n<p style=\"text-align:justify;\">C&rsquo;est ainsi que dans les ann\u00e9es 80, Robert Axelrod a organis\u00e9 un grand <strong>tournoi informatique pour faire s&rsquo;affronter des strat\u00e9gies<\/strong> du dilemme du prisonnier r\u00e9p\u00e9t\u00e9 (voir <a title=\"Robert Axelrod et l\u2019\u00e9volution de la coop\u00e9ration\" href=\"https:\/\/scienceetonnante.com\/blog\/2011\/10\/31\/robert-axelrod-et-levolution-de-la-cooperation\/\">mon billet d\u00e9taill\u00e9 sur le sujet<\/a>) A la surprise g\u00e9n\u00e9rale, la strat\u00e9gie gagnante s&rsquo;est r\u00e9v\u00e9l\u00e9e extr\u00eamement simple. Elle s&rsquo;appelle \u00ab\u00a0Donnant-Donnant\u00a0\u00bb, et consiste simplement \u00e0 <strong>jouer la m\u00eame chose que ce que votre adversaire a jou\u00e9 au tour pr\u00e9c\u00e9dent<\/strong> : s&rsquo;il vous a trahi au tour pr\u00e9c\u00e9dent, vous le punissez en trahissant; s&rsquo;il a collabor\u00e9 au tour pr\u00e9c\u00e9dent, vous collaborez.<\/p>\n<p style=\"text-align:justify;\">En moyenne, cette strat\u00e9gie a battu toutes les autres. C&rsquo;est int\u00e9ressant car elle montre que la collaboration peut \u00eatre avantageuse par rapport \u00e0 des comportements strictement \u00e9go\u00efstes. Et elle est d&rsquo;autant plus s\u00e9duisante qu&rsquo;elle est juste et bienveillante : on n&rsquo;essaye pas d&rsquo;entuber l&rsquo;autre s&rsquo;il joue le jeu. Notez aussi que c&rsquo;est une strat\u00e9gie bas\u00e9e sur le pardon et l&rsquo;absence de rancune : si l&rsquo;autre m&rsquo;a trahi 10000 fois mais qu&rsquo;il se met \u00e0 collaborer, je collabore !<\/p>\n<p style=\"text-align:justify;\">Bref cela fait plus de 30 ans que la strat\u00e9gie \u00ab\u00a0Donnant-Donnant\u00a0\u00bb semble l&rsquo;ind\u00e9boulonnable gagnante pour le jeu du dilemme du prisonnier. Mais tout cela est tomb\u00e9 \u00e0 l&rsquo;eau il y a quelques mois, avec la d\u00e9couverte d&rsquo;<strong>une toute nouvelle strat\u00e9gie qui montre que finalement, mieux vaut \u00eatre machiav\u00e9lique et manipulateur que juste et bienveillant\u2026<\/strong>Je vous en parlerai la semaine prochaine !<\/p>\n<h4>Billets reli\u00e9s, ici ou ailleurs<\/h4>\n<ul>\n<li><a title=\"Le dilemme du prisonnier\" href=\"https:\/\/scienceetonnante.com\/blog\/2010\/10\/13\/le-dilemme-du-prisonnier\/\">Le dilemme du prisonnier :<\/a> qu&rsquo;est-ce que c&rsquo;est et pourquoi on l&rsquo;appelle comme \u00e7a<\/li>\n<li><a title=\"Robert Axelrod et l\u2019\u00e9volution de la coop\u00e9ration\" href=\"https:\/\/scienceetonnante.com\/blog\/2011\/10\/31\/robert-axelrod-et-levolution-de-la-cooperation\/\">Le tournoi d&rsquo;Axelrod<\/a> sur l&rsquo;\u00e9volution de la coop\u00e9ration<\/li>\n<li>Ce billet est tr\u00e8s largement inspir\u00e9 de l&rsquo;\u00e9mission \u00ab\u00a0<a href=\"http:\/\/www.radiolab.org\/story\/whats-left-when-youre-right\/\" target=\"_blank\" rel=\"noopener\">What&rsquo;s left when you&rsquo;re right ?<\/a>\u00a0\u00bb de Radiolab<\/li>\n<\/ul>\n<h4>Cr\u00e9dits<\/h4>\n<ul>\n<li><a href=\"http:\/\/i-screame.deviantart.com\/art\/poker-chips-162258833\" target=\"_blank\" rel=\"noopener\">Jetons de poker, i-screame<\/a><\/li>\n<li>Split or Steal ? Extrait de la premi\u00e8re vid\u00e9o<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>La th\u00e9orie des jeux est un domaine des math\u00e9matiques qui \u00e9tudie &#8230; les jeux ! Enfin certains types de jeux. Cette discipline a \u00e9t\u00e9 invent\u00e9e \u00e0 l&rsquo;origine non pas pour s&rsquo;amuser, mais pour comprendre la mani\u00e8re dont des individus aux objectifs diff\u00e9rents pouvaient se mettre \u00e0 collaborer (ou pas). On pensait depuis longtemps que l&rsquo;on<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[18],"class_list":{"0":"post-6682","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-mathematiques","7":"tag-theorie-des-jeux"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/6682","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/comments?post=6682"}],"version-history":[{"count":0,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/6682\/revisions"}],"wp:attachment":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media?parent=6682"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/categories?post=6682"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/tags?post=6682"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}