Proiect Teoria Jocurilor [PDF]

Zitiervorschau

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

Proiect Teoria Jocurilor

Profesor coordonator: Zamfir Ionela Cătălina Student: Bărbuță Anamaria-Bianca Grupa 1072 Seria B

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

Cuprins 1.

2.

3.

Jocuri statice în informație completă.............................................................................................3 1.1

Problema 1.............................................................................................................................3

1.2

Problema 2.............................................................................................................................5

1.3

Problema 3.............................................................................................................................7

Jocuri dinamice în informație completă.........................................................................................9 2.1

Problema 1.............................................................................................................................9

2.2

Problema 2...........................................................................................................................10

2.3

Problema 3...........................................................................................................................12

2.4

Problema 4...........................................................................................................................14

Jocuri statice în informație incompletă........................................................................................16 3.1

Problema 1...........................................................................................................................16

3.2

Problema 2...........................................................................................................................17

3.3

Problema 3...........................................................................................................................19

Bibliografie..........................................................................................................................................21

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

1. Jocuri statice în informație completă 1.1 Problema 1 În perioada stării de urgență din România se impune limitarea și chiar interzicerea circulației persoanelor în mod nejustificat în anumite zone. Deoarece lui Andrei îi este indiferent de această stare de urgență, el îl cheamă pe Mihai în parc pentru a se vedea. Mihai este conștient că poliția îi poate prinde și amenda, însă îi surâde ideea de a se vedea cu prietenul lui. O dată ajunși în parc, poliția îi oprește și le cere actele. Dacă amândoi refuză să se legitimeze, atunci ei vor fi amendați cu suma de 3 mii lei fiecare. Dacă Andrei se legimitează, iar Mihai nu, atunci Andrei va fi amendat doar cu o mie de lei, iar Mihai cu 4 mii de lei. Dacă Mihai se legitimează și Andrei nu, atunci Mihai va fi amendat cu doar o mie de lei, iar Andrei cu 4 mii de lei. Dacă amândoi se legitimează, atunci ei vor fi amendați cu 2 mii de lei fiecare. Se cere: a) Descrieți jocul sub formă normală prin intermediul matricei câștigurilor. b) Determinați echilibrul Nash prin algoritmul maximizării câștigurilor relative. c) Determinați echilibrul jocului prin eliminarea strategiilor dominate. Rezolvare:

a) Jocul se desfășoară astfel: dacă Andrei se legitimează în fața poliției, atunci el primește o amendă de 2 mii de lei, dacă și Mihai alege să facă asta, sau o mie de lei dacă Mihai refuză. Dacă Andrei refuză să se legitimeze, atunci el primește o amendă de 4 mii de lei dacă Mihai se legitimează, și 3 mii de lei fiecare dacă Mihai nu se legitimează. Matricea câștigurilor este: Mihai

Andrei

L NL

L

NL

-2 , -2

-1 , -4

-4 , -1

-3 , -3

b) Rezolvăm problema prin algoritmul maximizării câștigurilor relative:

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

Mihai

Andrei

L NL

-

-

-

-

L

NL

-2 , -2

-1 , -4

-4 , -1

-3 , -3

Dacă Andrei crede că Mihai se va legitima, atunci îi rămâne de ales între a se legitima la rândul său și fiind amendat cu 2 mii de lei, sau a nu se legitima și a fi amendat cu 4 mii de lei.  max{-2,-4}=-2. Subliniem în tabel răspunsul cu pierderea cea mai mică, și anume -2. Dacă Andrei crede că Mihai nu se va legitima, atunci îi rămâne de ales între a se legitima și fiind amendat cu o mie de lei, sau a nu se legitima la rândul său și a fi amendat cu 3 mii de lei.  max{-1,-3}=-1. Subliniem în tabel răspunsul cu pierderea cea mai mică, și anume -1. Dacă Mihai crede că Andrei se va legitima, atunci îi rămâne de ales între a se legitima la rândul său și fiind amendat cu 2 mii de lei, sau a nu se legitima și a fi amendat cu 4 mii de lei.  max{-2,-4}=-2. Subliniem în tabel răspunsul cu pierderea cea mai mică, și anume -2. Dacă Mihai crede că Andrei nu se va legitima, atunci îi rămâne de ales între a se legitima și fiind amendat cu 1 mii de lei, sau a nu se legitima la rândul său și a fi amendat cu 3 mii de lei.  max{-1,-3}=-1. Subliniem în tabel răspunsul cu pierderea cea mai mică, și anume -2. Se obține echilibrul Nash în cășuța în care ambele elemente au fost subliniate. Varianta optimă pentru ambii băieți este de a se legitima în fața poliției și a fi amendați cu 2 mii de lei fiecare.

