Computing Correlated Equilibria

ErgasÐa-Episkìphsh dhmosÐeushc: Computing Equilibria in Multi-player Games Christos H.Papadimitriou,Tim RoughgardenmPl∀Lianèac Jan shc9IoulÐou2007PerÐlhyhSthn paroÔsa ergasÐa ja k noume mia episkìphsh thc dhmosÐeushc: Computing Equilibria in Multi-Player Games twn Papadimitriou kaiRoughgarden[Ch.05](ìpwc faÐnetai ki apìton tÐtlo!).H dhmosÐeushafor kurÐwc correlated equilibria,mia pio'genik 'morf issoropÐacapìta Nash equilibria,pou krÔbei mèsa thcèna eÐdoc sunergasÐacmetaxÔtwn paikt¸n(an kai den eÐnai akrib¸cètsi,oi paÐktec exakolou-joÔn kai skèftontai atomik ).Ja perigr youme autoÔtou eÐdouc ticisorropÐec,kai ja doÔme ti neìprosèfere h dhmosÐeush sth melèth touprobl matoc kaj¸c kai th genik idèa pÐsw apìta apotelèsmata pouparousi zontai.1Correlated equilibriaTa correlated equilibria eÐnaièna eÐdoc issoropÐac me thn gnwst ènnoia: kanènac paÐkthc denèqei sumfèron atomik na all xei thn strathgik tou.H basik diafor me ta Nash equilibria eÐnai ston trìpo me ton opoÐo k je paÐkthc k nei thn epilog thc strathgik c tou.Eis qjhsan apìton Aumann sto[R.J74].Ac xekin soume meèna par deigma gia na p roume mia pr¸th idèa perÐtÐnoc prìkeitai.'Estw to gnwstìpaiqnÐdi:h m qh twn fÔllwn.'Estw mÐa ekdoq tou sthn opoÐa h kopèla jèlei na parakolouj sei ton telikìthc eurovision kai o ntrac ton telikìtou mundial,kai dustuq¸c up rqei mia thleìrash sto spÐti kai aut paÐzontai tautìqrona.Ta payoffk je kat stashc dÐnontai apìton pÐnaka(paÐkthc gramm h kopèla,paÐkthc st lh o ntrac):1e me2,10,0m0,01,2Ed¸to mixed N.E.eÐnai to{k:(2/3,1/3),a:(1/3,2/3)},me anamenìmeno kèrdoc gia ton k je paÐkth2/3.An prosèxoume lÐgo ta payofftou paiqnidioÔja doÔme oti up rqoun dÔo katast seic pou den sumfèroun kanènan apìtoc dÔo paÐktec,oi katast seic(e,m)kai(m,e).GiatÐloipìn na mhn sunergastoÔn kai na apokleÐsoun autèc tic katast seic?K noun loipìn mia sumfwnÐa.Ja strÐyoun nìmisma kai anèrjei kor¸na ja doun mazÐeurovision alli¸c ja parakolouj soun mundial.Me autìton trìpo apèkeleisan tic dÔo sqhmec(kai gia touc dÔo)katast seic.Kajènac touc me pijanìthta1/2jaèqei kèrdoc2,afoÔja dei autìpou jèlei kai me pijanìthta 1/2jaèqei kèrdoc1afoÔja eÐnai me ton sÔntrofìtou.'A ra kajènac jaèqei anamenìmeno kèrdoc3/2.KaneÐc apìtouc dÔo denèqei sumfèron atomik na all xei afoÔja kerdÐsei ligìtero(den kerdÐzei tÐpota).Me thn arqik touc sumfwnÐa dhlad brèjhkan seèna eÐdoc issoropÐac,pou m lista plhr¸nei kai perissìtero.Aut h sumfwnÐa sunist ena correlated equilibrium tou paiqnidioÔme th strathgik k je p ikth na eÐnai:ja k nw autìpou ja mou upodeÐxei to nìmisma.Pio genik .'Estwèna tuqaÐo paiqnÐdi kièna sÔnolo pijanot twn gia tic dunatèc katast seic tou paiqnidioÔwste autèc naèqoun jroisma1.Upojè-toume oti mia anex rthth-amerìlhpth arq (parap nw to nìmisma)epilègei me tic dedomènec pijanìthtec k poia kat stash.Aut h kat stash upodeiknÔei se k je paÐqth k poia strathgik .Ja lème otièqoume correlated equilibri-um an kanènac paÐqthc denèqei megalÔtero anamenìmeno kèrdoc an epilèxei dik tou strathgik (qwrÐc en gènei na xèrei ti upodeiknÔei h arq stouc upìloipouc).LÐgo pio k tw ja doÔme entel¸c tupik ti shmaÐnei correlated equilibrium,mèsw grammik¸n exis¸sewn pou apeikonÐzoun autìakrib¸c pou zht me.Duo parathr seic pou prèpei na gÐnoun ed¸eÐnai oti k je mixed N.E.eÐnai kai correlated equilibrium(me tic pijanìthtec k je kat stashc na eÐnaiÐdiec me autèc pou prokÔptoun apìto mixed N.E.)kaiìti k je kurtìc sunduasmìc apìmixed N.E.eÐnai epÐshc correlated equilibrium,(me tic pijanìthtec na prokÔptoun apìtouc kurtoÔc sunduasmoÔc twn pijanot twn me tic opoÐec emfanÐzontai oi katast seic tou paiqnidioÔgia k je mixed N.E.).2Pareljìn kai prosforTa apìtelèsmata thc ergasÐac:21.Gia summetrik paiqnÐdia (kai k ti parap nw!)parousi zetai apodotikìc trìpoc gia ton upologismìenìc C.E.(poluwnumikìc wc proc thn fusik anapar stash tou paÐgniou).2.Parousi zetai mia genik idèa gia upologismìC.E.pou mporeÐna efar-mosteÐse sugkekrimèna paÐgnia sumfìrhshc kai paÐgnia se gr fouc me bounded tree-width.3.Gia pio genik paÐgnia sumfìrhshc kai paÐgnia se gr fouc (ektìc an P =NP )den up rqei algìrijmoc pou na ex gei bèltisto (ja oristeÐparak tw)C.E.se qrìno poluwnumikìwc proc thn fusik anapar s-tash tou paÐgniou.4.Parousi zetai ènac poluwnumikìc algìrijmoc gia upologismìN.E.se summetrik paÐgnia k strathgik¸n ìpou k =O (log n/log log n )Prin mil soume gia ta parap nw apotelèsmata ac gÐnoume pio tupikoÐston orismìtou C.E.'Estw paÐgnio k paikt¸n.Gia èna C.E.prèpei na broÔme èna sÔnolo pijanot twn gia to opoÐo ja petuqaÐnetai o stìqoc pou parousi sthke sto 1.'Estw s i k poia apìtic pure strathgikèc tou paÐqth i kai s =(s 1,...,s k )na dhl¸nei kat stash tou paiqnidioÔ.'Estw payoff i (s )na eÐnai to kèrdoc tou p ikth i ìtan oi paÐktec akoloujoÔn thn s .'Estw epÐshc p (s )eÐnai h pijanìthta h anex rthth arq na epilèxei thn kat stash s .An h arq upodeÐxei ston i paÐkth thn strathgik s i tìte autìc den prèpei na èqei sumfèron na all xei se k poia dik tou (dedomènou oti den gnwrÐzei ti upodeÐqthke stouc llouc).'Etsi gia k je paÐkth i :∀s i : s :s i =s ip (s )∗payoff i (s )≥ s :s i =s ip (s )∗payoff i (s |s i =s i )(me thn jroish na gÐnetai stic strathgikèc pou èqoun s i =s i kai ìpous |s i =s i shmaÐnei sthn s ìpou s i b le s i ).Oi anisìthtec autèc se sunduasmìme to gegonìc oti ta p (s )≥0eÐnai pijanìthtec me p (s )=1mac dÐnoun èna grammikìsÔsthma tou opoÐou oi lÔseic sunistoÔn C.E.An analogistoÔme oti oi sunduasmoÐtwn strathgik¸n eÐnai polloÐ,katalabaÐnoume oti to sÔsthma autìeÐnai 'meg lo'( gnwsta ta p (s )gia k je strathgik s ).M pwc ja moroÔsame na broÔme èna pio 'bolikì'sÔsthma?Gia k poia paiqnÐdia mporoÔme!(dec parak tw).MporoÔme epÐshc na broÔme to 'kalÔtero (bèltisto)C.E.,arkeÐna orÐsoume ti shmaÐnei autì.To kalÔtero ja mporoÔse p.q.na eÐnai autìpou megistopoieÐto kèrdoc ìlwn twn paiqt¸n,dhlad autìpou megistopoieÐto:sp (s )∗ipayoff i (s )3Gia ta apotelèsmata thc ergasÐacTo1o apotèlesma tan entel¸c kainoÔrio.To grammikìsÔsthma bèbaia pou prèpei na epilujeÐ tan gnwstìall autìgenik den eÐnai poluwnumikìwc proc thn anapar stash tou paÐgniou.Gia ta summetrik paÐgnia br kanìmwck poio'bolikì'sÔsthma pou touc odhgeÐse mia lÔsh tou arqikoÔ'meg lou' sust matoc.Perissìtera sthn epìmenh enìthta.Gia to2o up rqan prohgoÔmena apotelèsmata gia paÐgnia se gr fouc.Pio sugkekrimèna sto[SKO03]èna apìta dÔo kÔria apotelèsmata eÐnai h eÔresh enìc algorÐjmou pou upologÐzei C.E.se paÐgnia se gr fouc o opoÐoc basÐzetai sta susqetizìmena dÐktua Markov tou gr fou.O algìrijmoc autìc trèqei se poluwnumikìqrìno an efarmosteÐse dèntra.To3o apoteleÐkainoÔrio apotèlesma.BasÐzetai se mia anagwg pou k nei to prìblhma gia k poiouc gr fouc NP-complete.Gia to4o,par llhla kai anex rthta,parìmoia apotelèsmata parousi zon-tai sto[RJ04].To basikìapotèlesma pou parousi zetai eÐnai to:Je¸rhma1.To prìblhma upologismoÔenìc summetrikoÔN.E.seèna sum-metrikìpaÐgnio me n paÐktec kai k strathgikèc mporeÐna lujeÐgia tuqaÐa akrÐbeia se qrìno poluwnumikìwc proc to n k,ta bits pou qrei zontai gia thn anapar stash twn sunart sewn kèrdouc kai twn bits pou qrei zontai gia thn epilegmènh akrÐbeiaH apìdeixh dÐnetai sto paper kai eÐnai sqetik apl .To parap nw je¸rhma proupojètei k=O(log n/log log n).An to k eÐnai"akìmh megalÔtero apìton tìte h summetrÐa denèqei tÐpota na mac prosfèrei kaj¸c genikìtera paÐgnia an gontai se summetrik kiètsi exis¸netai h duskolÐa touc.3Kentrik shmeÐa sthn exagwg twn apote-lesm twnC.E.se summetrik paÐgnia'Estw G=(S={1,2},u1,...,u n),G dhlad èna summetrikìpaÐgnio n paikt¸nìpou k je paÐkthcèqei dÔo strathgikèc.Gia k je tètoio paÐgnio, kataskeu zeteèna sÔsthma me metablhtèc tic p i(j)kai p(j)ìpou oi men p i(j) dhl¸noun thn pijanìthta j to pl joc paÐktec sumperilambanomènou kai tou i dialègoun thn strathgik 1(sumbolik thn pijanìthta tou S i(j))kai oi p(j) thn pijanìthta akrib¸c j paÐktec na dialèxoun thn strathgik 1(sumbolik thn pijanìthta tou S(j)).To sÔsthma eÐnai to akìloujo:nj=0p i(j)u i(j,1)≥nj=0p i(j)u i(j−1,2),∀i∈{1,...,n}4nj=0[p(j)−p i(j)]u i(j,2)≥nj=0[p(j)−p i(j)]u i(j+1,1),∀i∈{1,...,n} nj=0p(j)=1,ni=1p i(j)=j p(j),∀j∈{0,...,n}0≤p i(j)≤p(j)≤1OrÐzoun mia sun rthsh epèktashc k je lÔshc tou sust matoc pou kataskeu -zoun.Ousiastik aut èqei stìqo na apon mei se k je kat stash thn pi-janìthta pou prèpei aut na p rei¸ste naèqoume C.E.To dÔskolo komm ti thc doulei c eÐnai h apìdeixh oti k je lÔsh autoÔtou sust matoc mporeÐp ntote na epektajeÐmèsw miac tètoiac sun rthshc.To sÔsthma pou orÐzounlÔnetai se poluwnumikìqrìno kaj¸c kai h epèktash.Sunep¸c se poluwnu-mikìqrìno mporoÔme na p roumeèna C.E.tou paÐgniou.To'kìlpo'ed¸eÐnai oti oi metablhtèc tou sust matoc pou orÐzetai den eÐnai polloÐ,se antÐjesh me to arqikìsÔsthma.Me parìmoia teqnik apodeiknÔetai toÐdio kai gia summetrik paÐgnia me perissìterec strathgikèc.'Ena epÐshc shmantikìshmeÐo eÐnai oti poujen sthn apìdeixh den qrhsimopoieÐtai to gegonìc oti oi sunart seic kèrdouc eÐnai Ðdiec.Autìmac dÐnei thn dunatìthta na sumper noume taÐdia pr gmata kai gia elafr¸c genikìtera paÐgnia.C.E.se paÐgnia sumfìrhshc kai paÐgnia se gr foucH genik idèa ed¸eÐnai gia k je paÐgnio na brÐskoumeèna'mikrì'sÔsthma exis¸sewn,na to epilÔoume kai na epekteÐnoume th lÔsh tou se C.E.ìp-wc k name kai prwtÔtera.To prìblhma eÐnai oti prèpei gia k je paÐgnio na paÐrnoume diaforetikèc exis¸seic sto sÔsthma qwrÐc na xeroume an pr g-matiìlec autèc epekteÐnontai se C.E.Sthn dhmosÐeush dÐnetai lÔsh se autìakrib¸c to prìblhma kai perigr fetai mia klash paignÐwn gia tic opoÐec m-poroÔme na broÔme tètoiec exis¸seic.Gia k je paÐgnio se kanonik morf orÐzetai mia sumpag c anapar stas tou,h P,diaqwrÐzontac kat k poio trìpo tic strathgikèc,me skopìthn kalÔterh anapar stash twn C.E.Gia to P autìorÐzetaièna prìblhma di-aqwrismoÔ,to opoÐo eÐnai epÐshc prìblhma beltistopoÐhshc.EÐnai to antÐs-toiqo'mikrì'prìblhma pou zht me.To shmantikìapotèlesma thc enìthtaceÐnai h mesh susqètish autoÔtou probl matoc me to prìblhma eÔreshc C.E. gia to paÐgnio.Pio sugkekrimèna:Je¸rhma2.An to prìblhma diaqwrismoÔgia to P epilÔetai se poluwn-umikìqrìno sthn anapar stash tou P tìte kai to prìblhma eÔreshc enìc C.E.mporeÐna lujeÐse poluwnumikìqrìno.5Efarmogèc autoÔtou jewr matoc mporoÔn na gÐnoun gia par deigma se summetrik paÐgnia,paÐgna se gr fouc all kai se paÐgnia sumfìrhshc.Sum-metrik paignia eÐdame prwtÔtera.An h prohgoÔmenh idèa efarmosteÐse paig-nia se gr fouc me bounded tree-width tìteèna C.E.mporeÐna upologisteÐse poluwnumikìqrìno kaj¸c se tètoiouc gr fouc mporoÔme(me dynamic programming)na d¸soume lÔsh sto prìblhma diaqwrismoÔse poluwnumikìqrìno.To apojarruntikìapotèlesma eÐnai oti to prìblhma tou diaqwrismoÔse genikoÔc gr fouc eÐnai NP-complete.To akìmh pio sqhmo apotèlesma eÐnaiìti(ektìc an P=NP)den up rqei algìrijmoc pou na ex gei bèltisto(giak poia sun rthsh beltistopoÐhshc)C.E.se qrìno poluwnumikìwc proc thn fusik anapar stash tou paÐgniou.Parìmoia apotelèsmata isqÔoun kai sepaÐgnia sumfìrhshc.Ta apotelèsmata aut prokÔptoun apìthn anagwg tou exact cover by3-sets sto ek stote prìblhma.4EpÐlogocH suneisfor thc dhmosÐeushc eÐnai sÐgoura meg lh,mhn xeqn me pou parousi sthke aut h dhmosÐeush(aut se SODA kai h'prohgoÔmen 'thc se STOC).Efar-mogèc twn Correlated Equilibria mporoÔme na broÔme pollèc.Endeiktik , efarmogèc up rqoun sta[R.J87][FR97]kai[FR99].Pio oikeÐa se em c efar-mog twn Correlated Equilibria eÐnai oi fwteinoÐshmatodìtec.H anex rththarq ed¸eÐnai oi fwteinoÐshmatodìtec(h m llon autìc pou touc program-matÐzei!).O qrìnoc pou paramènoun pr sinoi kìkkinoi eÐnai tètoioc¸ste na mhn mac sumfèrei na all xoume diadrom gia na kinhjoÔme.AutìgiatÐautìco qrìnoc upologÐsthke akrib¸c¸ste o drìmoc pou epilèxame arqik na gÐneikai o pio gr goroc gia mac( toul qiston aut h prìjesh up rqe).References[Ch.05]T.Roughgarden puting equilibria in multi-player games.In Proceedings of the Sixteenth Annual ACM-SIAMSymposium on Discrete Algorithms(SODA),pages82–91,2005.[FR97] D.Foster and R.Vohra.Calibrated learning and correlated euilib-rium.Games and Economic Behavior,21:40-55,1997.[FR99] D.Foster and R.Vohra.Regret in the on-line decision problem.Games and Economic Behavior,29:7-35,1999.6[R.J74]R.J.Aumann.Subjectivity and correlation in randomized strategies.Journal Of Mathematical Economics,1(1):67-96,1974.[R.J87]R.J.Aumann.Correlated euilibria as an expression of the bayesian rationality.Econometrica,55(1):1-18,1987.[RJ04] E.Markakis R.J.Lipton.Nash equilibria via polynomial equations.In Proceedings of the6th Latin American Theoritical Informatics(LATIN),pages413–422,2004.[SKO03]ngford S.Kakade,M.Kearns and L Ortiz.Correlated equilib-ria in graphical games.In Proceedings of the4th ACM Conferenceon Electronic Commerce,pages42–47,2003.7。