teoria_jocurilor

UNIVERSITATEA TEHNICĂ �GH. ASACHI� IAŞI FACULTATEA DE AUTOMATICĂ ŞI CALCULATOARE

Teoria jocurilor

Inteligenţă artificială - referat -

Iordache Ciprian-Doru, Leonte Bogdan Nicolae, Ţîmpu Radu Cristian

- 2002/2003 -

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m

Proiect la inteligenţă artificială Teoria jocurilor

________________________________________________________________________________

________________________________________________________________________________

1

Introducere În ziua de azi, calculatoarele executa în mod curent taskuri lungi şi complexe într-un timp

egal cu o fracţiune din timpul în care omul poate executa acelaşi lucru. Indirect, aceast lucru înseamnă că un calculator este un ajutor supus care face ceea ce i se spune să facă. El nu demonstrează nici o urmă de inteligenţă. Întrebarea �oare calculatoarele pot într-adevăr să gândească� a fost o problemă controversată chiar din ziua în care au fost create. Preocuparea specialiştilor de a crea programe "inteligente" (sisteme care prezintă caracteristici asociate cu inteligenţa umană cum ar fi inţelegerea vorbirii, învăţarea, judecata şi rezolvarea problemelor) a condus la apariţia unui domeniu interdisciplinar, cu aplicaţii practice nebănuite sub denumirea generică de inteligenţa artificială.

Inteligenţa artificială ca ştiinţă, are drept scop să confere calculatoarelor o serie de posibilităţi pentru relizarea unor sarcini, pe care decidentul uman (expertul) este capabil să le faca. Această disciplină a fost iniţiată în 1956 de către John McCarthy, Marvin Minsky, Allen Newell şi Herbert Simon de la Dartmouth College, având drept obiectiv formalizarea acţiunii inteligente. O definiţie riguroasă a inteligenţei artificiale simbolice se bazează pe o serie de cunoştinţe concrete ale acestei discipline şi în mod special pe fundamentele logice ale acesteia.

Inteligenţa artificială simbolică a insistat in permanenţa asupra noţiunii de euristică, având contribuţii importante în domeniul limbajelor de programare. Sistemul "Logic Theorist" al lui Newell, Shaw şi Simon a fost în 1956 primul sistem de inteligenţă artificială utilizat în demonstrarea teoremelor din logica propoziţiilor. Pentru realizarea acestui sistem, autorii au creat limbajul IPL (Information Processing Language), al cărui succesor bine cunoscut este limbajul LISP. De asemenea, limbajul PROLOG creat de A. Colmerauer si P. Roussel (1975), a fost realizat de o echipa de cercetători din domeniul inteligenţei artificiale de la Universitatea Luminy din Marseille, bazându-se în mod esenţial pe algoritmul de unificare. Aceste limbaje au avut drept primi utilizatori, cercetătorii din domeniul inteligenţei artificiale de la MIT, care erau frustraţi de lipsa de acces la resursele unui calculator, când doreau acest lucru si au avut ideea conceptului de "time sharing", iar din anul 1960 au demarat proiectul Machine Aided Cognition.

Din punct de vedere economic, inteligenţa artificială este un domeniu important tocmai datorită capacităţii sale de a aborda noi clase de probleme, diferite de cele tratate de informatica clasică, cum ar fi: percepţia, luarea de decizii, planificarea, diagnoza, interpretarea semnalelor, înţelegerea limbajului natural, concepţia. Aceste probleme acoperă activităţi umane dintre cele mai variate şi prezintă particularităţi comune care se bazează în mod fundamental pe exploatarea "inteligentă" a unor mari cantităţi de cunoştinţe, specifice domeniului studiat.

Inteligenţa artificială simbolică poate aborda o mare varietate de domenii: • vederea artificială - ce presupune recunoaşterea formelor, identic cu vederea umană; • robotica - focalizează producerea dispozitivelor mecanice capabile să reproduca mişcarea; • prelucrarea vocii - ce priveşte constituirea şi sinteza vocii umane; • prelucrarea în limbaj natural - înţelegerea şi vorbirea în limbaj natural; • demonstrarea teoremelor - în matematică şi logică;

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

