Jocuri strategice

8/16/2019 Jocuri strategice

1/7

Jocuri strategice

Se numește joc de n persoane:

Γ = (A1,...,An,f 1,...,f n), unde Ai ≠ Ø, i=͞1͞,͞n, f i : A1x...xAn → ℝ, i=͞1͞,͞n.

Mulțimea Ai, i=͞1͞,͞n este mulțimea strategiilor jucătorului i, iar f i este funcția de câștig a jucătorului i.

Exercițiul 1. Jocul ″Piatra, Foarfeca, Hârtia″. La acest joc doi jucători aleg, simultan șisecret, unul dintre cuvintele piatra (P), foarfeca (F), hârtia (H). Dacă aleg același cuvânt,

jucătorii sunt la egalitate, iar dacă aleg cuvinte diferite câștigul este stabilit după următoareaconvenție: dacă se aleg cuvintele P și F, câștigă jucătorul care a ales P, dacă se aleg cuvinteleF și H, câștigă jucătorul ce a ales F, iar dacă se aleg cuvintele H și P, câștigă jucătorul ce aales H.

La acest joc posibilitățile de acțiune sunt: A1 = {P, F, H}, A2 = {P, F, H}. Notândcâștigurile partidei cu 1, pierderea cu -1 și egalitatea cu 0, funcțiile de câștig dunt date detabelele:

F1Jucător 2↓ P F H

Jucător 1→ P 0 1 -1F -1 0 1H 1 -1 0

F2 Jucător 2↓ P F HJucător 1→ P 0 -1 1

F 1 0 -1H -1 1 0

sauP F H

P (0,0) (1,-1) (-1,1)F (-1,1) (0,0) (1,-1)H (1,-1) (-1,1) (0,0)

f 1 : A1xA2 → ℝ (câștigul primului jucător) f 2 : A1xA2 → ℝ (câștigul celui de-al doilea jucător)

f 1 (P, P) = 0 f 1 (F, P) = -1 f 1 (H, P) = 1f 1 (P, F) = 1 f 1 (F, F) = 0 f 1 (H, F) = -1f 1 (P, H) = -1 f 1 (F, H) = 1 f 1 (H, H) = 0

0 1 -1 0 -1 1Jucătorul 1: -1 0 1 Jucătorul 2: 1 0 -1

1 -1 0 -1 1 0


2/7

Exercițiul 2. Trei întreprinderi folosesc, cu scop tehnologic, apă dintr -un rezervor deapă. Fiecare are două strategii: construiește stație de purificare (strategia 1) și folosește apăfără purificare (strategia 2). Se presupune că dacă cel mult o singură întreprindere foloseșteapă nepurificată, atunci apa din rezervor este potrivită pentru folosință și întreprinderearespectivă nu are cheltuieli. Dacă cel puțin două întreprinderi folosesc însă apa nepurificată,

atunci fiecare utilizator de apă pierde 3 unități monetare. Folosirea instalației de purificarecostă întreprinderea respectivă 1 unitate monetară. Cele trei întreprinderi formează mulțimea jucătorilor: I={1,2,3}. Mulțimea strategiilor

jucătorului i este Si = {1,2}, i ∊ I. Dacă întreprinderea i își construiește stația de purificare,strategia ei este si = 1, iar dacă folosește apă fără purificare, si = 2.

Matricea de câștig a jucătorului întâi se poate scrie în forma unei matrici bidimensionale:

-1 -1 -1 -4H1(s) = 0 -3 -3 -3

unde liniile reprezintă strategiile jucătorului 1, iar coloanele reprezintă strategiile(s2,s3) ale jucătorilor 2 și 3 luați împreună, ordonate lexicografic: prima coloană (1, 1), a douacoloană (1, 2), a treia coloană (2, 1), a patra coloană (2, 2).

Matricele de câștig H2(s) și H3(s) ale jucătorilor 2 și 3 pot fi scrise în aceeși formă caH1(s). Liniile marchează strategiile jucătorului 2, respectiv 3, iar coloanele strategiilor

jucătorilor 1 și 3, respectiv 1 și 2 luați împreună, deci (s1,s3), respectiv (s1,s2).Observație. O notație mai generală pentru matricele de câștig este în forma unui tabel

de tipul următor: Situația Matricea de câștig s1 ... sn H1 ... Hn

Astfel, în cazul exemplului din urmă, matricele de câștig pot fi date și în formatabelului:

Situația Matricea de câștig s1 s2 s3 H1 H2 H31 1 1 -1 -1 -11 1 2 -1 -1 0

1 2 1 -1 0 -11 2 2 -4 -3 -32 1 1 0 -1 -12 1 2 -3 -4 -32 2 1 -3 -3 -42 2 2 -3 -3 -3

Apă purificată Apă nepurificată S1: S2: f 1 : (A1xA2xA3) → ℝ f1(S1,S1,S1) = -1 f1(S2,S1,S1) = 0f1(S1,S1,S2) = -1 f1(S2,S1,S2) = -3f1(S1,S2,S1) = -1 f1(S2,S2,S1) = -3f1(S1,S2,S2) = -4 f1(S2,S2,S2) = -3


3/7

S1: S2: f 2 : (A1xA2xA3) → ℝ f2(S1,S1,S1) = -1 f2(S1,S2,S1) = 0f2(S1,S1,S2) = -1 f2(S1,S2,S2) = -3f2(S2,S1,S1) = -1 f2(S2,S2,S1) = -3f2(S2,S1,S2) = -4 f2(S2,S2,S2) = -3