c) Pentru a obține echilibrul jocului prin eliminarea strategiilor dominate, vom testa cele mai mari câștiguri ale lui Andrei. Astfel, dacă Andrei se legimitează în fața poliției, amenda va fi mai mică în comparație cu cea pe care o va primi dacă nu se va legitima: -2>-4 și -1>-3, deci îi este optim să se legitimeze întotdeauna. Reducem mai departe dimensionalitatea matricei câștigurilor. Mihai

Andrei

L

L

NL

-2 , -2

-1 , -4

Având această informație, lui Mihai îi mai rămâne să se legitimeze și să primească o amendă de 2 mii de lei, sau să nu se legitimeze și să primească o amendă de 4

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

mii de lei. Deci el va prefera să se legitimeze. Astfel, cei doi aleg să se legitimeze și obținem echilibrul jocului: Mihai L Andrei

L

-2 , -2

1.2 Problema 2 Părinții Mariei și Adinei s-au gândit să le facă cadou de ziua lor o vacanță în afara țării. Maria preferă să meargă într-o vacanță în care să se poată relaxa pe plajă și citi o carte, pe când Adina ar preferă o vacanță plină de aventuri în natură. Astfel, Maria propune insula grecească Santorini, iar Adina propune Maroc. Câștigurile acestora exprimate în puncte de dezamăgire sunt date în tabelul de mai jos: Maria Santorini Adina

Maroc

9,0

0,6

0 , 10

9,0

Să se determine echilibrul și mixte.

Santorini Maroc

jocului atât prin strategii pure, cât

Rezolvare:

Strategii pure: algoritmul maximizării câștigurilor relative Maria Santorini Adina

Maroc

9,0

0,6

0 , 10

9,0

Santorini Maroc

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

-

-

-

-

Dacă Adina crede că Maria va alege Santorini, atunci Adinei îi rămâne de ales între Santorini cu câștigul de 9 puncte, fiind foarte dezamăgită, iar dacă alege Maroc, va aduna 0 puncte.  max{9,0}=9 . Dacă Adina crede că Maria va alege Maroc, atunci Adinei îi rămâne de ales între Santorini cu câștigul de 0 puncte, iar dacă alege Maroc, va aduna 9 puncte.  max{0,9}=9 . Dacă Maria crede că Adina va alege Santorini, atunci Mariei îi rămâne de ales între Santorini cu câștigul de 0 puncte, iar dacă alege Maroc, va aduna 6 puncte.  max{0,6}=6 . Dacă Maria crede că Adina va alege Maroc, atunci Mariei îi rămâne de ales între Santorini cu câștigul de 10 puncte, iar dacă alege Maroc, va aduna 0 puncte.  max{10,0}=10 . Observăm că nu există nici un punct de echilibru.

Strategii mixte: Considerăm că Adina crede că Maria alege Santorini cu o probabilitate q și Maroc cu o probabilitate 1-q, iar Maria crede că Adina alege Santorini cu o probabilitate p și Maroc cu o probabilitate 1-p. Câștigul așteptat, dacă Adina alege Santorini, este media următoarei loterii: L1 :

0 (q91−q ) => E(L ) = 9q + 0*(1 – q) = 9q 1

Câștigul așteptat, dacă Adina alege Maroc, este media următoarei loterii: L2 :

9 (q01−q ) => E(L ) = 9 – 9q 2

Câștigul așteptat, dacă Maria alege Santorini, este media următoarei loterii: L3 :

( 0p 1−10p ) => E(L ) = 10 – 10p 3

Câștigul așteptat, dacă Maria alege Maroc, este media următoarei loterii: L4 :

( 6p 1−0 p ) => E(L ) = 6p + 0*(1 – p ) = 6p 4

La optim, Adina și Maria trebuie să fie indiferente: E(L1) = E(L2) => 9q = 9 – 9q => 18q = 9 =>