2

• "General Problem Solving" - rezolvarea unei clase generale de probleme exprimate în limbaje formale;

• recunoaşterea formelor - recunoaşterea şi clasificarea diferitelor forme; • învătarea automată - maşini ce acumulează cunoştinţe prin observarea exemplelor; • sisteme bazate pe cunoştinţe; • teoria jocurilor. Dintre toate aceste domenii de activitate ale inteligenţei artificiale, obiectul de studiu al

acestui referat este numai teoria jocurilor. Pentru a putea fi implementat, un joc trebuie reprezentat in aşa fel încât sa fie pe înţelesul

calculatorului. De aceea, un joc poate fi gândit ca un arbore a tuturor stărilor viitoare ale jocului. De exemplu, în cazul unui joc de şah, starea jocului poate fi definită ca aranjamentul pieselor de pe tabla de şah precum şi cine este la rând să facă următoarea mutare. Starea curentă a jocului este rădăcina arborelui. În general, acest nod are numeroşi fii, aceştia fiind toate mutările posibile pe care le poate face jucătorul al cărui rând este, şi aşa mai departe. Fiecare din acest nod reprezintă starea jocului după fiecare mutare a oponentului. Aceste noduri au la rândul lor fii corespunzătoare celei de-a doua mutări a jucătorului curent şi aşa mai departe. Frunzele acestui arbore sunt stările finale ale jocului, stări din care nici o mutare nu mai poate fi făcută deoarece unul din jucători a câştigat, sau poate jocul e remiză (pat în cazul şahului). De fapt, arborele este un graf, deoarece pot fi mai multe mutări posibile dintr-o anumită stare a jocului într-o altă stare particulară.

Mulţi algoritmi au fost descoperiţi, printre cel mai cunoscut fiind algoritmul Minimax sau o versiune mai optimă algoritmul Minimax cu reducerea Alfa-Beta.

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

3

Algoritmul Minimax

Algoritmul MiniMax e un algoritm de căutare într-un arbore. Acest algoritm urmăreşte selectarea celei mai bune mutări pentru calculator într-un joc cu doi jucători. Algoritmul construieşte un arbore cu toate mutările posibile pentru ambii jucători. Acest algoritm este denumit Minimax deoarece pur şi simplu calculatorul face mutarea care-i oferă câştigul maxim, în acelaşi timp asigurându-se că oponentul face mutarea cea mai defavorabilă calculatorului. Deoarece mutările alternează, algoritmul alternează minimizând şi maximizând nivelele arborelui de căutare în mod recursiv.

Întrucât, chiar şi în cazul unui joc simplu, numărul mutărilor posibile creşte exponenţial, şi deoarece în general memoria unui calculator este limitată, acest algoritm face căutarea numai pe o adâncime fixă.

În continuare vom considera un arbore de căutare ipotetic, ca să studiem cum algoritmul Minimax selectează mutarea cea mai bună. Acest exemplu este pentru un joc în care sunt posibile exact două mutări, iar adâncimea maximă de căutare e 4. Observăm că şi în acest caz cu puţine mutări posibile, trebuiesc generate 30 situaţii posibile.

În figura de mai sus nodurile maximizante sunt reprezentate printr-un pătrat iar cele

minimizante printr-un cerc. Să presupunem că următorul jucător este calculatorul şi că în acest moment al jocului

arborele de căutare este cel din figura 1. Rădăcina arborelui ( cel mai de sus nod) este nodul curent şi reprezintă poziţia actuală în joc. Observăm că din această poziţie, calculatorul are numai două

Fig. 1 Arborele de căutare

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

4

