tutorial
21 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

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: Pierre.Lescanne@ens-lyon.fr13.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 . . . . . . . . . ...

Subjects

Informations

Published by
Reads 56
Language English
LIPResearchReportRR2006-51(version3)CPgames:atutorialPierreLescanneUniversite´deLyon,EcoleNormaleSupe´rieuredeLyon,LIP,43alle´ed’Italie,F69364Lyon,FranceAugust22,2007AbstractInthistutorialweintroducetheconceptofCP-gamewhichisageneralizationofthisofstrategicgame.FirstwepresentexampleswhicharerelevanttoaCP-gameapproach.ThenwegiveasomewhatnaiveintroductiontoCP-games.ThenwepresenttheconnectionbetweenCPgamesandgeneregulationnetworks.Contents1Introduction2Basicconcepts3Someexamples3.1Asimplegameonasquare....................3.1.1Arstversion.......................3.1.2Asecondversion.....................3.1.3Athirdversion......................3.2Strategicgames..........................3.2.1ThePrisonersDilemma.................Email:Pierre.Lescanne@ens-lyon.fr1223346666
3.2.2MatchingPennies.....................83.2.3Scissors,paper,stone...................83.2.4StrategicgamesasCPgames..............103.3Blinkoryouloose.........................103.3.1Arsttactic:Foresight..................103.3.2Asecondtactic:Hindsight................113.3.3Athirdtactic:Omnisight................113.4TheλphageasaCPgame....................114PresentationofC/Pgames144.1Singletonequilibrium.......................144.2Dynamicequilibrium.......................154.2.1Stronglyconnectedcomponents.............164.2.2Dynamicequilibriaasstronglyconnectedcomponents.175GeneregulationnetworksasC/Pgames6Conversionorpreference,howtochoose?18911IntroductionThispaperaimstobeadidacticintroductiontoconceptsdevelopedin[6]andusedin[2]asaformalizationofgeneregulationnetworks.CPgamesrelyonplayersandsynopsesthatarealsogamecalledsituations.Aplayermaychangeasynopsistoanotherprovidedthesynopsiscanbeconvertedtotheother,moreoverasynopsiscanbepreferredtoanother.ConversionandpreferencearetwobasicconceptsofCPgamesfromwhichtheytaketheirname(CandP).Thefollowingtutorialpresentsallthoseconceptsthroughexamples.2BasicconceptsTostartwith,letusgivethetwomainnotionsofgames.First,withnosurprise,agameinvolvesplayers.Second,agameischaracterizedbysitu-ations.InCPgamesthesesituationswillbecalledsynopsesorsometimesgamesituations.Aplayercanmovefromonesynopsistoanother,butshe11Seetheprefaceof[3]fortheuseofpersonalpronouns2
doesthatundersomeconstraintsasshehasnototalfreedomtoperformhermoves,thereforearelationcalledconversionisdefinedforeachplayer;ittellswhatmovesaplayerisallowedtoperform.ConversionofplayerAlicewillbewrittenIAlice.Assuch,conversiontellsbasicallytherulesofthegame.Inchessitwouldsay“aplayercanmoveherbishopalongadiagonal”,butitdoesnottellthegamelineoftheplayer.Inotherwordsitdoesnottellwhytheplayerchoosestomoveorhowtoconverthersynopsis.Anotherrelationcalledpreferencecomparessynopsesinorderforaplayertochooseabettermoveortoperformabetterconversion.PreferenceofplayerBethwillbe00writtenBBethandwhenwewritesBBethswemeanthatBethprefersstosor,ratherthans,shechoosess0.Preference(orchoice)issomewhatdis-connectedfromconversion,aplayercanclearlypreferasynopsisshecannotmovetoandviceversashecanmovetoasynopsisshedoesnotprefer.Akeyconceptingamesisthisofequilibrium.Asaplayercanconvertasynopsis,shecanconvertittoasynopsisshelikesbetter,inthesensethatsheprefersthenewsynopsissheconvertedto.Aplayerishappyinasynopsis,ifthereisnosynopsisshecanconverttoandsheprefers.Asynopsisisanequilibriumifeachplayerishappywiththissynopsis.WewillseethatthisconceptofequilibriumcapturesandgeneralizestheconceptsknownasNashequilibriuminstrategicgames.3SomeexamplesLetuspresenttheaboveconceptsofconversion,preferenceandequilibriumthroughexamples.Wewillintroduceanewconceptcalledchangeofmind.3.1AsimplegameonasquareAsanintroduction,wewilllookatvariationsofasimplegameonaboard.3
3.1.1ArstversionImagineasimplegamewhereAliceandBethplayusingtokensonasquare.Wenumberthefourpositionsas1,2,3and4.8?9>1:=;<>07162534??>>>>>????>>>???8?9>4:=;<8?9>2:=;<07162534?07162534>?>>>>????>>>>???8?9>3:=;<07162534AssumethatplayerAlicehasaredroundtokenandthatplayerBethhasabluesquaredtoken.Thetwoplayerplacestheirtokensononeverticesandthentheymovealongedges.Theycanalsodecidenottomove.AssumethatAliceandBethneverputtheirtokenonavertextakenbytheotherplayer,morepreciselyamovetowardsanoccupiedvertexcorrespondstoacaptureofthetokenatthatvertexandtoawin.Thenthegameends. 2*0(4TLSK|2vn--4MMNNPPPPNN|QQ2qq4|QI3rj4,4|UM14|34|1  1|23|2tl1|23|4 1|3sksk3+3+3SK|11|3oommooqqsskk//11//--33++3|1PP1|43|TL4rj1|43|22| 3lt2*2| 1  2|32|12|4ph 4|2mmTL4,RJ6.11NNFigure1:ConversionandpreferenceforthesquaregameThegamehas12situationsorsynopses,whichwewritei|jfor1i,j4andi6=j.Theabovepicturedsituationcorrespondsto1|2.Thetwocon-versionsaredescribedbyFigure1left.Inthisgure,3+isAlice’sconversionand3+isBeth’sconversion.4
--qq|d |md]--qqaZQB1'!ZB'4PPNN|24PPNN|2'B4|34|14|3d|Z4|1%,1|23|21|2 53|2B|Np1|3ppnn00..3NN|11PP|3ppnnb\hVNphVb\00..3|1B'|5B1|43|4Z1|4, 3|4%!2|32|1'2|3ZB|d2|11'B112|4mmQZa112|4mm]dPPm| d|NNFigure2:Agentchangesofmind(ontheleft)and(general)changeofmind(ontheright)forthesquaregameInthisgame,bothplayerssharethesamepreference,namelythefollow-ing:sinceaplayerdoesnotwanthertokentobecaptured,sheprefersasynopsiswherehertokenisontheoppositecorneroftheothertokentoasynopsiswherehertokenisnexttotheothertoken.ThisgivesthepreferencegiveninFigure1right.Thearrowfrom1|2to1|3meansplayersprefer1|3to1|2.Fromtheconversionandthepreferencewebuildarelationthatwecallchangeofmind.Alicecanchangehermindfromasynopsisstoanewones0,ifshecanconvertstothenewsynopsiss0andratherthansshechoosess0.ChangesofmindforAliceandBetharegiveninFigure2ontheleft.Inthisfigure,//isAlice’schangeofmindand//isBeth’sconversion.The(general)changeofmindistheunionoftheagentchangeofmind,itisgivenbyFigure2ontheright.Theequilibriaarethesinks(or“minimalpoint”)forthatrelation,namely1|3,4|2,3|1and2|4.Thismeansthatnochangeofmindarrowsleavethosenodes.Inthesesituationsplayershavetheirtokensonoppositecornersandtheydonotmove.Anequilibriumlike1|3whichisasinkiscalledaAbstractNashEquilibrium.5
3.1.2AsecondversionWeproposeasecondversionofthegame,wheremovesofthetokencanonlybemadeclockwise.Obviouslytheconversionchanges,butalsothepreference,asaplayerdoeswantnotbethreatenedbyanothertokenplacedbeforeherclockwiseandprefersasynopsisthatplacesthistokenasfaraspossible.Theconversions,thepreferencesandthechangesofmindaregiveninFigure8(page21).Ifonelooksattheequilibrium,oneseesthatthereisnofixedpositionwhereplayersarehappy.Tobehappytheplayershavetomovearoundforever,onechasingtheother.Itisnotreallyacycle,butaperpetualmove.Wealsocallthatanequilibrium.Itissometimecalledadynamicequilibriumorastationarystateaccordingtopeopleyoutalkto.3.1.3AthirdversionThethirdversionismeanttopresentaninterestingfeatureofthechangeofmind.Inthisversion,weusethesamerulesasthesecondone,exceptthatwesupposethatthegamestartswithbothtokenontheboardoritstartsasfollows.Alicehasputhertokenonnode1(thisgamepositionsisdescribedas1|ω).ThenBethchoosesapositionamong2,3or4.TheconversionisgiveninFigure3left.Bethmaychoosenottoplay,butinthiscaseshelooses,inotherwords,sheprefers2anypositionto1|ω.ThechangeofmindisgivenonFigure3right(page7).Thereisagainadynamicequilibriumandoneseesthatthisdynamicequilibriumisnotthewholegame,indeedoneenterstheperpetualmoveafteratleastonestepinthegame.3.2StrategicgamesInthispresentationofstrategicgameswedonotusepayofffunctions,butdirectlyapreferencerelation3andwepresentseveralgames.3.2.1ThePrisonersDilemmaTheproblemisstatedusuallyasfollowsTwosuspects,AandB,arearrestedbythepolice.Thepolicehaveinsufficientevidenceforaconviction,and,havingseparated2Wedonotdrawthepreferencethatwouldbecometoentangled.3SeeSection1.1.2of[3]foradiscussion.6
 *" umsk jU{Nb&&{b\qqb\C& oo\C&4L|T24PP&|24|3sk4|UM14|3oob{C\4|QQ1$1|23|21|2+3|2C{1|ω3+1|3sk3+3RJ|11|ω3__//1|3oo`^fXCXf^`//3|1{&<C+1|43|TL4Td\k//551 |4$3|PP4 2|33+2|1&2|3\C&{b//2|1 C5-2|4\b112|4\b{<43+Figure3:Conversionandchangeofmindforthirdversionofthesquaregamebothprisoners,visiteachofthemtoofferthesamedeal:ifoneactsasaninformeragainsttheother(finks)andtheotherremainsquiet,thebetrayergoesfreeandthequietaccomplicereceivesthefullsentence.Ifbothstayquiet,thepolicecansentencebothprisonerstoareducedsentenceinjailforaminorcharge.Ifeachnks,eachwillreceiveasimilarintermediatesentence.Eachprisonermustmakethechoiceofwhethertofinkortoremainquiet.However,neitherprisonerknowsforsurewhatchoicetheotherprisonerwillmake.Sothequestionthisdilemmaposesis:Whatwillhappen?Howwilltheprisonersact?Eachprisonercanbeintotwostates,eitherfink(F)orbequiet(Q).EachprisonercangofromQtoFandvice-versa,hencethefollowingconversion,where3+isprisonerAconversionand3+isprisonerBconversion(Figure4left).Eachprisonerpreferstogofreetobeensentencedandprefersalightsentencetoafullsentence.HencethepreferencearegiveninFig-ure4right,where//isprisonerApreferenceand//isprisonerBpreference.FromthiswegetthechangeofmindofFigure5.OneseesclearlythattheonlyequilibriumisF,FdespitebothpreferQ,QasshownonFigure4right.SuchanequilibriumiscalledaNashequilibriuminstrategicgametheory.7b{NN
