Elemente de Teoria Jocurilor

1

Specializarea:

Elemente de teoria jocurilor

ANUL III Semestrul VI

Cluj-Napoca 2013

2

Cuprins

Modulul 1 JOCURI STATICE DE INFORMATIE COMPLETA 7

Unitatea 1 Jocuri matriciale 7

Unitatea 2 Jocuri matriciale si programare liniara 19

Unitatea 3 Joc necooperativ 22

Unitatea 4 Aplicatii economice 35

TEME DE CONTROL 61

Modulul 2 JOC POZITIONAL 66

Unitatea 1 Jocuri dinamice (pozitionale) 66

Unitatea 2 Reducerea jocului pozitional 73

Unitatea 3 Rezolvarea jocului pozitional 77

TEME DE CONTROL 84

Modulul 3 JOCURI STATICE DE INFORMATIE INCOMPLETA 85

Unitatea 1 Joc static de tip Bayes 85

Unitatea 2 Echilibru de tip Nash-Bayes 92

TEME DE CONTROL 94

3

UNIVERSITATEA BABE-BOLYAI CLUJ-NAPOCA

FACULTATEA DE TIINE ECONOMICE I GESTIUNEA AFACERILOR

SPECIALIZAREA: FB, CIG, MN, IE

ANUL UNIVERSITAR 2013/2014

SEMESTRUL: VI

I. Informaii generale

Date de identificare a cursului

Date de contact ale titularului de curs:

Nume: Muresan Anton S.

Birou: Cabinetul 229, Etajul II Telefon: 0264-418653

Fax: 0264-412570

E-mail: [email protected] Consultatii: Joi orele 15,00-17,00

Date de identificare curs si contact tutori:

Numele cursului: ELEMENTE DE TEORIA JOCURILOR

Codul cursului: EBS0097

Anul III Semestrul VI

Tipul cursului: Optional

Pagina web a cursului: https://portal.portalid.ubbcluj.ro/ Tutori: Muresan Anton S.

Adresa e-mail tutori: [email protected]

4

Locul de desfurare a cursului: Cldirea Campus, sli etajul II Programarea n orar a activitilor (la nvmtul de zi): Sptmnal 2 ore de curs + 1 or de lucrri (seminar), conform orarului afiat la sediul facultii

Condiionri si cunosinte prerechizite:

Pentru inscrierea la cursul de faa este nevoie de parcurgerea si promovarea anterioara a disciplinelor de Matematici aplicate in economie (anul I, semestrul I) si Matematici financiare si actuariale (anul I, semestrul II). Este necesar a fi cunoscute notiunile de derivate, integrale, probabilitati.

Descrierea cursului :

Se vor avea in vedere urmatoarele obiective:

Familiarizarea studenilor cu tehnicile i metodele matematice utilizate n modelerea unor fenomene si procese economice si de interese diferite

Introducerea ctorva noiuni despre jucator, strategie (mutare, decizie), castig, solutie (punct de echilibru

Crearea bazelor de rationament si calcul pentru aplicatiile din domeniul economic

Organizarea temelor (partilor) in cadrul cursului: Cursul va avea urmatoarele trei parti:

1. Jocuri statice de informatie completa 2. Joc pozitional 3. Jocuri statice de informatie incompleta Organizarea temelor s-a facut avand in vederea ordinea fireasca si gradul de dificultate sa urmeze o ordine crescatoare. Informatia relevanta referitoare la fiecare tema (parte) se gaseste in lista bibliografica ce va fi prezentata ulterior, iar accesul va fi realizat direct.

Formatul si tipul activitatilor implicate de curs:

Formatul va fi unul clasic, permitand studentului de a-si gestiona singur, fara constrangeri, parcurgerea cursului. De sigur o participare la activitatile planificate va usura intelegerea tematicii cursului. Tipurile de activitati ce vor fi abordate in cadrul cursului vor fi atat cele clasice cat si proiecte de grup, discutii pe anumite teme si proiecte de cercetare.

5

Materiale bibliografice obligatorii:

Principalele materiale bibliografice pe care le vom utiliza, si care se vor gasi la biblioteca facultatii, iar unele vor putea fi accesate prin internet, sunt:

1. Blaga P. Muresan A.S., Lupas Al., Matematici aplicate in economie, vol. 2, ed. Promedia Plus, Cluj-Napoca, 1999

2. Gibbons, R., Game theory for applied economists Princeton Univ. Press, Prenceton, New Jersey

3. Muresan, A.S., Non cooperative games, Ed. Mega, Cluj-Napoca, 2012 4. Muresan A.S.Blaga P., Matematici aplicate in economie, vol. 2, ed.

Transilvania Press, Cluj-Napoca, 1996 5. Muresan A.S., Cercetari operationale, vol. 1 si 2, lito. UBB, Cluj-Napoca, 1997

Materiale si instrumente necesare pentru curs :

Vom folosi: calculator si softuri specifice pentru a putea vizualiza aplicatiile, pentru a prelucra date. Astfel, mentionam aici: Word, Excel, Adobe Reader.

Politica de evaluare si notare:

Evaluarea si notarea finala se va face prin rezolvarea de probleme, intocmirea unor referate si elaborarea unor proiecte aplicative. Toate acestea se vor realiza in cadrul examenului (colocviului) din sesiunea de examene. Intrarea in examenul final este conditionata de realizarea sarcinilor ce rezulta din temele de control de la sfarsitul fiecarui modul al suportului de curs. Studentii vor primi feed-back la rezultatele realizate in examenul final prin comunicare directa cu cei care solicita. In cazul cand studentul doreste sa revina la un examen de marire a notei, acest nou examen se va desfasura in aceleasi conditii, cu aceleasi cerinte, ca si examenul initial.

Elemente de deontologie academica:

Pentru a evita situatiile care pun in discutie onestitatea studentilor facem de la inceput precizarea ca se interzice categoric frauda, iar tentativele de frauda se

6

vor trata conform reglementarilor in vigoare elaborate la nivelul facultatii si universitatii. Este normal ca atunci cand se utilizeaza anumite date, texte, formulari, etc. luate din alte surse, sa se faca citarea, si astfel sa se asume meritele doar pentru munca si contributia proprie. Se va cere studentului sa aiba un comportament academic fata de profesori si colegi.

Studentii cu dizabilitati:

Nu vor avea nici o problema in a se incadra in cerintele cursului si a celorlalte activitati, sansele in pregatire si obligatiile lor fiind de aceeasi factura ca si pentru studentii fara dizabilitati.

Strategii de studiu recomandate:

Recomandam studentilor sa se pregateasca mai intai din aspectele teoretice, asa incat, mai intai, din curs, sa fie studiate modulele cu teoria si exemplele ilustrative formulate, apoi sa se abordeze problemele rezolvate, iar apoi si problemele formulate spre rezolvare. Pentru tot cursul, apreciem ca fondul de timp necesar insusirii complete este de 56 de ore, din care 40 pentru suportul de curs, 8 pentru activitatile directe cu tutorii, iar 12 pentru sarcinile individuale de studiu al bibliografiei si realizarea temelor de control.

7

I. Suportul de curs propriu-zis

Modulul 1

JOCURI STATICE DE INFORMATIE COMPLETA

Concepte de baz Jucator, strategie, castig, joc matricial, punct de echilibru Obiective:

a. definirea notiunii de joc matricial b. considerarea diverselor tipuri de jocuri matriciale

c. notiunea de solutie

Recomandri privind studiul: se recomanda studentilor sa-si insuseasca notiunile importante, in aplicatiile practice, de joc matricial si de solutii ale acestora. De asemenea solutiile pentru diversele probleme formulate plecand de la jocurile matriciale

Rezultate ateptate:

a) se asteapta ca studentii sa poata formula si opera cu diversele tipuri de jocuri matriciale, sa le recunoasca si sa le utilizeze in aplicatii

b) sa fie in stare sa gasesca solutiile pentru jocurile si problemele simple intalnite in aplicatii

Unitatea 1

Jocuri matriciale : definitie, clasificari, solutie

Obiective:

a) evidentierea principalelor tipuri de jocuri matriciale b) prezentarea diverselor tipuri de clasificari c) lamurirea notiunii de solutie

Noiuni cheie : Jucator, strategie, castig, joc matricial, punct de echilibru CONINUTUL UNITII

Exist situaii n care modelele matematice la care se ajunge se prezint sub forma unor jocuri matriciale. Asa sunt, de exemplu, acelea in care 2 sau mai multi parteneri, prin deciziile pe care le iau, influenteaza rezultatul (castigul) fiecarui participant.

8

Jocuri statice de informaie completa

In aceasta unitate consideram jocuri de urmatoarea simpla forma: mai intai jucatorii aleg simultan actiuni (decizii), apoi ei obtin castiguri ce depind de combinatia actiunilor ce tocmai au fost alese. In clasa unor astfel de jocuri statice (sau cu miscare-simultana) ne restrangem atentia asupra jocurilor cu informatie completa. Adica, functia de castig a fiecarui jucator (functia ce determina castigurile jucatorilor de la fiecare combinatie de actiuni) este total cunoscuta de toti jucatorii. Jocuri cu suma nula de doua persoane

Consideram un joc cu doi jucatori : jucatorul 1 si jucatorul 2. Ceea ce jucatorul 1 castiga este tocmai ce jucatorul 2 pierde, si vice versa. In continuare sa avem o intelegere intuitiva a unui astfel de joc introducem, prin cateva exemple simple, ideile de baza.

Exemplul 1.1. (Potrivirea monedelor) Fiecare din cei doi participanti (jucatori) pune pe masa o moneda, fara ca celalalt jucator sa o vada. Daca monedele se potrivesc, adica, daca ambele monede sunt cu capul sau ambele cu pajura, atunci jucatorul 1 ia ambele monede. Daca ele nu se potrivesc, jucatorul 2 ia ambele monede. In alte cuvinte, primul caz, jucatorul 1 primeste un castig (o moneda) de la jucatorul 2, si, in al doilea caz, jucatorul 1 primeste un castig de -1 (isi pierde moneda sa). Aceste castiguri pot fi listate in urmatorul tabel:

Juctorul 2

Juctorul 1 1 (capul) 2 (pajura)

1 (capul) 1 -1

2 (pajura) -1 1

De asemenea, ele pot fi scrise in matricele de castig pentru cei doi jucatori:

,

1111

1

=H

=

1111

2H

Spunem ca fiecare jucator are doua strategii (actiuni, mutari, decizii). In matricea 1H prima linie reprezinta prima strategie a jucatorului 1, a doua linie reprezinta a

9

doua strategie a jucatorului 1. Daca jucatorul 1 alege strategia 1, inseamna ca moneda sa arata capul deasupra. Strategia 2 inseamna pajura deasupra. Similar, prima si a doua second coloana a matricei 1H corespunde respectiv la prima si a doua strategie a jucatorului 2. In 2H avem aceleasi situatii, dar pentru jucatorul 2. Observatia 1.1. Acest ansamblu de concurs (competitie) este un joc de doua persoane cu suma nula (zero). Simplu spunand, un joc este o multime de reguli in care se precizeaza intregul process de competitie (sau concurs), incluzand jucatorii, strategiile, si castigurile (rezultatele) dupa fiecare jucare a jocului. Toate acestea sunt descrise complet.