mutări posibile A şi B. Momentan ignorăm numerele din interiorul nodurilor, le vom calcula mai tarziu. Pentru început observăm că nodul curent este un nod maximizant, altfel spus, dintre mutările A şi B o vom alege pe cea care ne furnizează valoarea maximă. Următorul nivel din arborele de căutare este corespunzător mutărilor posibile celui de-al doilea jucător, să presupunem omul. Pentru a nu complica lucrurile vom urma numai ramura A a arborelui de căutare. Omul va trebui să aleagă acum între mutările C şi D. Observăm că nodurile sunt reprezentate prin cercuri, aşadar sunt noduri minimizante. Aşadar, vom presupune că omul va alege mutarea care va lăsa calculatorului cea mai mică valoare posibilă. Şi aşa se va continua mai departe în mod recursiv. Cel mai simplu algoritm MiniMax e posibil ca să evalueze recursiv toate cele 16 �frunze� ale arborelui de căutare, apoi va merge înapoi, minimizând valoarea pentru mutările omului şi maximizând mutările calculatorului. După cum observăm, în exemplul nostru cea mai bună mutare pentru calculator este A deoarece valoarea din A este mai mare decât cea din B. Nodul A la rândul lui este un nod minimizant, aşadar va reflecta minimul dintre 10 şi 14. Nodul C maximizează, luând valoarea cea mai mare dintre 9 şi 10. Nodul G minimizează valorile 10 şi 11, şamd.

Conform celor de mai sus, nodul din colţul din stânga, evaluat la 10, este cea mai bună poziţie pe care calculatorul o poate obţine, Astfel încât dacă o luăm în sens invers pe arbore, de jos în sus, prin G şi C şi în final A care e mutarea cea mai bună pe care calculatorul o poate face în final.

Valorile din interiorul nodurilor reprezintă cât de bună e poziţia actuală în cadrul jocului din punctul de vedere a calculatorului. Acest lucru pare foarte uşor dacă beneficiem de luxul de a căuta până la finalul jocului, în acest caz o victorie fiind foarte bună, iar o înfrângere fiind foarte rea. Dar, de cele mai multe ori, în realitate, căutarea în adâncime e limitată, iar în acest caz e se utilizează o funcţie statică de evaluare a poziţie în cadrul jocului care returnează o valoare ce indică cât de bună e această poziţie. În terminologia inteligenţei artificiale, acest număr e numit euristic. În caz că dorim să implememtăm o astfel de euristică, trebuiesc luate în considerate următoarele lucruri: Care sunt elementele interesante ale jocului şi cum trebuie evaluate astfel încât să determinăm dacă o poziţie e mai bună decât alta? Care sunt valorile relative care trebuie asignate fiecărui element? Acest lucru de multe ori necesită o sofisticat analiză a jocului în cauză şi nu întotdeauna acest lucru e uşor.

Algorimul în limbaj pseudocod ar putea fi următorul:

(minimax returnează caloarea pentru o poziţie dată n, adâncimea maximă e d) int minimax(n: node, d: int): if leaf(n) or depth=0 return evaluate(n) if n is a max node v := L for each child of n v' := minimax (child,d-1) if v' > v, v:= v' return v if n is a min node v := W for each child of n v' := minimax (child,d-1) if v' < v, v:= v' return v

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

5

L reprezintă o valoare minimă cu care se iniţializează variabila ce reprezintă costul maxim pentru un nod maximizant, iar W reprezintă o valoare maximă cu care se iniţializează variabila ce reprezintă costul minim pentru un nod minimizant.

Algoritmul MiniMax cu reducerea Alfa-Beta

După cum am mai precizat, arborele de căutare în cazul algoritmului MiniMax poate creşte

foarte mult, astfel încât se utilizează tehnici avansate care să limiteze timpul şi resursele necesare algoritmului de căutare MiniMax. Cea mai uşoară tehnică de acest gen este limitarea adâncimii de căutare. O altă tehnică este aşa-zisa reducere Alfa-Beta