q=1 /2 {1−q=1/2

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

E(L3) = E(L4) => 10 – 10p = 6p => 10 = 16p =>

{1−p=5/8 p=3 /8

 Echilibrul : {( 1/2 ; 1/2 ) , ( 5/8 , 3/8 )}

1.3 Problema 3 În dimineața zilei de luni, soții Popescu se decid să facă curat în casă. Ei au de curățat sufrageria (S), baia (W) și bucătăria (B). Sufrageria este mult mai ușor de curățat în echipă decât individual, iar satisfacția va fi maximă. Baia, fiind mică, este suficient să fie curățată de o singură persoană. Câștigurile jocului sunt reprezentate în figura de mai jos: Soția S S Soțul

Se cere:

W

B

10,10 1,8

1,4

8,1

6,6

8,7

4,1

7,8

4,4

W B

a) Să se descrie jocul sub formă normală. b) Să se determine echilibrele Nash în strategii pure. c) Există echilibru în strategii mixte? Dacă da, care va fi acesta? Rezolvare: a) Jucătorii în cadrul acestei probleme sunt soțul și soția. Strategiile acestora sunt reprezentate de curățarea sufrageriei (S), băii ( W) și bucătăriei (B). Si = {S,W,B}, i = 1,2. Câștigurile sunt indicate în matricea câștigurilor de mai sus. Dacă cei doi soți își vor coordona deciziile, atunci ei vor avea câștiguri de 10 unități,6 unități și respectiv 4 unități pentru curățenia în sufragerie, baie și bucătărie. b) Strategii pure: O strategie pură este reprezentată de eliminarea strategiilor dominate. Pentru asta, verificăm dacă există strategii dominate prin compararea câștigurilor aduse de cele 3 trategii: U1(S,*) = (10, 1, 1); U1(W,*) = (8, 6, 8); U1(B,*) = (4, 7, 4). Observăm că nu putem aplica algoritmul eliminării strategiilor dominate deoarece acestea nu există. Pentru jocul 2 se aplică același raționament deoarece jocul este simetric.

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

U2(S,*) = (10, 1, 1); U2(W,*) = (8, 6, 8); U2(B,*) = (4, 7, 4). O altă strategie pură este reprezentată de algoritmul determinării celui mai bun răspuns. Soția S S Soțul

-

-

-

-

-

-

Dacă

W

B

10,10 1,8

1,4

8,1

6,6

8,7

4,1

7,8

4,4

W B soțul crede că soția va alege să facă curat în sufragerie, atunci cel mai convenabil îi este

să facă și el curat în sufragerie.  max{10, 8, 4} = 10. Dacă soțul crede că soția va alege să facă curat în baie, atunci cel îi este să facă curat în bucătărie.  max{1, 6, 7} = 7. Dacă soțul crede că soția va alege să facă curat în bucătărie, convenabil îi este să facă curat în baie.  max{1, 8, 4} = 8. Dacă soția crede că soțul va alege să facă curat în sufragerie, convenabil îi este să facă și ea curat în sufragerie.  max{10, 8, 4}=10 . Dacă soția crede că soțul va alege să facă curat în baie, atunci cel îi este să facă curat în bucătărie.  max{1, 6, 7}=7 . Dacă soția crede că soțul va alege să facă curat în bucătărie, convenabil îi este să facă curat în baie.  max{1, 8, 4}=8 .

mai convenabil atunci cel mai atunci cel mai mai convenabil atunci cel mai

Astfel, vom avea trei echilibre în strategii pure, respectiv (S,S), (W,B) și (B,W). Cei doi soți vor face ori împreună curat în sufragerie, ori unul va face în baie iar celălalt în bucătărie. c) Strategii mixte: Considerăm că jucătorul 1, soțul, va avea următoarele probabilități pentru cele 3 strategii: p1, p2, 1-p1-p2, iar jucătorul 2, soția, va avea următoarele probabilități: q1, q2, 1-q1-q2. pi,qi  [0,1]. Câștigurile așteptate ale soțului sunt următoarele: L1 :

(q101 q12 1−q 11−q 2) => E(L ) = 10q + q + 1 – q – q = 9q + 1 1

1

2

1

2

1

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

L2 :

(q81 q62 1−q 81−q 2) => E(L ) = 8q + 6q + 8 – 8q – 8q = 8 – 2q

L3 :

(q41 q72 1−q 41−q 2) => E(L ) = 4q + 7q + 4 – 4q – 4q = 4 + 3q

2

3

1

1

2

2

1

1

2

2

2

2