Observatia 1.2. Datele (elementele) din tabelul de mai sus formeaza o matrice de castig (payoff matrix a jucatorului 1, adica 1H ). Matricea 2H este matricea de castig a jucatorului 2, si avem

H1 H2t O2 ,

unde tH 2 este transpusa lui 2H .

Observatia 1.3. Castigul este o functie de strategiile celor doi jucatori. Daca, de exemplu , moneda jucatorului 1 este cu capul deasupra (strategia 1) si moneda jucatorului 2 este cu capul deasupra (strategia 1), atunci elementul 111 =h noteaza castigul pe care jucatorul 1 il primeste de la jucatorul 2. La fel, daca jucatorul 1 alege strategia 2 (pajura) si jucatorul 2 alege strategia 1 (capul), atunci elementul

121 =h este castigul pe care jucatorul 1 il primeste. In acest caz, castigul pe care jucatorul 1 il primeste este un numar negativ. Aceasta inseamna ca jucatorul 1 pierde o unitate monetara, deci jucatorul 1 plateste o unitate monetara jucatorului 2 Exemplul 1.2. (Piatra-hartia-foarfecele) Foarfecele bate hartia, hartia bate piatra, si piatra bate foarfecele. Exista doi jucatori: 1 si 2. Fiecare jucator are trei strategii. Fie strategiile 1, 2, 3 reprezentand piatra, hartia respectiv foarfecele. Daca presupunem ca invingatorul cadstiga cate 1 unitatea monetara de la cel care pierde atunci matricea de castig este:

10

Juctorul 2

1 2 3

Juctorul 1 1 0 -1 1

2 1 0 -1

3 -1 1 0

Observatia 1.4. Matricele de castig pentru cei doi jucatori sunt:

,

011101110

1

=H ,011101

110

2

=H

Avem 21 HH = si 321 OHH t =+ .

Exemplul 1.3. Consideram jocul de doua personae cu suma nula pentru care matricea de castig este data in urmatorul tabel: Juctorul 2

q

p

0 1 2

Juctorul 1 0 0 1 4

1 -1 2 7

2 -4 1 8

3 -9 -2 7

Avem matricele de castig:

,

729814721410

1

=H

=

787421219410

2H

Jucatorul 1 are patru strategii, in timp ce jucatorul 2 are trei strategii. Observatia 1.5. Castigul jucatorului 1 (adica, ceea ce jucatorul 2 plateste la jucatorul 1) poate fi determinat de functia

11

f : 0, 1, 2, 3 0, 1, 2 Z, fp, q q2 p2 2pq.

In fiecare din exemplele de mai sus exista doi jucatori, anume jucatorul 1 si jucatorul 2, si o matrice de castig, 1H (exista de asemenea si matricea 2H asa ca

021 =+tHH ). Fiecare jucator are mai multe strategii. Strategiile jucatorului 1 sunt

reprezentate de liniile matricei de castig 1H , si acelea ale jucatorului 2 de coloanele matricei de castig 1H . (Strategiile jucatorului 2 sunt reprezentate de liniile matricei de castig 2H , si acelea ale jucatorului 1 de coloanele matricei de castig 2H ). Jucatorul 1 alege o strategie din multimea strategiilor sale, si jucatorul 2, independent, alege o strategie din multimea strategiilor sale. Dupa ce cele doua alegeri au fost facute, jucatorul 2 plateste jucatorului 1 o valoare, care este castigul corespunzator acestei situatii jucare a jocului. Aceasta valoare este reprezentata in matricea de castig. Aceasta valoare poate fi pozitiva, 0, sau negativa. Daca castigul este pozitiv, jucatorul 1 primeste o valoare pozitiva de la jucatorul 2, adica, jucatorul 1 castiga o valoare de la jucatorul 2. Daca castigul este negativ, jucatorul 1 primeste o valoare negativa de la jucatorul 2, adica, jucatorul 1 pierde o valoare catre jucatorul 2 (jucatorul 2 castiga o valoare de la jucatorul 1). Castigul jucatorului 1 este egal cu pierderea jucatorului 2. Ce jucatorul 1 castiga este tocmai ceea ce jucatorul 2 pierde, si vice versa. De aceea, un astfel de joc este numit un joc cu suma zero (nula).

Jocuri matriciale

In cele ce urmeaza presupunem ca jucatorul 1 are m strategii si jucatorul 2 are n strategii. Notam prin ija , mi ,1= , nj ,1= castigul pe care jucatorul 1 il obtine de la jucatorul 2 daca jucatorul 1 alege strategia i si jucatorul 2 alege strategia j .

Asa obtinem matricea de castig )(1 AH :

( )

==

mnmm

n

n

ij

aaa

aaa

aaa

aA

...

............

...

...

21

22221

11211

12

Definitia 1.1. Numim joc matricial jocul care este complet determinat de matricea A de mai sus.

Sa rezolvam jocul, adica sa gasim solutia (ce castig maxim are jucatorul 1 si ce startegii sunt alese de ambii jucatori pentru a obtine aceasta) examinam elementele matricei A .

In acest joc, jucatorul 1 vrea sa obtina un castig aij cat mai mare posibil, in timp ce jucatorul 2 va face alegerea sa cea mai buna si conduca la o valoare aij cat mai mica posibil. Interesele celor doi jucatori sunt complet opuse (in conflict). Daca jucatorul 1 alege strategia i el poate fi sigur ca va obtine cel putin castigul

min1jn

a ij. #

Acesta este elementul minim al liniei i din matricea de castig A .

Deoarece jucatorul 1 vrea sa-si maximizeze castigul sau el poate alege strategia i asa incat sa faca valoarea de mai sus cat de mare posibil. Adica, altfel spus jucatorul 1 poate alege strategia i in asa fel incat el sa primeasca un castig nu mai mic decat

max1im

min1jn

a ij . #

Cu alte cuvinte, daca jucatorul 1 face cea mai buna alegere a sa, ceea ce obtine el nu poate fi mai mic decat valoarea de mai sus.

Similar, daca jucatorul 2 alege strategia sa j , el va pierde cel mult

max1im

a ij . #

Dar, jucatorul 2 vrea sa-si minimizeze pierdearea sa, iar pentru asta va incerca sa sa-si aleaga strategia sa j asa ca sa obtina minimul valorii de mai sus. Anume, jucatorul 2 poate alege j asa incat pierderea sa sa fie nu mai mare decat

min1jn

max1im

a ij . #

Asa, daca jucatorul 2 face cea mai buna alegere a sa, castigul pe care il obtine jucatorul 1 nu poate fi mai mare decat valoarea de mai sus. Am vazut ca jucatorul 1 poate alege strategia i care sa-I asigure un castig care sa fie cel putin

13

v 1 max1im

min1jn

a ij,

in timp ce jucatorul 2 poate alege strategia j asa ca sa faca pierderea sa (castigul jucatorului 1) cel mult

v 2 min1jn

max1im

a ij.

Exista ceva relatie intre valorile v1 si v2 ? Raspunsul este dat prin

Lema 1.1. Urmatoarea inegalitate are loc: 21 vv , adica

v 1 max1im

min1jn

a ij min1jn

max1im

a ij v 2 . #

Demonstratie. Pentru fiecare mi ,1= avem

njaa ijijnj

,1,min1

=

si pentru fiecare nj ,1= avem

miaa ijnjij

,1,max1

=

Deci inegalitatea

min1jn

a ij max1im

a ij

are loc, pentru fiecare mi ,1= , si fiecare nj ,1= .

Deoarece membrul stang al ultimei inegalitati este independent de j , luand minimul in raport cu j in ambii membri avem

mivaa ijminjijnj

,1maxminmin 2111 ==

adica,

min1jn

a ij v 2 .

Deoarece membrul drept al ultimei inegalitati este independent de i , luand maximul in raport cu i in ambii membri obtinem

14

max1im

min1jn

a ij v 2 ,

adica, 21 vv , si demonstratia este completa.

Sa examinam cele trei exemple din sectiunea 1.1.

In Exemplul 1.1 avem 2=m , 2=n , deci ,1)1,1(maxminmax

21211===

ijjiav

.1)1,1(minmaxmin21212

=== ijij

av

Asa, in Exemplul 1.1 avem 21 vv < .

In Exemplul 1.2, avem 3=m , 3=n , deci ,1)1,1,1(maxminmax

31311===

ijjiav

.1)1,1,1(minmaxmin31312

=== ijij

av

Asa, in Exemplul 1.2 avem 21 vv < .

In Exemplul 1.3, avem 4=m , 3=n , deci ,0)9,4,1,0(maxminmax

31411===

ijjiav

.0)8,2,0(minmaxmin41312

=== ijij

av

Asa, in Exemplul 1.3 avem 21 vv = .

Puncte sa in strategii pure

Exista situatii in care 21 vv = . In consecinta dam

Definitia 1.2. Daca elementele matriei de castig A ale jocului matriceal satisfac urmatoarea egalitate

,maxminminmax 211111 vaav ijminjijnjmi ===

cantitatea )( 21 vvv == este numita valoarea jocului. Observatia 1.6. Valoarea v este valoarea comuna a acelora date in (3) si (5). Valoarea jocului din Exemplul 1.3 este 0=v .

15

Daca egalitatea (7) are loc, atunci exista un i si un j astfel incat ,minmaxmin

111vaa ij

njmijinj==

si .maxminmax

111vaa ij

minjijmi==

Deci .maxmin

11

= ijmijinj

aa

Dar, evident avem .maxmin

11

ijmijijinj aaa

Astfel .minmax

11 jinjjiijmiavaa

===

Deci, pentru orice i si orice j .jijiij avaa =

In consecinta, daca jucatorul 1 alege strategia i , atunci castigul sau nu poate fi mai mic decat v daca jucatorul 2 pleaca de la strategia j ; daca jucatorul 2 alege strategia j , atunci castigul sau nu poate sa depaseasca v daca jucatorul 1 se departeaza de la strategia i .

Definitia 1.3. Numim i si j strategii optimale ale jucatorilor 1 si 2 respectiv. Perechea ),( ji este un punct sa (saddle point) in strategii pure a jocului. Spunem ca = ii , = jj este o solutie (sau echilibru Nash) a jocului.

Observatia 1.7. Relatia (8) ne arata ca valoarea castigului la punctul sa ),( ji (solutia jocului) este valoarea jocului. Cand jucatorul 1 isi mentine strategia sa optimala i , el se poate astepta sa-si creasca castigul sau daca jucatorul 2 se departeaza de la startegia sa optimala j . Similar, daca jucatorul 2 isi mentine strategia sa optimala j , castigul jucatorului 1 poate descreste daca el se departeaza de la strategia sa optimala i . Astfel, daca jocul are un punct sa

),( ji atunci egalitatea (7) are loc si va ji = .

Observatia 1.8. Un joc matriceal poate avea mai mult decat un punct sa in startegii pure. Totusi, castigurile la diferitele puncte sa sunt egale,. Valoarea lor comuna fiind valoarea jocului.

16

Exemplul 1.4. Consideram jocul matrieal cu matricea de castig

=

576500212634

A

Avem pentru minimul liniilor sale

min4, 3, 6, 2 2, min1, 2, 0, 0 0, min5, 6, 7, 5 5

si atunci maximul acestor minime este:

.5)5,0,2(max 1v==

Acum, avem pentru maximele coloanelor sale

,5)5,0,2(max,7)7,0,6(max,6)6,2,3(max,5)5,1,4(max ====

si atunci minimul acestor maxime este: .5)5,7,6,5(min 2v==

Cum 521 == vv avem punct sa in satrategii pure. Este usor de verificat ca )1,3( si )4,3( sunt ambele puncte sa in strategii pure pentru ca

a31 a34 v 5.

Observatia 1.9. Daca jocul matricial are un punct sa in startegii pure ),( ji , atunci el este foarte usor de gasit. Realmente, prin Definitia 1.3 a unui astfel de punct sa in startegii pure (8), valoarea jia este un element din matricea de castig A

= )( ija care este in acelasi timp minimul din linia sa si maximul din coloana sa.

In Exemplul 1.3, )1,1( este un punct sa in strategii pure al jocului deoarecei 011 =a este cel mai mic element din prima linie si in acelasi timp este cele mai mare element din prima coloana.

In Exemplul 1.4 53431 == aa sunt doua elemente cu cea mai mica valoare in linia a treia si in acelasi timp cele mai mari din prima si a patra coloana, respective.

Un joc matricial poate avea mai multe puncte sa in strategii pure. In acest caz putem demonstra urmatorul rezultat:

17

Lema 1.2. Fie ),( ji si ),( ji puncte sa in strategii pure ale unui joc matricial. Atunci ),( ji si ),( ji sunt de asemnea puncte sa in strategii pure si valorile la toate aceste puncte sa sunt egale, adica

. === jijijiji aaaa

Demonstratie. Dovedim ca i , j este un punct sa in startegii pure. Faptul ca i , j

este un punct sa in startegii pure se face intr-un mod similar.

Deoarece ),( ji este un punct sa in strategii pure avem

jijiij aaa

pentru toti i=1,m si toti j=1,n . Deoarece ),( ji este un punct sa in strategii pure avem

jijiij aaa

pentru toti i=1,m si toti j=1,n . Din aceste inegalitati obtinem , jijijijiji aaaaa

care dovedesc (9). Prin (9) si prin inegalitatile de mai sus avem jijiij aaa

pentru toti i=1,m si toti j=1,n . Deci ),( ji este un punct sa in strategii pure. Din aceasta lema rezulta ca un joc matricial cu puncte sa in strategii pure are urmatoarele proprietati:

-- interschimarea sau proprietatea rectangulara a punctelor sa in strategii pure,

-- egalitatea valorilor la toate punctele sa in startegii pure.

Exemplul 1.5. Jocul cu matricea de castig

=

112417503

A

are punctual sa in strategii pure )2,3( deoarece 11 =v , 12 =v si 132 == va .

Exemplul 1.6. Perechea )3,3( este un punct sa in strategii pure pentru jocul ca matricea de castig

18

=

011101110

A

Avem 0=v .

Exemplul 1.7. Perechea )3,2( este un punct sa in strategii pure pentru jocul cu matricea de castig

=

213210214132

A

Valoarea jocului este 0=v . Exemplul 1.8. Jocul cu matricea de castig

=

417112114

A

are patru puncte sa in strategii pure deoarece avem (vezi Lema 1.2) .123221312 vaaaa =====

Exemplul 1.9. Jocul cu matricea de castig

=

8114490657

A

Nu are un punct sa in strategii pure, in sensul Definitiei 1.2 deoarece 5)1,0,5(max1 ==v

si .8)8,9,14(min2 ==v

19

Unitatea 2

Jocuri matriciale si programare liniara

Obiective:

a) studentii trebuie sa cunoasca elementele de programare liniara b) sa stie incadra un joc matricial in una din problemele de programare liniara de care ea apartine