Reducerea Ala-Beta permite realizarea aceleeaşi analize, dar mai eficient, fără pierdere de informaţii. În primul rând, arborele de căutare trebuie parcurs într-o ordine predefinită, să zicem de la stânga spre dreapta, de sus în jos, mai întâi în adincime, sărind (=reducând) peste toate nodurile ce nu pot influenţa determinarea celei mai bune valori. Exemplificarea o vom face tot pe arborele de căutare din figura 2. Pentru început vom sări peste nodul J şi fiii săi, nodurile tip frunză 13 şi 14. Scopul explorării părintelui nodului J este acela de a dacă valoarea nodului A poate fi redusă sub 10, care este valoarea deja stabilită de fiul stâng al nodului A, C. Pornind căutarea de la nodul D, mai întâi vom evalua nodul I, în care vom avea valoarea 14. Acest lucru va determina ca nodul D să aibă cel puţin valoarea 14, indiferent de valoarea posibilă din J. Cum valoarea 14 din D va fi neglijată în favoarea valorii 10 din nodul C, ar fi o pierdere de timp să se evaluez nodul J şi fiii săi. Valoarea din A sigur va fi 10 sau mai mică. Acelaşi argument poate fi folosit şi la evaluarea celui de-al doilea fiu de tip frunză a lui K. Având în vedere faptul căutarea sus-jos, de la stânga la dreapta şi în adâncime mai întâi, în timp ce explorăm nodul K, observăm că în A deja avem valoarea 10. Astfel, K este explorat ca să vedem dacă nu poate furmiza o valoare mai mare ca 10 în B. Dar cum primul fiu al lui K are valoarea 5, se ştie deja că nodul K va furniza valarea maxim 5, deci nu poate furniza o valoare mai mare ca 10 în nodul B, astfel încât ar fi o pierdere de timp să mai evaluăm şi fiul din dreapta al nodului K şi astfel căutarea se mută la nodul L. Similar, cum primul fiu al lui L produce valoarea 4, e ştiut faptul că L poate furniza valoarea maxim 4 părintelui său E, astfel încât nu se mai continuă căutarea şi pentru fiul din dreapta. Totuşi, observăm că în nodul E se propagă valoarea 5 şi nu 2 ca în cazul anterior, dar acest lucru nu contează deoarece, în acest moment, nodul B este nod minimizant şi se observă că poate fi cel mult 5, care nu e mai bun ca valoarea 10 din A, astfel încât nu se va mai parcurge nodul F sau vreunul din fiii săi.

Figura 2. Arborele de căutare în cazul reducerii Alfa-Beta

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

6

În acest caz, algoritmul în limbaj pseudocod ar fi următorul:

{(alfa+beta algor), adâncimea d. * dacă valoarea e mai mică decât min, returnează min. * dacă valoarea e mai mare decât max, returnează max. *) fun minimax(n: node, d: int, min: int, max: int): int = if leaf(n) or depth=0 return evaluate(n) if n is a max node v := min for each child of n v' := minimax (child,d-1,...,...) if v' > v, v:= v' if v > max return max return v if n is a min node v := max for each child of n v' := minimax (child,d-1,...,...) if v' < v, v:= v' if v < min return min return v

} În cazul reducerii Alfa-Beta, trebuie să mai facem o precizare. Eficienţa acestui algoritm

depinde de ordinea în care succesorii unui nod sunt examinaţi. Astfel, la un nod minimizant trebuie sa considerăm nodurile de la cel mai mic la cel mai mare scor, iar la un nod maximizant de la cel mai mare la cel mai mic scor. Se poate demonstra că în cele mai favorabile circumstanţe, MiniMax cu reducere Alfa-Beta analizează tot atâtea situaţii ca şi MiniMax fără reducere Alfa-Beta dar la o adâncime dublă.

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

7

Echilibrul Nash

Cel mai bun mod de a aborda �Echilibrul Nash� este folosind exemple. Fie N jucatori cu un numar finit de strategii. Ex:

• 2 jucatori ( Ion, Maricica) • 2 strategii ( fiecare jucător are două variante (opţiuni): strategia 1 şi strategia 2)

Presupunem că amândoi jucătorii au ales una dintre variante fara a şti ce a ales adversarul. Un mod convenabil de a reprezenta un astfel de joc este matricea câştigurilor:

Maricica Strategia 1 Strategia 2

