tutorial

Description

LIP Research Report RR2006-51 (version 3)CP games: a tutorial∗Pierre LescanneUniversit´e de Lyon, Ecole Normale Sup´erieure de Lyon,LIP, 43 all´ee d’Italie, F69364 Lyon, FranceAugust 22, 2007AbstractIn this tutorial we introduce the concept of CP-game which is ageneralization of this of strategic game. First we present exampleswhich are relevant to a CP-game approach. Then we give a somewhatnaive introduction to CP-games. Then we present the connectionbetween CP games and gene regulation networks.Contents1 Introduction 22 Basic concepts 23 Some examples 33.1 A simple game on a square . . . . . . . . . . . . . . . . . . . . 33.1.1 A first version . . . . . . . . . . . . . . . . . . . . . . . 43.1.2 A second version . . . . . . . . . . . . . . . . . . . . . 63.1.3 A third version . . . . . . . . . . . . . . . . . . . . . . 63.2 Strategic games . . . . . . . . . . . . . . . . . . . . . . . . . . 63.2.1 The Prisoner’s Dilemma . . . . . . . . . . . . . . . . . 6∗Email: [e-mail]13.2.2 Matching Pennies . . . . . . . . . . . . . . . . . . . . . 83.2.3 Scissors, paper, stone . . . . . . . . . . . . . . . . . . . 83.2.4 Strategic games as CP games . . . . . . . . . . . . . . 103.3 Blink or you loose . . . . . . . . . . . . . . . . . . . . . . . . . 103.3.1 A first tactic: Foresight . . . . . . . . . . . . . . . . . . 103.3.2 A second tactic: Hindsight . . . . . . . . . . . . . . . . 113.3.3 A third tactic: Omnisight . . . . . . . . . ...

Informations

• Publié par: Vewyig
• Nombre de lectures: 56
• Langue: English

Extrait

LIPResearchReportRR2006-51 (version3) CPgames:atutorial PierreLescanne ∗ Universite´deLyon,EcoleNormaleSupe´rieuredeLyon, LIP,43alle´ed’Italie,F69364Lyon,France August22,2007 Abstract InthistutorialweintroducetheconceptofCP-gamewhichisa generalizationofthisofstrategicgame.Firstwepresentexamples whicharerelevanttoaCP-gameapproach.Thenwegiveasomewhat naiveintroductiontoCP-games.Thenwepresenttheconnection betweenCPgamesandgeneregulationnetworks. Contents 1Introduction 2Basicconcepts 3Someexamples 3.1Asimplegameonasquare.................... 3.1.1Afirstversion....................... 3.1.2Asecondversion..................... 3.1.3Athirdversion...................... 3.2Strategicgames.......................... 3.2.1ThePrisoner’sDilemma................. ∗ Email: [e-mail] 1 2 2 3 3 4 6 6 6 6

3.2.2MatchingPennies.....................8 3.2.3Scissors,paper,stone...................8 3.2.4StrategicgamesasCPgames..............10 3.3Blinkoryouloose.........................10 3.3.1Afirsttactic:Foresight..................10 3.3.2Asecondtactic:Hindsight................11 3.3.3Athirdtactic:Omnisight................11 3.4TheλphageasaCPgame....................11 4PresentationofC/Pgames14 4.1Singletonequilibrium.......................14 4.2Dynamicequilibrium.......................15 4.2.1Stronglyconnectedcomponents.............16 4.2.2Dynamicequilibriaasstronglyconnectedcomponents.17 5GeneregulationnetworksasC/Pgames 6Conversionorpreference,howtochoose? 18 91 1Introduction Thispaperaimstobeadidacticintroductiontoconceptsdevelopedin[6] andusedin[2]asaformalizationofgeneregulationnetworks.CPgames relyonplayersandsynopsesthatarealsogamecalledsituations.Aplayer maychangeasynopsistoanotherprovidedthesynopsiscanbeconvertedto theother,moreoverasynopsiscanbepreferredtoanother.Conversionand preferencearetwobasicconceptsofCPgamesfromwhichtheytaketheir name(CandP).Thefollowingtutorialpresentsallthoseconceptsthrough examples. 2Basicconcepts Tostartwith,letusgivethetwomainnotionsofgames.First,withno surprise,agameinvolvesplayers.Second,agameischaracterizedbysitu- ations.InCPgamesthesesituationswillbecalledsynopsesorsometimes gamesituations.Aplayercanmovefromonesynopsistoanother,butshe 1 1 Seetheprefaceof[3]fortheuseofpersonalpronouns 2