La optim cei doi soți trebuie să fie indiferenți. La echilibru avem E(L1) = E(L2) = E(L3). 8 – 2q2= 4 + 3q2 => 4 = 5q2 => q2 = 4/5 9q1 + 1 = 8 – 2q2 => 9q1 = 7 – 2*4/5 => q1 = 3/5 Soluția nu convine jocului deoarece q1 + q2 > 1. Pentru soție, soluția va fi aceeași deoarece jocul este simetric. Astfel, putem spune că jocul admite echilibru doar în strategii pure.

2. Jocuri dinamice în informație completă 2.1 Problema 1 În pauza dintre cele două ore matematică, doi colegi, Alex și Ionuț, aleg să se joace Conquiztador, un joc de inteligență. Pentru a pune stăpânire pe unul din teritoriile adversarului, participanții trebuie să răspundă la întrebări cu două variante de răspuns. Cel care va alege primul va fi Alex. Dacă amândoi vor alege același răspuns, Alex va câștiga. În caz contrar, va câștiga Ionuț. În caz de câștig, valoare acestuia va fi de 8, iar în caz contrar, de -3. Se cere: a) Să se descrie jocul dinamic. b) Să se determine echilibrul jocului dinamic în informație completă.

Rezolvare: a) Jucătorii în cadrul acestei probleme sunt Alex și Ionuț. Strategiile acestora sunt reprezentate alegerea primei sau celei de-a doua variante de răspuns.

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

Ordinea în care sunt luate deciziile: Mai întâi va alege Alex, apoi Ionuț. Câștigurile se regăsesc în figura de mai jos, în dreptul nodurilor terminale.

(30 ) (−33 ) (08 ) (−38 )

-

-

-

b) Pentru rezolvarea problemei, vom aplica algoritmul inducției recursive, adică analizăm jocul pornind de la ultima etapă. Atât Alex, cât și Ionuț sunt jucători raționali, și deci vor alege acele decizii care le vor aduce câștiguri maxime. Dacă Ionuț consideră că Alex va alege varianta 1 de răspuns a întrebării, atunci are de ales între varianta 1 de răspuns și varianta 2: max{0, 3} = 3, îngroșând arcul corespunzător. Dacă Ionuț consideră că Alex va alege varianta 2 de răspuns a întrebării, atunci are de ales între varianta 1 de răspuns și varianta 2: max{8, -3} = 8, îngroșând arcul corespunzător. Alex, știind ce va alege Ionuț, are de ales între varianta 1 de răspuns și varianta 2: max{-3, 0} = 0, îngroșând arcul corespunzător. Se formează astfel un drum de la primul nod pana la ultimul. Astfel, putem spune că Alex alege varianta 2 de răspuns, iar Ionuț varianta 1 de răspuns.

2.2 Problema 2 Pentru a sărbătorii ziua de Valentine’s Day, Andra și Mircea își dau întâlnire la film. Cei doi au de ales între a viziona filmele: Crazy Stupid Love(C), The Lucky One(L), The Great Gatsby(G). Toate cele 3 filme sunt cu tematică romantică, iar Mircea și Andra nu pot cădea de acord asupra unuia. Pentru a nu se certa, Andra va alege prima, urmată de Mircea care va alege altceva, pentru a ajunge în final să vadă filmul neales de vreunul din ei. Ordinea preferințelor Andrei sunt: The Lucky One, Crazy Stupid Love și The Great Gatsby, pe când

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

cele ale lui Mircea sunt fix invers. Câștigul asociat filmului favorit este 10, pentru următorul loc este 5, iar pentru fimul cel mai puțin preferat, câștigul este 1. Se cere: a) Să se scrie forma normală și cea extinsă a jocului. b) Să se determine echilibrul perfect în subjoc. c) Să se determine echilibrul Nash pentru forma normală a jocului. Rezolvare: a) Forma normală a jocului este reprezentată de un tabel 8x3. Strategiile Andrei sunt (C, L, G), iar ale lui Mircea sunt ((LCC), (LGC), (LCL), (LGL), (GCC), (GGC), (GCL), (GGL). Matricea câștigurilor este umătoarea: Mircea (LCC) (LGC) (GCL) (GGL)

C Andra

L G

(LCL)

(LGL)

(GCC)

(GGC)

1,10

1,10

1,10

1,10

5,5

5,5

5,5

5,5

1,10

10,1

1,10

10,1

1,10

10,1

1,10

10,1

5,5

5,5

10,1

10,1

5,5

5,5

10,1

10,1

Forma extinsă:

1

5 10

1 5

10

10

5 1

10 5

1

b) Pentru a determina echilibrul jocului dinamic, vom aplica algoritmul inducției recursive. Pornind de la faptul că Andra alege filmul Crazy Stupid Love, Mircea va avea de ales între celelalte două, iar acesta alege The Lucky One cu câștigul de 10. Dacă Andra alege The Lucky One, atunci Mircea alege Crazy Stupid Love, cu câștigul de 10, iar dacă Andra alege The Great Gatsby, Mircea alege Crazy Stupid Love, cu câștigul mediu de 5. În final, cei doi vor refuza mereu filmul preferat al celuilalt și vor urmări filmul care le aduce satisfacție medie amândurora, adică Crazy Stupid Love, cu câștigul de 5 unități.

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