Strategia 1 a11,b11 a12,b12 Ion Strategia 2 a21,b21 a22,b22

Unde aij este caştigul lui Ion dacă Ion joacă strategia i şi Maricica joacă strategia j, iar bij este câştigul Maricicăi dacă Ion joacă strategia i si Maricica joacă strategia j. Deci, a-urile sunt caştigrile lui Ion iar b-urile sunt caştigurile Maricicăi. Presupunem că fiecare jucător preferă câştigurile cele mai mari, fara a ţine cont de câştigurile celuilalt. Fie Jocul 1


Strategia 1 0,1 2,6 Ion Strategia 2 2,0 3,1

Cum ar trebui să joace Ion şi Maricica? Se observă că indiferent de strategia aleasă de Maricica, Ion va alege strategia 2. De ce? Pentru ca un câştig de 2 sau 3 este mai bun decât un câştig de 0 sau 2. Cand un jucător alege strategia j indiferent de alegerea celuilalt, spunem că j este strategia lui dominantă. Strategia 2 este strategia dominantă a Maricicăi. La fel si pentru Ion. Deci strategia de echilibru este (2,2) cu un câştig de (3,1). Un prim rezultat ar fi:

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

8

Într-un joc cu 2 jucători, unde fiecare are 2 strategii, dacă ambii jucători au o strategie dominantă, echilibrul se obtine atunci când jucătorii joaca strategiile dominante. Jocul 2


Strategia 1 0,2 2,1 Ion Strategia 2 2,0 3,1

Strategia dominantă a lui Ion este strategia 2. Maricica nu are o strategie dominantă. Cum putem defini echilibrul in acest caz? Strategiile alese reprezintă echilibrul dacă Ion îşi alege strategia cunoscand strategia aleasă de Maricica, si invers. Obţinem echilibrul Nash atunci când fiecare jucător maximizează câştigul cunoscând strategia aleasă de oponent. Echilibrul pentru jocul anterior se realizează în (2,2) cu un caştig de (3,1) Definiţie echivalentă a echilibrului Nash pentru un joc cu 2 jucători:

• presupunerile fiecărui jucător in privinţa alegerii făcute de adversar sunt corecte • fiecare jucător alege strategia care maximizează câstigul său considerând că oponentul

va aplica strategia presupusă de el În incercarea de a atinge echilibrul Nash, care ar fi procesul de alegere a strategiei? Fiecare jucător se va gândi la o strategie maximizantă pentru adversar, ştiind că celălalt jucător este inteligent şi raţional. Dupa găsirea acestei strategii, jucătorul va căuta cea mai buna strategie pentru a contracara (presupusa) strategie adversarului. Jocul 3


Strategia 1 1,3 .5,1 Ion Strategia 2 0,0 4,2

Nici un jucător nu are o strategie dominantă. Există doua echilibre Nash: (1,1) şi (2,2)

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

9

Teorema: Nu exista un joc cu urmăoarele 4 proprietăţi:

• 2 jucători • fiecare jucător are 2 strategii • nici un jucător nu are o strategie dominantă • există numai un echilibru Nash în strategii pure

Demonstraţia se realizează prin reducere la absurd. (consultaţi bibliografia) Echilibrul Nash în strategii mixte Jocul 4

Oameni săraci cu copii

Muncă remunerată Refuz de a munci

Asigură ajutor pentru copii 3,2 -1,3 Statul

Nu asigură ajutor pentru copii -1,1 0,0