c) sa-si insuseasca metodele de rezolvare si sa interpreteze rezultatele obtinute

Noiuni cheie : ecuatii liniare, functii scop, probleme de programare liniara, probleme duale, algoritmul simplex, solutii

CONTINUTUL UNITTII

Jocuri matriciale si programare liniara

In continuare, formulam jocul matricial ca o problema de programare liniara. Fie )( ijaA = matricea de castig a jocului.

Nu este o restrictie sa presupunem ca 0>ija pentru toti mi ,1= , si pentru toti nj ,1= . Atunci valoarea v a jocului trebuie sa fie un nunar pozitiv.

Prin alegearea strategiei mixte mSX jucatorul 1 poate obtine celk putin castigul asteptat

min1jn

XA j u.

Deci avem uXA j , nj ,1= adica

=

=m

iiij njuxa

1.1,

cu

.,1,011

=

==m

iii mixx

Notam mixux ii ,1,/ , == . Atunci problema devine

20

=

=

ux

njxa

i

iij

1,1,1

,

,

mixi ,1,0,

=

Jucatorul 1 vrea sa-si maximizeze valoarea u , (acest maxim este valoarea v a jocului), adica, el vrea sa minimizeze valoarea 1/u. Astfel problema se reduce la urmatoarea problema de programare liniara

minf x 1 x 2 x m

i1

m

a ijx i 1, j

x i 0, i

#

#

#

# #

Similar, jucatorul 2, prin alegerea unei strategii mixte nSY , poate face ca jucatorul 1 sa nu primeasca mai mult decat

.max1

wYA timi

=

Asa, avem wYA ti , mi ,1= , adica,

=

=n

jjij miwya

1.1,

unde

,,1,011

=

==m

jjj njyy

Notam njywy jj ,1,/ , == .

Deoarece jucatorul 2 vrea sa minimizeze w (acest minim este la fel valoarea v a jocului), adica, el vrea sa maximizeze valoarea 1/w , problema de mai sus se reduce la urmatoarea problema de programare liniara, care este duala lui (39), formulata mai sus:

21

maxg y1 y2 yn

j1

n

a ijy j 1, i

y j 0, j .

#

#

#

# #

Astfel problema gasirii solutiei unui joc matricial este este echivalenta cu problema rezolvarii unei perechi de probleme de programare liniara duale.

Observatia 1.28. Datorita teoremei dualitatii, bine cunoscuta in programarea liniara, este suficient sa se rezolve una singura dintre acele probleme de mai sus.

Exemplul 1.18. Consideram acelasi joc matricial ca in Exemplul 1.17. Astfel avem

=

804243324

B

Sa obtinem 0>ija vom aduna constanta 1 la fiecare element al matriei B si asa vom obtine

=

915354435

A

Corespunzatoarea problema de programare liniara (40) este [ ] ,3,2,1max yyyg ++=

0,,19513541435

,

3,

2,

1

,

3,

2,

1

,

3,

2,

1

,

3,

2,

1

++++++

yyyyyyyyyyyy

In continuare se rezolva aceasta problema folosim metoda simplex. Matricea simplex poate fi scrisa si apoi folosim algoritmul simplex.

22

Unitatea 3

Joc necooperativ

Obiective:

a) studentii trebuie sa recunoasca tipurile de jocuri necooperative b) sa stie incadra un joc necooperativ in unul din categoriile de care el apartine

c) sa-si insuseasca metodele de solutionare directa in cazul diferitelor tipuri de jocuri necooperative Noiuni cheie : jucator, strategie (mutare, decizie), castig, punct de echilibru

CONINUTUL UNITII

1. Definiia jocului necooperativ

Teoria jocurilor este acea ramur a matematicii care formuleaz i rezolv probleme legate de diferite modele ale situaiilor conflictuale. Deoarece jocul este prototipul situaiilor conflictuale de orice fel, termenii teoriei jocurilor sunt n mare parte dai prin termeni uzuali folosii n jocurile efective. Astfel de termeni sunt, de exemplu joc, ctig, strategie i altele. Orice termen al teoriei jocurilor are ns un coninut cu caracter pur matematic. Termenul joc este folosit pentru denumirea unui joc oarecare, definit matematic. Orice joc definit, pentru a i se scoate n eviden aspectul concret n raport cu jocul n general, va fi supranumit prin folosirea unui atribut, de obicei cu un anumit sens din limbajul de toate zilele. Pentru a deosebi acest joc de jocul efectiv se mai adaug uneori atributul matematic i se spune, mai complet, joc matematic. La orice joc obinuit particip un numr de n (numr natural) juctori. Din punct de vedere matematic numai existena juctorilor este esenial, precum i posibilitatea identificrii lor, respectiv deosebirii lor de toi ceilali juctori. De aceea mulimea juctorilor I se identic cu multimea primelor n numere naturale:

{ }nI ,...,1= . Fiecare juctor Iii , , poate aplica mai multe strategii. n cazul unui joc efectiv juctorul i poate, n momentele de decizie ale jocului, s aleag dintr-o mulime iS de variante. Vom considera c iS este o multime finit pentru orice i. Deoarece din punct de vedere matematic natura concret a variantelor nu este interesant, doar posibilitatea de identificare a lor, se va nota { }ii mS ,...,1= i se consider n continuare notaia general { }ii sS = , unde ni ,1= (i variaz de la 1 la

23

n) i pentru i fixat ii ms ,1= ( is variaz de la 1 la im ). Lund cte o strategie a fiecrui juctor se obine o situaie (strategie) a jocului ( )nsss ,...,1= , element al produsului cartezian ....1 i

Iin SxSxSS

==

n fiecare situaie s, fiecare juctor i, primete o sum ( )sH i . Aceat funcie, definit pe mulimea tuturor situaiilor s, se numete matricea de ctig a juctorului i.

Definiia 1. Se numete joc necooperativ sistemul { } { } >==

24

Matricea de ctig a juctorului 2 are urmtoarea exprimare:

( ) =sH 2 ( ) ( )( ) ( )

=

1111

2,22,11,21,1

22

22

HHHH

unde acum liniile corespund strategiilor juctorului 2 i coloanele corespund strategiilor juctorului 1.

Observaia 2. O notaie mai general pentru matricele de ctig este n forma unui tabel de tipul urmtor:

Situaia Matricea de ctig

1s ... ns 1H ... nH

Astfel, n cazul exemplului considerat, matricele de ctig pot fi date i n urmtoarea form:

Situaia Matricea de ctig

1s 2s 1H 2H

1

1

2

2

1

2

1

2

1

-1

-1

1

-1

1

1

-1

1. Definiia punctului de echilibru

Fie dat un joc necooperativ oarecare { } { } >=

25

ctig negativ) permanent. Situaie similar s-ar produce dac juctorul 1 ar aplica permanent strategia a doua.

Dac analiza s-ar fi fcut din punctul de vedere al juctorului 2 am fi ajuns la aceiai concluzie: nu este avantajos ca juctorul 2 s aplice permanent una i aceiai strategie.

Din cele stabilite rezult c n orice situaie ( ),, 21 sss = unul dintre juctori are o alt situaie preferat 's , fa de cea existent s n acel moment, la care se poate ajunge modificnd numai strategia juctorului cu alt preferin:

Situaia dat s

Situaia preferat 's pentru

juctorul 1 2

(1,1) (1,2) (1,2) (2,2) (2,1) (1,1) (2,2) (2,1)