doesthatundersomeconstraintsasshehasnototalfreedomtoperformher moves,thereforearelationcalledconversionisdefinedforeachplayer;ittells whatmovesaplayerisallowedtoperform.ConversionofplayerAlicewill bewrittenI Alice .Assuch,conversiontellsbasicallytherulesofthegame. Inchessitwouldsay“aplayercanmoveherbishopalongadiagonal”,butit doesnottellthegamelineoftheplayer.Inotherwordsitdoesnottellwhy theplayerchoosestomoveorhowtoconverthersynopsis.Anotherrelation calledpreferencecomparessynopsesinorderforaplayertochooseabetter moveortoperformabetterconversion.PreferenceofplayerBethwillbe 00 writtenB Beth andwhenwewritesB Beth swemeanthatBethprefersstos or,ratherthans,shechoosess 0 .Preference(orchoice)issomewhatdis- connectedfromconversion,aplayercanclearlypreferasynopsisshecannot movetoandviceversashecanmovetoasynopsisshedoesnotprefer. Akeyconceptingamesisthisofequilibrium.Asaplayercanconverta synopsis,shecanconvertittoasynopsisshelikesbetter,inthesensethatshe prefersthenewsynopsissheconvertedto.Aplayerishappyinasynopsis, ifthereisnosynopsisshecanconverttoandsheprefers.Asynopsisisan equilibriumifeachplayerishappywiththissynopsis.Wewillseethatthis conceptofequilibriumcapturesandgeneralizestheconceptsknownasNash equilibriuminstrategicgames. 3Someexamples Letuspresenttheaboveconceptsofconversion,preferenceandequilibrium throughexamples.Wewillintroduceanewconceptcalledchangeofmind. 3.1Asimplegameonasquare Asanintroduction,wewilllookatvariationsofasimplegameonaboard. 3

3.1.1Afirstversion ImagineasimplegamewhereAliceandBethplayusingtokensonasquare. Wenumberthefourpositionsas1,2,3and4. 8?9> 1 :=;< > 0716 • 2534 ? ? > � � � � � > > > >    ? ? ? ? � � �> > >     ? ? ? 8?9> 4 :=;< � 8?9> 2 :=;< 07162534 ? 07162534 >  ? > > > > � � � � ? ? ? ?     > > > >� � � � ? ? ?   8?9> 3 :=;< � 07162534  AssumethatplayerAlicehasaredroundtokenandthatplayerBethhas abluesquaredtoken.Thetwoplayerplacestheirtokensononeverticesand thentheymovealongedges.Theycanalsodecidenottomove.Assumethat AliceandBethneverputtheirtokenonavertextakenbytheotherplayer, morepreciselyamovetowardsanoccupiedvertexcorrespondstoacapture ofthetokenatthatvertexandtoawin.Thenthegameends.  2*  0( 4 TLSK | 2 vn -- 4 MMNNPPPPNN | QQ 2 qq 4| QI 3 rj4, 4| UM 1 4|34|1   1 | 23 | 2 tl 1 | 23 | 4  1 | 3 sk sk3+ 3+ 3 SK | 1 1 |  3 oo mm oo qq ss kk // 11 // -- 33 ++ 3 | 1 PP 1 | 43 | TL 4 rj 1 | 43 | 2 2 |  3 lt2* 2 |  1   2 | 32 | 1 2 | 4 ph  4 | 2 mm TL 4, RJ 6. 11 NN Figure1:Conversionandpreferenceforthesquaregame Thegamehas12situationsorsynopses,whichwewritei | jfor1 ≤ i,j ≤ 4 andi 6 =j.Theabovepicturedsituationcorrespondsto1 | 2.Thetwocon- versionsaredescribedbyFigure1left.Inthisfigure, 3+ isAlice’s conversionand 3+ isBeth’sconversion. 4

 --qq   | d   | m d ] --qq aZ Q B 1 ' ! Z B '  4 PPNN | 24 PPNN | 2 '  B 4 | 34 | 14 | 3 d | Z 4 | 1 %  , 1 | 23 | 21 | 2  5 3 | 2 B | N p 1 | 3 ppnn00.. 3 NN | 11 PP | 3 ppnnb\ h V N p h V b \ 00.. 3 | 1 B ' | 5 B 1 | 43 | 4 Z 1 | 4 ,  3 | 4 % !  2|32|1 ' 2|3 Z B | d 2|1 1 '  B   11 2 | 4 mm Q Z a 11 2 | 4 mm ]d PP m |   d |  NN Figure2:Agentchangesofmind(ontheleft)and(general)changeofmind (ontheright)forthesquaregame Inthisgame,bothplayerssharethesamepreference,namelythefollow- ing:sinceaplayerdoesnotwanthertokentobecaptured,sheprefersa synopsiswherehertokenisontheoppositecorneroftheothertokentoa synopsiswherehertokenisnexttotheothertoken.Thisgivesthepreference giveninFigure1right.Thearrowfrom1 | 2to1 | 3meansplayersprefer1 | 3 to1 | 2. Fromtheconversionandthepreferencewebuildarelationthatwecall changeofmind.Alicecanchangehermindfromasynopsisstoanewone s 0 ,ifshecanconvertstothenewsynopsiss 0 andratherthansshechooses s 0 .ChangesofmindforAliceandBetharegiveninFigure2ontheleft.In thisfigure, // isAlice’schangeofmindand // isBeth’sconversion. The(general)changeofmindistheunionoftheagentchangeofmind,it isgivenbyFigure2ontheright.Theequilibriaarethesinks(or“minimal point”)forthatrelation,namely1 | 3,4 | 2,3 | 1and2 | 4.Thismeansthatno changeofmindarrowsleavethosenodes.Inthesesituationsplayershave theirtokensonoppositecornersandtheydonotmove.Anequilibriumlike 1 | 3whichisasinkiscalledaAbstractNashEquilibrium. 5

