{
"cells": [
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The notexbook extension is already loaded. To reload it, use:\n",
" %reload_ext notexbook\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
""
],
"text/plain": [
""
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%load_ext notexbook\n",
"%texify"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"---\n",
"# Interaction stratégique\n",
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## I. Jouer en simultané\n",
"\n",
"On considère pour commencer les situations où les agents vont jouer leurs actions de manière simultanée. \n",
"Pour la simplicité, les exemples impliquent à chaque fois deux agents, mais les notions restent valides pour plus de deux agents. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 1. Un problème classique: le dilemme du prisonnier"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Deux joueurs ont été appréhendés après un vol. Il est clair que au moins un des deux a commis ce délit. \n",
"Ils sont interrogés en parallèle, et disposent des mêmes actions: garder le **silence**, ou **dénoncer** l'autre. \n",
"Ils jouent donc en simultané, sans se concerter. \n",
"Selon le choix de stratégies des joueurs, les gains sont les suivants: \n",
"\n",
"|R \\ B | **silence** | **dénoncer** |\n",
"|------|------|------|\n",
"| **silence** | (20,20) | (0,30) |\n",
"| **dénoncer** | (30,0) | (10,10) | \n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Analysons du point de vue du joueur R les **meilleures réponses** selon les choix de l'agent B: \n",
"* si B garde le silence, il vaut mieux que R dénonce l'autre (30>20)\n",
"* si B dénonce, il vaut mieux que R dénonce aussi (10>0)\n",
"\n",
"Les meilleures réponses pour R sont donc: \n",
"\n",
"| meilleure réponse | action de B |\n",
"|------|------|\n",
"|dénonce | dénonce|\n",
"|dénonce | silence|\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Stratégie dominante\n",
"\n",
"Lorsque, pour un joueur $X$, la table de meilleures réponses indique toujours la même stratégie, on parle de **stratégie dominante** pour le joueur $X$. \n",
"\n",
"> La stratégie **dénoncer** est donc dominante pour R et pour B\n",
"\n",
"#### Stratégies dominées\n",
"\n",
"Il est rare qu'il existe des stratégies dominantes. Mais il est plus courant de pouvoir identifier des **stratégies dominées** par une autre stratégie. Il est en fait possible de distinguer plusieurs niveaux de dominance: \n",
"* une stratégie $s$ **domine fortement** une autre stratégie $s'$ si les gains obtenus pour $s$ sont toujours (ie. quelque soit la stratégie de l'autre joueur) strictement supérieurs à ceux de la stratégie $s'$. \n",
"* une stratégie $s$ **domine faiblement** une autre stratégie $s'$ si les gains obtenus pour $s$ sont toujours (ie. quelque soit la stratégie de l'autre joueur) supérieurs ou égaux à ceux de la stratégie $s'$, et strictement supérieurs pour au moins une stratégie de l'autre agent. \n",
"\n",
"Considérons cet autre exemple: \n",
"\n",
"|R \\ B | **a** | **b** | **c** |\n",
"|------|------|------|------|\n",
"| **d** | (20,20) | (0,30) | (20,10) |\n",
"| **e** | (30,10) | (10,0) | (0,10) |\n",
"\n",
"\n",
"On constate qu'ici, pour l'agent R, aucune stratégie ne domine l'autre. Pour l'agent B, la stratégie $c$ est dominée par la stratégie $a$, mais aucune stratégie n'est dominante. \n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Equilibre de Nash\n",
"\n",
"Lorsque les stratégies sont des **meilleures réponses mutuelles**, on se trouve dans un **équilibre de Nash**: aucun agent n'aurait intérêt, unilatéralement, a changer de stratégie. \n",
"\n",
"> Ici la stratégie jointe **dénoncer/dénoncer** est un EN\n",
"\n",
"Ici, on observe que cet équilibre de Nash est dominé par le résultat (20,20) qui serait atteint si les deux joueurs gardaient le silence. \n",
"\n",
"Ce type de dilemme a été largement étudié, et même utilisé dans des jeux (par exemple dans l'émission de TV britannique Golden Balls, qui repose sur une situation proche). \n",
"\n",
"On a pour coutume de parler d'action de **coopération**, ou de **trahison** dans ce cadre. Notons que l'on peut varier les valeurs dans de gains la matrice sans changer la nature du dilemme. Il y a en effet une valeur obtenue en cas de coopération mutuelle ($cc$), une valeur de piège obtenue en cas de trahison mutuelle ($tt$), et dans le cas ($tc$), une valeur T de traitrise et une de dupe ($tc$). \n",
"Pour rester dans une situation de dilemme, il faut que $tc>cc>tt>ct$. \n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(20, 20)\n"
]
}
],
"source": [
"def jouerDP(s1,s2):\n",
" gains = {'cc':(20,20), 'ct':(0,30), 'tt':(10,10), 'tc': (30,0)}\n",
" return gains[str(s1)+str(s2)]\n",
"\n",
"print (jouerDP('c','c'))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 2. Dilemme du prisonnier itéré"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Imaginons à présent que deux joueurs (toujours les mêmes) jouent plusieurs fois d'affilée un dilemme du prisonnier. \n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Définir une stratégie pour le dilemme du prisonnier itéré, c'est donc définir quel coup jouer, en fonction de :\n",
"* les coups que l'on a joués précédemment\n",
"* les coups que l'autre a joués précédemment\n",
"\n",
"Notez que cela inclue également quel premier coup jouer. Les stratégies peuvent également faire intervenir des aspects stochastiques, etc."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Des stratégies classiques sont les suivantes: \n",
"* toujours coopérer/trahir\n",
"* jouer au hasard\n",
"* alterner trahison et coopération\n",
"* donnant-donnant (tit-for-tat): commencer par coopérer, puis jouer comme le dernier coup joué par l'adversaire\n",
"* rancunière: on coopère, et dès que l'autre trahit, on trahit pour toujours"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"def prochainCoup(mesCoups,adversCoups,nom):\n",
" \"\"\"selon la liste de mes coups et des coups de l'autre\n",
" je choisis un coup \"\"\"\n",
" \n",
" #\n",
" # strategies de base\n",
" #\n",
" if nom=='trahison':\n",
" return 't'\n",
" \n",
" if nom=='coopere':\n",
" return 'c'\n",
" \n",
" if nom=='titfortat':\n",
" if adversCoups == []:\n",
" return 'c'\n",
" else:\n",
" return adversCoups[-1]\n",
" \n",
" if nom=='random':\n",
" return random.choice(['t','c'])\n",
" if nom=='alterne':\n",
" if mesCoups == []:\n",
" return 'c'\n",
" elif mesCoups[-1]=='t':\n",
" return 'c'\n",
" else:\n",
" return 't'\n",
" # \n",
" # quelques strategies proposees par les etudiants en cours\n",
" #\n",
" \n",
" if nom=='titfortatBis':\n",
" if adversCoups == []:\n",
" return 't'\n",
" else:\n",
" return adversCoups[-1]\n",
" if nom=='titfortatTer':\n",
" if adversCoups == []:\n",
" return 'c'\n",
" else:\n",
" if len(mesCoups) == 1:\n",
" return adversCoups[-1]\n",
" elif adversCoups[-1]=='t' or (mesCoups[-1]=='t' and mesCoups[-2] == 'c'):\n",
" return 't'\n",
" else:\n",
" return 'c'\n",
" \n",
" if nom=='equipeABis':\n",
" nbC = 0\n",
" nbT = 0\n",
" for i in adversCoups:\n",
" if i =='c':\n",
" nbC += 1\n",
" else:\n",
" nbT += 1\n",
" if len(adversCoups)<4:\n",
" return 'c'\n",
" else:\n",
" if nbT>nbC:\n",
" return 't'\n",
" else:\n",
" return 'c'\n",
" \n",
" \n",
" if nom=='equipeA': \n",
" if (len(adversCoups) < 5):\n",
" return 'c'\n",
" return 't'\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"c\n"
]
}
],
"source": [
"print (prochainCoup([],[],'random'))"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [],
"source": [
"nbIterations=10\n",
"toPlot = {'R':[0], 'B':[0]}\n",
"coupsJoues = {'R': [], 'B': []}\n",
"gainsCumules = {'R': 0, 'B': 0}\n",
"strategie = {'R': 'titfortat', 'B': 'trahison'}\n",
"\n",
"for i in range(nbIterations):\n",
" coupR = prochainCoup(coupsJoues['R'],coupsJoues['B'],strategie['R'])\n",
" coupB = prochainCoup(coupsJoues['B'],coupsJoues['R'],strategie['B'])\n",
" gainR,gainB = jouerDP(coupR,coupB)\n",
" gainsCumules['R']+=gainR\n",
" gainsCumules['B']+=gainB\n",
" coupsJoues['R']+=coupR\n",
" coupsJoues['B']+=coupB\n",
" #print (\"R joue \",coupR, \", B joue\", coupB, \"--> gains:\", gainR, gainB)\n",
" toPlot['R'].append(gainsCumules['R'])\n",
" toPlot['B'].append(gainsCumules['B'])\n",
"\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAA3wAAAEpCAYAAADIyCBPAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nOzdd3yc1Zn3/8/l3nvFTQbb2GBc5d4IhCQENhCW3h0HU0xvhicQTDbP7yHll7IlybLJBrJLQtqTTbLJZpNNgiTLvReMjY2Ne+/dks7zx3UP94ws27Ik65Y03/frNa+x7jPl0swc+b7mnHMdCyEgIiIiIiIidU+9pAMQERERERGRC0MJn4iIiIiISB2lhE9ERERERKSOUsInIiIiIiJSRynhExERERERqaOU8ImIiIiIiNRRSvhERKqAmXUzs31mdmfSsYiIiIikKOETqUPM7EYz+6OZ7TGzk2a2xczeNrNxFXisd8zsFxciztrIzO43s2BmLc5wk38F3ggh/PgCPf8CM3vjQjx2qefJuvc9el9Tl2NmtsrMpptZg3Lef3iU7LeKfu5nZjPMrE2p22V8hsysU3S7nDIec5yZLTKz42ZW6Q1zzWykmc2o4H3P9PvcYmarzax+ZeOLHu8TZvZkJe6f/j6WmNlWM/upmfUu5/3L9T5WlpltMLOvn+M2V0a/x8CqfO7yMLPc6P+Q1tX93CJyYSjhE6kjzOybwC+BLcDngY8DLwAtgZlmdsl5PuQjwItVGmQdZWYPA42B55KOpQpk6/v+/wNjgE8Dvwdew/tPeXwZ+F4I4WD0cz/gFaB0ovC76DmORj93im6XU8Zj/jOwH/hkdJ/KGhk9V0Wc6ff5JWDAPZWIK90ngAonfJHU+zgOeBYYBvyunMl7ed/H6rAI/z3WVfcThxAWAEuAp6r7uUXkwijXt5ciUrOZ2Q34idLkEMIbpZr/zcz+Bjh2Po8ZQni3isKr80II3wW+m3QcVaG2vu9m1jSEcF6f8VI2hBDmRP/+q5ldDtyLJwFne96+wKeAx8/1BCGEXcCucsbTH3g9hJBXztuXKRp9q5IRuNJCCCVm9iPgMeCNC/EcFZD+Ps42s/14ot0POONn+3zexzPcv0kI4XhF7luWKOmcc84bXjg/BL5uZl8OIRQlGIeIVAGN8InUDU8C88tI9gAIIfw2hLA19bOZPWNm883sgJntMLPfmlmf9PuUntoXTW3abWZDzWyOmR01s8VmNqHU/T5jZgvN7Eg0PWqumU06W/Bm1t7M/tnMtkVT2FanpnaZWU40ten6Uvd5w8wWlBHfqGj64zEzm2lmvaOpc/9hZoej6XpXlXqsYGaPljo2w8x2nyPuJmb2VTPbZGYnzGypmX26Cl6PgWZWGL0Wq8zsM2e43Xgzy4veiz1m9i9m1jKtvY2ZfT+a2nbczDaa2b+c47lPm9JpZldFcR+PPi/fsbSprXaG6a5lTV0zsxui9+e4mW2PXr+Gae0Z72t07LTPQPTz02b2LTPbBSxPe00KzOxgdFliZrec7Xc+g6VAj3Lc7j5gWQjh/ej5rwR+G7Wtj+LcELV99DqZT+NcHt3urxZPRbzSfApnfeDb0bE3ovvXjz6XG6PP20ortWY09fqZT+9eCRwHpgP/kPa6BTN7J/q5v/m0703R52ilmT1pZvXO9ftEfgkMs3JMPTzbe28+3fQZoFdajG+c6zHL4VB03fCst6rY+zgy6i/HiEb3zew1M1se/a3ZbGZvmVmXsp7QzJ6KbrMveg/apLWdNqXTzKZE788x8791eeZfTKTaO5jZm9HfgqNRbLmlnnODmX39bM8d+Q3QDh9hFpFaTiN8IrWc+VSlMcBZ14SU0h34R+BDoBXwEFBoZv1CCAfOcr9mwJvAN4Ht+HSnX5lZzxDCUfNpo78Avo2fADUBhuMnDmeKvynwDj697VXgPaBPdDlfzYDXga8CR4C/B/4NOAH8F/Ad4Hng52bWI4Rw9EwPVE6/IJ4qtw64FfiNmeWGEJZU4vX4b2A3cCfQFPgW0AJYkXa7ccCfgf8Abgba49MQ20Y/A3wDGItPzdqOJzATz+cXNLPLgD8AfwL+NnqM14CL8RGR83msW4Gf4NMV/xdwCfB/8C8fnz2fx4o8B+TjUwrrma+9+k/g18CX8OmGV1CxKXk9gfXluN3VwKy0nxfhv8vXgZuAbfjnr7RtwF3AW8C06H7go1BjgNn49MRfEI8Kfgn//L4KzMffj7fMLIQQfpL22Dl4H/gSsAPvU63xhCo1PTQ1bbEbsDqK4xAwJHr8pvh7c9bfJ4Swysz2Ra/DR5/P0srx3n8f6AtcBXw2ult5R0PT1Yv+JhrQO/pd3j9bbJGKvI8/wUf2X8Wn34L/Hfv/gK1AR/w1/4uZXRFCKE67763AMmAq/vf4G9H9HikrODObCHwP+CL+2WiFv5fp6+z+A/+7+Sz+9+M5/MuEoSGEtefz3CGEg9EXBh/HR0hFpDYLIeiiiy61+AJ0BgLwYKnjhn+pk7rYGe5fHz+5OwTcm3b8HeAXaT/PiJ7nqrRjQ6Jjn4p+vhnYc57xPwiUAEPO0J4TPcf1pY6/ASwoI75JacceiY59Me3YZdGxa9OOBeDRUo8/A9id9vP90e1aRD9fXfr5ouP5wM8r8Xo8ApwCuqcdGxc91xtpxwqAv5a671XR7QZGP68AHjvP5y/9vr+NnzDXTzt2a/Q8Y8p6bdJutwH4etrn8UPgh6Vu8zl8unH7st7XM30Gop8Xl7pdbnS85Xn+zgGfytcAX/N6B35yf/s57mf4CNq0Usevjx4zp9Tx0p+hgdHPV54hpkfTfm6Hf4nxSqnb/R5YXapfBEr1J+BRIJTj92mAJ2QfnOv3KfWZeescj1ue9/7r+JTMcr93ZbxmpS+bgCsu0Pv4xDketz6eUAdgYql+sQ5okHbsW8D2tJ+vJLMvPwssPMtzfYrT//41x5Pmfz6f5y71WSqs6Puhiy661JyLpnSK1H4WXZeu5PcMnjikLtM+uoPZaDP7k5ntAYrwIhIt8HUuZ3MKP7lLSa2J6R5dLwdaR9OKPmFmzcsR/1X4ifuSctz2XE7iiVBK6lvtv5RxrFsln+vj+KhZoZk1SF3wUbfUNKqKvB4j8RO7zakDIYRCYGfqZzNrhn+7/7NSzz0Tf4+GRzddAjxnZo+Y2bne27PF86uQOTrxS/xzM/48HqcfPmpWOua/4COfFalGWHrkYR1wGPhxNH3wfEb2vo2/dgeBHwP/FEJ4+xz3aYsX6znr1N8qMhAfwf55qeM/BfqZWae0Y1vK25/MpyW/amZr8ST3FPC/gd5Wziql+O9f5rTFyIV478/ka8CI6HIdPpL1ezM7W3+v6Pt42siXmV1rZrPM7ADeR1L9uHT/+2vIXBv3LtDJzBqd4bmWAEPN7JtmNrGM240EdoW0NZ8hhCP4iHfpflre5z7X+yoitYQSPpHabzd+ota91PF/Iz7x+YiZ9QT+iCeKD+KjRyPwhKLJOZ7rYAihJPVDCOFk9M8m0c+rgRvw6X6/B3ab2Y/NrONZHrM9Pl2qKhxKjw9PACGebnVazJXQAT8ZOlXqMoNo7VcFX48upCV3adKPtcVHD75T6rlP4GuVUmvPHsWneX0RWG1m75vZ7ef5e3bFpwV+JEr+9nCWqall6BBd/75UzKlpk+VZL1da6bj24ZUeGwI/A3aZ2e/M7OJyPFYqUfg4fpL8lJVaj1mG1GeorCmbVa1rdL2j1PHUz23LOFYeX8FHj17HK5SOIC5UU94+cuIct70Q7/2ZbAwhLIguv8enYzbh7BUnK/o+ZrzOZjYCX/u2GZ9mPAYYXeo5UvaX+vkk/je5zIQvhPA/wGR8SvY7+N+S76R9iXRaP02LsXQ/Le9zn+t9FZFaQmv4RGq5EEKRmc3GT3S/mHZ8B9EJgJml3+VT+EjBDdE3wKl1gOdz8n62eH6Hl0FvjX/D/i28YMSZEo09nH29XqryXemTkSqJN3KiAo+/F98C48az3agCr8d2vEJjaekjOPvxEd0Z+El0aVuj596PT1V83MwG4eu/3jKzZaH81Ti3lXruVOXH9vhrAGd+j9KTkNRtpwKLy3ie1Mn/8TIe50zvxWn704UQZgOfitZCfhxfn/Rj4hPvM9kYvBw9ZpaPj85+zcz+K4Rwpn3w9kTX1VG2P/WlSKe05wWf0g3x6wtlvC5ncQvwDyGEr6YOmNl15xlbm1LPX1p53/sqF0I4YWYfAAPOcrOKvo+lX+fP4lMob0t9Zsys13k+5pmfLIQ3gTejL4xuwtdSH8S3Dzmtn0Y6c/b35mzO9b6KSC2hET6RuuFbwCgzK89+WE3xNXPpU3pupYq/AAohHAi+Cfmv8HVzZ/JnfKrSoDO078RHAz46YTOvBlkVe5OlbC71+PXwqaZn82d8NO5w2ojCR5fSNz6P12M+MNzMPhqxjQq0fHQyFyXqc4BLy3rukFaRNe0+y/AiDvUoO6E8k7nAZy1zc+2b8M/LzOjn1LS19NdwFF5YImU1niDnnCHmPWmPlWNm6SML15xHvACEEI6FEH4L/Ctnf73Luu8p4OXofn9zltudADbixUHSlXcU+XxGm1fgU69LVxy9FVgTfMuHcz5XqdcV/O/BRyNb0ftc+suIc8WZA6w5y3OX970/eZbnqJDo970EX8tXpip4H1OaAqdKfUFwVznvW24hhF0hhH/Gp6+nPttz8WmZHxVliqZ+X0fcT89XDmd/X0WkltAIn0gdEEL4tZl9C3jDzD6GlxPfjY/CpE6WD0fXf8GnA/7QzH4AXI5P6So9zee8mdmDeCL2B3yUqS9+gvqjs9ztR/j6wj+al2ZfjZ949QshvBB8r69f41PsPozifIbz3FfwHH4FTDOzxcAH+Mb1rc5+F/6EV9P8k5l9BVgZ3WcI0CSE8GIFX48fAi/ho4Iz8JPIv+P09UXPA382sxK8kuMhfJ3UdcAXQghrzGxm9LutwEcjHsALf8w7x++W7sv4qMx/mNl38anDXwH+OxpNI3q8LcDfm9nL+Ijc88SVIInex2fwfSFb4VVTT+LTXW8Ebg5eNfU/8OqS3zcvyz8Un8p2TtHI1Oeix9iIr9N8kMw1nOX1S7y65XP4NL0zKSReM5myOrp+0MzeBo6GEJZzuo345/i+aM3XqbK+LAAIIeyN+vhLZlYELMAT70/jRWbO5b3o+gkz+ws+PXs1/jmeFq3h24v3xcbl/X2iKYX98QS5TOfx3r8HdDaz+/HP7O4QwoZy/G7pcswsNZrbES+C1Br4wTnuV5n3MeVPwJPR+/RbvELu3ecT/JmY2at4v3oH/1swFJiEj+4RQvhvMysEfmpmL+Cjls/ifz++VsGnzcX7uojUdklWjNFFF12q9oJPKfoTfuJ2Ck8yfklaRcrodvfiBS6O4SNFo0irqBjd5h1Or9K5u4zn/KiaIJ7c/C563uP4VK2vAI3PEXd74F/w0bzj+Inf42ntnfFS+wfxan9TKbtK5+5Sj3slaZXuyoo5+rkFvt3EXnxK5UulH48yKlHiJ8av4oVgTkb3/QNwXSVfj0F4ifgT+EnnjfgJ/hulbjcqer6DeCL3Lj6FsXXU/jV8auIhPFH+KzDhHM/9DlGV0bRjV+MjCMej9+g7nF6RcwQ+OnkUTxDHlf5MRbe7Fh+ZOBLFvQRPKhuUeq3XRY/1n/iJc1lVOktXVr0UT343Ra/dZryUfbtz/M6nPVZaP/moGukZ7ntz9Po2LXX8GfyzWkRUefIMn6G78FGUk6RV0TzD71c/+rxtim7/LnBXqdu8Qakqp9Fxw7dq2IqP8L+T1rd+Fb0XO6LbPFBGnKf9Pml/cw4Bzcvx9+ms7z0+kvbD6DMWKPV5L8fjl67QuRv/zH+sHPet1PuYdvvno/fnCPA/+Jc8pf/ebOD0fpHxmJxepfN6fFbBLrwfrsaTPUt7jI74l0n78L/tecCIUs9zzueOjg2NPic55/Me6KKLLjXzYiGcz1R/ERGpy8xsIZ4wPJh0LLVBVNlwM17Sv3QFzTrPzH4CHAkhfD7pWCoj29/H0szs/+DJ4seTjkVEKk9r+EREBDPrYmZ34qOLZU4rlNMFr/r6NeCJpGOpbmbWA69C+1rSsVRWNr+PpUXTdB8grtYqIrWc1vCJiAh4oY5XgLfwLT2k/P4RaGZmrUMIB5IOphp1Bx4KIaw95y1rh2x9H0vrCXwphPBO0oGISNWoEVM6O3ToEHJycpIOQ0REREREpFZauHDh7hDCaXv91ogRvpycHBYs0AwiERERERGRioiqmZ9Ga/hERERERETqKCV8IiIiIiIidZQSPhERERERkTpKCZ+IiIiIiEgdpYRPRERERESkjlLCJyIiIiIiUkedM+Ezs381s51mtiLt2NfM7D0zW2ZmvzKzNmltL5rZWjNbbWafvFCBi4iIiIiIyNmVZ4TvDeBTpY79CRgYQhgErAFeBDCzy4Dbgcuj+3zHzOpXWbQiIiIiIiJSbudM+EII+cDeUsf+GEIoin6cA3SP/n0D8HYI4UQIYT2wFhhZhfGKiIiIiIhUu+JiOHgw6SjOX1Ws4fsc8F/Rv7sBm9LaNkfHREREREREao2TJ2H2bPjKV+DTn4Z27eDll5OO6vw1qMydzewLQBHwVupQGTcLZ7jvVGAqQM+ePSsThoiIiIiISKUcOwbz5kFeHuTne7J39Ki39e8Pd9wB116bbIwVUeGEz8zuA64Hrg4hpJK6zUCPtJt1B7aWdf8QwuvA6wC5ubllJoUiIiIiIiIXwuHDMGuWJ3d5eZ7snTwJZjBoEEyZAhMn+qVTp6SjrbgKJXxm9ilgOjAphHA0rek3wI/N7BvARUBfYF6loxQREREREamE/fth5sw4wVu40Nfl1a8Pw4bBY4/BpEkwbpxP36wrzpnwmdlPgCuBDma2GXgFr8rZGPiTmQHMCSE8FEJYaWY/A97Fp3pOCyEUX6jgRUREREREyrJrFxQUxFM0ly6FEKBhQxg5EqZP99G7sWOhZcuko71wLJ6NmZzc3NywYMGCpMMQEREREZFaauvWePQuPx/efdePN20KY8bE0zNHj/ZjdY2ZLQwh5JY+XqmiLSIiIiIiItUtBPjwwzi5y8uDdeu8rUULGD8e7r7bp2jm5kKjRsnGmyQlfCIiIiIiUqOFAO+/n5ngbYo2g2vbFiZMgEce8RG8IUOggbKcj+ilEBERERGRGqWkBFauzJyiuWOHt3Xq5CN3zz/vCd7AgVCvKnYXr6OU8ImIiIiISKKKiryoSiq5KyiAvXu9rXt3+PjHPbmbNAn69fOtE6R8lPCJiIiIiEi1OnkSFizw5C4/37dLOHTI2y65BG64wZO7iRMhJ0cJXmUo4RMRERERkQvq2DGYOzeeojl7th8DGDAA7rorrqLZrVuysdY1SvhERERERKRKHT4Ms2bFCd68eT6qZwaDB8MDD3hyN2GCr8mTC0cJn4iIiIiIVMr+/T4tM7UGb+FCKC6G+vVh+HB4/HGfojlunFfVlOqjhE9ERERERM7Lrl3x+rv8fC+4EoLvdzdyJLzwgo/gjRkDLVsmHW12U8InIiIiIiJntWVLnNzl5cGqVX68aVMYOxZmzPAEb9QoPyY1hxI+ERERERH5SAiwYUPmHnjr1nlby5Ywfjzce69P0Rw+3Ef1pOZSwiciIiIiksVCgDVrMhO8TZu8rV07L6wybZqP4A0eDA2UQdQqertERERERLJISQmsXBknd/n5sGOHt3Xu7CN306d7gnf55VCvXrLxSuUo4RMRERERqcOKimDJkji5KyiAvXu9rUcPuOYaT+4mTYK+fbXJeV2jhE9EREREpA45eRIWLIinaBYWwqFD3tanD9x4Y5zg5eQkGqpUAyV8IiIiIiK12LFjMHduPEVz9mw/BnDZZXD33fEm5926JRurVD8lfCIiIiIitcihQzBrVjyCN28enDrlUzGHDIGpU+MEr2PHpKOVpCnhExERERGpwfbtg5kz4wRv0SIoLob69SE3F5580qdnjhsHbdokHa3UNEr4RERERERqkJ07vbBKaormsmW+dUKjRr6x+Ysv+gjemDHQokXS0UpNp4RPRERERCRBW7bEyV1eHrz3nh9v1gzGjoVXX/UEb9QoaNIk2Vil9lHCJyIiIiJSTUKADRsyE7wPPvC2Vq1g/Hi4/36fojlsmI/qiVSGEj4RERERkQskBFi9Ok7u8vNh82Zva9fOR+4ee8yvBw/2dXkiVUkJn4iIiIhIFSkpgRUrMhO8nTu9rUsXH7mbONEvl10G9eolG6/UfUr4REREREQqqKgIliyJk7uCAq+qCdCzJ3zyk/Em5336+NYJItVJCZ+IiIiISDmdPAnz58cjeIWFcPiwt/XtCzfdFI/i9eqVbKwioIRPREREROSMjh6FuXPjBG/2bDh+3NsuvxzuuccTvAkT4KKLko1VpCxK+EREREREIocOwaxZ8RTNefPg1CmfijlkCDz0kI/eTZgAHTokHa3IuSnhExEREZGstW+fr7tLjeAtXgzFxdCgAeTmwlNPeYI3bhy0aZN0tCLnTwmfiIiIiGSNHTs8wUuN4C1f7lsnNG7sG5u/+KJP0Rw9Glq0SDpakco7Z8JnZv8KXA/sDCEMjI61A34K5AAbgFtDCPvMzIBvA58GjgL3hxAWXZjQRURERETObvPmzC0S3nvPjzdrBmPHwpe+5CN4I0dCkybJxipyIZRnhO8N4B+BH6UdewH4cwjhNTN7Ifp5OnAt0De6jAK+G12LiIiIiFxQIcD69XFyl5fnPwO0auXr7iZP9gRv+HBo2DDZeEWqwzkTvhBCvpnllDp8A3Bl9O83gXfwhO8G4EchhADMMbM2ZtY1hLCtqgIWEREREQFP8N57z5O7VIK3ZYu3tW/vid3jj/sUzUGDoH79ZOMVSUJF1/B1TiVxIYRtZtYpOt4N2JR2u83RMSV8IiIiIlIpJSW+5i59iuauXd7WpYsndqk98AYMgHr1ko1XpCao6qItVsaxUOYNzaYCUwF69uxZxWGIiIiISG1XVORVM1PJXUEB7N/vbb16wbXXenI3cSL06eNbJ4hIpoomfDtSUzXNrCuwMzq+GeiRdrvuwNayHiCE8DrwOkBubm6ZSaGIiIiIZI8TJ2D+/HgEb9YsOHzY2/r1g5tvjhO8Xr2SjVWktqhowvcb4D7gtej612nHHzWzt/FiLQe0fk9EREREynL0KMyZEyd4c+bA8ePeNnAg3HuvT9GcMAG6dk02VpHaqjzbMvwEL9DSwcw2A6/gid7PzGwKsBG4Jbr57/EtGdbi2zJMvgAxi4iIiEgtdPCgj9qlpmjOnw+nTvlauyFD4OGHffRu/Hjo0CHpaEXqhvJU6bzjDE1Xl3HbAEyrbFAiIiIiUvvt3QszZ8YJ3qJFXnilQQMYMQKeftoTvHHjoHXrpKMVqZuqumiLiIiIiGSpHTsyt0hYvtyPN24Mo0fDF77gUzRHj4bmzZONVSRbKOETERERkQrZtClzi4TVq/148+YwdizcdpuP4I0YAU2aJBurSLZSwiciIiIi5xQCfPBBZoK3fr23tW7t6+6mTPEEb9gwaNgw2XhFxCnhExEREZHThADvvRcnd/n5sGWLt3Xo4IndE0/4FM0rroD69ZONV0TKpoRPRERERCgu9jV3qRG8ggLYtcvbunb1xG7iRL8eMECbnIvUFkr4RERERLLQqVOweHE8gjdzJuzf7205OXDttXGSd8klSvBEaislfCIiIiJZ4MQJ3/culeAVFsKRI97Wrx/ccosndxMnQs+eycYqIlVHCZ+IiIhIHXT0KMyeHU/RnDPHkz7wNXf33x8neF26JBqqiFxASvhERERE6oCDB33ULjWCN38+FBVBvXowdCg88ohP0Rw/Htq3TzpaEakuSvhEREREaqE9e3zdXSrBW7wYSkqgQQPf9+7ZZ330btw4aNUq6WhFJClK+ERERERqge3b4+0R8vJgxQo/3qQJjB4NL73kCd6YMdCsWbKxikjNoYRPREREpAbauDFzk/M1a/x48+Y+anf77T5Fc8QIaNw42VhFpOZSwiciIiKSsBBg3brMBG/DBm9r3RomTIAHHvARvKFDoWHDRMMVyT6HD3sVpNatYeTIpKM5L0r4RERERKpZCLBqVZzc5efD1q3e1rGjJ3ZPPeUjeAMHQv36ycYrknX27/dFsqkOunChV0G68054662kozsvSvhERERELrDiYli2LB7BKyiA3bu97aKL4g3OJ06EAQO0yblItdu1yztmqpMuXerfzDRq5CN6zz/vHXXMmKQjPW9K+ERERESq2KlTsGhRfO44cyYcOOBtvXvDddfFSd7FFyvBE6l2W7dmzqF+910/3rSpJ3UzZngHHTXKj9ViSvhEREREKun4cd/3LnXuOGsWHDnibZdeCrfdFo/g9eiRbKwiWScE+PDDzDnUa9d6W8uWXgXpnnu8g+bm+qheHaKET0REROQ8HTni9RtSAwRz58KJE942aBBMnhwneJ07JxurSNYJAd5/P07w8vJg0yZva9vWO+bDD/sw++DBvnllHVa3fzsRERGRKnDgABQWxuePCxZ4/YZ69WDYMJg2zc8dx4+Hdu2SjlYky5SUwMqVmVM0d+zwts6dPcGbPt2vL7/cO24WUcInIiIiUsru3b7uLnXuuGSJn1M2bOj73j33nJ87jh0LrVolHa1Ilikq8qIqqQ5aUAB793pb9+7w8Y/Hi2T79cv6RbJK+ERERCTrbdsWL+3Jy/PBAoAmTbx+w8sv+7nj6NHQrFmysYpknZMnfVg91UlnzoRDh7ztkkvgxhu9g06aBL16ZX2CV5oSPhEREck6H36YOfvr/ff9eIsWXr/hzjv93DE3Fxo3TjZWkaxz7JgvjE110tmz/RjAZZfBXXd5B50wAbp1SzbWWkAJn4iIiNRpIXhBvvQCfR9+6G1t2/o544MP+gDB0KF1vn6DSM1z+LCXtk110nnzfFTPzIuqPPBAnOB17Jh0tLWO/qSJiIhInVJS4ltqpZK7/HyfsgnQqZMnds884+ePAwdmXf0GkeTt2+fTMlMddOFCKC6G+vVh+HB44gnvqOPHQ5s2SUdb6ynhExERkVqtuNjrN6RmfxUUwJ493vQ0Y4YAACAASURBVNatG3zsY3H9hksv1fIekWq3a1fmItlly3zovVEj39j8hRe8k44Z4/OqpUop4RMREZFa5dQpHxBIzf6aORMOHvS2iy+Gz3wm3gOvd28leCLVbsuWzEWyq1b58aZNvbTtjBme4I0c6cfkglLCJyIiIjXa8eNx/Yb8fF/qc/Sot/XvD3fcESd43bsnG6tI1gkBNmzIXCS7bp23tWzp0zLvu8876PDhPqon1UoJn4iIiNQohw97Ub7UAMHcuXH9hkGDYMqUuH5Dp05JRyuSZUKANWviBC8vDzZv9rZ27TyxmzbNO+ngwb4uTxKlhE9EREQStX8/FBbG548LF/q+yvXrw7Bh8Pjjcf2Gtm2TjlYky5SUwIoVmVM0d+70ts6dPbFLLZK97DJVQaqBKpXwmdlTwOeBACwHJgNdgbeBdsAi4J4QwslKxikiIiJ1xO7dmRU0lyzxQYOGDb1+w/PP+7nj2LE+I0xEqlFRkXfKVHJXUOBVNQF69IBPfCJO8Pr21SLZWqDCCZ+ZdQMeBy4LIRwzs58BtwOfBr4ZQnjbzL4HTAG+WyXRioiISK2zdWtmgb533/XjTZt6Ub5XXvHzx1GjVL9BpNqdPAkLFsQJXmEhHDrkbX36wE03eXI3aRL06pVsrFIhlZ3S2QBoamangGbANuAq4M6o/U1gBkr4REREssaGDZmzv9au9eMtW8K4cXDPPX7+mJur+g0i1e7YMZgzJ+6kc+b4MYDLL4e7744XyV50UbKxSpWocMIXQthiZl8HNgLHgD8CC4H9IYSi6GabgW5l3d/MpgJTAXr27FnRMERERCRBIcD772cW6Nu40dvatvXE7uGH/XrIEGig6gEi1evQIS9tm+qk8+b53iZm3imnTvUEb/x46Ngx6WjlAqjMlM62wA1Ab2A/8HPg2jJuGsq6fwjhdeB1gNzc3DJvIyIiIjVLSQmsXJm5Bm/7dm/r1MnPG597zq8vv1z1G0Sq3b59vu4u1UEXLYLiYq+ClJsLTz3l38CMGwdt2iQdrVSDynzP9nFgfQhhF4CZ/V9gLNDGzBpEo3zdga2VD1NERESSUFQES5fGs78KCmDvXm/r3h2uvjqu39Cvn+o3iFS7nTszF8kuX+5D740b+8LYF1/0Tjp6NLRokXS0koDKJHwbgdFm1gyf0nk1sAD4K3AzXqnzPuDXlQ1SREREqsfJk74tQmr218yZcf2GSy6BG2+MNznPyVGCJ1LtNm/OXCT73nt+vFkzL2376que4I0cCU2aJBur1AiVWcM318x+gW+9UAQsxqdo/g5428y+HB37QVUEKiIiIlXv2DHf2Dw1QDBrVly/YcAAuOuuOMHrVuaqfBG5YEKA9eszF8l+8IG3tWrl6+4mT/YOOny4720iUoqFkPzyudzc3LBgwYKkwxAREanzDh/2pC41QDBvno/qmcHgwXH19fHjfU2eiFSjEGD16jjBy8uDLVu8rX37+NuXSZNg0CBflycSMbOFIYTc0sdVK0tERKQO27/fp2Wmzh8XLozrNwwfDk88EddvaNs26WhFskxJia+5S5+iuWuXt3XpEi+QnTTJh9xVBUkqQAmfiIhIHbJrV2YFzaVLfdCgUSNf0vPCC37+OHas6jeIVLuiIli8OE7uCgr8WxnwTc0/9ak4yevTR4tkpUoo4RMREanFtmzJLNC3apUfb9rUk7oZM+L6DU2bJhqqSPY5cQIWLIgTvMJCn1cN0Lcv3HxzPE2zV69kY5U6SwmfiIhILRECbNiQOftr3Tpva9nS193dd19cv6FRo0TDFck+R4/CnDlxJ50zB44f97aBA+Hee+MEr2vXZGOVrKGET0REpIYKAdasySzQt2mTt7Vr5+eM06b59eDB0ED/q4tUr4MHvQpSqpPOnw+nTvlauyFD4KGH4ipIHTokHa1kKf3XICIiUkOUlMCKFZlr8Hbs8LbOnf28cfp0v77sMtVvEKl2e/dmVkFatMg7boMGkJsLTz8dV0Fq3TrpaEUAJXwiIiKJKSqCJUvi2V8FBbBvn7f16AHXXBPXb+jbV/UbRKrdjh2Zi2SXL/fjjRvD6NHwhS94Jx09Gpo3TzZWkTNQwiciIlJNTp70+g2pc8fCQjh0yNv69IGbboqX9+TkJBqqSHbatCkzwVu92o83b+5VkG691RO8ESOgSZNkYxUpJyV8IiIiF8ixYzB3bjz7a/ZsPwY+JfPuu+ME76KLko1VJOuEAB98kFkFaf16b2vd2tfdTZniHXTYMGjYMNl4RSpICZ+IiEgVOXTI6zekzh/nzfP6DWZev2Hq1Lh+Q8eOSUcrkmVCgPfey6yCtGWLt3Xo4IndE0/49aBBUL9+svGKVBElfCIiIhW0b5/Xb0gleIsWQXGxnyfm5sKTT3qCN24ctGmTdLQiWaakBJYty6yCtGuXt3XtGi+QnTQJ+vdXFSSps5TwiYiIlNPOnV5YJTVAsGyZDxo0agSjRsGLL/r545gx0KJF0tGKZJmiIv/WJfUNzMyZsH+/t+XkwLXXxkneJZeoCpJkDSV8IiIiZ7BlS5zc5eX5bDCAZs28fsOrr/q546hRqt8gUu1OnPB971KdtLAQjhzxtn794Oab4wSvZ89kYxVJkBI+ERERfKRu/frMAn0ffOBtrVr5urv77/fzx2HDfFRPRKrR0aNe+SjVSefMgePHvW3gQO+gqSpIXbokGqpITaKET0REslIIXnE9vUDf5s3e1q6dnzM+9phfDx6s+g0i1e7gQR+1S3XSBQu8ClK9ejB0KDz8cFwFqX37pKMVqbGU8ImISFYoKYEVKzIL9O3c6W1dusQzvyZO9C0TVL9BpJrt2ePr7lKddPFi77gNGvi+d08/7R117FjfNkFEykUJn4iI1ElFRX6+mEruCgq8qib4cp5PfjIu0Nenj+o3iFS77dszK2guX+7HGzeG0aPhpZe8k44e7Rufi0iFKOETEZE64cQJn/GVmv1VWAiHD3tb375w003xKF6vXsnGKpKVNm3KrIK0Zo0fb97c9y657TbvpCNGeNInIlVCCZ+IiNRKR4/C3Lnx+ePs2XH9hssvh3vv9eRuwgS46KJkYxXJOiHAunWZi2Q3bPC21q29Yz7wgHfSoUOhYcNEwxWpy5TwiYhIrXDoUFy/IT8f5s2L6zcMGQIPPRQneB06JB2tSJYJAVatylwku3Wrt3Xo4J3zqaf8+oorVAVJpBop4RMRkRpp716v35AaIFi0KK7fkJvr546TJvlMMNVvEKlmxcW+5i49wdu929suuiiePz1pEvTvr0WyIglSwiciIjXCjh1eWCV1/rh8uQ8aNG7sG5t/4Qt+/jhmjOo3iFS7U6f8W5fUNzAzZ8KBA97Wuzdcd12c5F18sRI8kRpECZ+IiCRi8+bM5T3vvefHmzXzUbtbbvFzx5EjoUmTZGMVyTonTvi86VQnnTULjhzxtksvhVtvjRO8Hj2SjVVEzkoJn4iIXHAhwPr1mQX61q/3tlatfN3d5Ml+/jhsmOo3iFS7I0dgzpy4k86Z40kf+Jq7yZPjjSo7d042VhE5L0r4RESkyoXgI3bpI3hbtnhb+/Z+zvj4457gDRqk+g0i1e7AgcwqSPPn++aV9ep51cxp0+IqSO3aJR2tiFSCEj4REam0khJfc5ee4O3a5W1dunhil5r9NWCAn1OKSDXas8cXyaY66ZIl3nEbNvR975591jvp2LE+7C4idYYSPhEROW9FRbB4cZzcFRTA/v3e1qsXXHttPPurTx/VbxCpdtu3Z34Ds2KFH2/SBEaPhpdf9g46erQvnBWROksJn4iInNOJEz7jK71+w+HD3tavH9x8c5zg9eqVbKwiWWnjxswtEtas8ePNm3sVpDvu8A46YoSXvhWRrFGphM/M2gDfBwYCAfgcsBr4KZADbABuDSHsq1SUIiJSrY4e9ZoNqQRvzhw4ftzbBg6Ee+/12V8TJkDXrsnGKpJ1QoC1a+PkLi8PPvzQ29q08Y75wAPeSYcO9c0rRSRrVfYvwLeBP4QQbjazRkAz4H8Bfw4hvGZmLwAvANMr+TwiInIBHTzoo3apAYL5833brXr1YMgQePhhHxwYPx46dEg6WpEsEwK8+27mFM1t27ytY0fvnM8849cDB6oKkohkqHDCZ2atgInA/QAhhJPASTO7AbgyutmbwDso4RMRqVH27s2s37B4sddvaNDAZ3w9/bSfO44bB61bJx2tSJYpLoZlyzIXye7e7W3dusHHPhbPoe7fX4tkReSsKjPCdzGwC/ihmQ0GFgJPAJ1DCNsAQgjbzKxT5cMUEZHK2LEjc/bX8uV+vHFjr9nwhS/47K/Ro33Jj4hUo1OnYNGiOMGbOdO3TQDo3Ruuv96Tu0mT/GcleCJyHiqT8DUAhgGPhRDmmtm38emb5WJmU4GpAD179qxEGCIiUtqmTZmzv1av9uPNm3vV9dtui+s3NGmSbKwiWef4cZg3L7MK0tGj3nbppd5BU4tke/RINlYRqfUqk/BtBjaHEOZGP/8CT/h2mFnXaHSvK7CzrDuHEF4HXgfIzc0NlYhDRCSrhQAffBAnd3l5sGGDt7Vu7eeMU6Z4gjdsmG+7JSLV6MgRmD077qRz53rpWzO44oq4g06YAJ07Jx2tiNQxFU74QgjbzWyTmV0aQlgNXA28G13uA16Lrn9dJZGKiAjgCd5772UmeFu3eluHDn7e+OSTPkBwxRWq3yBS7Q4cgMLCuJMuWOCbV9ar59+6PPpoXAWpXbukoxWROq6yVTofA96KKnR+AEwG6gE/M7MpwEbglko+h4hIVisu9jV3qeSuoAB27fK2rl09sZs0yc8fBwzQ8h6Rard7d2YVpKVLvQpSw4YwciQ895x30rFjoWXLpKMVkSxTqYQvhLAEyC2j6erKPK6ISDY7dcqrZqbXb9i/39tycuDaa+ME75JLlOCJVLtt2zKrIK1c6cebNIExY+Dll72TjhoFzZolG6uIZD3txCkikrATJ3zfu1SCV1joS34A+vWDW26JK7CrxpVIAj78MLMK0vvv+/EWLXzvkrvu8g6am+ulb0VEahAlfCIi1ezoUa/fkDp/nDPHkz7wNXf33x8neF26JBqqSPYJAdauzVwku3Gjt7Vt64VVHnzQO+jQob55pYhIDaa/UiIiF9jBg5n1G+bPj+s3DB0Kjzzis7/Gj4f27ZOOViTLlJTAu+/GUzTz833KJkCnTp7YPfusd9KBA73jiojUIkr4RESq2J49vu4uleAtXuznlA0a+L53zz7r55DjxkGrVklHK5Jliou9qEp6FaQ9e7ytWzf42MfiRbKXXqpFsiJS6ynhExGppO3bM+s3rFjhx5s0gdGj4aWX/NxxzBjVbxCpdqdOwcKFmVWQDh70tosvhs98Jp5D3bu3EjwRqXOU8ImInKeNGzMTvDVr/Hjz5j5qd/vtPkAwYoTqN4hUu+PHYd68OMGbNcsXzgL07w933BEneN27JxuriEg1UMInInIWIcC6dZkF+jZs8LbWrb1+wwMPxPUbGjZMNFyR7HPkiCd1qU46dy6cPOkjdYMGwZQp/g3MhAm+Jk9EJMso4RMRSRMCrFoVJ3f5+bB1q7d17OiJ3VNPxfUb6tdPNl6RrLN/v1dBSiV4Cxd6FaT69WHYMHj8ce+o48d7VU0RkSynhE9EslpxMSxfnpng7d7tbRddFNdumDTJZ4NpeY9INdu92wurpDrpkiX+zUzDhjByJDz/vHfSsWOhZcukoxURqXGU8IlIVjl1ChYtigcHZs6EAwe8rXdvuO66OMm7+GIleCLVbuvWzEWy777rx5s29cpHr7ziHXT0aD8mIiJnpYRPROq048d937v0+g1HjnjbpZfCrbfGCV6PHsnGKpKVNmzIXCS7dq0fb9HCp2Xefbd30txcaNQo0VBFRGojJXwiUqccOQKzZ8cDBHPmwIkT3nbFFTB5clygr3PnZGMVyTohwPvvZyZ4Gzd6W9u2Xljl4Ye9gw4Z4ptXiohIpegvqYjUagcOZNZvWLDA6zfUq+f1G6ZN88GB8eOhXbukoxXJMiUlPiUzfZHs9u3e1qmTd87nnvMEb+BA77giIlKllPCJSK2yZ4/Xb0gleEuW+Dllw4a+792zz/o55Nix0KpV0tGKZJniYu+UqeSuoMA7Lfied1dfHVdB6tdPi2RFRKqBEj4RqdG2b8+c/bVihR9v0sRrNrz8cly/oVmzZGMVyTqnTvmweqqTFhbCwYPedskl8JnPxItkc3KU4ImIJEAJn4jUKBs3Zs7+WrPGj7doAePGwR13xPUbGjdONlaRrHP8uG9snuqks2fD0aPeNmAA3HlnvEi2W7dkYxUREUAJn4gkKAQvyJdegf3DD72tTRuv3/DAA57gDR2q+g0i1e7wYU/qUgne3Llw8qSP1A0eDJ//vCd3Eyb4mjwREalxdPokItUmBK/fkD5Fc9s2b+vY0c8bn3nGr6+4QvUbRKrd/v2+OWWqky5c6Ovy6teH4cPh8cf9G5hx47yqpoiI1HhK+ETkgikuhmXL4uSuoAB27/a2bt3gYx+LZ3/176/lPSLVbtcu75ipTrp0qX8z06gRjBwJ06d7gjdmDLRsmXS0IiJSAUr4RKTKnDrlAwKpKZozZ/q2CQC9e8P118cF+nr3VoInUu22bs0cYn/3XT/etKkndTNmeCcdNcqPiYhIraeET0Qq7PhxmDcvPn+cNSuu39C/P9x2myd3EyZAjx7JxiqSdULwRbGp5C4vD9at87aWLX1zynvu8U46fLiP6omISJ2jhE9Eyu3IkdPrN5w44SN1V1wBU6bE9Rs6d046WpEsE4KXtU0fwdu0ydvatfOO+cgjnuANHqwqSCIiWUJ/7UXkjA4ciOs35Of7dltFRV5MZdgwePRRT/DGj/fzSRGpRiUlsHJlZoK3Y4e3de7snXP6dL++/HJVQRIRyVJK+ETkI7t3e/2G1Pnj0qV+TtmwoddveO45HxwYO1b1G0SqXVGRd8r0Kkh793pbjx5wzTXxItm+fbVIVkREACV8Illt27bMwYGVK/14kyZev+GLX4zrNzRrlmysIlnn5EkfVk910sJCOHTI2/r0gRtvjBO8Xr2U4ImISJmU8IlkkfT6Dfn58P77frxFC99W6667/PwxNxcaN042VpGsc+yYL4xNddLZs/0YwGWXeQdNVUHq1i3ZWEVEpNZQwidSR4XgCV0qucvLg40bva1tWz9nfPBBP38cMkT1G0Sq3aFDmVWQ5s3zUT0zL6oydWpcBaljx6SjFRGRWkqneCJ1REmJb6mVPkVz+3Zv69TJzxufe86vBw5U/QaRardvX1wFKS8PFi2C4mKoX9+H1Z94Iq6C1KZN0tGKiEgdoYRPpJYqLj69fsOePd7WrRtcdZWP3k2cCJdequU9ItVu507vmKlOumyZD703auQLY194wTvpmDE+r1pEROQCqHTCZ2b1gQXAlhDC9WbWG3gbaAcsAu4JIZys7POIZLtTp2DhwvjcceZMOHjQ2y6+GD7zmbh+Q06OEjyRardlS+YQ+6pVfrxpUy9t++qrcRWkJk2SjVVERLJGVYzwPQGsAlpFP38F+GYI4W0z+x4wBfhuFTyPSFY5ftzrN6TW4M2aBUePetuAAXDHHXH9hu7dk41VJOuEABs2ZFZBWrfO21q18mmZ993nCd7w4T6qJyIikoBKJXxm1h24DvjfwNNmZsBVwJ3RTd4EZqCET+ScDh/2+g2pAYK5c+P6DYMGwZQpcYLXqVPS0YpkmRBgzZo4wcvLg82bva1dO0/spk3zTjp4sK/LExERqQEqO8L3LeB5ILUFc3tgfwihKPp5M6Da0SJl2L/ft9VKnT8uXOj7KtevD8OGweOPx/Ub2rZNOlqRLFNSAitWxMldQQHs2OFtnTt7YpdaJHvZZaqCJCIiNVaFEz4zux7YGUJYaGZXpg6XcdNwhvtPBaYC9OzZs6JhiNQau3fHM7/y82HJEh80aNjQl/Q895yfP44dCy1bnvvxRKQKFRV5p0yvgrRvn7f16AHXXBMneH37apGsiIjUGpUZ4RsHfMbMPg00wdfwfQtoY2YNolG+7sDWsu4cQngdeB0gNze3zKRQpDbbujVzD7x33/XjTZt6Ub5XXvHzx1Gj/JiIVKOTJ2HBgjjBKyz0ffEA+vSBm26KqyD16pVsrCIiIpVQ4YQvhPAi8CJANML3bAjhLjP7OXAzXqnzPuDXVRCnSI23YUNmgb61a/14y5Ywbhzcc4+fP+bmqn6DSLU7dgzmzIk76Zw5fgzg8svh7rvjRbIXXZRsrCIiIlXoQuzDNx1428y+DCwGfnABnkMkUSHA++9nFujbuNHb2rb1xO7hh/16yBBooB0vRarXoUNe2jbVSefN871NzLxTTp3qCd748dCxY9LRioiIXDAWQvKzKXNzc8OCBQuSDkPkjEpKYOXKzDV427d7W6dO8dKeSZN8sED1G0Sq2b59vu4u1UEXLYLiYq+ClJsbd9Jx46BNm6SjFRERqXJmtjCEkFv6uMYdRMpQVARLl2YW6Nu719u6d4err47PH/v1U/0GkWq3c2fmItnly33ovXFjXxj74oveSUePhhYtko5WREQkMUr4RPD6DQsXxrO/Zs6M6zdccgnceKMndxMnQk6OEjyRard5c+Yi2ffe8+PNmnlp21df9QRv5Eho0iTZWEVERGoQJXySlY4d843NUwMEs2bF9RsGDIC77ooTvG7aSVKkeoUA69dnLpL94ANva9XK191NnuwddPhw39tEREREyqSET7LC4cOe1KUGCObN81E9Mxg8GB54IK7f0KlT0tGKZJkQYPXqOMHLy4MtW7ytfXtP7B57zDvpoEG+Lk9ERETKRQmf1En79/u0zNT548KFcf2G4cPhiSfi+g1t2yYdrUiWKSnxNXfpUzR37fK2Ll0yqyANGKAqSCIiIpWghE/qhF27MitoLl3qgwaNGvmSnhde8PPHsWNVv0Gk2hUVweLFcXJXUODfyoBvav6pT8VJXp8+WiQrIiJShZTwSa20dWvm7K9Vq/x406ae1M2YEddvaNo00VBFss+JE7BgQdxJCwt9XjVA375w883xItlevZKNVUREpI5Twic1XgiwYUNmBfZ167ytZUtfd3fffXH9hkaNEg1XJPscPQpz5sSddPZsOH7c2wYOhHvvjRO8rl2TjVVERCTLKOGTGicEWLMmc3nPpk3e1q4dTJgA06b5uePgwdBAn2KR6nXokI/apTrp/Plw6pSvtRsyBB56KK6C1KFD0tGKiIhkNZ0qS+JKSmDlyswK7Dt2eFvnzn7eOH26J3iXX676DSLVbu/ezCpIixZ5x23QAHJz4emn4ypIrVsnHa2IiIikUcIn1a6oCJYsiZO7ggI/nwTo0QOuuSYu0Ne3r+o3iFS7HTsyqyAtX+5D740bw6hR8IUveCcdMwaaN086WhERETkLJXxywZ086fUbUrO/Cgt9Rhh4Qb4bb4wL9OXkJBqqSHbatClzkezq1X68WTMftbvlFu+kI0ZAkybJxioiIiLnRQmfVLljx2Du3Hj21+zZfgzgssvg7rs9uZswAbp1SzZWkawTAnzwQeYi2fXrva11a193N2WKd9Jhw6Bhw2TjFRERkUpRwidVpqQEvvpVePVVL9Bn5vUbpk6NE7yOHZOOUiTLhADvvZe5SHbLFm9r39475xNP+PWgQVC/frLxioiISJVSwidVYvt2uOce+J//gc9+1gcIxo2DNm2Sjkwky5SUwLJlmWvwdu3ytq5d4/nTkyZB//6qgiQiIlLHKeGTSvvDH3ybrcOH4fXX4fOfV6EVkWpTVORVM1NTNGfOhP37vS0nB669Nk7yLrlEnVNERCTLKOGTCjt50ov1ff3rvrfyO+/4Gj0RuYBOnPB971JTNAsL4cgRb+vXD26+OU7wevZMNlYRERFJnBI+qZB16+COO/y886GH4BvfgKZNk45KpA46etQrH6WmZ86Z44tkwb9puf9+T+4mToQuXRINVURERGoeJXxy3n7yE3jwQa/t8ItfwN/+bdIRidQhBw/6qF1qBG/+fJ+2Wa8eDB0KDz/sI3jjx3vRFREREZGzUMIn5XbkCDz2GPzwhzB2LPz4x9CrV9JRidRye/b4urtUgrd4sRdeadDA97175hlP8MaO9W0TRERERM6DEj4plyVL4PbbYc0aX7c3Y4afj4rIedq+PXOT8xUr/HjjxjB6NLz0kk/PHD0amjdPNlYRERGp9XTKLmcVAvzTP/kgQ/v2vu3CVVclHZVILbJxY+Ym52vW+PHmzX3vkttv9wRv5EhP+kRERESqkBI+OaM9e3w/vV//Gj79aXjjDW2cLnJWIXhFo/QEb8MGb2vdGiZM8H1LJk3y9XgNGyYaroiIiNR9SvikTPn5cNddsGOHV+B88klt3yVymhBg1ao4ucvPh61bva1DBx+5e+opv77iCq90JCIiIlKNlPBJhuJi+PKX4Utfgosv9mrww4cnHZVIDVFcDMuWxSN4BQWwe7e3XXRRvP/dxIkwYIC+JREREZHEKeGTj2ze7KN6+flwzz2+dq9ly6SjEknQqVOwaFGc4M2cCQcOeFtODlx3nSd3kyb5NyRK8ERERKSGUcInAPzmNzB5Mpw4AW++Cffem3REIgk4ftz3vUtN0Zw1y/cjAbj0Urj1Vk/uJkyAnj2TjVVERESkHJTwZbnjx+H55+Ef/sFrSLz9NvTrl3RUItXkyBGft5wawZs717/1AF9zN3myj+BNmABduiQbq4iIiEgFKOHLYqtXw223wdKlXpTltddUFV7quAMHoLAwHsFbsACKiqBePf/GY9q0OMFr1y7paEVEREQqrcIJn5n1AH4EdAFKgNdDCN82s3bAT4EcYANwawhhX+VDlaoSgk/bfPRRaNIEfvtbuP76pKMSuQB27/bCKqkRvKVLoaTEt0MYMQKefdYTvHHjoFWrpKMVERERqXKVGeErAp4J5ABZ3wAADwxJREFUISwys5bAQjP7E3A/8OcQwmtm9gLwAjC98qFKVTh4EB5+GH78Y7jySvj3f4du3ZKOSqSKbNsWb4+QlwcrV/rxJk1g9Gh46SVfgzd6NDRrlmysIiIiItWgwglfCGEbsC369yEzWwV0A24Aroxu9ibwDkr4aoQFC+D222H9evi7v4MXX9S2YFLLffhh5ibn77/vx5s391G7O+/0EbwRIzRfWURERLJSlazhM7McYCgwF+gcJYOEELaZWaeqeA6puJIS+OY3PcHr0sXPjcePTzoqkfMUAqxdGyd3eXmwcaO3tWnj6+6mTvUEb9gwaKAlyiIiIiKVPiMysxbAL4EnQwgHrZz7UJnZVGAqQE+VN79gdu6E++6DP/wBPvtZ+P73VYtCaomSEnj33XiKZn6+T9kE6NjRE7tnnvEpmgMHarhaREREpAyVSvjMrCGe7L0VQvi/0eEdZtY1Gt3rCuws674hhNeB1wFyc3NDZeKQsv35z3D33bBvH3znO/DQQ9oXWmqw4mIvqpIavSsogD17vO2ii3zR6aRJnuj1768Ps4iIiEg5VKZKpwE/AFaFEL6R1vQb4D7gtej615WKUM7bqVPwyiu+zUL//vDf/w2DBiUdlUgpp07BwoXxFM2ZM72qEEDv3vA3f+PJ3cSJcPHFSvBEREREKqAyI3zjgHuA5Wa2JDr2v/BE72dmNgXYCNxSuRDlfGzYAHfcAXPmwOc/D9/6ltevEEnc8eO+sXlqeuasWXD0qLf17+8VhVIJXo8eycYqIiIiUkdUpkrnTOBMX7lfXdHHlYr7+c/hgQe8tsXbb/um6iKJOXwYZs+Op2jOnQsnT/pI3RVXwOc+51M0J0yAzp2TjlZERESkTlIZuzrg6FF46il4/XUYNQp+8hOfESdSrfbvh8LCeIrmwoVQVAT16nnVzMce89G78eNVOUhERESkmijhq+VWrPCZcCtXwvTpvr9ew4ZJRyVZYfduL6ySSvCWLPHh5YYNYeRIeO45H8EbOxZatkw6WhEREZGspISvlgrBR/SefBJat4Y//hGuuSbpqKRO27o1Xn+Xl+dbJgA0aQJjxniloIkTfZi5WbNkYxURERERQAlfrbRvn6/V++Uv4ROfgB/9SEug5ALYsCFO7vLzfdNzgBYtYNw43/Nj4kTIzYXGjRMNVURERETKpoSvlpk1y6twbt0KX/2q7ztdr17SUUmtFwK8/35mgrdxo7e1beuFVR56yKdoDhkCDfSnQ0RERKQ20FlbLVFcDF/5Cnzxi9Crl9fGGDky6aik1iop8SmZqeQuPx+2b/e2Tp185O655/x64EB9qyAiIiJSSynhqwW2boV77oG//MULtHzve75uT6Tciou9qEpqBK+gAPbu9bbu3eHqqz25mzQJ+vXTJuciIiIidYQSvhru97+H++7zrRd+8AOYPFnn4lIOJ0/6tgipBK+wEA4e9LZLLoEbbogTvJwcfahERERE6iglfDXUyZPw4ovwjW/AoEG+kfqAAUlHJTXWsWMwb148RXP2bP+WAPyDc8cd8Sbn3bsnG6uIiIiIVBslfDXQ2rU+dXPhQpg2Db7+da98L/KRw4e9gk9qBG/ePP+WwMy/Ifj8530Eb8IEX5MnIiIiIllJCV8N8+//Dg8/7HtX/+pXcOONSUckNcL+/TBzZpzgLVzo6/Lq14fhw+Hxxz3BGz/eq2qKiIiIiKCEr8Y4fBgefRTefNMHZd56C3r0SDoqScyuXV5YJTVFc+lS3zqhUSMvzzp9uk/RHDMGWrZMOloRERERqaGU8NUAixf7FM61a33bhZdf1jZnWWfr1ji5y8uDVav8eNOmMHYszJjhI3ijRvkxEREREZFyUFqRoBDg7/8enn8eOnb0bRcmTUo6KrngQoAPP8xM8Nat87aWLX1a5r33+odh+HAf1RMRERERqQAlfAnZvRs+9zn47W/h+uvhhz+EDh2SjkouiBBgzZo4ucvPh02bvK1dO5/DO22aXw8ZouFdEREREakyOrNMwDvvwF13edL37W/DY49pG7Q6paQEVq7MTPB27PC2zp195G76dJ+iefnlUK9esvGKiIiISJ2lhK8aFRXBl74EX/4y9OkD//mfMPT/tXfvsXlXdRzH31862BiTjGUisgvD0KiDZCAN4z4DQhCNMxAQyMhiTMYfIBNIzCASAwkCiYgkgATmFJDLFiRIhDgHGMotG+MSbkXusgLCCAhFwN2+/nGK3UgR2PY8p/3t/UqW9vm16fPJetL285zzO2ev2qm0ydasKZuqfFTu7rkH3nqrfGzSJDjssIFDzjs7bfeSJElqGwtfm6xYASecUHbWnz0bLr0UxoypnUobZdUqWL58YAbvvvugr698bLfdylkaM2aUkjdlStWokiRJ2rJZ+NrgllvK/XqrV8O118KsWbUT6XP54ANYunSg4D3wQLkGMHVqWZ87Y0a5B2/ChLpZJUmSpPVY+Froww/hjDPg8svLZos33FBW9GmIe+89uP/+gSWay5aVWb0ImDYN5swps3cHHVS2V5UkSZKGKAtfi/T0lLP1HnsMTj8dzj/f3fWHrLffLmttu7vLv4cegrVroaMDurpg7txS8A48EMaOrZ1WkiRJ+swsfJtZJixYAKeeCqNHw223wZFH1k6lDaxcOVDu7r67tPLM0sinT4d588oSzf3280ZLSZIkDWsWvs3onXfgpJNg4UI45JByv97OO9dOJV55ZcMjEnp6yvVtt4X994dzzikzeNOnw6hRdbNKkiRJm5GFbzNZtqws4Xz5ZTjvvHLMWkdH7VRboEx46aUNC97zz5ePbb99WZY5e3YpeHvv7TpbSZIkNZqFbxOtWwcXXQRnnVVm87q7y6SR2iQTnnlmoNx1d5czMADGjSvF7uSTyxLNadNs4ZIkSdqiWPg2weuvl8mixYvh6KPhqqtghx1qp2q4devgiScGyl13d/lGAOy0Uyl48+aVt1OnwlZb1c0rSZIkVWTh20hLlsCJJ5b79q64ouzUH1E7VQOtWQOPPjqwRPOee8qumgCTJ8Phh5dyN2NGOfTcb4IkSZL0Pxa+z2n1ajj7bLjwwjKBdMcdsMcetVM1yKpVsHz5wBLN++6Dvr7ysc5OOOqogYK3yy51s0qSJElDnIXvc3jxRTj+eFi6tMzoXXxxOXpBm+CDD8p/6EcF74EHyjWA3XeHWbNKuTvoILc8lSRJkj6nlhW+iDgCuAToAOZn5gWteq52WLhwYNnmokVwzDG1Ew1TfX1w//0DSzSXLSvTphGw557lXIuDDy4Fb/z42mklSZKkYa0lhS8iOoDLgMOAXuDBiLg1M59qxfO10vvvw9y5MH9+OYf7+uthypTaqYaRt9+Ge+8dKHgPPwxr18KIEdDVBaedVgreAQfA2LG100qSJEmN0qoZvn2A5zLzBYCIuBGYCQyrwvf4NY/wg5918nTvdpx57AucM+tZtu5J6KmdbIh7991y7113Nzz2WDk6YeTIcrD5mWeWJZr77gtjxtROKkmSJDVaqwrfBGDFeo97genrf0JEzAHmAEyePLlFMTbe2rVw9Jxx9P2njyXM5NBFd8Gi2qmGkdGjy4GE555bZvD22QdGjaqdSpIkSdqitKrwDbY3fm7wIPNK4EqArq6uHOTzq+rogIXXrGLCF95kx3G/qB1neBk5smy4svXWtZNIkiRJW7RWFb5eYNJ6jycCr7bouVpmr2M7a0eQJEmSpI22VYu+7oNAZ0TsGhHbAMcBt7bouSRJkiRJg2jJDF9mromIU4DFlGMZFmTmk614LkmSJEnS4Fp2Dl9m3g7c3qqvL0mSJEn6/1q1pFOSJEmSVJmFT5IkSZIaysInSZIkSQ1l4ZMkSZKkhrLwSZIkSVJDWfgkSZIkqaEiM2tnICJWAv+oneMTjAferB1CWwTHmtrFsaZ2caypXRxrapehPNZ2ycwvfvzikCh8Q1lELM/Mrto51HyONbWLY03t4lhTuzjW1C7Dcay5pFOSJEmSGsrCJ0mSJEkNZeH7dFfWDqAthmNN7eJYU7s41tQujjW1y7Aba97DJ0mSJEkN5QyfJEmSJDWUhe8TRMQREfH3iHguIubVzqNmiohJEfG3iOiJiCcjYm7tTGq2iOiIiEci4s+1s6i5ImJsRNwUEU/3/3zbr3YmNVNEnNb/+/OJiLghIkbVzqTmiIgFEfFGRDyx3rVxEbEkIp7tf7tDzYyfhYVvEBHRAVwGfBuYChwfEVPrplJDrQHOyMyvA/sCJzvW1GJzgZ7aIdR4lwB/ycyvAdNwzKkFImICcCrQlZl7AB3AcXVTqWF+DxzxsWvzgDszsxO4s//xkGbhG9w+wHOZ+UJmrgJuBGZWzqQGyszXMvPh/vf7KH8UTaibSk0VEROB7wDza2dRc0XE9sDBwG8BMnNVZv6rbio12Ahg24gYAYwGXq2cRw2Smd3AWx+7PBO4uv/9q4HvtzXURrDwDW4CsGK9x734R7haLCKmAHsBS+smUYP9GvgpsK52EDXaV4CVwO/6lw/Pj4jtaodS82TmK8AvgZeB14B3MvOvdVNpC/ClzHwNygv3wI6V83wqC9/gYpBrbmeqlomIMcAfgZ9k5ru186h5IuK7wBuZ+VDtLGq8EcA3gN9k5l7AvxkGS540/PTfOzUT2BXYGdguImbVTSUNPRa+wfUCk9Z7PBGXCKhFImJrStm7LjNvrp1HjXUA8L2IeImyTP2QiPhD3UhqqF6gNzM/Wq1wE6UASpvbt4AXM3NlZq4Gbgb2r5xJzfd6RHwZoP/tG5XzfCoL3+AeBDojYteI2IZyA/CtlTOpgSIiKPe59GTmr2rnUXNl5pmZOTEzp1B+pt2Vmb4Srs0uM/8JrIiIr/ZfOhR4qmIkNdfLwL4RMbr/9+mhuEGQWu9WYHb/+7OBP1XM8pmMqB1gKMrMNRFxCrCYsuPTgsx8snIsNdMBwInA4xHxaP+1szLz9oqZJGlT/Ri4rv9F0xeAH1bOowbKzKURcRPwMGXX60eAK+umUpNExA3AN4HxEdEL/By4AFgUET+ivOhwTL2En01kemuaJEmSJDWRSzolSZIkqaEsfJIkSZLUUBY+SZIkSWooC58kSZIkNZSFT5IkSZIaysInSZIkSQ1l4ZMkSZKkhrLwSZIkSVJD/RdOg0ynnRot2AAAAABJRU5ErkJggg==\n",
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"%matplotlib inline\n",
"import numpy as np\n",
"from matplotlib import pyplot as plt\n",
"from IPython.core.pylabtools import figsize\n",
"import networkx as nx\n",
"import pylab\n",
"figsize(12.5, 4)\n",
"#print (toPlot['R'],toPlot['B'])\n",
"p = np.linspace(0, nbIterations, nbIterations+1)\n",
"plt.plot(p, toPlot['R'], color='red')\n",
"plt.plot(p, toPlot['B'], color = 'blue')\n",
"legende = \"Gains cumulés des joueurs R (\" + strategie['R'] + \") et B (\" + strategie['B']+\")\"\n",
"plt.suptitle(legende, y=1.02, fontsize=15)\n",
"plt.tight_layout()\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> En 1980, Robert Axelrod propose d'organiser des confrontations de stratégies lors d'un tournoi https://en.wikipedia.org/wiki/The_Evolution_of_Cooperation. \n",
"C'est à cette occasion que la stratégie tit-fot-tat est proposée, par Anatol Rapoport. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Comment évaluer la qualité des stratégies proposées? \n",
"Il faut définir précisément ce que l'on veut dire par *meilleure stratégie*. \n",
"On peut penser au moins à deux définitions: \n",
"* une stratégie qui bat toutes (ou le maximum) d'autres stratégies lors des matchs un contre un\n",
"* une stratégie qui obtient un gain cumulé après tous les matchs le plus élevé possible. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Si l'objectif est simplement de battre les autres stratégies, alors la stratégie *toujours trahir* est la meilleure. Mais si l'objectif est de maximiser le gain sur l'ensemble des rencontres, alors les choses sont moins claires...\n",
"En pratique, Tit-for-tat s'avère être une excellente stratégie. Pourtant elle est clairement battue par une stratégie de trahison constante, par exemple. Mais elle obtient de très bons scores contre toutes les stratégies. \n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Pour aller plus loin sur sur le dilemme du prisonnier itéré: \n",
"> * le site et les travaux de B. Beaufils, J.-P. Delahaye et Ph. Mathieu à l'Université de Lille. http://www.lifl.fr/IPD/ipd.html\n",
"* un module Python [axelrod](https://axelrod.readthedocs.io/en/stable/) permettant de rejouer les tournois d'Axelrod, avec plus de 200 stratégies pré-codées.\n",
"* et voir aussi la magnifique *explorable explanation* [The Evolution of Trust](http://ncase.me/trust/), par Nicky Case. \n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Les stratégies stochastiques"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"De manière générale, une stratégie stochastique à mémoire 1 coup est une stratégie qui donne la probabilité de joueur *c* au coup suivant, selon les coups joués par les joueurs au tour précédent: \n",
"\n",
"$ P = \\{Pcc,Pct,Ptc,Ptt \\}$\n",
"\n",
"Comment modéliser le tit-for-tat? \n",
"\n",
"A quoi correspond une stratégie $P = (1,0,0,1)$\n",
"\n",
"### Les ZD-stratégies\n",
"\n",
"En 2012, Press et Dyson ont publié un article qui a fait sensation dans le domaine. \n",
"Ils définissent une famille paramétrique de stratégies stochastiques, où les probabilités sont liées selon les équations suivantes (pour le cas où les gains sont 5/3/1): \n",
"\n",
"$$ Pcc = 3a + 3b + c$$\n",
"$$ Pct = 1 - 5b + c$$\n",
"$$ Ptc = 5a + c$$\n",
"$$ Ptt = a + b + c$$\n",
"\n",
"De manière remarquable, lorsqu'une stratégie $ZD(a,b,c)$ joue contre une autre statégie quelconque $G_2$, leurs gains sont liés de manière linéaire $aG1 + bG2 + c= 0$. En particulier, si $a=0$ et $b \\not = 0$, le gain de G2 est fixe (-b/c)!\n",
"\n",
"Sur les statégies ZD, voir également l'article de J.-P. Delahaye [Le dilemme du prisonnier et l'illusion de l'extorsion](http://cristal.univ-lille.fr/~jdelahay/pls/242.pdf)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## II. Jouer séquentiellement"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Considérons à présent un deuxième jeu très classique: **le jeu de la poule mouillée** (*the game of chicken*) \n",
"\n",
"|R \\ B | sauter | rester |\n",
"|------|------|------|\n",
"| **sauter** | (5,5) | (2,7) |\n",
"| **rester** | (7,2) | (0,0) | "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Si l'on analyse ce jeu en tenant à présent compte de la séquence, c'est-à-dire du fait que un joueur jour après l'autre, que pouvons-nous en dire? "
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [],
"source": [
"#--- pour petits tests rapides ---#\n",
"\n",
"\n",
"# exemple Game of chicken\n",
"successeurs = {'init':['a-saute','a-reste'],'a-saute':['a-saute-b-saute','a-saute-b-reste'],'a-reste':['a-reste-b-saute','a-reste-b-reste']}\n",
"valeur = {'a-saute-b-saute':(5,5), 'a-reste-b-saute':(7,2), 'a-saute-b-reste':(2,7),'a-reste-b-reste':(0,0)}\n",
"\n",
"\n",
"def feuille(state): # les feuilles n'apparaissent pas comme clés dans mon dictionnaire successeurs\n",
" return state not in successeurs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 1. Induction à rebours et algorithme Minimax\n",
"\n",
"On représente le jeu comme un arbre, où chaque joueur joue alternativement à chaque niveau de profondeur. \n",
"L'analyse peut alors se faire à rebours: en remontant depuis les feuilles, on fait suppose que le joueur, confronté à plusieurs coups possibles, choisira celui qui lui procure *à ce stade-là* le meilleur gain. \n",
"Au niveau au-dessus on peut itérer ce même raisonnement, suppoant ce que fera le joueur suivant, et ainsi de suite jusqu'à la racine. C'est le principe de l'**induction à rebours**. "
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"étendu noeud a-saute\n",
"player: 0\n",
"étendu noeud a-saute-b-saute\n",
"player: 1\n",
"feuille: (5, 5)\n",
"étendu noeud a-saute-b-reste\n",
"player: 1\n",
"feuille: (2, 7)\n",
"étendu noeud a-reste\n",
"player: 0\n",
"étendu noeud a-reste-b-saute\n",
"player: 1\n",
"feuille: (7, 2)\n",
"étendu noeud a-reste-b-reste\n",
"player: 1\n",
"feuille: (0, 0)\n",
"(7, 2)\n"
]
}
],
"source": [
"from operator import itemgetter\n",
"\n",
"\n",
"def backward_induction(state,turn_taking):\n",
" \"\"\" implementation de backward induction, turn_taking: sequence of agents \n",
" \"\"\"\n",
" v = maxValue(state,0,turn_taking)\n",
" return v\n",
"\n",
"def maxValue(state,depth,turn_taking):\n",
" if feuille(state): # si feuille on renvoie la valeur\n",
" print(\"feuille:\", valeur[state])\n",
" return valeur[state]\n",
" \n",
" v = inf # joue le role de infini\n",
"\n",
" for s in successeurs[state]:\n",
" print (\"étendu noeud \", s)\n",
" player= turn_taking[depth]\n",
" print(\"player:\", player)\n",
" # on remonte le vecteur de score pour lequel la valeur est max pour le joueur player\n",
" v = max([v,maxValue(s,depth+1,turn_taking)],key=itemgetter(player))\n",
" return v\n",
"\n",
"#------------------\n",
"# test\n",
"#------------------\n",
"turn_taking=[0,1] # le joueur 0 jour, puis le joueur 1\n",
"inf = [-1000]*len(turn_taking) # joue le role de infini\n",
"print (backward_induction('init',turn_taking))\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Dans le cas où le jeu est un jeu à **somme nulle**, on peut se contenter de représenter la valeur au feuille de l'arbre par une valeur unique: un joueur cherche alors à minimiser le score tandis que l'autre cherche à le maximiser, on parle donc d'algorithme **minimax**. Notez qu'il s'agit d'un cas particulier d'induction à rebours. (Voir le code ci-dessous dans lequel les fonctions `minValue` et `maxValue` sont distinguées, par soucis de lisibilité). \n",
"\n",
"La valeur retournée par l'algorithme de recherche minimax est appelée **la valeur théorique du jeu**, qui serait obtenue sous l'hypothèse que les agents jouent rationnellement selon cet algorithme. \n"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"étendu noeud b\n",
"étendu noeud d\n",
"étendu noeud h\n",
"étendu noeud i\n",
"étendu noeud e\n",
"étendu noeud j\n",
"étendu noeud k\n",
"étendu noeud c\n",
"étendu noeud f\n",
"étendu noeud l\n",
"étendu noeud m\n",
"étendu noeud g\n",
"étendu noeud n\n",
"étendu noeud o\n",
"9\n"
]
}
],
"source": [
"def minimax(state):\n",
" \"\"\" implementation de minimax, version Russel & Norvig, Chapter 6\n",
" \"\"\"\n",
" v = maxValue(state)\n",
" return v\n",
"\n",
"def maxValue(state):\n",
" if feuille(state): # si feuille on renvoie la valeur\n",
" return valeur[state]\n",
" v = -inf\n",
" for s in successeurs[state]:\n",
" print (\"étendu noeud \", s)\n",
" v = max(v,minValue(s))\n",
" return v\n",
" \n",
"def minValue(state):\n",
" if feuille(state): # si feuille on renvoie la valeur\n",
" return valeur[state]\n",
" v = inf\n",
" for s in successeurs[state]:\n",
" print (\"étendu noeud \", s)\n",
" v = min(v,maxValue(s))\n",
" return v\n",
"\n",
"#------------------\n",
"# test\n",
"#------------------\n",
"\n",
"inf = 1000 # joue le role de infini\n",
"successeurs = {'a':['b','c'],'b':['d','e'],'c':['f','g'],'d':['h','i'],'e':['j','k'],'f':['l','m'],'g':['n','o']}\n",
"valeur = {'h':4, 'i':9, 'j': 8, 'k': 12, 'l':5, 'm':6, 'n':1, 'o':7}\n",
"print (minimax('a'))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 3. Elagage Alpha-beta (pruning)\n",
"\n",
"L'algorithme minimax étend l'intégralité des noeuds de l'arbre. Pour éviter cette exploration complète de l'arbre de jeu, on peut exploiter le fait que les joueurs sont des MINimisateurs et des MAXimisateurs. En chaque noeud, on va garder mémoire dans la recherche de deux valeurs, qui vont parfois permettre de couper certaines parties de l'arbre de recherche. \n",
"\n",
"* la valeur $\\alpha$ est une borne inf que la recherche maximise. C'est donc la valeur min que peut se garantir le joueur MAX. \n",
"* la valeur $\\beta$ est une borne sup que la recherche minimise. C'est donc la valeur max que peut se garantir le joueur MIN. \n",
"\n",
"Donc le joueur MAX met à jour les valeurs $\\alpha$, et le joueur MIN met à jour les valeur $\\beta$. \n",
"\n",
"Il y a donc deux types de coupes dans l'arbre de recherche qui peuvent survenir: \n",
"* une **coupe** $\\alpha$ survient lorsque, pour un noeud MIN, on a trouvé un noeud parmi les fils avec une valeur $\\leq \\alpha$\n",
"* une **coupe** $\\beta$ survient lorsque, pour un noeud MAX, on a trouvé un noeud parmi les fils avec une valeur $\\geq \\beta$\n",
"\n",
"Pour bien comprendre le principe de la coupe, il faut raisonner sur deux niveaux (MAX et MIN). Par exemple, pour une coupe $\\alpha$, si on trouve pour un noeud MIN une valeur $\\leq \\alpha$ cela signifie que MIN remontera une valeur $\\leq \\alpha$ (il minimise), quelque soient les valeurs des autres fils explorés. Or (au dessus) MAX a une garantie d'obtenir au moins $\\alpha$. Poursuivre l'exploration est donc superflu. \n"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"étendu noeud b\n",
"étendu noeud d\n",
"étendu noeud h\n",
"étendu noeud i\n",
"étendu noeud e\n",
"étendu noeud j\n",
"étendu noeud k\n",
"coupe beta\n",
"étendu noeud c\n",
"étendu noeud f\n",
"étendu noeud l\n",
"étendu noeud m\n",
"coupe alpha\n",
"9\n"
]
}
],
"source": [
"def alphabeta(state):\n",
" \"\"\" implementation de alphabeta, version Russel & Norvig, Chapter 6\n",
" \"\"\"\n",
" v = maxValue(state,-inf,inf)\n",
" return v\n",
"\n",
"def maxValue(state,alpha,beta):\n",
" if feuille(state): # si feuille on renvoie la valeur\n",
" return valeur[state]\n",
" v = -inf\n",
" for s in successeurs[state]:\n",
" print (\"étendu noeud \", s)\n",
" v = max(v,minValue(s,alpha,beta))\n",
" if v >= beta: # coupe beta, pas la peine d'étendre les autres fils\n",
" print (\"coupe beta\")\n",
" return v\n",
" alpha = max(alpha,v) # mise à jour de alpha par MAX\n",
" return v\n",
" \n",
"def minValue(state,alpha,beta):\n",
" if feuille(state): # si feuille on renvoie la valeur\n",
" return valeur[state]\n",
" v = inf\n",
" for s in successeurs[state]:\n",
" print (\"étendu noeud \", s)\n",
" v = min(v,maxValue(s,alpha,beta))\n",
" if v <= alpha: # coupe alpha, pas la peine d'étendre les autres fils\n",
" print (\"coupe alpha\")\n",
" return v\n",
" beta = min(beta,v)\n",
" return v\n",
"\n",
"#------------------\n",
"# test\n",
"#------------------\n",
"\n",
"inf = 1000 # joue le role de infini\n",
"successeurs = {'a':['b','c'],'b':['d','e'],'c':['f','g'],'d':['h','i'],'e':['j','k'],'f':['l','m'],'g':['n','o']}\n",
"valeur = {'h':4, 'i':9, 'j': 8, 'k': 12, 'l':5, 'm':6, 'n':1, 'o':7}\n",
"\n",
"print (alphabeta('a'))\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Pour aller plus loin"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Limites des concepts de solution proposés"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On observe souvent que les humains ne se comportent pas de la manière prescrite par les solutions de théorie des jeux. \n",
"En particulier, de nombreux jeux reposent sur une notion de **confiance réciproque** qui peut amener à des solutions plus favorables pour tout le monde. \n",
"Un des plus connu est le **Trust Game**: un agent, doté d'un budget $B$, a le choix entre donner un certaine somme à un autre agent et ne rien donner. S'il donne une somme $x$ à l'agent 2, cette somme est triplée et l'agent 2 a alors le choix entre ne rien donner, ou donner une somme en retour à l'agent 1. \n",
"Par induction à rebours, l'agent 1 ne doit rien donner initialement, car il n'y a aucune incitation pour l'agent 2 a lui rendre de l'argent... \n",
"Toutefois les expériences avec des sujets humains contredisent ces prédictions. \n",
"\n",
"Des travaux tentent donc de capturer ces notions de confiance réciproque. \n",
"Intuitivement, si l'on considère le jeu séquentiel suivant: \n",
"* 1: jouer A: (2,0)\n",
"* 1: jouer B: \n",
" * 2: jouer C: (0,2)\n",
" * 2: jouer D: (2,1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Dans ce cas-là, le raisonnement suivant est possible: si le joueur 2 observe que 1 n'a pas joué A qui lui aurait garanti un gain de 2, par réciprocité le joueur 2 doit offrir au moins au moins autant à l'agent 1. Sur cette exemple, l'agent 2 devrait donc jouer D selon ce principe. Mais ce principe peut être itéré, ce qui amène à des nouveaux concepts de solutions. \n",
"\n",
"> Pour aller plus loin: Joshua Letchford, Vincent Conitzer, and Kamal Jain. An \"Ethical\" Game-Theoretic Solution Concept for Two-Player Perfect-Information Games. In Proceedings of the Fourth Workshop on Internet and Network Economics (WINE-08), pp. 696-707, Shanghai, China, 2008"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Récréation finale: l'exemple du jeu de Hex\n",
"\n",
"Le jeu de Hex est un jeu combinatoire dont les règles s'expriment très simplement, mais qui est d'une grande richesse. Les règles sont les suivantes: \n",
"* chaque joueur peut poser à son tour une tuile n'importe où sur le terrain\n",
"* le joueur qui parvient à relier ses deux bordures (de même couleur) est le gagnant\n",
"\n",
"\n",
"\n",
"Ce jeu possède quelques propriétés remarquables:\n",
"* les matchs nuls ne peuvent pas se produire\n",
"* tout joueur jouant en premier dispose d'une **stratégie gagnante** (il peut donc gagner quelque soit les coups joués par les autres). \n",
"\n",
"Toutefois ces stratégies gagnantes ne sont connues que pour les petites tailles de parties (jusqu'à 7x7 à ma connaissance). \n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> Version du 10 Mars 2021. Style *no$\\TeX$book* [(voir ici)](https://pypi.org/project/notexbook-theme/).\n",
"En cas de problème d'affichage, ouvrir l'URL dans le nbviewer.jupyter.org/\n",
"Pour profiter pleinement du notebook et pouvoir tester de manière interactive, vous devez l'ouvrir par `jupyter notebook`"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"anaconda-cloud": {},
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.4"
}
},
"nbformat": 4,
"nbformat_minor": 1
}