S1: S2: f 3 : (A1xA2xA3) → ℝ f3(S1,S1,S1) = -1 f3(S1,S1,S2) = 0f3(S2,S1,S1) = -1 f3(S2,S1,S2) = -3f3(S1,S2,S1) = -1 f3(S1,S2,S2) = -3f3(S2,S2,S1) = -4 f3(S2,S2,S2) = -3

Matricile:

H1(S) = -1 -1 -1 -40 -3 -3 -3

H2(S) = -1 -1 0 -3-1 -4 -3 -3

H3 (S) = -1 0 -1 -3-1 -3 -4 -3

Definitie. O strategie a jocului de n persoane va fi notată

x = (x1,...,xn) ∊ A1x...xAn.

Se numește punct de echilibru o strategie ͞ x = (͞x1,..., ͞xn) ∊ A1x...xAn pentru caref i(͞x1,..., ͞xn) ≥ f i (͞x1,...,xi,..., ͞xn), oricare ar fi xi ∊ Ai, i=͞1͞,͞n.

f 1 (͞x1,..., ͞xn) ≥ f 1 (x1, ͞x2,..., ͞xn)f 2 (͞x1,..., ͞xn) ≥ f 2 (͞x1, x2,..., ͞xn)...............................................

f n (͞x1,..., ͞xn) ≥ f n (͞x1, ͞x2,..., xn)Punctul de echilibru ͞x este o strategie de la care nici un jucător nu se poate abate fără a

pierde. Rațiunea care îl poate face pe jucătorul i să adere la strategia ͞x este numai teama că încaz contrar, alegând o strategie x i diferă de cea indicată de punctul de echilibru, iar ceilalți n-1

jucători rămânând fideli strategiilor personale ͞x j, j≠1 câștigul său va fi diminuat.


4/7

Jocuri matriciale cu sumă nulă

Jocuri cu punct șa – câștigul unuia = pierderea altuia (funcția de câștig a primului jucătorul este f, iar -f este funcția de câștig pentru cel de-al doilea).

Fie jocul (A1, A2, f) unde f : A1 x A2 →ℝ. Dacă A1 = {x1,...,xm} A2 = {y1,...,yn} iar f (xi,

yi) = aij, i=͞1͞,͞m, j=͞1͞,͞n (dacă jucătorul 1 alege strategia xi din A1 și al doilea alege strategia y j din A2 atunci jucătorul 2 plătește primului jucător suma aij) Principiul minimax:

a11 a12 ........... a1n.............................................

A = .............................................am1 am2 ......... amn

Dacă jucătorul P1 alege strategia xi∊ A1, atunci el trebuie să se aștepte ca adversarul

său P2 să aleagă acea strategie y j ∊ A2 pentru care câștigul său aij este minim, adică:

αi = min aij, 1≤ j ≤ nPrin urmare, jucătorul 1 este sigur că va primi cel puțin un câștig egal cu α i. Deoarece

alegerea aceasta depinde de varianta sa el poate să-și aleagă strategia a.î. acest minim să fiecel mai mare posibil. Deci există o alegere a jucătorului P1 pentru care este este sigur că va

primi cel puțin:

v1 = max (αi) = max min aij 1≤i≤m 1≤i≤m 1≤j≤n

Într-un mod analog, ținând seama de faptul că câștigurile jucătorului P2 sunt totelementele matricii A însă luate cu semnul minus, jucătorul P2 alege strategia y j și esteinteresat ca să-și asigure un căștig de cel puțin:

β j = - min aij 1≤i≤m

Cu alte cuvinte, este interesat să-și reducă pierderea la minim și deci el trebuie săconsidere pierderea maximă la adoptarea strategiei y j, adică:

β j = max aij.1≤i≤m

Deoarece alegerea aceasta depinde de voința sa, el poate astfel să-și aleagă strategiaîncât acest minim să fie cât mai mare posibil, adică:

max min - aij .1≤j≤n 1≤i≤m

sau, ceea ce este echivalent, să-și aleagă astfel strategia încât să-și asigure o pierdere minimă,adică:

v2 = min β j = min max aij.1≤j≤m 1≤j≤n 1≤i≤m


5/7


6/7


7/7

A = 1 -1

-1 1

v1 = max (min aij) – pe linie → v1 = max (-1,-1) = -11≤j≤2

v2 = min (max aij) – pe coloana → v2 = min (1, 1) = 11≤i≤2

Exercițiul 5. O familie se aprovizionează pentru iarnă cu cărbune. Cantitateanecesară și condițiile de aprovizionare în timpul iernii sunt date prin tabelul următor:

Iarna Cantitatea necesară în t Prețul unitar u.m./t ușoară 4 70

obișnuită 5 75

grea 6 80

Dacă aprovizionarea se face vara, prețul este de 60 u.m./t. Având un spațiu de depozitare pentru 6t de cărbune să se rezolve următoarea

problemă: Să se formuleze problema aprovizionării în timpul verii în termenii teoriei jocurilor(să se scrie matricea jocului).

Rezolvare:

Daca se cumpara carbunele vara cand strategia familiei este:Iarna ușoară: 4t * 60 u.m./t = 240 u.m.Iarna obișnuită: 5t * 60 u.m./t = 300 u.m. Iarna grea: 6t * 60 u.m./t = 360 u.m.

Matricea de câștig a familiei

ușoară obișnuită grea

ușoară -240 -240-75 -240-80-80obișnuită -300 -300 -300-80

grea -360 -360 -360

v1 = max (min aij) = max (-400, -380, -360) = -3601≤i≤3 1≤j≤3 1≤i≤3 = > v1 = v2 = -360 = >

v2 = min (max aij) = min (-240, -415, -360) = -360 Soluția: Iarna va fi grea. 1≤j≤3 1≤i≤3 1≤j≤3

Jocuri strategice

Documents

Transcript of Jocuri strategice