c) Echilibrul Nash pentru forma normală a jocului prin algoritmul celui mai bun răspuns:

Mircea (LCC) (LGC) (GCL) (GGL)

C Andra

L G

(LCL)

(LGL)

(GCC)

(GGC)

1,10

1,10

1,10

1,10

5,5

5,5

5,5

5,5

1,10

10,1

1,10

10,1

1,10

10,1

1,10

10,1

5,5

5,5

10,1

10,1

5,5

5,5

10,1

10,1

Soluția cea mai convenabilă este (G,C).

2.3 Problema 3 Pentru ziua de 1 mai, două grupuri de prieteni,fete și băieți, doresc să facă un grătar la iarbă verde. Fetele decid să vină cu mâncarea, iar băieții cu băutura. La grătar se vor mânca mici(M) și aripioare de pui(A), iar de băut se va bea bere(B) și vin(V). Băieții sunt de acord că berea merge cu micii, iar asta este preferința lor, pe când fetele spun că aripioarele sunt mai delicioase cu un pahar de vin, fiind preferința lor. Jocul în forma sa extinsă este următorul:

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

Se cere: a) Să se determine echilibrul jocului în informație imperfectă. Rezolvare: a) Jocul în informație incompletă poate fi analizat ca un joc static, fără a cunoaște istoria jocului, luând deciziile în mod simultan. Matricea câștigurilor va fi următoarea: Fetele M Băieții

B V

-

-

-

-

A

5,4

2,2

3,3

4,5

Dacă băieții cred că fetele vor cumpăra mici, atunci ei vor avea de ales între a cumpăra bere sau vin.  max{ 5, 3} = 5. Băieții vor cumpăra bere. Dacă băieții cred că fetele vor cumpăra aripioare de pui, atunci ei vor avea de ales între a cumpăra bere sau vin.  max{ 2, 4} = 4. Băieții vor cumpăra vin. Dacă fetele cred că băieții vor cumpăra bere, atunci ele vor avea de ales între a cumpăra mici sau aripioare de pui.  max{ 4, 2} = 4. Fetele vor cumpăra mici. Dacă fetele cred că băieții vor cumpăra vin, atunci ele vor avea de ales între a cumpăra mici sau aripioare de pui.  max{ 3, 5} = 5. Fetele vor cumpăra aripioare de pui.

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

Astfel, se poate observa că echilibrul jocului este unul multiplu, format din cuplurile (V, A) și respectiv (M, B). Adică, prietenii vor avea la grătar mici cu bere sau aripioare de pui cu vin.

2.4 Problema 4 Pentru următoarea problemă se consideră doi piloți, Mihai și Vlad, care se vor întrece într-o cursă. Cei doi își pot alege tipul de anvelope folosite și își pot împiedica unul altuia participarea la cursă. Jocul în forma extinsă este următorul:

Se cere: a) Descrieți jocul sub formă normală; b) Determinați echilibrele acestui joc. Rezolvare: a) Înainte de a decide ce tip de anvelope să folosească, Mihai poate face o manevră strategică care l-ar împiedica pe adevarsarul său Vlad să participe la cursă. Astfel, într-o primă etapă, Mihai trebuie să decidă dacă să prevină sau nu participarea lui Vlad la cursă (decizii P și NP). Dacă Mihai împiedică participarea lui Vlad, Mihai va avea 4 puncte la sfârșitul cursei, iar Vlad nu va avea niciuna. Dacă Mihai nu împiedică participarea lui Vlad, ambii piloți trebuie să aleagă simultan tipul de anvelope (ploaie sau uscat). Sub nodurile terminale se găsesc vectorii câștigurilor fiecărui jucător. b) Jocul în informație incompletă poate fi analizat ca un joc static. Matricea câștigurilor pentru ultima etapă a jocului va fi următoarea:

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