Este usor de observat că nu exista un echilibru Nash. Nu există un echilibru Nash dacă dorim ca fiecare agent să aleagă o strategie şi nu probabilitatea de a aplica o strategie. Poate există totuşi un echilibru dacă fiecare agent alege probabilitatea unei strategii. Ce este probabilitatea de a alege o strategie? Presupunem că alegerea statului (să ofere ajutor pentru copii sau nu) este o variabilă aleatoare din perspectiva statului (statul dă cu zarul) iar alegerea omului sărac (de a munci sau nu) este tot o variabilă aleatoare din perspectiva săracului ( saracul da şi el cu zarul) unde: p = probabilitatea ca statul să ofere ajutor pentru copii. ( 1 � p) = probabilitatea ca statul să nu ofere ajutor pentru copii. q = probabilitatea ca săracul să muncească. ( 1 � q) = probabilitatea ca săracul să nu muncească. Ce înseamnă că guvernul alege p iar saracul alege q? Dacă guvernul alege p, nu înseamnă că oferă sau nu oferă ajutor pentru copii unui anumit individ, ci că oferirea acest ajutor se bazează pe o alegere aleatoare dintr-o distribuţie unde probabilitatea de a oferi ajutor este egală cu p.

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

10

Deci, în acest nou joc, săracul alege probabilitatea de munci, nu dacă munceste sau nu, iar statul alege probabilitatea de a oferi ajutor pentru copii. Strategiile în care agenţii aleg probabilităţile p şi q se numesc strategii mixte. Dacă p şi q sunt restrictionaţi la valorile 0 şi 1, strategiile sunt �pure�. Echilibrul Nash în strategii mixte: La echilibru, cunoscându-se probabilitatea ca statul să ofere ajutor pentru copii, săracul nu doreste sa-şi schimbe probabilitatea de a munci şi similar, cunoscându-se probabilitatea ca săracul să muncească (q), statul nu doreşte să-şi schimbe probabilitatea de a oferi ajutor pentru copii. Cu alte cuvinte:

• presupunerile sunt corecte: p=πp şi p=πq unde πp este valoarea presupusă de sarac a probabilităţii ca statul să ofere ajutor pentru copii, iar πq este valoarea presupusă de stat a probabilităţii ca săracul să muncească. • Statul alege p astfel încât să-şi maximizeze beneficiile ştiind valoarea presupusă a

probabilităţii ca săracul să muncească iar saracul alege q astfel încât să-şi maximizeze beneficiile stiind valoarea presupusă a probabilităţii ca statul să ofere ajutor pentru copii.

Pentru a decide dacă jocul precedent are un echilibru în strategiile mixte, trebuie determinate beneficiile aşteptate de fiecare agent.

Oameni săraci cu copii

Muncă remunerată Refuz de a munci

Asigură ajutor pentru copii 3,2 -1,3 Statul

Nu asigură ajutor pentru copii -1,1 0,0

Ebgov = pπq3 + p(1 - πq)(-1) + (1 � p) πq(-1) + (1 � p)(1 - πq)0

= 5pπq - p - πq

Ebpauper = pπp2 + (1 � p)πp3 + q(1 - πp) 1 + (1 � q)(1 - πp)0

= -2qπp + q + 3πp

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

11

Statul doreşte să aleagă un p astfel încât sa maximizeze Ebgov iar săracul doreşte să găsească un q astfel încât să maximizeze Ebpauper. Începem cu problema de maximizare a statului. δEbgov/δp=5πq-1 Observăm că derivata funcţiei de obiectiv a statului nu mai contine variabila p. Singura solutie în intervalul (0,1) se obţine dacă πq=0.2 si pentru această valoare, statului nu-i mai pasă ce valoare va alege pentru p.

În acelaşi mod se obţine πp=0.5 Ce-am descoperit? Dacă p = 0.5 săracului nu-i pasă ce valoare va alege pentru q, iar dacă q=0.2 statului nu-i mai pasă ce valoare va alege pentru p. Deci p=0.5, q=0.2 este un echilibru în strategia mixtă pentru jocul 4. Cum ar trebui interpretat echilibrul intr-o strategie mixtă? Evident, nu este la fel de intuitiv ca echilibrul în strategiile pure. Un argument împotriva echilibrului în strategiile mixte este afirmaţia că agenţii nu îşi aleg uneori la întamplare acţiunile în viaţa de zi cu zi. Un argument mai puternic împotriva echilibrului în strategiile mixte îl constituie faptul că la echilibru, îi este indiferent ce actiunea pe care o alege. De fapt, în exemplul precedent am arătat că statului nu-i pasă dacă oferă ajutor pentru copii atât timp cât probabilitatea ca săracul să muncească este 0.2, iar săracului nu-i pasă dacă munceşte sau nu, atât timp cât probabilitatea ca statul să ofere ajutor pentru copii este 0.5. Dar dacă oricare dintre agenţi decide să-şi schimbe probabilitatea, echilibrul se prăbuşeşte.

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