3.1.2Asecondversion Weproposeasecondversionofthegame,wheremovesofthetokencan onlybemadeclockwise.Obviouslytheconversionchanges,butalsothe preference,asaplayerdoeswantnotbethreatenedbyanothertokenplaced beforeherclockwiseandprefersasynopsisthatplacesthistokenasfaras possible.Theconversions,thepreferencesandthechangesofmindaregiven inFigure8(page21).Ifonelooksattheequilibrium,oneseesthatthereis nofixedpositionwhereplayersarehappy.Tobehappytheplayershaveto movearoundforever,onechasingtheother.Itisnotreallyacycle,buta perpetualmove.Wealsocallthatanequilibrium.Itissometimecalleda dynamicequilibriumorastationarystateaccordingtopeopleyoutalkto. 3.1.3Athirdversion Thethirdversionismeanttopresentaninterestingfeatureofthechangeof mind.Inthisversion,weusethesamerulesasthesecondone,exceptthat wesupposethatthegamestartswithbothtokenontheboardoritstartsas follows.Alicehasputhertokenonnode1(thisgamepositionsisdescribed as1 | ω).ThenBethchoosesapositionamong2,3or4.Theconversionis giveninFigure3left.Bethmaychoosenottoplay,butinthiscaseshe looses,inotherwords,sheprefers 2 anypositionto1 | ω.Thechangeofmind isgivenonFigure3right(page7).Thereisagainadynamicequilibrium andoneseesthatthisdynamicequilibriumisnotthewholegame,indeed oneenterstheperpetualmoveafteratleastonestepinthegame. 3.2Strategicgames Inthispresentationofstrategicgameswedonotusepayofffunctions,but directlyapreferencerelation 3 andwepresentseveralgames. 3.2.1ThePrisoner’sDilemma Theproblemisstatedusuallyasfollows Twosuspects,AandB,arearrestedbythepolice.Thepolice haveinsufficientevidenceforaconviction,and,havingseparated 2 Wedonotdrawthepreferencethatwouldbecometoentangled. 3 SeeSection1.1.2of[3]foradiscussion. 6

 *"  um sk  j   U { N b &&    { b \ qq b \ C &   oo\ C & 4 L | T 24 PP & | 2  4 | 3 sk 4 | UM 14 | 3 oob { C \ 4 | QQ 1 $  1 | 23 | 21 | 2  + 3 | 2 C { 1 | ω 3+ 1 | 3 sk 3+ 3 RJ | 11 | ω 3 __// 1 | 3 oo` ^f X C X f ^ `// 3 | 1 {& < C + 1 | 43 | TL 4 T d \ k // 55 1   | 4 $   3 | PP 4    2 | 3 3+ 2 | 1 & 2 | 3 \ C & { b // 2 | 1   C   5- 2 | 4 \ b 11 2 | 4 \ b { <4 3+ Figure3:Conversionandchangeofmindforthirdversionofthesquaregame bothprisoners,visiteachofthemtoofferthesamedeal:ifone actsasaninformeragainsttheother(finks)andtheotherremains quiet,thebetrayergoesfreeandthequietaccomplicereceivesthe fullsentence.Ifbothstayquiet,thepolicecansentenceboth prisonerstoareducedsentenceinjailforaminorcharge.Ifeach finks,eachwillreceiveasimilarintermediatesentence.Each prisonermustmakethechoiceofwhethertofinkortoremain quiet.However,neitherprisonerknowsforsurewhatchoicethe otherprisonerwillmake.Sothequestionthisdilemmaposesis: Whatwillhappen?Howwilltheprisonersact? Eachprisonercanbeintotwostates,eitherfink(F)orbequiet(Q).Each prisonercangofromQtoFandvice-versa,hencethefollowingconversion, where 3+ isprisonerAconversionand 3+ isprisonerBconversion (Figure4left).Eachprisonerpreferstogofreetobeensentencedandprefers alightsentencetoafullsentence.HencethepreferencearegiveninFig- ure4right,where // isprisonerApreferenceand // isprisonerB preference. FromthiswegetthechangeofmindofFigure5.Oneseesclearlythat theonlyequilibriumisF,FdespitebothpreferQ,QasshownonFigure4 right. SuchanequilibriumiscalledaNashequilibriuminstrategicgametheory. 7 b {  NN