Vlad PL Mihai

PL US

-

-

-

-

US

1,4

2,3

5,4

0,3

Dacă Mihai crede că Vlad va alege anvelopele de ploaie, atunci el va avea de ales între a utiliza anvelopele de ploaie sau uscat.  max{ 1, 5} = 5. Mihai va alege anvelopele de uscat. Dacă Mihai crede că Vlad va alege anvelopele de uscat, atunci el va avea de ales între a utiliza anvelopele de ploaie sau uscat.  max{ 2, 0} = 2. Mihai va alege anvelopele de ploaie. Dacă Vlad crede că Mihai va alege anvelopele de ploaie, atunci el va avea de ales între a utiliza anvelopele de ploaie sau uscat.  max{ 4, 3} = 4. Vlad va alege anvelopele de uscat. Dacă Vlad crede că Mihai va alege anvelopele de uscat, atunci el va avea de ales între a utiliza anvelopele de ploaie sau uscat.  max{ 4, 3} = 4. Vlad va alege anvelopele de ploaie.

Astfel, se poate observa că echilibrul jocului este format din (US, PL). Adică, dacă Mihai alege anvelopele de uscat, Vlad le va alege de ploaie. Putem reduce dimensionalitatea jocului și obținem astfel:

La prima etapă Mihai are de ales între strategia P ce îi asigură un câștig de 4 u.m. și strategia NP ce îi aduce 5 u.m. Evident alege NP. Echilibrul jocului va fi {(NP, US, PL)} = {(5, 4)}.

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

3. Jocuri statice în informație incompletă 3.1 Problema 1 Problema clasică a “pieței lămâilor” este aceea în care sunt vândute bunuri folosite, cum ar fi mașinile la mâna a doua. Vânzătorii știu foarte bine care sunt valorile mașinilor pe care le vând, însă cumpărătorilor nu, ei știind doar distribuția de probabilitate a acestora. Presupunem că valoarea reală a mașinii este v (știută doar de vânzător), iar pentru cumpărător este o variabilă aleatoare uniform distribuită în intervalul[vm,vM], cu 0 < vm < vM . Vom presupune, de asemenea, că prețul minim la care doresc vânzătorii să tranzacționeze mașina este f v, cu f ∈ (0,1), cunoscut atât de către vânzător, cât și de către cumpărător. Se cere să se determine condițiile în care există un echilibru pe piață și să se determine echilibrul bayesian asociat. Rezolvare: Pentru un cumpărător, o strategie pură constă în oferta unui preț p. Cel mai bun răspuns pentru vânzător este să accepte orice preț care depășește f v, respectiv p ≥ f ⋅ v. În competiție perfectă, fiecare cumpărător oferă p = E(v/p), respectiv prețul care egalează valoarea așteptată a mașinii, condiționat de faptul că vânzătorul dorește să vândă mașina la prețul p. Cazul I În cazul echilibrului care este Pareto optimal, toate mașinile vor fi vândute. Atunci p ≥ f ⋅ vM . În acest caz, valoarea așteptată a mașinilor este E(v/p) = , deci p =

v m+ v M 2

v m+ v M 1+ vM / vm ≥ f ⋅ vM sau echivalent, f ≤ . 2 2

1+ vM / vm v m+ v M v m+ v M , fie p = , iar f ⋅ vM ≤ = p, adică E(v/p) = p 2 2 2 este optimal Pareto. Dacă f ≤

Cazul al II-lea Să presupunem acum că f

≥

1+ vM / vm , respectiv pentru proprietari valoarea 2

mașinilor este relativ mare. Fie V(´v) evenimentul valoarea reală a mașinii este mai mică sau egală cu ´v și S(p) evenimentul proprietarului dorește să vândă mașina la prețul p.

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

Pentru f ⋅ vm ≤ p < f ⋅ vM avem: S (p) S (p) ⋅P [V ( ´v )] P ⋅ ( v´ −vm ) /(vM −vm) P (V ( ´v ) ˄ S ( p )) P V ( v´ ) V ( v´ ) P[V(´v)/S(p)] = = = P[S ( p ) ] P[S ( p ) ] ( p/f −vm)/( vM −vm)

[ ]

=

P

[ ]

S (p) ⋅ ( v´ −vm ) V ( v´ ) p/f −vm

[ ]