12

În acest sens, echilibrul în strategiile mixte este criteriu destul de slab.

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

13

Optimizarea Pareto

Economistul italian Vilfredo Pareto, 1848-1923, a fost unul din liderii Scolii Lausanne si un ilustru membru al �celei de-a doua generatii� a revolutiei neoclasice. In cursul vietii a elaborat diverse teoreme, in special in domeniul economic si social. Printre cele mai cunoscute este cea a veniturilor distribuite. El argumenta ca in toate tarile si timpurile, ditributia venitului si bunastarii urmareste un tipar logaritmic regulat care poate fi sintetizat de formula:

log N = log A + m log x unde N este numarul de salariati care obtin venituri mai mari decat x, si A si m sunt constante. De-a lungul anilor, Legea lui Pareto s-a dovedit a fi remarcabil de elastica in studiile empirice. De asemenea, Teoria lui Pareto despre societate pretinde ca exista o tendinta de a se intoarce la echilibru cand un unmar egal de persoane de Clasa I si Clasa II sunt prezente in elita conducatoare. Ocazional, cand devine prea inclinata intr-o parte, o elita va fi inlocuita in masa de o alta. Daca sunt prea multe persoane de Clasa I in elita conducatoare, inseamna ca violenta si conservatoarea Clasa II se afla in esaloanele inferioare, dorind si fiind capabile sa preia puterea cand Clasa I greseste prea tare prin siretenie si coruptie. Daca elita conducatoare este compusa in general din persoane din Clasa II, atunci va cadea intr-o mizerie birocratica, ineficienta si reactionara, o prada usoara pentru Clasa I, mai calculata si mobila. (Clasa I, Clasa II = politica de stanga, dreapta) Reamintim cateva notiuni generale: teoria jocurilor utilizeaza matrici de castiguri pentru a reprezenta utilitatea pe care doi jucatori (A si B) se asteapta sa o primeasca in conditiile date.

persoana A a b a 1,2 2,3 persoana B b 4,5 5,6

O strategie S este definita ca un set de actiuni pe care le pot avea toti jucatorii. In acest caz o strategie de (a,b) ar da persoanei B 2 si persoanei A 3. De asemenea ne referim la strategia persoanei B in S ca S(persoana B), ceea ce reprezinta �a� in cazul nostru. In mod general, jucatorii se presupune ca au cunostinte generale despre matrice. Adica persoana A cunoaste ca persoana B cunoaste ca persoana A cunoaste ... numerele din matricea castiguilor. Intrebarea care le punem sunt: ce vor face jucatorii? ce ar trebui sa faca jucatorii? Presupunem ca jucatorii sunt rationali (maximizarea utilitatii). Presupunem ca ei participa deoarece altfel le-ar aduce castiguri mai mici (rationalitate individuala). O strategie S se spune ca este stabila daca nici un jucator nu este motivat sa se abata de la ea.

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

14

In teoria jocurilor, din teoremele dezvoltate de Pareto s-a adoptat axioma Pareto-optimitatii: o strategie S este Pareto-optimal daca nu exista nici o strategie S� in care cel putin unui jucator sa nu o duca mai bine si nici un jucator nu o duce mai rau decat in S. In exemplele de la echilibrul Nash, eficienta poate fi determinata prin notiunea de Pareto-optimal. Ca si la echillibrul Nash, teorema se intelegel cel mai bine prin urmarirea unor exemple. Un prim exemplu a unui echilibru ce este Pareto-optimal poate fi jocul dilema prizonierilor, cu matricea costurilor:

persoana A

Strategia 1 (se confeseaza)

Strategia 2 (nu se confeseaza)