Q,Q sk3+ Q,F SK  SK  F,Q sk3+ F,F rr Q,Q // Q,F II  \\ ww gg77  UU // F,Q ll F,F Figure4:Conversionandpreferenceintheprisoner’sdilemma Q,Q // Q,FQ,Q ___// Q,F          F,Q // F,FF,Q ___// F,F Figure5:Agentand(general)changeofmindintheprisoner’sdilemma TheparadoxcomesfromthefactthatF,Fisanequilibriumdespitethe factonehas: Q,Q ss F,F inthepreference. kk 3.2.2MatchingPennies Thissecondexampleisalsoclassic.Thisisasimpleexampleofstrategic gamewherethereisnosingletonequilibrium. Thegameisplayedbetweentwoplayers,PlayerAandPlayerB. Eachplayerhasapennyandmustsecretlyturnthepennyto heads(H)ortails(T).Theplayersthenrevealtheirchoices simultaneously.Ifthepenniesmatch(bothheadsorbothtails), PlayerAwins.Ifthepenniesdonotmatch(oneheadsandone tails),PlayerBwins. Theconversionissimilartothisoftheprisoner’sdilemma(Figure6left) andthepreferenceisgivenbywhowins(Figure6center). ChangeofmindformatchingpenniesisinFigure6right.Onenotices thatthereiscycle.Thiscycleistheequilibrium.Noplayerhasclearmind ofwhattoplayandchangeshermindseachtimeshelooses. 3.2.3Scissors,paper,stone Herewepresentthefamousgameknownasscissors,paper,stone.Itinvolves twoplayers,AliceandBethwhoannounceeitherscissors(C)orpaper(P) 8

H,H sk3+ H,T SK  SK  T,H sk3+ T,T rr H,H // H,T OO II  ,, T,H oo T,T H,H ___// H,T OO       T,H oo___ T,T Figure6:Conversion,preferenceand(general)changeofmindinMatching Pennies orstone(T)withtherulesthatstonebeatsscissors,scissorsbeatpaper,and paperbeatsstone.Thereareninesituations(seebelow),oneseesthatAlice mayconverthersituationP,CtoP,PorP,Tandthesamefortheother situations.Theconversionisgivenbelowleft.Sincetherules,itseemsclear thatAliceprefersT,PtoP,PandP,PtoC,P,hencethepreferencegiven belowrightwith // isAlice’spreferenceand // isBeth’spreference. Toavoidacumbersomediagram,inthepreferencewedonotputthearrows deducedbytransitivity. xp .& tt ## C,C sk3+ C,P sk3+ C,TC,C ll // C,PC,T KCSK  xp SK  [S .& SK  [SGG  UUII  WW rr P,C sk3+ P,P sk3+ P,TP,C ll // P,P // P,T  SK  SK  SK  II  II �� rr T,C sk3+ T,P sk3+ T,TT,CT,P // T,T nf80jj ;; Fromtheaboveconversionandpreference,onegetsthefollowingchange ofmind. tt f c _ [ X C,C ___// C,P oo___ C,T    GG          - ( $ OO   -WW ( ___//  ___// P,CP,PP,T $ ( - OO   X [  _      c  f 44       $   T,C oo jj ___ T,P ___// T,T X f [ c_ Oneseesalsoperpetualmovesasinthematchingpenniesofwhichitis ageneralization. 9