Dacă ´v > p/f , atunci această probabilitate este zero. Dacă f ⋅ vm ≤ p/f , atunci P[V(´v v´ −vm )/S(p)] = , care reprezintă o distribuție uniformă în intervalul [vm, p/f]. Cu alte p /f −vm cuvinte, cumpărătorii vor achiziționa mașinile dacă și numai dacă p ≤ ( p / f + vm ) / 2. Atunci, unicul echilibru Nash posibil este p = ( p / f + vm ) / 2 sau echivalent p = vm . 2−1/f Interpretarea acestui echilibru este următoarea: segmentul de piață pe care se vor vm vinde mașinile va fi [vm , .], respectiv doar mașinile cu valoare mică vor fi vândute, iar 2 f −1 cele cu valoare mare nu vor fi oferite pentru a fi tranzacționate.

3.2 Problema 2 Dilema prizonierului modificată presupune participarea la joc a doi jucători, dar există incertitudine în cazul tipului jucătorului 1, care poate fi fie altruist (a), fie rațional (r). În contrast, jucătorul 2 se știe a fi jucător rațional. Astfel, ne putem gândi că Natura selectează unul din jocurile următoare: Jocul 1(altruist) M M F

F

4,4

-1 , 5

3 , -1

-2 , 0

Jocul 2(rational) M M

F

4,4

-1 , 5

5 , -1

1,1

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

F

Putem folosi notația Ti pentru a defini setul de tipuri al jucătorului i, astfel având T1 = { a, r}, T2 = { r }. Pentru T1 vom avea nevoie de o distribuție de probabilitate πa ∈ [0, 1] asociată jucătorului 1 de tip altruist, iar π r = 1−πa este probabilitatea tipului rațional. Jocul extins se regăsește în figura următoare:

O caracteristică importantă este faptul că jucătorul 1 are două seturi de informații, în timp ce jucătorul 2 are doar unul. Motivul este întocmai faptul că presupunem că jucătorul 1 își cunoaște tipul, spre deosebire de jucătorul 2 care are o singură părere (corectă) despre tipul jucătorului 1. Când e rândul jucătorului 1 să joace, el își cunoaște propriul tip, dar nu cunoaște acțiunea aleasă de jucătorul 2 (efectul jocului simultan). Când este rândul jucătorului 2 să joace, el nu știe nici care sunt tipurile jucătorului 1 cu care se confruntă, nici alegerea jucătorului 1. Într-un fel, este ca și cum jucătorul 2 se confruntă cu doi posibili jucători, iar natura alege împotriva căruia să joace. Pentru a reprezenta acest joc în forma normală, jucătorul 1 trebuie să aibă patru strategii pure: în fiecare set de informații el are două acțiuni din care poate alege. Putem defini strategia jucătorului 1 drept xy ∈ {MM,MF, FM,FF}. unde x descrie ce face un jucător altruist 1 și y ceea ce face unul rațional. Aceasta este o previzualizare a ceea ce vom vedea în curând mai general: când vom introduce informații incomplete, o strategie a unui jucător este acum o rețetă care spune fiecărui tip de jucător ce ar trebui să facă dacă acesta este tipul pe care Natura l-a ales pentru joc. Odată ce avem seturi de strategie pure pentru fiecare jucător, fiecare pereche de strategii pure va da naștere unei căi de joc care începe cu alegerea Naturii și apoi continuă cu acțiunile simultane ale ambilor jucători. În acest exemplu, dacă jucătorul 1 joacă M este altruist, iar F dacă este rațional (MF), iar dacă jucătorul 2 joacă M, atunci cu probabilitate πa rezultatul va avea (4, 4) unități de utilitate și cu probabilitate (1 - πa) unitățile vor fi (5, −1).

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

Astfel, perechea de unități din perechea de strategii (MF, M) este u1 = πa4 + (1 − πa)5, and u2 = πa4 + (1 − πa)(−1). Pentru certitudine, presupunem că πa = 1/2, caz în care aceste unități vor fi (u1, u2) = (4.5, 1.5). În mod similar, putem completa celelalte nouă perechi de unități din celelalte combinații de strategii pure pentru a obține următoarea formă matricială joc:

MM M FM FF

