ࡱ > m o j k l a )s jbjbtt k c $ $ $ $ $ $ $ D 0 X X X t L t 0 o ̃ ̃ | H H H H H H ΰ а а а а а а , R Y - $ H H H H H $ $ H H ) H V $ H $ H ΰ h L $ $ $ $ H ΰ $ $ X D ? 0 o $ 0 0 t { d 0 0 { UNIVERSIT DE PARIS X NANTERRE UFR DE SCIENCES CONOMIQUES COLE DOCTORALE DIPLME DTUDES APPROFONDIES LABORATION DUN AUTOMATE CELLULAIRE ET APPLICATION AU DILEMME DU PRISONNIER par Monsieur Tristan BOYER. Sminaire de recherche mineur Dynamiques collectives et volution des conventions sous la direction de Monsieur le Professeur Andr ORLAN. SESSION DE SEPTEMBRE 1994 LUniversit de Paris X Nanterre nentend donner aucune approbation ou improbation aux opinions mises dans les mmoires : ces opinions doivent tre considres comme propres leur auteur. Le dilemme du prisonnier est un des cas classiques tudis par la thorie des jeux. Il a alors pour objet de montrer que la rationalit classique des agents, fonde sur les hypothses dune capacit de calcul illimite et dune maximisation des gains individuels sous la contrainte de la matrice des gains du jeux, ne permet pas lmergence dune solution optimale au sens de Pareto. En prenant en compte une notion temporelle dans la thorie des jeux, on parvient, par lintroduction de comportements individuels stratgiques, concevoir des interactions qui permettent lmergence de solutions plus favorables lensemble des participants au jeu. Lorsque lhorizon du jeu est indtermin ou infini on accde encore plus facilement ces solutions. Toutefois, on observe toujours la victoire sans partage dun comportement, que nous appellerons convention sans quil y ait l de prsupposs relatifs la dfinition donne par D.Lewis. Une convention est ici plutt un choix qui peut tre fait par plusieurs personnes. STRUCTURE DU DILEMME DU PRISONNIER: CooprationDfectionCoopration(R,R)(S,T)Dfection(T,S)(P,P) Avec S
5P+3T lorsque lon a comme ici huit voisins. Dans le cas o la seconde condition du raisonnement conduisant la dcision de lindividu est abandonne (celle relative au fait que le meilleur et le plus mauvais ont adopt le mme comportement), les rsultats ne sont pas radicalement diffrents. La seule diffrence notable entre les consquences dune prise de dcision concerne les proportions finales dindividus coopratifs et dfectionnistes. Dans le dernier cas, la proportion de dfectionnistes oscille in fine entre 4 et 12%. On peut noter lapparition dun phnomne que lon navait pas peru dans le premier cas, cest celui du dplacement de lignes ou franges de dfectionnistes selon un rythme comparable celui du clignotement dj observ lorsque les deux conditions de dcision taient appliques ensemble. On observe bien entendu les mmes phnomnes que prcdemment sur certains cas particuliers. De mme, il ny a pas de changement pour les cas de damier ou dalternance de lignes ou encore pour celui ou la dfection gagne. EXEMPLES DANS LESQUELS LA MATRICE DE PAYOFF PEUT PROVOQUER LE STATU QUO La matrice de payoff est ici la prsentation la plus courante du dilemme du prisonnier: CooprationDfectionCoopration(3,3)(1,4)Dfection(4,1)(2,2) Les rsultats obtenus ici diffrent trs nettement des prcdents. Parmi les deux cents tirages effectus au hasard selon le mme schma que dans les exemples prcdents, aucun na conduit un autre rsultat que la victoire sans partage de la dfection. Lapplication de la rgle dindcision voque plus haut ou son inapplication ne change rien aux rsultats obtenus. Les rsultats peuvent savrer stables et autorisant le polymorphisme dans le cas o le terrain est dj rempli de joueurs. Ces rsultats montrent encore une fois limportance du placement des individus sur le terrain. Alors que dans le cas prcdent, un noyau de 2x2 tait suffisant pour assurer la prennit et mme le dveloppement et la conqute de la coopration, il faut ici un noyau minimal de 3x3 afin de ne pas tre absorb par le comportement dfectionniste. La structure des amas, le positionnement des individus, est donc la clef du dveloppement dun comportement. Toutefois, on ne peut rduire le dveloppement dune convention ce seul positionnement: le poids de cet amas est aussi un facteur essentiel de lextension dun comportement travers une population. Toutefois, cette extension ou cohabitation dans une mme population de deux conventions, peut tre rendue impossible. Si, dans le cas prsent, un changement de convention en faveur de la coopration est impossible, son maintien reste envisageable. EXEMPLES DANS LESQUELS LA MATRICE DE PAYOFF CONDUIT A LA VICTOIRE DE LA DEFECTION La matrice de payoff est ici: CooprationDfectionCoopration(21,21)(10,30)Dfection(30,10)(20,20) Cette matrice empche la coopration dexister sur le terrain de lautomate. En effet, le score maximal possible pour un individu qui coopre est de 8x21=168 et celui dun dfectionniste qui pourrait entrer en comparaison avec lui est de 5x20+3x30=190. Dans cette configuration, et quelle que soit la rgle de dcision choisie parmi les deux que nous proposons, la dfection gagne sans partage. LISTING DU PROGRAMME program AutomCell; uses moteur; var jx, nbo, nbd, nbc, conti: integer; procedure saisieAuto; begin matj[0, 2] := 1; matj[0, 0] := 0; matj[0, 1] := 1; matj[2, 0] := 0; matj[1, 0] := 0; matj[2, 2] := 21; matj[2, 1] := 10; matj[1, 2] := 30; matj[1, 1] := 20; spa := 1; schAB := 4; schBA := 4; end; procedure pourcentage; var i, j: integer; begin nbc := 0; nbd := 0; nbo := 0; for i := 1 to maxtab do for j := 1 to maxtab do begin if mat1[i, j] = 2 then nbc := nbc + 1 else if mat1[i, j] = 1 then nbd := nbd + 1 else nbo := nbo + 1; end; end; procedure nettoyage; var r: rect; begin showdrawing; setRect(r, 5, 5, 1600, 1600); forecolor(whitecolor); fillrect(r, black); end; procedure attente; var theEvent: EventRecord; begin FlushEvents(everyEvent, 0); repeat with theEvent do if GetNextEvent(everyEvent, theEvent) then begin case what of keyDown: begin note(1000, 100, 4); end; mouseDown: begin Exit(attente); end; otherwise end; end; systemTask; until false; end; procedure saisieMan; var ch: string; i, j: integer; begin showtext; writeln('ligne', i, ' ', '**********'); for i := 1 to maxtab do begin write('ligne', i, ' '); readln(ch); for j := 1 to maxtab do begin if ch[j] = '0' then mat1[i, j] := 0; if ch[j] = '1' then mat1[i, j] := 1; if ch[j] = '2' then mat1[i, j] := 2; end; end; end; procedure terraform; var i, j: integer; begin for i := 1 to maxtab do begin mat1[i, 0] := mat1[i, maxtab]; mat1[i, maxtabmax] := mat1[i, 1]; end; for j := 1 to maxtab do begin mat1[0, j] := mat1[maxtab, j]; mat1[maxtabmax, j] := mat1[1, j]; end; mat1[0, 0] := mat1[maxtab, maxtab]; mat1[maxtabmax, maxtabmax] := mat1[1, 1]; mat1[0, maxtabmax] := mat1[maxtab, 1]; mat1[maxtabmax, 0] := mat1[1, maxtab]; end; procedure initialisation; var i, j: integer; begin for i := 0 to maxtab + 1 do for j := 0 to maxtab + 1 do begin mat1[i, j] := 0; mat2[i, j] := 0; matutil[i, j] := 0; end; end; procedure hasard; var i, j, y, z: integer; x: extended; begin for i := 1 to maxtab do for j := 1 to maxtab do begin x := random; if x < random then z := 2 else z := 1; x := random; if x > random then y := 1 else y := 1; mat1[i, j] := z * y; mat2[i, j] := y * z; end; end; procedure pourdessin; var r: rect; begin showdrawing; textfont(monaco); textsize(9); end; procedure dessin; const cote = 10; var colonne, ligne, i, j: integer; r: rect; begin showpen; {dessin du terrain} ligne := trunc(coups / 4); colonne := (coups - (4 * ligne)); for i := 1 to maxtab do begin for j := 1 to maxtab do begin forecolor(blackcolor); moveto(j * cote + cote * colonne * 12, 15 * ligne + 140 + i * cote + ligne * cote * 12 + cote * (jx - 1) * 12); line(0, cote); line(cote, 0); line(0, -cote); line(-cote, 0); end; end; {dessin d'un coup} for i := 1 to maxtab do begin for j := 1 to maxtab do begin moveto(10 + cote * colonne * 12, 15 * ligne + 15 + 130 + ligne * cote * 12 + cote * (jx - 1) * 12); forecolor(blackcolor); writedraw('priode', coups); penmode(patcopy); pensize(1, 1); setrect(r, 1, 1, cote - 1, cote - 1); offsetrect(r, j * cote + 1 + cote * colonne * 12, 15 * ligne + 140 + i * cote + ligne * cote * 12 + 1 + cote * (jx - 1) * 12); if mat1[i, j] = a then begin forecolor(redcolor); fillrect(r, black); end; if mat1[i, j] = b then begin forecolor(bluecolor); fillrect(r, gray); end; if mat1[i, j] = c then begin forecolor(blackcolor); fillrect(r, white); end; end; end; delay(0, long); moveto(10 + cote * colonne * 12, 15 * ligne + 15 + 130 + ligne * cote * 12 + cote * (jx - 1) * 12); forecolor(blackcolor); writedraw('priode', coups); moveto(cote * colonne * 12 - 25, 15 * ligne + (i + 1) * cote + 15 + 130 + ligne * cote * 12 + cote * (jx - 1) * 12); writedraw(nbc, '%c'); moveto(cote * colonne * 12 + 5, 15 * ligne + (i + 1) * cote + 15 + 130 + ligne * cote * 12 + cote * (jx - 1) * 12); writedraw(nbd, '%d'); moveto(cote * colonne * 12 + 35, 15 * ligne + (i + 1) * cote + 15 + 130 + ligne * cote * 12 + cote * (jx - 1) * 12); writedraw(nbo, '%'); end; procedure ecriture2; var i, j: integer; begin for i := 1 to maxtab do b e g i n f o r j : = 1 t o m a x t a b d o b e g i n i f m a t 1 [ i , j ] = a t h e n w r i t e ( ' " ' ) ; i f m a t 1 [ i , j ] = b t h e n w r i t e ( ' %' ) ; if mat1[i, j] = c then write(''); end; writeln; end; end; procedure testFin; var i, j: integer; begin fin := 0; for i := 1 to maxtab do for j := 1 to maxtab do begin x := mat1[i, j] - mat2[i, j]; if x = 0 then fin := fin else fin := fin + 1; end; end; procedure transfert1_2; var i, j: integer; begin for i := 1 to maxtab do for j := 1 to maxtab do mat1[i, j] := mat2[i, j]; for i := 1 to maxtab do begin mat1[i, 0] := mat2[i, maxtab]; mat1[i, maxtabmax] := mat2[i, 1]; end; for j := 1 to maxtab do begin mat1[0, j] := mat2[maxtab, j]; mat1[maxtabmax, j] := mat2[1, j]; end; mat1[0, 0] := mat2[maxtab, maxtab]; mat1[maxtabmax, maxtabmax] := mat2[1, 1]; mat1[0, maxtabmax] := mat2[maxtab, 1]; mat1[maxtabmax, 0] := mat2[1, maxtab]; end; procedure roule; var i, j: integer; begin ecriture2; nbc := 0; nbd := 0; nbo := 0; for i := 1 to maxtab do for j := 1 to maxtab do begin if mat1[i, j] = 2 then nbc := nbc + 1 else if mat1[i, j] = 1 then nbd := nbd + 1 else nbo := nbo + 1; end; writeln; writeln('periode', coups, '.'); writeln('C=', nbc, ' D=', nbd, ' =', nbo); calcUtil; transfertUtil; decision; testFin; transfert1_2; end; procedure rouledessin; begin dessin; calcUtil; transfertUtil; decision; testFin; transfert1_2; pourcentage; end; procedure pgmtexte; var j: integer; begin showtext; for j := 1 to 7 do begin initialisation; coups := 0; fin := 1; saisieAuto; hasard; repeat begin coups := coups + 1; roule; end; until coups >= 12; ecriture2; writeln('***********'); end; end; begin begin showtext; pourdessin; conti := 1; repeat begin initialisation; coups := 0; fin := 1; saisieAuto; saisieMan; {ou hasard} pourcentage; terraform; nettoyage; repeat begin coups := coups + 1; rouledessin; if coups >= 12 then fin := 0; end; until fin = 0; dessin; note(1000, 100, 4); writeln('stop:0 encore:1 ret'); readln(conti); attente; end; until conti = 0; end; end. unit moteur; interface const maxtab = 10; maxtabmax = 11; a = 1; b = 2; c = 0; type matrice = array[0..maxtabmax, 0..maxtabmax] of integer; matjeu = array[0..2, 0..2] of integer; var long: longint; i, j, x, schAB, schBA, spa, fin, coups, xx: integer; mat1, mat2, matutil: matrice; matj: matjeu; procedure calcUtil; procedure transfertUtil; procedure decision; implementation procedure calcUtil; var i, j, n, m, xa, xb, xc: integer; begin for i := 1 to maxtab do for j := 1 to maxtab do begin x := 0; xa := 0; xb := 0; xc := 0; for n := i - 1 to i + 1 do for m := j - 1 to j + 1 do begin if mat1[n, m] = a then xa := xa + 1 else if mat1[n, m] = b then xb := xb + 1 else if mat1[n, m] = c then xc := xc + 1 else end; x := xa * matj[mat1[i, j], a] + xb * matj[mat1[i, j], b] + xc * matj[mat1[i, j], c] - matj[mat1[i, j], mat1[i, j]]; matutil[i, j] := x; end; end; procedure transfertUtil; var i, j: integer; begin for i := 1 to maxtab do begin matutil[i, 0] := matutil[i, maxtab]; matutil[i, maxtabmax] := matutil[i, 1]; end; for j := 1 to maxtab do begin matutil[0, j] := matutil[maxtab, j]; matutil[maxtabmax, j] := matutil[1, j]; end; matutil[0, 0] := matutil[maxtab, maxtab]; matutil[maxtabmax, maxtabmax] := matutil[1, 1]; matutil[0, maxtabmax] := matutil[maxtab, 1]; matutil[maxtabmax, 0] := matutil[1, maxtab]; end; procedure decision; var i, j, n, m, min, max, decmin, decmax: integer; begin for i := 1 to maxtab do for j := 1 to maxtab do begin max := matutil[i, j]; min := matutil[i, j]; decmax := mat1[i, j]; decmin := mat1[i, j]; for n := i - 1 to i + 1 do for m := j - 1 to j + 1 do begin if max < matutil[n, m] then begin max := matutil[n, m]; decmax := mat1[n, m]; end; if min > matutil[n, m] then begin min := matutil[n, m]; decmin := mat1[n, m]; end; end; if decmax = decmin then mat2[i, j] := mat1[i, j] else mat2[i, j] := decmax; end; end; end. PAGE PAGE 1 PAGE PAGE 6 PAGE PAGE 27 PAGE PAGE 32 Z [ q % & J K o p ( ) M N t u K q" r" s" t" u" v" w" x" z" ƻƻƻƻƻƻƻƻƻƻƻƻ㡝㎝ j9 h" h" OJ QJ Uj3 h" h" OJ QJ Uh" j6, h" h" OJ QJ Uh" 5>*OJ QJ h" 5EHOJ QJ h" 5EHOJ QJ h" >*OJ QJ h" OJ QJ o(h" OJ QJ h" 5OJ QJ o( h" 5OJ QJ 0 ; K o t > x y b c e f U1$ ]Ugd" $Udh 1$ ]Ua$gd" 2 $Udh $d %d &d 'd 1$ N O P Q ]Ua$gd" $Udh 1$ ]Ua$gd" $Udh 1$ ]Ua$gd" r (s f g h i j k l m n p q $ $&. / 1$ If ] a$gd" $U1$ ]Ugd" U1$ ]Ugd" $ $&. / 1$ If ] a$gd" _ kd $$If T P 4F U 4 P a f4T $ $&. / 1$ If ] a$gd" _ kd $$If T P 4F U 4 P a f4T $U1$ ]Ugd" U1$ ]Ugd" _ kd $$If T P 4F U 4 P a f4T # % Ff $$ $ $. / 1$ If ] a$gd" % & ) , / 2 5 8 ; > A D G J K N Q T W Z ] ` c f i l FfJ $$ $ $. / 1$ If ] a$gd" Ff l o p s v y | Ff Ff $$ $ $. / 1$ If ] a$gd" FfJ Ff $$ $ $. / 1$ If ] a$gd" " % ( ) , / 2 5 8 ; > A Ff Ff $$ $ $. / 1$ If ] a$gd" A D G J M N R U X [ ^ a d g j m q t u x z | ~ Ff$ Ff ! $$ $ $. / 1$ If ] a$gd" ? @ K L M m $$U1$ ]Ua$gd" U1$ ]Ugd" $U1$ ]Ugd" Ff' $$ $ $. / 1$ If ] a$gd" m n o { v _ kd) $$If T P 4F U 4 P a f4T $ $ $. / 1$ If ] a$gd" $U1$ ]Ugd" $ $ $. / 1$ If ] a$gd" _ kd* $$If T P 4F U 4 P a f4T y z ! ! p" q" s" t" v" w" y" z" |" U1$ ]Ugd" U1$ ]Ugd" _ kdh+ $$If T P 4F U 4 P a f4T z" {" }" ~" " " " " # # # # # # $ $ $ $ $ $ $ $ $ $ % % % % % % "% շը{l] jum h" h" OJ QJ Uj\j h" h" OJ QJ Ujg h" h" OJ QJ Uje h" h" OJ QJ Uja h" h" OJ QJ UjY h" h" OJ QJ UjQ h" h" OJ QJ Uj%L h" h" OJ QJ Uh" OJ QJ jF h" h" OJ QJ Uh" j? h" h" OJ QJ U |" }" " " " " # # # # # # $ $ $ $ $ $ $ $ $ $ % % % !% $% %% U1$ ]Ugd" U1$ ]Ugd" "% #% %% &% '% , , - - - - - - - - - - - - - - - . . / / / / / / / ծ՟ՐxiZ jD h" h" OJ QJ Uj h" h" OJ QJ Uh" 6OJ QJ j, h" h" OJ QJ Uj h" h" OJ QJ Uj h" h" OJ QJ Uj~ h" h" OJ QJ Ujw h" h" OJ QJ Uh" >*OJ QJ h" OJ QJ js h" h" OJ QJ Uh" jVq h" h" OJ QJ U %% '% (% ) ) + + , , , - - - - - - - - - - - - / / / / $U1$ ]Ua$gd" U1$ ]Ugd" U1$ ]Ugd" / / / / / ]0 ^0 `0 b0 c0 0 0 0 0 31 41 51 1 1 1 1 $ $ $. / 1$ If ] a$gd" $U1$ ]Ugd" $$U1$ ]Ua$gd" U1$ ]Ugd" U1$ ]Ugd" / / / ^0 _0 `0 a0 b0 0 )1 31 N3 O3 P3 Q3 R3 S3 T3 U3 V3 W3 X3 Y3 Z3 3 3 3 3 3 3 3 仯sdU j h" h" OJ QJ Uj7 h" h" OJ QJ Uj- h" h" OJ QJ Uj h" h" OJ QJ Ujt h" h" OJ QJ Uj h" h" OJ QJ Uh" 56>*OJ QJ h" 5>*OJ QJ jj h" h" OJ QJ Uj( h" h" OJ QJ Uh" OJ QJ h" j h" h" OJ QJ U 1 1 1 1 1 1 _ kdH $$If T P 4F U 4 P a f4T $ $ $. / 1$ If ] a$gd" 1 1 1 1 1 $ $ $. / 1$ If ] a$gd" _ kd $$If T P 4F U 4 P a f4T 1 1 1 N3 O3 Q3 R3 T3 U3 W3 X3 Z3 3 3 3 3 3 U1$ ]Ugd" U1$ ]Ugd" _ kd $$If T P 4F U 4 P a f4T 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 7 7 7 9 9 9 9 9 9 9 9 9 䯠zk\ j h" h" OJ QJ UjN h" h" OJ QJ Uh" 56>*OJ QJ h" 5>*OJ QJ j h" h" OJ QJ Uj h" h" OJ QJ Uh" OJ QJ j/ h" h" OJ QJ Ujf h" h" OJ QJ Ujn h" h" OJ QJ Uh" OJ QJ h" jP h" h" OJ QJ U !3 3 3 3 3 3 3 3 3 3 3 3 3 3 7 7 7 7 7 7 7 7 7 $U1$ ]Ugd" $$U1$ ]Ua$gd" U1$ ]Ugd" U1$ ]Ugd" 7 8 8 8 8 #8 +8 38 _ kd $$If T P 4F U 4 P a f4T $$&. / 1$ If ]a$gd" 38 48 >8 F8 N8 $$&. / 1$ If ]a$gd" _ kd $$If T P 4F U 4 P a f4T N8 O8 P8 Q8 9 9 9 9 9 9 9 9 9 9 9 9 9 U1$ ]Ugd" U1$ ]Ugd" _ kd $$If T P 4F U 4 P a f4T 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 : : : !: 2: 6: K: N: : : : : ; ; ; ; ; ; <