3.2.4StrategicgamesasCPgames AstrategicgameisaspecifickindofCPgames.Tobeastrategicgame,a CPgamehastofulfillthefollowingconditions. 1.Eachsynopsisisan-Cartesianproduct,wherenisthenumberofplay- ers.TheconstituentsoftheCartesianproductarecalledstrategies. 2.Conversionforplayera,writtenI a ,isanychangealongthea-thdimen- sion,i.e.,(s 1 ,...,s a ,...,s n )I a (s 1 ,...,s 0 a ,...,s n )ifandonlyifs a 6 =s 0 a . Henceinstrategicgames,conversionis • symmetric,(sI a s 0 impliess 0 I a s), • transitive,(sI a s 0 ands 0 I a s 00 implysI a s 00 ), • andirreflexive(itisnottruethatsI a s). 3.3Blinkoryouloose Blinkandyoulooseisagameplayedonasimplegraphwithtwoundifferen- tiatedtokens.Therearethreepositions: @GAF •• BECD@GAFBECD@GAF • BECD@GAF • BECD@GAFBECDG@FA •• BECD Therearetwoplayers,LeftandRight.Theleftmostpositionaboveisthe winningpositionforLeftandtherightmostpositionisthewinningposition forRight.Inotherwords,theonewhoownsbothtokenisthewinner.Let uscallthepositionsL,CandRrespectively.Oneplaysbytakingatoken ontheoppositenode. 3.3.1Afirsttactic:Foresight Aplayerrealizesthatshecanwinbytakingtheopponent’stokenfasterthan theopponentcanreact,i.e.,playerLeftcanconvertCtoLbyoutpacing playerRight.PlayerRight,inturn,canconvertCtoR.Thisversionof thegamehastwosingletonequilibria:LandR.Thisisdescribedbythe followingconversion L sk C 3+ R where 3+ istheconversionforLeftand 3+ istheconversionfor Right.Thepreferenceis uuuu L 55 C 55 R 01

where // isthepreferenceforLeftand // isthepreferenceforRight. Thechangeofmindisthen: L oo___ C ___// R andoneseesthattherearetwoequilibria:namelyLandR,whichmeans thatplayershavetakenbothtokenandkeepthem. 3.3.2Asecondtactic:Hindsight Aplayer,sayLeft,analysiswhatwouldhappenifshedoesnotact.Incase Rightacts,thegamewouldendupinRandLeftlooses.Asweallknow, peoplehatetoloosesotheyhaveanaversionforaloosingposition.Actually LeftconcludesthatshecouldhavepreventedtheRoutcomebyacting.In otherwords,itiswithinLeft’spowertoconvertRtoC.Similarlyforplayer RightfromLtoC. L 3+ C sk R Wecallnaturallyaversiontherelationthatescapesfrompositionsaplayer doesnotwanttobe,especiallyaloosingposition.Aversiondeservesitsname asitworkslikeconversion,butfliesfrombadposition.Wegetthefollowing changeofmind: L ___// C oo___ R withCthesingletonequilibrium 3.3.3Athirdtactic:Omnisight Theplayershavebothhindsightandforesight,resultinginaC/Pgame yq L yq 91 C 91 R withonechange-of-mindequilibriumcoveringalloutcomesthus,nosingleton equilibriumexists. _ U _ U L ii U i _ i )) C iiU i _ i )) R 3.4TheλphageasaCPgame Theλphageisagameinspiredfrombiology[4,5].Theoriginofthegame willbegiveninSection5,herewegivejusttherulesofthegame. 11