n concluzie, jocul repetndu-se este necesar aplicarea fiecrei strategii is cu probabilitatea (frecvena relativ)

iisp care s asigure un ctig ct mai mare, n

totalitatea jocurilor jucate, pentru fiecare juctor, sau, ceea ce este acelai lucru, de a asigura valoarea medie cea mai mare posibil a ctigului pentru fiecare juctor. Pentru notarea matricei linie a tuturor probabilitilor

iisp , ii ms ,1= , asociate

juctorului i, se folosete simbolul [ ].,...,1 iimii ppP = . Vectorul ,iP indiferent de valorile probabilitilor, se numete strategie mixt a juctorului i. Dac o singur probabilitate din vectorul ,iP este diferit de 0, fiind egal cu 1, atunci ,iP este (echivalent cu) strategia pur is a juctorului i. Dac toate strategiile ,iP ni ,1= sunt pure, ( )nPPP ...,,1= este (echivalent cu ) strategia pur (situaia ( )nsss ...,,1= ) a ntregului joc. Notm cu iJ matricea linie format din im cifre egale cu 1 i atunci se poate scrie ,1=Tii JP unde T este simbolul transpunerii matricei.

26

Cu iP notm strategia mixt a tuturor juctorilor j, cu excepia juctorului i,

luai la un loc, presupunnd c fiecare juctor i-a fixat strategia sa n mod independent de restul juctorilor: jiji PP = . Aici nmulirea vectorilor se consider component cu componen n sensul unui produs cartezian. Prin convenie se asigur ordonarea lexicografic la scrierea elementelor vectorului

iP . De exemplu, dac [ ] [ ] [ ]343332313232221212111 ,,,,,,,, ppppPpppPppP === , sunt strategiile mixte ale juctorilor { }3,2,1=I , avem

[ ]342333233223312334223322322231223421332132213121321

,,,,,,,,,,, pppppppppppppppppppppppp

PPP

=

==

[ ]34123312321231123411331132113111312

,,,,,,, pppppppppppppppp

PPP

=

==

[ ].,,,,, 231222122112231122112111213

pppppppppppp

PPP

=

==

Cu notaiile introduse dm urmtoarea definiie:

Definiia 1. Rezolvarea jocului necooperativ const n determinarea acelor strategii mixte (soluii) ,iP ,1=Tii JP ni ,1= , pentru care, considernd constant vectorul

iP , funcia de ctig T

iiii PHPF = are valoare maxim, oricare ar fi i.

Strategiile ,iP se noteaz cu ( )nPPP ,...,1= i obiectul matematic astfel determinat se numete punct de echilibru al jocului.

Exemplul 2. Datele jocului necooperativ din exemplul precedent. pot fi reprezentate prin urmtoarele 2 tabele:

1F

2F

2P

1P

21p 22p 1P

2P

11p 12p

11p 1 -1 21p -1 1

12p -1 1 22p 1 -1

crora le corespund urmtoarele sisteme de egaliti

27

( ) ( )( ) ( ) .

,

,1,1

2212112112112

1222211122211

22211211

ppppppFppppppF

pppp

++=

++=

=+=+

Dac 21 , PP este soluia problemei, atunci nu exist nici un vector de probabilitate

[ ]01201101 , ppP = pentru care ( ) ( ),,, 2111201101 PPFFPPFF =>= unde ( ) ( ) 0122221011222101 ppppppF ++= i nu exist nici un vector de probabilitate [ ]02202102 , ppP = pentru care ( ) ( ),,, 2122021202 PPFFPPFF =>= unde ( ) ( ) .0221211021121102 ppppppF ++=

De exemplu,

=

=

21

,

21

,

21

,

21

21 PP este o soluie a jocului i avem 021 == FF .

3. Stabilirea punctelor de echilibru ale jocului necooperativ Soluia problemei exemplului 1 din punctul precedent a fost obinut printr-un procedeu particular, n funcie de elementele matricelor asociate jocului respectiv i nu printr-o metod care s fie valabil n cazul oricrui joc necooperativ i pentru orice soluie a acestuia.

Pentru a rezolva jocul necooperativ, potrivit definiiei 1 din presupunem c am obinut strategiile mixte ,iP ni ,1= i scriem funciile de ctig ,iF n form matriceal ,Tiii PF = unde [ ]iii FF ,...,= este o matrice linie cu im componente egale cu .iF

Reamintim c iJ este un vector linie format din im componente egale cu 1. Astfel, avnd n vedere definiia amintit rezult c se poate scrie

,Tii

Tiii PPHP =

adic

( ) ,0= TiTiii PHP unde

,0iP ni ,1= i .0 TiTii PH

28

Dac componenta j a vectorului TiTii PH ar fi pozitiv, atunci prin nmulirea la stnga cu vectorul iP cu toate componentele egale cu 0, exceptnd componenta j egal cu 1, ar rezulta iTiiii FPHPF >= , contrar definiiei 1 conform creia iF este valoarea maxim a expresiei Tiii PHP

pentru iP fixat.

Astfel raionnd, iP fiind un vector linie de probabiliti iisp , 10 iisp pentru orice valori ale probabilitilor, deci i pentru soluia problemei pentru care avem maxim, maximul funciei de ctig iF este atins (ntre altele) pentru o strategie is pentru care

( ) ( ) ,max 000

Tiii

s

Tiii

PsHPsHi

=

unde 0is este o strategie oarecare. Aici cu ( ) Tiii PsH , respectiv ( ) Tiii PsH 0 am notat elementul cu indice de linie is , respectiv 0is al matricei .Tii PH

Introducnd o matrice linie iT cu variabile independente nenegative iist , ii ms ,1=

[ ]iimii

ttT ,...,1= ,

pentru fiecae juctor i, se poate scrie o ecuaie matriceal echivalent cu inecuaia 0 Ti

Tii PH ; .

Ti

Tii

Ti TPH =

n concluzie rezult urmtoarea teorem: Teorema 1. Determinarea punctelor de echilibru ale jocului necooperativ

const n rezolvarea, n numere negative, a sistemului de ecuaii multiliniare:

,1=Tii JPT

iT

iiTi TPH = , ,0=

TiiTP

unde ni ,1= .

Observaia 1. Valorile reale necunoscute iF se consider scrise ca diferen a dou valori nenegative ,iF i ,,iF , iF = ,iF - ,,iF pentru a avea toate necunoscutele nenegative.

Observaia 2. Pentru rezolvarea problemei formulate in teorema 1 i n mod implicit pentru rezolvarea problemei formulate prin definiia 1 din punctul precedent se poate aplica orice metod pentru rezolvarea sistemelor de ecuaii-inecuaii de grad oarecare n numere negative. O metod destul de eficient este metoda eliminrii complete.

29

Observaia 3. Avnd n vedere c determinarea punctelor de echilibru ale unui joc necooperativ const n rezolvarea sistem de ecuaii multiliniare, teoria ce se prezint ar putea fi intitulat ,,teoria jocurilor multiliniare,, Prin faptul c am descris metoda de rezolvare a oricrui joc necooperativ nc nu rezult c soluia este efectiv i nu este vid. De aceea este important urmtoare teorem a lui Nash

Teorema 2. (J. Nash) Orice joc necooperativ are soluia nevid. Nu vom da demonstraia acestei teoreme din urmtoarele dou motive n

primul rnd pentru c se bazeaz pe cunotine matematice care depesc cadrul cursului i n al doilea rnd pentru c nu este constructiv ci existenial.

Exemplul 1. Problema din exemplul 1. punctul precedent, conform teoremei 1, este echivalent cu problema rezolvrii n numere nenegative,

,0,0,0,0 2121 TTPP a sistemului de ecuaii multiliniare:

,111 =TJP TTT TPH 1111 = ,011 =

TTP

,122 =TJP TTT TPH 2222 = ,022 =

TTP

unde

[ ] [ ]

[ ][ ] [ ]

[ ] [ ],,,,11

11,

1111

,,,,

1,1,,

,,,,

''

2'

2''

2'

22''

1'

1''

1'

11

21

2221212111

21

1221

2221212111

FFFFFFFF

HH

ttTttTJJ

PPPPppPppP

==

=

=

==

==

==

==

unde

,,,0,0,0,0 2''

2'

21''

1'

1''

2'

2''

1'

1 FFFFFFFFFF ==

sau, n form dezvoltat i reordonat:

''

12221

11''

1'

12221

22211211

0,1,1

Fpp

tFFpp

pppp

+

=++

=+=+

30

0,0

22''

2'

21211

21''

2'

21211

=++

=+++

tFFpp

tFFpp

.0,0,0,0 2222212112121111 ==== tptptptp

Rezolvnd acest sistem prin metoda eliminrii se obine soluia gsit cu ocazia rezolvrii problemei din exemplul 1, punctul 2. prin procedeul particular.

Observaia 4. Avnd n vedere nenegativitatea necunoscutelor, avem urmtoarele echivalene

,0,00 1212111112121111 ===+ tptptptp

,0,00 2222212122222121 ===+ tptptptp

i prin urmare ecuaia 0=TiiTP poate fi nlocuit cu im ecuaii de forma

iiisis mstp ii ,1,0 == oricare ar fi .,1, nii =

4. Stabilirea punctelor de echilibru ale jocului bimatriceal

Definiia 1. Jocul necooperativ n cazul a doi juctori se numete joc bimatriceal.

Un astfel de joc permite o rezolvare mai simpl. Problema formulat prin teorema 1 din punctul 4.3. avnd n vedere c 21 PP = i 12 PP = poate fi descompus n trei subprobleme independente. Subproblema (1) const n rezolvarea n numere nenegative 2P a sistemului de ecuaii liniare

==

TTT

T

TPHJP

1211

22 ,1, (1)

Subproblema (2) const n rezolvarea n numere nenegative 1P a sistemului de ecuaii

==

TTT

T

TPHJP

2122

11 ,1 (2)

ambele subprobleme rezolvndu-se prin metoda simplex. Deoarece soluia general se obine ca o combinaie liniara convex a soluiilor de baz, rezult c trebuie s selectm acele soluii de baz ( )21 , PP pentru care se verific i subproblema (3) format din sistemul de ecuaii

31

011 =TTP , .022 =

TTP

Dac pentru un indice 1s oarecare, 111 ms necunoscuta 11st intr n soluia de baz a subproblemei (1) i pe deasupra 0

11 st ( 011 =st n caz de degenerare), atunci 0

11 =sp

Deci pentru toate cazurile 011 st avem 011 =sp i la fel pentru 0212 st rezult

0212 =sp proprietatea care permite stabilirea soluiei care verific sistemul (3).

Soluia general se obine scriind combinaia liniar convex a tuturor soluiilor de baz 1P asociate unui 2P fixat i combinaia liniar convex a tuturor soluiilor de baz 2P asociate unui 1P .

Exemplu 1. Problema din exemplul 1 punctul 3. se refer la un joc bimatriceal. Cele trei sisteme sunt urmtoarele

=+++

=++

=+

00

,1

12''

1'

12221

11''

1'

12221

2221

tFFpptFFpp

pp ( )'1

=++

=+++

=+

00

,1

22''

2'

21211

21''

2'

22211

1211

tFFpptFFpp

pp ( )'2

