[PDF] Chapitre 5 Jeux classiques en théorie algorithmique des jeux

View - Download Chapitre 5 Jeux classiques en théorie algorithmique des jeux

Previous PDF

Next PDF

Chapitre5

Jeuxclassiques enth´eorie

algorithmiquedesjeux Cechapitre vise`apr´ esenteretrappe lerquelquesjeuxclas siquesdelath´eoriealgo- rithmiquedesj euxtout enintroduisantles conceptsdebas edela th´eoriedesjeux.Ce chapitren'esttoutefoispas unelisteexhaustivedes jeux´etudi ´esen informatique.Afin d'obtenirplusd'information, lelecteur peuts er´ ef´ereraulivre [Nisanetal.,2007]. Lechapitre s'organisedelafa¸consuiv ante.Dans lasection 5.1,nous allonsintroduire lanotiond' ´equilibrede Nash(mixte)endiscutantlac omplexit´ eduprobl`emede leur calcul.Ensuite, nousallonsinstanciersurdes jeuxsimples, commelesjeux sym´etriques, etpuissur lesje uxdep otentielordinal(avec leursdi ff

´erentesvariantes).Finalement,

commecesclasses dejeux poss` edent plusieurs´equilibres,nousallons discuterquelssont lesdi ff

´erentscrit`erespour les´evaluer.

Cechapitre estessentiellemen tunrapidesurvol. Nouspr´esentonscependantune contributionpersonnelle(obtenue encollaborationav ecFannyP ascual)concernan tl'exis- tenced'´ equilibresdeNashpursetd'?-´equilibresdeNashpursdanslesjeuxd'allo cation detˆac hes,lorsqu'unjoueurestresponsablede plusieurstˆac hes[43].

5.1Jeuxstatiques (non-r´ ep´et´es)

Cettesectionse consacreaux jeuxo `unjoueurssont enconcurrence.Dansle chapitre2, section2.5,lesnotions debases urlath ´eoriedes jeuxon t´e t´e introduitescommelanotion dejoueur, destrat´egiepure. Nousallonsaus sifixerlesnotationsquel'onconserveradans lasuitedu document. L'ensembledesjoueurssera not´e parlasuite [n]={1,...,n}.Chaquejoueur iaun ensembleS i destrat´ egiespures.Soitm i lacardinalit´ edeS i i =(q i,1 ,q i,2 ,...,q i,m i )corres- pond`aunve cteurdeprobabilit ´esur lesstrat´egiespur es:la strat´egiepure?estchoisie aveclaprobabilit ´e q i, ?[0,1],avec m i ?=1 q i, =1. L'espacedes strat´egiesmixtes dujoueuricorrespond`aunsimplexeque nousnoterons K i .SoitK= n i=1 K i l'espacedess trat´egie smixtes. Observonsquen'importequelle strat´e giepure?peutˆetreconsid ´er´ee commeune strat´egiemixtee tellequele ve cteure estceluiconstitu ´e uniquementdez´ero` al'ex- 39

40CHAPITRE5.JEUXCLASSIQUESEN TH

EORIEALGORITHMIQUEDES JEUX