Strategia 1 (se confeseaza) 5,5 2,10 persoana B

Strategia 2 (nu se confeseaza) 10,2 3,3

Daca ambele persoane marturisesc crima (nestiind ce va face cealalta persoana) amandoua primesc o condamnarede 5 ani.

Daca numai o persoana marturiseste (�am facut-o impreuna�), va obtine o pedeapsa mai scurta, pentru cooperare, si cealalta persoana va optine o pedeapsa mai lunga cu o condamnare bazata pe evidente solide. Daca nici una dintre persoane nu marturiseste, e mult mai dificil pentru stat sa prezinte cazul si condamnarile vor fi mai mici. In acest joc, amandoua persoanele vor marturisi, (strategia dominanta pentru amandoua), in timp ce solutia Pareto-optimala ar fi ca nici unul dintre ei sa nu marturiseasca. Extinderile in acest caz vor fi natura argumentelor, constrangerile, sau intelegerile secrete dintre cele doua persoane, pentru a se gasi o solutie Pareto-optimala. Teoriticianul jocului va cauta sa defineasca in ce mod aceste intelegeri vor fi suportate si ce note de constrangere vor fi impuse. Impunerile pot fi in forma unei razbunari daca unul din jucatori renunta la intelegere sau razbunarea devine posibila prin repetarea jocului.

* * *

Un alt exemplu din care se poate arata un rezultat Pareto-optimal este �prieteni cu preferinte asimetrice� Vom considera doua persoane, Ion si Maricica. Ion o place pe Maricica, dar Maricica nu-l place pe Ion la fel de mult. Fiecare cunoaste aceasta, si nici unul dintre ei nu vrea sa-l sune pe celalalt pana nu se decide ce va face dupamiaza: sa stea acasa la ei sau sa mearga la piscina din cartier. Matricea castigurilor:

Maricica Acasa Piscina

Acasa 2,0 2,1 Ion Piscina 3,0 1,2

Biblio

teca

virtu

ala d

e Inte

ligen

ta ar

tifici

ala

http

://eu

reka

.cs.tu

iasi.r

o/~fle

on/bvia

.htm

C

oordonat

or: Flo

rin L

eon

florin

leon@

yahoo.co

m


________________________________________________________________________________

________________________________________________________________________________

15

In acest caz, strategia cea mai buna a Maricicai depinde de ceea ce face Ion. Dar daca presupune ca Ion este rational, va gandi ca el va decide sa nu stea acasa, pentru ca a merge la piscina e o strategie dominanta pentru el. Stiind aceasta, ea se poate decide sa stea acasa (deoarece 2>1). Aceasta se cheama dominare iterata. In acest exemplu, Maricica primeste o utilitate mai mare ca a lui Ion din cauza preferintelor lor relative, si Ion primeste o utilitate mai mica decat ar fi avut daca Maricica ar fi vrut sa fie cu el. In acest exemplu, Piscina-Acasa (3,0), Acasa-Piscina (2,1) si Piscina-Piscina (1,2) sunt toate rezultate (strategii) Pareto-optimal.

* * *

Un exemplu asemanator: Ion si Vasile prefera amandoi sa fie in aceleasi locuri (sa inoate sau sa mearga in excursie) dar preferintele lor difera referitor la locul unde fiecare trebuie sa fie. Ion ar prefera sa mearga la inot, iar Vasile ar prefera sa mearga in excursie. Forma normala arata asa:

Vasile Inot Excursie

Inot 3,2 1,1 Ion Excursie 1,1 2,3

Acest joc are trei echilibre Nash: Inot-Inot, Excursie-Excursie si (Inot,2/3;Excursie,1/3)- (Inot,1/3;Excursie,2/3). Se observa ca strategia mixa difera pentru fiecare jucator in parte in al treilea echilibru: fiecare se duce la activitatea sa preferata cu o probabilitate de 2/3. Toate aceste echilibrele sunt Pareto-optimal de data aceasta.

teoria_jocurilor

Documents

Transcript of teoria_jocurilor