Q,Qsk3+Q,FSK SK F,Qsk3+F,FrrQ,Q//Q,FII\\wwgg77UU//F,QllF,FFigure4:Conversionandpreferenceintheprisoner’sdilemmaQ,Q//Q,FQ,Q___//Q,FF,Q//F,FF,Q___//F,FFigure5:Agentand(general)changeofmindintheprisoner’sdilemmaTheparadoxcomesfromthefactthatF,Fisanequilibriumdespitethefactonehas:Q,QssF,Finthepreference.kk3.2.2MatchingPenniesThissecondexampleisalsoclassic.Thisisasimpleexampleofstrategicgamewherethereisnosingletonequilibrium.Thegameisplayedbetweentwoplayers,PlayerAandPlayerB.Eachplayerhasapennyandmustsecretlyturnthepennytoheads(H)ortails(T).Theplayersthenrevealtheirchoicessimultaneously.Ifthepenniesmatch(bothheadsorbothtails),PlayerAwins.Ifthepenniesdonotmatch(oneheadsandonetails),PlayerBwins.Theconversionissimilartothisoftheprisoner’sdilemma(Figure6left)andthepreferenceisgivenbywhowins(Figure6center).ChangeofmindformatchingpenniesisinFigure6right.Onenoticesthatthereiscycle.Thiscycleistheequilibrium.Noplayerhasclearmindofwhattoplayandchangeshermindseachtimeshelooses.3.2.3Scissors,paper,stoneHerewepresentthefamousgameknownasscissors,paper,stone.Itinvolvestwoplayers,AliceandBethwhoannounceeitherscissors(C)orpaper(P)8
H,Hsk3+H,TSK SK T,Hsk3+T,TrrH,H//H,TOO II,,T,HooT,TH,H___//H,TOOT,Hoo___T,TFigure6:Conversion,preferenceand(general)changeofmindinMatchingPenniesorstone(T)withtherulesthatstonebeatsscissors,scissorsbeatpaper,andpaperbeatsstone.Thereareninesituations(seebelow),oneseesthatAlicemayconverthersituationP,CtoP,PorP,Tandthesamefortheothersituations.Theconversionisgivenbelowleft.Sincetherules,itseemsclearthatAliceprefersT,PtoP,PandP,PtoC,P,hencethepreferencegivenbelowrightwith//isAlice’spreferenceand//isBeth’spreference.Toavoidacumbersomediagram,inthepreferencewedonotputthearrowsdeducedbytransitivity.xp.&tt##C,Csk3+C,Psk3+C,TC,Cll//C,PC,TKCSK xpSK [S.&SK [SGGUUIIWWrrP,Csk3+P,Psk3+P,TP,Cll//P,P//P,TSK SK SK IIIIrrT,Csk3+T,Psk3+T,TT,CT,P//T,Tnf80jj;;Fromtheaboveconversionandpreference,onegetsthefollowingchangeofmind.ttfc_[XC,C___//C,Poo___C,TGG-($OO-WW(___//___//P,CP,PP,T$(-OOX[_cf44$T,Coojj___T,P___//T,TXf[c_Oneseesalsoperpetualmovesasinthematchingpenniesofwhichitisageneralization.9
3.2.4StrategicgamesasCPgamesAstrategicgameisaspecifickindofCPgames.Tobeastrategicgame,aCPgamehastofulfillthefollowingconditions.1.Eachsynopsisisan-Cartesianproduct,wherenisthenumberofplay-ers.TheconstituentsoftheCartesianproductarecalledstrategies.2.Conversionforplayera,writtenIa,isanychangealongthea-thdimen-sion,i.e.,(s1,...,sa,...,sn)Ia(s1,...,s0a,...,sn)ifandonlyifsa6=s0a.Henceinstrategicgames,conversionissymmetric,(sIas0impliess0Ias),transitive,(sIas0ands0Ias00implysIas00),andirreflexive(itisnottruethatsIas).3.3BlinkoryoulooseBlinkandyoulooseisagameplayedonasimplegraphwithtwoundifferen-tiatedtokens.Therearethreepositions:@GAF••BECD@GAFBECD@GAFBECD@GAFBECD@GAFBECDG@FA••BECDTherearetwoplayers,LeftandRight.TheleftmostpositionaboveisthewinningpositionforLeftandtherightmostpositionisthewinningpositionforRight.Inotherwords,theonewhoownsbothtokenisthewinner.LetuscallthepositionsL,CandRrespectively.Oneplaysbytakingatokenontheoppositenode.3.3.1Arsttactic:ForesightAplayerrealizesthatshecanwinbytakingtheopponent’stokenfasterthantheopponentcanreact,i.e.,playerLeftcanconvertCtoLbyoutpacingplayerRight.PlayerRight,inturn,canconvertCtoR.Thisversionofthegamehastwosingletonequilibria:LandR.ThisisdescribedbythefollowingconversionLskC3+Rwhere3+istheconversionforLeftand3+istheconversionforRight.ThepreferenceisuuuuL55C55R01
where//isthepreferenceforLeftand//isthepreferenceforRight.Thechangeofmindisthen:Loo___C___//Randoneseesthattherearetwoequilibria:namelyLandR,whichmeansthatplayershavetakenbothtokenandkeepthem.3.3.2Asecondtactic:HindsightAplayer,sayLeft,analysiswhatwouldhappenifshedoesnotact.IncaseRightacts,thegamewouldendupinRandLeftlooses.Asweallknow,peoplehatetoloosesotheyhaveanaversionforaloosingposition.ActuallyLeftconcludesthatshecouldhavepreventedtheRoutcomebyacting.Inotherwords,itiswithinLeft’spowertoconvertRtoC.SimilarlyforplayerRightfromLtoC.L3+CskRWecallnaturallyaversiontherelationthatescapesfrompositionsaplayerdoesnotwanttobe,especiallyaloosingposition.Aversiondeservesitsnameasitworkslikeconversion,butfliesfrombadposition.Wegetthefollowingchangeofmind:L___//Coo___RwithCthesingletonequilibrium3.3.3Athirdtactic:OmnisightTheplayershavebothhindsightandforesight,resultinginaC/PgameyqLyq91C91Rwithonechange-of-mindequilibriumcoveringalloutcomesthus,nosingletonequilibriumexists._U_ULiiUi_i))CiiUi_i))R3.4TheλphageasaCPgameTheλphageisagameinspiredfrombiology[4,5].TheoriginofthegamewillbegiveninSection5,herewegivejusttherulesofthegame.11