Acum, odată ce avem acest ne putem aplica vechiul instrumente putem aplica echilibrul Nash acestui F) este unica (strategia dominantă,

M

F

4,4

-1 , 5

4.5 1.5

,

3.5 1.5

, -1.5, 2/5

4, -1

F

0,3

-0.5, 0,5

nou mod de modelare a jocului, de analiză a echilibrului. Anume, joc și vedeți cu ușurință că (MF, în acest caz) Nash echilibru.

3.3 Problema 3 Se consideră următorul joc de poker în informație incompletă între Ionescu și un străin din oraș. Cu probabilitatea 0.75, Ionescu consideră că străinul este o remiză rapidă (R). Cu probabilitate 0.25, Ionescu consideră că străinul are o tragere lentă (L). Ionescu cunoaște probabilitatea fiecărui tip înainte să ia o acțiune și nu obsrvă tipul străinului. Acest lucru înseamnă că Ionescu crede că este în figura din stânga 75% din timp, iar în cea din dreapta 25% din timp. Străinul își cunoaște propriul tip și, de asemenea, știe exact cine este Ionescu. Utilitățile acestui joc se regăsesc în figurile următoare:

Se cere:

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

a) Câte tipuri are fiecare jucător? b) Are vreunul din jucători o strategie dominantă? c) Determinați toate strategiile pure Bayes-Nash ale acestui joc. Rezolvare: a) În cazul jucătorului Ionescu, acesta are un singur tip, spre deosebire de jucătorul străin care are două tipuri, R și L. b) Se observă că în acest joc, indiferent de ce va alege Ionescu, strategia dominantă aleasă de străin (de tip R) este cea de a trage o carte. Deci orice echilibru al acestui joc l-ar avea pe străinul de tip R să aleagă “trage”. În cazul lui Ionescu, alegerea de a aștepta este optimă, cu excepția cazului în care străinul R alege “trage”. Atunci Ionescu va trage si el. c) Presupunând că Ionescu alege “trage”, atunci și străinul R va trage. De asemenea și în cazul străinului de tip L, strategia dominantă va fi de a trage o carte. (2 > 1). Deci, când Ionescu alege strategia de a trage o carte, și străinul ( atât R cât și L) va trage o carte. Verificăm mai departe daca strategia aleasă de Ionescu este cea optimă prin determinarea valorii așteptate ale ambelor strategii ale lui acestuia. Dacă Ionescu alege să tragă, atunci valoarea așteptată va fi: E [Trage|Trage dacă R; Trage dacă L] = 2 * 3/4 + 5 * 1/4 = 11/4 Dacă Ionescu alege să aștepte, atunci valoarea așteptată va fi: E [Așteaptă|Trage dacă R; Trage dacă L] = 1 * 3/4 + 6 * 1/4 = 9/4 Deci, strategia lui Ionescu de a trage o carte este cel mai bun răspuns. Astfel, unul din echilibrele Bayes-Nash este: dacă Ionescu trage o carte, stăinul cu tipul R, dar și de tipul L aleg să tragă o carte. Presupunând că Ionescu alege să “aștepte”, cel mai bun răspuns al străinului R este tot de a trage o carte, dar pentru tipul L al străinului, cel mai bun răspuns este de a aștepta. Dacă Ionescu alege să aștepte, valoarea așteptată va fi: E [Așteaptă|Trage dacă R; Așteaptă dacă L] = 1 * 3/4 + 8 * 1/4 = 11/4 Dacă Ionescu alege să tragă o carte, valoarea așteptată va fi: E [Trage|Trage dacă R; Așteaptă dacă L] = 2 * 3/4 + 4 * 1/4 = 10/4

ACADEMIA DE STUDII ECONOMICE BUCUREȘTI FACULTATEA DE CIBERNETICĂ, STATISTICĂ ȘI INFORMATICĂ ECONOMICĂ SPECIALIZAREA: CIBERNETICĂ ECONOMICĂ

Din moment ce 11/4 > 10/4, Ionescu va alege să aștepte în loc să tragă o carte. Astfel, al doilea echilibru Bayes-Nash este: dacă Ionescu așteaptă, străinul trage daca tipul acestuia este R și așteaptă daca este de tip L.

Bibliografie http://www.eco.uc3m.es/docencia/new_juegos/en_doc/2.2%20Dynamic%20imperfect%20info.pdf http://faculty.haas.berkeley.edu/stadelis/Game%20Theory/econ160_week7b.pdf https://belkcollegeofbusiness.uncc.edu/azillant/wpcontent/uploads/sites/846/2014/12/ECON6206_gtexp_chapter4notes.pdf Teoria jocurilor pentru economisti, Aplicatii, Capitolul 3, problema 3.4.