.0,0,0,0 2222212112121111 ==== tptptptp ( )'3 Subproblemei ( )'1 i corespunde matricea simplex (linia funciei de optimizat (pentru fixarea ideilor se consider minimizat) este linia egal cu 0):

=

0000000010111100111111000011

1S .

Obinem urmtoarele soluii de baz

[ ] [ ]0,2,0,1,1,0,2,0,0,1,0,1,0,0,0,0,21

,

21

131211 ==

= XXX Aici simbolul X s-a folosit

pentru uniformizarea notaiei necunoscutelor

.,,,,, 126115''

14'

13222211 txtxFxFxpxpx ======

32

Astfel de uniformizri vor fi folosite i n continuare, ori de cte ori va fi necesar fr nici o precizare special.

Subproblema ( )'2 are urmtoarea matrice simplex

=

0000000010111100111111000011

2S

i are soluiile de baz

[ ] [ ]2,0,0,1,1,0,0,2,0,1,0,1,0,0,0,0,21

,

21

232221 ==

= XXX

S notm cu ,3,1;2,1,' == jiX ij vectorii care se obin prin omiterea componentelor .2,1,, ''' =iFF ii Obinem:

,0,0,21

,

21

,0,0,21

,

21

'

21'

11

=

= XX

[ ] [ ],0,2,0,1,2,0,0,1 '22'12 == XX

[ ] [ ].2,0,1,0,0,2,1,0 '23'13 == XX . Pentru a stabili perechile de soluii ( )'2'1 , ji XX care s fie soluii ale problemei de joc bimatriceal, trebuie s fie ndeplinit condiia 0

11st 011 =sp i

0212st 0212 =sp Se constat c exist o singur soluie 1P = 2P =

21

,

21

obinut

pentru 022211211 ==== tttt i ''1'1 FF = 0''2'2 === FF i prin urmare 021 == FF .

4. Stabilirea punctelor de echilibru ale jocului antagonist

Definiia 1. Se numete joc antagonist jocul bimatriceal cu matricele (bidimensionale) 1H i 2H dac 021 =+ THH unde 0 este matricea nul.

33

Avnd n vedere c orice egalitate este echivalent cu dou inegaliti, sistemele (1), (2) i (3) din punctul 4. pot fi scrise n urmtoarea form:

,11

0

22

22

121

T

T

TT

PJPJ

PH (4)

,11

0

11

11

211

T

T

JPJP

HP (5)

==

0)(0)(

2211

1211T

TT

PHPPHP

(6)

unde 1 conine ca elemente una i aceiai valoare ,1F iar 2 conine una i aceiai valoare ,2F

Din subproblema (6) rezult TT PP 2211 = deci 12 FF =

Aceste valori pot fi considerate i ca alori minimax (minumul unor valori maxime) obinute prin minimizarea funciei ,1F (maximul este infinit), respectiv maximin (maximul unor valori minime) obinute prin maximizarea funciei 12 FF = (minimul este infinit). Adugnd sistemului (4) funcia ''1'11 FFF = iar sistemului (5) funcia ''2'22 FFF += rezult dou probleme de programare liniar, una duala celeilalte. Desigur se poate folosi notaia simplificat 21 FFF == i considerm c se determin F = MIN prin sistemul (4) i F = MAX prin sistemul (5). Astfel, cel puin o soluie prticular a jocului antagonist se poate obine rezolvnd numai unul dintre sistemele (4) i (5). Jocul antagonist poate avea ns, ca joc bimatriceal, i alte soluii, rezultnd din rezolvarea sistemului (1), (2) i (3) din punctul 4. punnd FFF == 12 Avnd n vedere simetria celor dou sisteme (4) i (5) i notnd 21 FFF == , rezult urmtoarea teorem cu privire la jocurile antagoniste (teorema von Neumann-Morgenstern). Teorema 1. Minimul n raport cu 2P al maximelor (minimax) funciei ( )21 , PPF n raport cu 1P , pentru 2P fixat, este egal cu maximul n raport cu

1P al minimelor (maximin) funciei ( )21 , PPF n raport cu 2P , pentru 1P fixat, deci

34

( ) ( ).,minmax,maxmin 21212112

PPFPPFPPPP

=

Observaia 1. n cazul unui joc bimatriceal oarecare, ca o extindere a condiiei de la jocul antagonist, se poate formula ntrebarea: pentru care soluie ( )21 , PP funcia 21 FF + ia valoarea minim? Aceast formulare conduce la problema considerrii cooperiei: cnd poate avea loc cooperare i cnd nu? La jocul antagonist .021 =+ FF

Exemplul 1. Jocul bimatriceal din exemplul 1 al punctului 4.4. este un joc antagonist. Deoarece are o singur soluie, aceeai soluie se obine i dac se minimizeaz funcia 1FF = deci ''1'1 FFF = , n ipoteza utilizrii la rezolvare a sistemului (4), nlocuind linia format numai din zerouri n matricea simplex 1S cu linia funciei de minimizat [ ]0,0,0,0,1,1,0,0 . Astfel se obine matrice simplex

0001100010111100111111000011

care prin reducere conduce la aceeai soluie 1P = 2P =

21

,

21

, pentru care

,0''1'

1 == FF deci FMIN = 0.

35

Unitatea 4

Aplicatii economice

Obiective:

a) studentii trebuie sa cunoasca etapele unui proces de modelare matematica folosind jocurile b) sa stie incadra o problema economica in una din categoriile de jocuri de care ea apartine

c) sa-si insuseasca metodele de rezolvare directa si sa interpreteze rezultatele gasite

Noiuni cheie : jucator, decizie, duopol, oligopol, punct de echilibru CONINUTUL UNITII

Aplicatii in economie

In cele ce urmeaza dam ceva aplicatii ale jocurilor in economic. Vom evalua functia de castig pentru fiecare jucator, care va fi dependenta de strategiile jucatorilor. Aici multimile strategiilor vor fi intervale ale axei reale. 1. Modelul Cournot al duopolului

Consideram o foarte simpla versiune a modelului lui Cournot. Fie 1q si 2q notate cantitatile unui produs omogen, produse de firmele 1 si 2, respectiv. Fie