ceptiondeson ?`eme´el´ ement´etant`a1.Celasignifieaussiquee estuncoin dusimplexe K i D´efinition20(profildestrat´egie smixtes)Unprofildestrat ´egies mixtesQ= (q 1 ,...,q n )estun´ el´ement deKquisp´ ecifielesstrat´egies(pureou mixtes)detous les joueurs:le vecteur deprob abilit´eq i correspond`alastrat´egie mixteutilis´eepar lejoueur i. Ensuivan tlesconventionsclassiquesde lath´ eoriedesjeux,defa¸conabusive, nous

´ecrironsQ

-i ,leprofil Qpriv´edelastrat´egie dujoueur i:Q -i =(q 1 ,...,q i-1 ,q i+1 ...,q n correspondauvecteur destrat ´egiesdetouslesjoueurssaufdujoueuri. Lesjeuxp euven tavoirdescoˆutsal´eatoires: sachantunprofildesstrat´e giesQ?K,

lecoˆ utdechaquejoueuriestlav aleuresp´ er´eeducoˆ ut.Enparticulier,lecoˆutesp´er´epar

lejoueurijouantlastrat´e giepuree estnot´ eec i (e ,Q -i

5.1.1Meille urer´eponse

Lastrat ´egiexdujoueuriparrapport auprofilQestunemeilleurer´eponse,si c i (x,Q -i i (q i ,Q -i )pour toutq i K i .L'ensem ble(compact,convexe,nonvide)de touteslesme illeures r´eponsesdujoueuriparrapport `aQ -i (ensembledesstrat ´egiesdes autresjoueurs)est not´ eeBR i (Q -i Parexemple,consid´ eronsle jeudontlescoˆutssontrepr´esen t´es parlatable 5.1(c'est lemˆ emequeceluiprisenexempledanslec hapitre2,pages 13et 19). joueur2 s 1 s 2 joueur1 s 1 20 s 2 11 joueur1 s 1 s 2 joueur2 s 1 20 s 2 11

Coˆutdujoueur1Coˆutdujoueur2

Tab.5.1-C oˆuts dujeud´ecrit`alapage19

Sanspe rtedeg´en´eralit´e ,supposons quepsoitunr ´eel comprisentre0et1etquele joueur2jouelastrat ´egiemixte (1-p,p),c'est- `a-direqu'iljoueralastrat´egies 1 avecla probabilit´e1-p,etla strat´ egies 2 aveclaprobabilit´ep.Alorsp ourle joueur1,leco ˆut esp´er´edujoueur1est´egal`a1s'iljoue lastrat ´egie pures 2 c'est-`a-direc 1 (s 2 ,(1-p,p))=1.

Sinonilest `a 2-2p.Alors,s i

1 2 1 2 K 1 sip= 1 2 (0,1)si 1 2 >p≥0 Unestrat´ egiemixteestcaract´eris´eepar l'ensemble des strat´egiespures`alaquelle elleattribueune probabilit´ estricteme ntpositive.Cetensemble s'appellelesupport.Par exemple,toutesle sstrat ´egiespuressont desstrat´egiesmixtesdesupportr ´eduit`aun singleton.Deplus,

5.1.JEUXST ATIQUE S(NON-R

EP ET ES)41 Propri´et´e1Unestrat ´egiemixteestunemeilleurer´eponse parr apport `aun ensemblede strat´egiesQsietseulement sitoutes lesstrat ´egiesde sonsupport sontaussides meilleures r´eponsesparrapport`a Q. Enfait, consid´eronsunestrat ´egiemixteayantunsupp ortcon tenantaumoinsdeux

´el´ements?ett.Siune strat´ egie pure?deson supportaunco ˆutplus´elev´ equecelle t,

alorsilest pr´ef ´erablep ourlejoueurdechoisirt`alaplacede?lorsquelastrat´ egie?est choisie.Doncainsiestc onstruiteunes trat´egie mixteay antuncoˆ utplusp etitquecelle ded´ epart. Lapremi `ere´etapepourmod´eliserun syst`emeenc oncurrencepeutˆetrede l'exprimer sousforme dejeu.L'´etap esuivan teestde pr´ediredansquel´etatstableilvaˆetre. JohnNashprouv aitdans [Nash,1950]quetoutjeu poss `edeunesituationd'´ equilibre mixte,quel'on nomme´ equilibredeNash danslaquelleaucun joueurn'aint´e rˆe tuni- lat´eralementdes'´ecarter.Ceconceptd'´equilibre deNashp ourlesjeuxa´et´eunp oint importantdelath´eoriede jeux. 5.1.2

EquilibredeNash

D´efinition21([Nash,1950])Un´equilibredeNashmixteestunpr ofilQ =(q 1 ,···,q n telque ?i,?q i K i onac i (q i ,Q -iquotesdbs_dbs29.pdfusesText_35

[PDF] cours et exercices corrigés de théorie des jeux pdf

[PDF] théorie des jeux dilemme du prisonnier

[PDF] théorie des jeux cours

[PDF] théorie des jeux exemple

[PDF] en amour ecouter son coeur ou la raison

[PDF] coeur photo booth

[PDF] texte au subjonctif passé

[PDF] choisir la bonne unité de masse ce2

[PDF] comparer des longueurs ce1

[PDF] mesurer des longueurs ce1

[PDF] séquence utiliser la règle graduée et léquerre ce2

[PDF] comparer des longueurs ce2

[PDF] estimer des longueurs ce2

[PDF] comment choisir ses lunettes de soleil en fonction de son visage

[PDF] lunette pour visage ovale femme