QaQP =)( pretul care curata piata (the market-clearing price) cand cantitatea agregata pe piata este 21 qqQ += . Deci avem

( )

36

continuuu divizibil si outputuri negayive nu pot fi. Astfel, spatiul strategiilor fiecarei firme este ),0[ =iS , numerele reale nenegative, in care caz o tipica strategie is este o cantitate aleasa, 0iq . Deoarece 0)( =QP pentru aQ , nici o firma nu va produce o cantitate aqi > . Castigul firmei i , o functie de strategiile alese de ea si de cealalta firma, profitul sau, poate fi scris ca

].)([),( cqqaqqq jiijii +=pi

Cum stim, un punct de echilibru (echilibrul Nash) este perechea ),( 21 qq unde iq , pentru fiecare firma i , rezolva problema de optimizare

].)([max),(max00

cqqaqqq jiiqjiiq ii+=

37

echilibrul Cournot, din contra, cantitatea agregata este mare, asa ca pretul asociat este scazut, asa ca tentatia de a creste outputul este redusa.

Observatia 1.37. O alta rezolvare, inafara de cea algebrica, pentru echilibrul Nash in jocul Cournot se poate lua un procedeu grafic folosind cel mai bun raspuns pentru o firma:

( ) ( )cqaqR = 112 21

-- cel mai bun raspuns al firmei 2, si

( ) ( )cqaqR = 221 21

-- cel mai bun raspuns al firmei 1.

Un al treilea mod de a rezolva pentru un echilibru Nash este sa aplicam procedeul de eliminare iterata a strategiilor strict dominate.

2. Modelul Bertrand al duopolului

Acest model al lui Bertrand este bazat pe faptul ca firmele acum isi aleg preturile, altfel decat la modelul lui Cournot. Modelul lui Bertrand este un joc diferit decat modelul jocului lui Cournot deoarece spatial strategiilor este diferit si functiile de castig sunt diferite. Astfel obtinem un alt punct de echilibru, dar conceptual de echilibru folosit este tot de echilibru Nash definit in sectiunile precedente. Consideram cazul produselor diferentiate. Daca firmele 1 si 2 aleg preturile 1p and

2p , respectiv, cantitatea ce consumatorii o cer de la firma i este

,),( jijii bppappq +=

unde 0>b reflecta extinderea la care produsul firmei i este un substitut pentru produsul firmei j. Aceasta o nerealista functie de cerere pentru ca cererea pentru produl firmei i este positiva chiar cand firma i isi alege un pret arbitrar de inalt, cu conditia ca firma j de asemenea isi alege un pret destul de inalt. Presupunem ca sunt costuri de productie constante, ca sunt costurile marginale constante, la c , unde ac < , si ca firmele actioneaza simultan (isi aleg preturile lor). Translatam problema economica intr-un joc necooperativ. Exista din nou doi jucatori. In acest moment totusi, strategiile posibile la fiecare firma sunt preturile diferite care se pot schimba, altfel decat diferitele cantitati ce se pot produce. Vom presupune ca preturile negative nu sunt admisibile, dar ca orice pret nenegativ poate fi ales nu exista nici o restrictie la preturi determinate de monede. Astfel la fiecare firma spatiul strategiilor poate fi din nou reprezentat ca ),0[ =iS , si o strategie tipica

is esste acum un pret, 0ip .

38

Vom presupune din nou ca functia de castig pentru fircare firma este tocmai profitul. Profitul firmei i cand este ales pretul ip si rivala sa alege pretul pj este

ip i, p j q ip i, p jp i c a p i bp jp i c.

Astfel, perechea de preturi ),( 21 pp este un echilibru Nash daca, pentru fiecare firma i , ip rezolva problema

).)((max),(max00

cpbppapp ijipjiip ii+=

39

2. Doi juctori scriu, independent , unul din numerele 1, 2 sau 3. Dac ei au scris acelai numr atunci juctorul 1 pltete juctorului 2 un numr de uniti monetare egal cu numrul scris de primul juctor. n caz contrar, juctorul 2 pltete juctorului 1 numrul de uniti monetare egal cu numrul pe care juctorul 1 l-a scris. Care este matricea de ctig a acestui joc?

Soluie. Este uor de constatat c matricea de ctig a juctorului 1 este:

=

333222111

A

3. Care dintre jocurile precedente are punct a n strategii pure? Soluie. Pentru primul joc avem:

( ) ,55,3,5,1maxminmax31411

=== ijji

av

( ) ,510,5,9minmaxmin41312

=== ijij

av

Cum 521 == vv rezult c primul joc are punct a n strategii pure. Este usor de verificat c (2,2) i (4,2) sunt puncte a n strategii pure deoarece .54222 == aa

Astfel 4,2 == ii sunt strategii optimale ale juctorului 1 i 2=j este strategia optimal a juctorului 2. Pentru al doilea joc avem:

( ) ,13,2,1maxminmax31311

=== ijji

av

( ) ,22,3,3minmaxmin31312

=== ijij

av

Astfel al doilea joc nu are punct a n strategii pure deoarece .21 21 vv =

40

Pentru al doilea joc, fie ( )321 ,, xxxX = i ( )321 ,, yyyY = strategiile mixte ale juctorului 1, respectiv 2. Atunci ctigul ateptat al juctorului 1 este:

==

++++==3

12212312111

3

122

jjiij

i

t yxyxyxyxyxyxaYAX

.3332 33231332 yxyxyxyx +++

5. Folosind eliminarea iterat a strategiilor strict dominate rezolvai jocul cu matricea de ctig:

=

011101110

A

Soluie. n matricea A, elementele primei linii sunt mai mici dect elementele corespunztoare din linia a 3-a. n consecin, juctorul 1 niciodat nu va folosi prima sa strategie. Prima linie va fi eliminat. Obinem astfel matricea de ctig redus:

=

011101

'A

Acum, n aceast matrice 'A fiecare element al primei coloane este mai mare dect elementele corespunztoare ale coloanei a 3-a. n consecin juctorul 2 nu va folosi niciodat prima sa strategie, deci prima coloan poate fi eliminat. Aa obinem matricea redus:

=

0110

''A

Similar obinem succesiv:

[ ] [ ].0,01''' == IVAA Astfel strategiile optimale (pure) sunt ( ) ( )1,0,0,1,0,0 == YX i valoarea jocului este .0=v Avem, desigur, un punct a n strategii pure ( ) ( )3,3, = ji deoarece .033 == va 6. Gsii strategiile optimale ale jocurilor cu matricile de ctig:

a)

=

3102

A , b)

=

0221

A , c)

=

1111

A

Soluie. Acestea sunt jocuri matriciale 2 x 2. Astfel, putem folosi strategiile mixte ( ) ( )qqYppX == 1,,1, unde

cbdabcad

vcbda

bdqcbda

cdp+

=

+

=

+

=

,,

a) Obinem: ,

23

10321032

,

43

103203

,

21

103213

=

+

==

+

==

+

= vqp

41

Deci .23

,

41

,

43

,

21

,

21

=

=

=

vYX

b) Avem: ,

34

22012202

,

32

220120

,

32

220120

=

+

==

+

==

+

= vqp

Deci .34

,

31

,

32

,

31

,

32

=

=

=

vYX

c) Obinem:

( )( ) ( )

( ) ( ),0

41111

,

21

,

21

111111

=

===

+

= vqp

Deci .0,21

,

21

=

==

vYX

7. Rezolvai problema precedent folosind metoda lui Williams. Soluie. Fie ( ) ( )2121 ,,, yyYxxX == strategiile mixte pentru juctorii 1 si 2 respectiv. Sunt satisfcute relaiile

ac

bdyy

yybadc

x

xxx

==+

==+2

121

2

121 ,1,,1 (conform metodei lui

Williams).

a) Obinem ,10231

,12

121 =

==+x

xxx deci ,

21

, 2121 === xxxx respectiv

,32103

,12

121 =

==+yy

yy deci .41

,

43

,3 2112 === yyyy

Astfel

=

=

41

,

43

,

21

,

21 YX i atunci

23

2323

21

,

21

4143

3102

21

,

21

=

=

==

t

YAXv

b) Avem ,22102

,12

121 =

==+x

xxx deci ,

31

,

32

,2 2121 === xxxx respectiv

.

31

,

32

,

1220

,1 212

121 ==

==+ yyyy

yy Astfel ,31

,

32

==

YX i

34

3132

34

,

34

3132

0221

31

,

32

=

=

==

t

YAXv

42

c) Avem ( ) 11111

,12

121 =

==+x

xxx deci ,

21

, 2121 === xxxx respectiv

( ).

21

,,11111

,1 21212

121 ====

==+ yyyyyy

yy Astfel ,21

,

21

==

YX i

.0

2121

1111

21

,

21

=

=

v

8. Rezolvai problema 6 cu metoda grafic descris pentru jocurile matriceale de tip n2 respectiv 2m .

Soluie. Fie ( ) ( )yyyxxX == 1,,1, respectiv, strategiile mixte pentru juctorii 1 i 2. Trasm liniile drepte ac, bd i ab, cd respectiv n cele dou figuri (sistemele de coordonate) n planele xOv respectiv yOv. Apoi determinm coordonatele punctelor de intersecie ale acestor linii drepte.

a) Matricea de ctig este ,3102

=A astfel avem liniile drepte care unesc punctele de coordonate

(1,2), (0,1) respectiv (1,0), (0,3). Ecuaiile acestor drepte sunt:

212

101

=

vx respectiv

030

101

=

vx

Sau

1+= xv respectiv 33 += xv

Punctul de intersecie are coordonatele: .23

,

21

== vx Astfel ,21

,

21

=

X este strategia optimal

a juctorului 1 iar 23

=v este valoarea jocului.Pentru strategia optimal a juctorului 2 considerm liniile drepte ce unesc punctele de coordonate (1,2), (0,1) respectiv (1,1), (0,3). Ecuaiile acestor drepte sunt:

202

101

=

vy respectiv

131

101

=

vy

Sau

yv 2= respectiv 32 += yv

Punctul de intersecie are coordonatele .23

,

43

== vy Astfel

=

41

,

43Y este strategia optimal a

juctorului 2, iar 23

=v este valoarea jocului.

43

b) Procednd ca i n cazul punctului a) gsim valorile 34

,

32

,

32

=== vyx aa nct strategiile

optimale sunt

==

31

,

32YX i valoarea jocului este

34

=v .

c) Gsim valorile ,0,21

,

21

=== vyx deci

==

21

,

21YX sunt strategiile optimale, iar

valoarea jocului este 0=v . 9. Folosind metoda grafic, rezolvai jocurile matriceale cu matricele de ctig:

a)

=

=

814965

),57383692

AbA

Soluie.

a) Fie ( )xxX = 1, o strategie mixt a juctorului 1. Liniile drepte ae; df; cg; dh; care unesc punctele: (1,2), (0,8); (1,9), (0,3); (1,6), (0,7); (1,3), (0,5) au ecuaiile:

.

353

101

;676

101

;939

101

;282

101

=

=

=

=

vxvxvxvx

Punctul de intersecie ce corespunde maximului minimelor este determinat de dreptele care unesc punctele (1,9), (0,3) respectiv (1,3), (0,5), adic

,

353

101

939

101

=

=

vxrespectivvx

sau .3652 +=+= xvrespectivxv

Coordonatele punctului de intersecie (maximul minimelor) sunt .29

,

41

== vx

Astfel

=

43

,

41X este strategia optimal a juctorului 1, iar valoarea jocului este .

29

=v

Pentru strategia mixt a juctorului 2 avem ( )4321 ,,, yyyyY = i ea se va determina aa nct 14321 =+++ yyyy i 2

9==

vYAX t .

Ajungem la sistemul de ecuaii liniare

==+++

=+++

4,101818271826

1

4321

4321

jyyyyy

yyyy

j

care are soluia [ ].1,0,1,,0,0 4231 ==== qqyqyyy

Se consider c 41

=q , deci strategia optimal a juctorului 2 este

=

43

,0,41

,0Y .

44

b) Fie ( )yyY = 1, o strategie mixt pentru juctorul 2. Liniile drepte ab, cd, ef care unesc punctele (1,5), (0,6); (1,9), (0,4); (1,1), (0,8) au ecuaiile

.

181

101

,

949

101

,

565

101

=

=

=

vyvyvy

Punctul de intersecie (minimul maximelor este acelai pentru oricare dou drepte) se obine din sistemul de ecuaii (format cu ultimele dou, pentru minimul maximelor)

.87,45 +=+= yvyv

Astfel avem 3

17,

31

== vy i atunci

=

32

,

31Y este strategia optimal pentru juctorul al doilea

iar valoarea jocului este .3

17=v

Strategia mixt a juctorului 1 are forma ( )321 ,, xxxX = i se determin aa nct 1321 =++ xxx i .

317

== vYAX

t

Ajungem la sistemul de ecuaii liniare

==++

=++

3,1017171717

1

321

321

ixxxx

xxx

i

Se constat c strategia optimal a juctorului 1 este .125

,

127

,0

=

X

10. Rezolvai jocul matriceal pentru care matricea de ctig este

.

564328306

=A

Soluie. Folosim metoda descris pentru jocurile matriceale de forma 3x3.

Pentru juctorul 1, cu strategia mixt (coordinate baricentrice) ( )321 ,, xxxX = calculm .533,62,486 32133223211 xxxAXxxAXxxxAX ++=+=++=

Ecuaia liniei 21 = AXAX este .02106 321 =+ xxx

Dar 1321 =++ xxx aa nct gsim .562 31 =+ xx

Ecuaia liniei 32 = AXAX este 32131 53362 xxxxx ++=+ , sau ,053 321 =+ xxx adic .562 31 =+ xx

45

Ecuaia liniei 13 = AXAX este

562,053,486533 31321321321 =+=+++=++ xxadicxxxsauxxxxxx

Regiunea ,1R n care 131min = AXAX jj se determin din inegalitile 21 AXAX

i 31 AXAX care ne dau .562 31 =+ xx

Astfel regiunea ,1R este delimitat de punctele

65

,

61

,0

43

,0,41

i ( )1,0,0

ntruct ,3

14

65

,

61

,01 =

AX ,

29

43

,0,411 =

AX ( ) 41,0,01 = AX constatm c valoarea maxim

este .3

14max,

314

=


i 32 AXAX care ne dau .562 31 + xx

Astfel regiunea ,2R este delimitat de punctele ( ) ( )

43

,0,41

,

65

,

61

,0,0,1,0,0,0,1 .

ntruct ( ) ,00,0,12 = AX ( ) ,20,1,02 = AX ,314

65

,

61

,02 =

AX ,

29

43

,0,412 =

AX constatm

c valoarea maxim este .3

14max,

314

=


i 23 AXAX care ne dau .053 321 =++ xxx

Astfel regiunea ,3R este determinat de punctele .43

,0,41

,

65

,

61

,0

ntruct ,3

14

65

,

61

,03 =

AX ,

29

43

,0,413 =

AX constatm c valoarea maxim este

.

314

max,3

14=

Acum valoare jocului v este dat de relaia =

==

321

31 3323133max,max,maxminminmax AXAXAXAXv

RSXRSXRSXjjSX III

46

.

314

314

,

314

,

314

min =

=

Strategia optimal a juctorului 1, pentru care se obine valoarea juctorului este .65

,

61

,0

=

X

Pentru juctorul 2 fie ( )321 ,, yyyY = o strategie mixt. Calculm .564,328,36 32133212311 yyyYAyyyYAyyYA ttt ++=+=+=

Regiunea ,1T n care ,max 131tt

iiYAYA

= se determin din inegalitile tt YAYA

21 i tt YAYA

21 ,

care ne dau .210 2121 yyiyy

ntruct aceste inegaliti se contrazic rezult c regiunea ,1T este mulimea vid, .1 =T

Regiunea ,2T n care ,max 231tt

iiYAYA

=

se determin din inegalitile tt YAYA

12 i

tt YAYA

32 , care ne dau .310 2121 yyiyy

Rmne doar .31

21 yy Regiunea 2T este delimitat de punctele ( )

310,

31

,0,31

,

32

,0,0,1 .

ntruct ( ) ,80,0,12 = tYA ,314

0,31

,

322 =

tYA ,

314

31

,0,322 =

tYA constatm c valoarea minim este

.

314

min,3

14=

Regiunea 3T , n care ,max 331tt

iiYAYA

= se determin din inegalitile tt YAYA

13 i tt YAYA

23 ,

care ne dau .31

21

2121 yyiyy

Rmne doar .31

21 yy

Regiunea 3T este delimitat de punctele ( ) ( ) .32

,0,31

,1,0,0,0,1,0,0,31

,

32

ntruct ,3

140,

31

,

323 =

tYA ( ) ,60,1,03 =

tYA ( ) ,51,0,03 =tYA ,

314

32

,0,313 =

tYA constatm c

valoarea minim este .3

14,

314

=v

Acum valoarea jocului v este dat de relaia

47

.

314

314

,

314

maxmax,min,minmaxmaxmin3323133 31

=

=

==

tiTSX

tiTSX

tiTSY

ti

iSXYAYAYAYAv

III

Strategiile optimale ale juctorului 2 sunt ,0,31

,

32

1

=

Y

=

32

,0,31

2Y . Astfel soluia (strategia

optimal) pentru juctorul 2 este ( ) [ ],1,01 21 += cuYYY iar valoarea jocului .314

=v

11. Folosind programarea liniar, rezolvai jocurile cu matricile de ctig:

a)

=

=

456493285306

),1520

AbA

Soluie. Considerm problema de programare liniar

[ ] ''2'1 ...max nyyyg +++= miyan

jjij ,1,1

1

'

==

.,1,0' niy j =

a) Avem, n primul caz, problema [ ]

.0,1512

max

'

2'

1

'

2'

1

'

2

'

2'

1

+

+=

yyyy

yyyg

Matricea simplex ataat este

000111101510120

asupra creia aplicm ARS. Obinem succesiv

53

51

5200

101

51

10101

210

2110

51

510

540

51

510

511

10120

Astfel ,61

101

35

,

153

'

11'

1max ====== ywydeciyiwdeciw

g

.

65

,

21

2'

2 == ydeciy

48

n plus .0,0 43'4'3 ==== yydeciyy

De asemenea 52

'

1 =x aa nct 31

,

51

,

32

2'

2'

11 ==== xdecixxwx

n concluzie strategiile optimale ale celor doi juctori sunt ,65

,

61

,

31

,

32

=

=

YX iar valoarea

jocului este .35

== vw

a) n cazul al doilea problema de programare liniar este: [ ]

4,1,014564193281536

max

'

'

4'

3'

2'

1

'

4'

3'

2'

1

'

4'

3'

1

'

4'

3'

2'

1

=++++++++

+++=

jyyyyyyyyy

yyyyyyyg

j

pentru care matricea simplex este

.

00001111110045641010932810015306

Aplicnd algoritmul reducerii simplex (ARS) obinem succesiv

810

810

81

85

450

211

210

21

2770

810

810

89

83

411

410

431

47

43

230

143

285

2810

281000

141

71

1410

141

2110

71

281

2830

1431

2101

71

143

1491

1423000

Astfel avem ,1143

maxw

g == deci 3

14=w respectiv

,

71

,

1 =y ,141

,

2 =y ,0,

3 =y ,0,

4 =y ,71

,

5 =y ,0,

6 =y ,0,

7 =y aa nct:

.0,0,32

,0,0,31

,

32

765432,

11 ======== yyyyyyywy n concluzie o strategie optimal

a juctorului 2 este ,0,0,31

,

32

=

Y iar valoarea jocului este 3

14== vw . De asemenea avem

49

,0,1 =x ,281

,

2 =x ,285

,

3 =x ,0,

4 =x ,0,

5 =x ,0,

6 =x ,281

,

7 =x aa nct

.

61

,0,0,0,65

,

61

,0 765432,

11 ======== xxxxxxxwx Strategia optimal a juctorului 1

este .65

,

61

,0

=

X Observm c exist i o alt soluie pentru c n ultima linie a matricei precedente

este un element egal cu 0 ntr-o coloan neredus. Obinem

143

285

2810

281000

71

72

710

71120

141

283

2850

716011

71

143

1491

1423000

Astfel ,141

,

1 =y ,0,

2 =y ,71

,

3 =y ,0,

4 =y ,71

,

5 =y ,0,

6 =y ,0,

7 =y deci

.0,0,32

,0,32

,0,31

7654321 ======= yyyyyyy

O alt soluie (strategie optimal) pentru juctorul 2 este .0,32

,0,31

2

=

Y

n concluzie, strategia optimal general a juctorului 2 este

( ) [ ],1,0,1 21 += YYY iar valoarea jocului este .314

=v

12. Matricea de ctig n reprezentare general

Trei firme utilizeaz, cu scop tehnologic, apa dintr-un acelai rezervor. Fiecare firm are la dispoziie dou strategii: i construiete staie de purificare (strategia 1) sau folosete apa nepurificat (strategia 2). Se tie c dac cel mult o firma folosete apa nepurificat atunci apa din rezervor este bun i nu apar cheltuieli. Dac, ns, cel puin dou firme folosesc apa nepurificat atunci fiecare firm pierde 3 uniti monetare. Construirea staiei de purificare cost o unitate monetar. Scriei matricele de ctig pentru acest joc. Soluie. Avnd n vedere anunul constatm c este un joc de 3 ,,persoane la care fiecare ,,juctor are 2 strategii. Deci .2,3 321 ==== mmmn Numrul situaiilor jocului este 8321 = mmm , iar ctigurile juctorilor sunt reprezentate n urmtorul tabel (reprezentare general):

50

Situaii Ctiguri

s1 s2 s3 H1(s) H2(s) H3(s)

1 1 1 -1 -1 -1

1 1 2 -1 -1 0

1 2 1 -1 0 -1

1 2 2 -4 -3 -3

2 1 1 0 -1 -1

2 1 2 -3 -4 -3

2 2 1 -3 -3 -4

2 2 2 -3 -3 -3

Valorile ,,ctigurilor au fost calculate avnd n vedere enunul. Spre exemplu, n situaia (1,2,2), firmele 2 i 3 folosesc apa nepurificat deci (cum sunt dou) fiecare firm pierde 3 uniti monetare. Firma 1, ns, i construiete staie de purificare, deci mai cheltuiete o unitate monetar, deci, ,,ctigul ei este -4.

13. Matricea de ctig n reprezentare bidimensional

Dou fabrici produc acelai tip de produs A, respectiv B, n dou sortimente 21 AiA respectiv

21 BiB . Produsele sunt interschimbabile. n urma unui test, fcut n avans, s-a constatat c preferinele cumprtorilor, exprimate n procente, sunt reprezentate n urmtorul tabel

B

A B1 B2

A1 40 90

A2 70 20

Precizm c precedentele date se refer la prima fabric (primul produs), n timp ce precedentele pentru a doua fabric (al doilea produs) sunt completare fa de procentul de 100%. Scrieti matricele de ctig pentru acest joc. Soluie. Sunt 2 juctori (fabricile) i fiecare are cte 2 strategii (posibiliti, sortimente). Din enun se constat c sunt precizate n tabelul cu cu punctele chiar ,,ctigurile primului ,,jucotor. Astfel ntr-o reprezentare general (tabelar) matricile de ctig pentru cei doi juctori pot fi scrise n tabelul:

51

Situaii Ctiguri

s1 s2 H1(s) H2(s)

1 1 40 60

1 2 90 10

2 1 70 30

2 2 20 80

n acest caz (pentru c sunt doar doi juctori) se poate utiliza i reprezentarea bi-matriceal (obinuit) pentru matricele de ctig. Astfel avem:

=

=

80103060

,

20709040

21 HH

14. Rezolvarea jocului bimatriceal Reconsiderm problema precedent cu urmtoarele modificri n condiiile privind cumprarea: se tie c 50% din cei care cumpr produsul A2 vor cumpra i produsul B2 respectiv se tie c 50% din cei care cumpr produsul B2 vor cumpra i produsul A2. Exprimnd vnzrile n valori absolute considernd 1000 de uniti vndute i pstrnd celelalte consideraii din enunul problemei precedente, se cere:

a) scriei matricele de ctig

b) rezolvai jocul bimatriceal necooperativ. Soluie. Se pstreaz datele privind juctorii i stagiile (,,mutrile) de la problema precedent. Sunt modificri doar la valorile ,,ctigurilor.

a) Se obine tabelul cu reprezentarea general a matricelor de ctig

Situaii Ctiguri

s1 s2 H1(s) H2(s)

1 1 400 600

1 2 900 100

2 1 700 300

2 2 600 900

Se consider c modificrile ,,eseniale sunt doar la situaia (2,2) (n rest sunt datele de la problema precedent la care procentele (100%) au fost nlocuite cu unitile vndute (1000)), care au fost calculate conform relaiilor

52

.90020021800,600800

21200 =+=+

n scrierea bi-matriceal avem matricile de ctig:

=

=

900100300600

,

600700900400

21 HH

b) ntruct

=+

1500100010001000

21tHH

deci nu este o matrice cu toate elementele egale (sum constant) jocul din aceast problem este un joc bi-matriceal (nu este antagonist). Pentru a-l rezolva trebuie s gsim toate soluiile admisibile de baz pentru dou sisteme de ecuaii liniare, iar apoi se vor pstra doar perechile de soluii care verific i al treilea sistem de ecuaii.

Primul sistem este:

=+++

=+++

=+

060070009004001

12''

1'

12221

11''

1'

12221

2221

tFFpptFFpp

pp

pentru care avem succesiv:

070010

7001

7001

761

0741

73

73

739000

1700

107001

7001

710

01011600700001119004001000011

21

6001

60010001

21

6001

60010010

65065

611100

10000113001100600070010111000

.

300110006001000011

90001110500

Se constat c avem trei soluii admisibile de baz:

53

.300,00,9001,0

0,0,0,650,21

,

21

,0,300,0,700,0,1

1211''

1'

12221

1211''

1'

12221

1211''

1'

12221

======

======

======

ttFFpp

ttFFpp

ttFFpp

Al doilea sistem este

=+++

=+++

=+

090010003006001

22''

2'

21211

21''

2'

21211

2221

tFFpptFFpp

pp

Pentru care avem succesiv

0161

65

65

217000

006001

6001

6001

211

106001

6001

6001

210

01011900100001113006001000011

115

11001

110010010

116

11001

110010001

115100

113

1181100

5001100110001000011

60001113000

.

100001160011000110090010110800

i acum, n acest caz, sunt trei soluii admisibile de baz:

.0,6000,9001,0.3

0,0,0,11

5100,

115

,

116

.2

,500,0,0,600,0,1.1

2221''

2'

21211

2221''

2'

21211

2221''

2'

21211

======

======

======

ttFFpp

ttFFpp

ttFFpp

Ultimul sistem de ecuaii este de forma

,2,1,2,1,0 === iisis sitp ii

deci produsul dintre un ,,p, i un ,,t cu aceeai indici trebuie sa fie 0 (zero).

Testnd toate cele 9 combinaii posibile (fiecare cu fiecare) constatm c doar soluiile (combinaiile) (2, II) satisfac acest ultim sistem. ntradevr

.0021

,0021

,00115

,00116

2222212112121111 ======== tptptptp

54

Nici o alta combinaie (din cele 8 rmase) nu se poate accepta pentru ca mcar o ecuaie din ultimul sistem nu este verificat. Spre exemplu combinaia (3, I) nu convine pentru c dei

.001,001,03000 222212121111 ====== tptptp

totui .060012121 = tp

n concluzie unica soluie (care verific toate cele trei sisteme) este:

,0,11

5100,0,650,

21

,

21

,

115

,

116

,,

2,

2,,

1,

122211211 ======== FFFFpppp

.022211211 ==== tttt

Astfel strategia optimal a jucatorului 1 este ,115

,

116

1

=P cu catigul

,650,,1,11 == FFF iar strategia optimal a juctorului 2 este

=

21

,

21

2P cu catigul

.

115100

,,

2,

22 == FFF

15. Rezolvarea jocului antagonist Reconsiderm jocul de la problema 13. Se cere: a) Rezolvai jocul. b) Scriei matricele de structur.

Soluie. Matricele de ctig sunt:

=

=

80103060

,

20709040

21 HH

i cum

=+

100100100100

21tHH jocul este antagonist cu suma constant 100.

a) Pentru a rezolva un astfel de joc este nevoie s rezolvm problema de programare liniar corespunztoare. n cazul de fa avem

55

=

=

+++=+++

=+

.min02070

090401

''

1'

1

12''

1'

12221

11''

1'

12221

2221

FFF

tFFpptFFpp

pp

Utilizm pentru rezolvare ARS i atunci putem scrie succesiv:

10000110101120700011190401000011

00011000101120700011190401000011

000000010000113011001000701011500

17010

701

701

750

07010

701

701

721

0741

73

73

75500

17010

701

701

750

70100050010000113011001000701011500

00011001000011

3011001000701011500

0001100107

1001

10010001

103

1001

10010010

6521

211100

0000000107

1001

10010001

103

1001

10010010

6521

211100

.

6521

210000

107

1001

10010001

103

1001

10010010

6521

211100

Astfel avem soluia (unic)

56

,0,65,103

,

107

''

1'

12221 ==== FFpp .0,0 1211 == tt

Problema dual (pentru primul juctor) are soluia (citibil tot din ultima matrice)

.

21

,

21

1211 == pp Deci

=

21

,

21

1P este strategia optimal a primului juctor, care va obine ctigul

maxim ,651 =F iar strategia optimal a juctorului 2 este

=

103

,

107

2P care va obine ctigul

maxim .652 =F

b) Matricele de structur (care reflect mprirea ctigurilor pe juctori, corespunztor deciziilor alese) sunt date n urmtoarele tabele

B B1 B2

A

A

= A1 14 13,5 27,5

A2 24,5 3 27,5

38,5 16,5 55

A A1 A2

B

B

= B1 21 10,5 31,5

B2 1,5 12 13,5

22,5 22,5 45

Elementele din matricele de structur constituie termenii rezultai ca urmare a exprimrii funciilor de ctig. Astfel n prima matrice au fost trecui termenii lui

===

2121

20709040

103

107

2111111tt PHPPHPF

dup cum urmeaz:

( ) ( ),2190

1035,13,

2140

10714 211212221111 phpphp ====

57

( ) ( ).2120

1033,

2170

1075,24 222212222111 phpphp ==== Apoi, pe ultima coloan, sunt

trecute sumele elementelor de pe liniile corespunztoare, iar pe ultima linie sunt trecute sumele de pe coloanele corespunztoare. Tabelul (de 55) reprezint ctigul final (maxim) al juctorului 1. ntr-un mod cu totul analog se obin elementele matricei de structur pentru al doilea juctor pornind de la

===

103

107

80103060

21

21

1222222tt PHPPHPF

De altfel situaia sintetic, exprimat n procente, asupra structurii tipurilor de produse, este urmtoarea:

%.5,13:%,5,31:%,5,27:%,5,27: 2121 BBAA

Asta n condiia c producia ambelor fabrici este 100%. Datorit antagonicitii pieei, a doua fabric realizeaz o vnzare mai mic dect prima, care este de 45%.

16. Considerm problema 15 n ipoteza c a doua fabric, la momentul cnd i alege strategia sa, cunoate strategia aplicat de prima fabric. Se cere:

a) Scriei matricele de ctig ale acestui nou joc.

b) Rezolvai jocul.

c) Comparai rezultatul obinut cu cel anterior i interpretai diferena dintre ele.

Soluie. a) Fa de problema anterioar (15) acum al doilea juctor are o informaie suplimentar: tie ce strategie a ales primul juctor. n consecin se va modifica matricea de ctig a juctorului 1, deoarece juctorul 2 poate aplica alte dou strategii obinute prin combinarea strategiilor sale ,21 BiB dup cum urmeaz:

strategia ,1B ca rspuns la strategia ,1A



strategia ,2B ca rspuns la strategia .2A

Astfel avem matricea de ctig a juctorului 1 dat de tabelul

58

B 1B 1B 2B 2B

A 1B 2B 1B 2B

1B 40 40 90 90

2B 70 20 70 20

Acum 2P va fi de forma [ ],,,, 242322212 ppppP = iar [ ].,, 12111 ppP = a) Pentru rezolvare, observm mai nti c strategia a treia este dominant aa nct poate fi

eliminat, deci 023 =p i atunci problema de programari liniar ce trebuie rezolvat este

=

=

++++=++++

=++

.min0202070

09040401

''

1'

1

12''

1'

1242221

11''

1'

1242221

242221

FFF

tFFppptFFppp

ppp

Avem succesiv

00011000010112020700011190404010000111

10000111010112020700011190404010000111

17010

701

701

75

750

07010

701

701

72

721

0741

73

73

7550

72000

17010

701

701

75

750

0000000010000111

30110010050070101150500

0001100010000111

30110010050070101150500

701000505001000011130110010050070101150500

59

5521

21000250

107

1001

1001000

211

103

1001

1001001

210

5521

21110250

.

400100500052

501

50100101

53

501

50100210

4011115000

Soluia optim este ,0,40,0,53

,

52

''

1'

1242221 ===== FFppp ,0,0 1211 == tt deci

= 0,

53

,

52

'

2P este o strategie optimal a juctorului 2. Se constat c mai exist i o alt soluie,

conform matricei

,

400100500020110050050100001112000110050

deci ,0,40,0,53

,

52

''

1'

1242221 ===== FFppp .20,0 1211 == tt

Astfel o alt strategie optimal a juctorului 2 este [ ]0,1,0''2 =P . n concluzie, innd cont i de faptul c ,023 =p soluia general (strategia optimal a juctorului 2) este

[ ] [ ] 11,0,0,0,1,00,0,53

,

52

212121''

22'

212 =++

=+= cuPPP iar valoarea maxim a lui

[ ].0,1,40 1''1'111 === PcuFFFesteF b) Compararea rezultatelor ne evideniaz matricele de structur (simplificate necompletate unde

sunt zerouri)

60

B B1 B1

A B1 B2

A

= A1 162 401+242 40

162 401+242 40

A A1

B

B

= B1 B1 242 242

B1 B2 601+362 601+362

60 60

Constatm o descretere cu 15% pentru prima fabric, ceea ce d o cretere cu 15% pentru fabrica a doua. Aceasta se datoreaz informaiei suplimentare pe care a avut-o fabrica a doua. Mai putem spune c prima fabric va face 40% din sortimentul A1 iar a doua fabric va face numai sortimentul B1, n total de 60% (cu mprirea: 242% datorit ,,strategiei B1: B1 i (601+362) % datorit ,,strategiei B1: B2, cu

[ ] 1,1,0 2121 =+ ).

61

TEME DE CONTROL

1. Fie un joc de dou persoane cu suma nul dat cu matricea de ctig

==

5354816106963

1 AH

Care este matricea de ctig a juctorului 2? Cte strategii are juctorul 1, respectiv juctorul 2?

2. (Jocul Morra). Doi juctori arat simultan unul sau dou degete de la mna stng i n acelai timp spun numrul de degete pe care ei cred c l va arta oponentul.Dac un din juctor nimerete numrul de degete artat de oponent, el primete aa de multe uniti monetare ct este numrul de degete pe care le-au artat mpreun. Dac ambii juctori nimeresc sau niciunul nu nimerete atunci niciunul nu primete nimic. Care este matricea de ctig a acestui joc?

3. Care dintre jocurile problemelor precedente au puncte a n strategii pure?

4. S se exprime ctigurile ateptate de ctre juctorul 1 n cazurile jocurilor precedente.

5. Folosind eliminarea iterat a strategiilor dominante rezolvai jocul cu matricea de ctig

=

3132515442030211

A

6. Gsii strategiile optimale i valoarea jocului (cu relaiile de calcul) pentru jocurile cu urmtoarele matrice de ctig:

;2532)

=Aa ;

5416)

=Ab .

1342)

=Ac

7. Rezolvai problema 6 cu metoda Williams.

8. Rezolvai problema 6 cu metoda grafic pentru jocurile de tip 2 x n i m x 2.

9. Folosind metoda grafic, rezolvai jocurile cu urmtoarele matrice de ctig:

62

a) ,153412

=A b)

=

05611342

A

10. Folosind coordonatele boricentrice rezolvai jocul cu matricea de ctig:

=

012111211

A

11. Folosind programarea liniar rezolvai jocurile cu urmtoarele matrice de ctig:

a) ,210381

032

=A b) .8114490657

=A

12. O firm produce trei tipuri de produse ,,, 321 PPP folosind trei tipuri de materiale .,, 321 MMM

Cheltuielile cu materialele ncorporate n cte o unitate de produs sunt date n tabelul:

P

M P1 P2 P3

M1 4 4 6

M2 3 5 3

M3 5 2 4

Scriei matricele de ctig n reprezentare general.

13. Dou ramuri economice au de fcut investiii n 4 obiective. Strategia cu codul i const n a finana

obiectivul i, .4,1=i Ca urmare a tuturor analizelor fcute s-a constatat c, pentru prima ramur,

ctigurile sunt date de matricea:

=

00021210

23012110

A

Se presupune c fiecare ramur i materializeaz ctigul n nelegere cu cealalt, adic ceea ce ctig una pierde cealalt i invers.

Scriei matricele jocului n reprezentare general.

63

14. Considerm dou persoane care joac un joc necooperativ dat cu matricele:

=

=

8781

,

4371

21 HH

Rezolvai jocul.

15. Pentru dezvoltarea economic i social a unui ora apare problema construirii sau nu a dou obiective economice. Exist dou strategii corespunztoare Ministerului tutelar i pentru autoritile locale ale oraului: 1 a construi primul obiectiv, 2 a construi al doilea obiectiv. Autoritile oraului au 2 strategii: 1 agreeaz (accept) propunerea Ministerului, 2 nu agreeaz (accept) propunerea.

Strategiile se aplic independent. Ctigurile sunt date de matricele:

=

=

1125

,

11210

21 HH

Rezolvai acest joc necooperativ.

16. Fie reconsiderat Problema 12. Acum se cere:

16.1. Care sunt procentele 321 ,, ppp pe care s le facem, n avans, pentru oferta cu materialele n aa

fel nct stocul s fie sigur asigurat i s

Elemente de Teoria Jocurilor

Documents

Transcript of Elemente de Teoria Jocurilor