Teoria Jocurilor

TEORIA JOCURILOR

1. Noțiuni generale

Teoria jocurilor este teoria matematică care se ocupă cu determinarea metodelor de alegere a deciziilor în cazuri de competiție sau situații conflictuale. O situație conflictuală este cea în care acționează doi sau mai mulți factori (persoane fizice, firme, partide politice) având scopuri contrarii. Astfel de situații sunt: concurența economică, vânzările la licitație, alegerile parlamentare etc.. Teoria jocurilor se ocupă și de cazurile în care o activitate intră în conflict cu caracterul întâmplător al unor evenimente naturale (epidemii, secetă). Pentru construirea unui model formal, simplificat al situației cercetate se vor selecta caracteristicile principale, cele secundare neglijându-se. Terminologia folosită este cea de la jocurile de societate sau de noroc.

Prin joc sau joc strategic se înțelege situația în care acționează o mulțime de elemente raționale (numite jucători sau parteneri) care în mod succesiv și independent, într-o ordine și condiții fixate într-un ansamblu de reguli, iau câte o decizie (efectuează o mutare) dintr-o mulțime dată de alternative. Regulile jocului fixează și situațiile în care se termină jocul, precum și câștigul sau recompensa pentru fiecare jucător. Un joc realizat se mai numește partidă.

Acțiunile întreprinse de jucători în cadrul unei partide se numesc mutări. Acestea pot fi: libere – când alegerea alternativei este univocă sau

aleatoare, când alegerea alternativei este supusă întâmplării și e determinată de un mecanism aleator (zar).

După cantitatea de informație de care dispune fiecare jucător există jocuri cu informație completă (șahul) și jocuri cu informație parțială (bridge-ul), necunoașterea intențiilor adversarului constituind elementul esențial al situațiilor conflictuale.

Ansamblul de reguli ce definesc în mod unic mișcările libere în funcție de situația ivită în timpul jocului se numește strategie. Dacă unul dintre adversari are la dispoziție m alternative, iar partida se încheie printr-o alegere, se spune că jucătorul are la dispoziție m strategii pure. Când partidele se repetă, jucătorii pot alege strategii pure cu anumite frecvențe sau probabilități și atunci se spune că utilizează o strategie mixtă. Dacă numărul strategiilor pure este finit, spunem că avem un joc finit, în caz contrar avem un joc infinit. Fiecare jucător urmărește aplicarea unei strategii care să îi aducă un câștig maxim, deci își caută o strategie optimă.

Câștigul pi realizat de jucătorul Pi are semnificația unei sume bănești sau a unui număr de puncte, bunuri etc.. Dacă pi > 0, jucătorul Pi realizează un câștig în sensul uzual al cuvântului, iar dacă pi < 0 înregistrează o pierdere.

Din punct de vedere al câștigului distingem:

jocuri cu sumă nulă – când la sfârșitul unei partide suma pierdută de o parte din jucători este câștigată de ceilalți și

jocuri cu sumă nenulă – când jucătorii pot să-și mărească concomitent câștigurile, prin alegerea unor strategii adecvate.

După numărul n al jucătorilor, jocurile pot fi cu doi parteneri sau cu n > 2 parteneri.

Fie cu doi parteneri P1 și P2 ce constă în 3 mutări libere. O mutare înseamnă alegerea unuia dintre numerele a sau b, a ≠ b. La prima mutare P1 alege liber pe a sau pe b; la a doua mutare P2, informat asupra alegerii făcute de P1, alege la rândul său unul din numerele a sau b. În sfârșit, la a treia mutare P1, informat asupra alegerii făcute de P2, alege unul dintre numerele a sau b.

Observăm că este un joc în doi, cu mutări libere și informație

Vârful 0 arată momentul inițial, iar cifra 1 scrisă sub 0 arată că prima mutare este a lui P1. Din 0 pornesc două muchii spre vârfurile a și b, ce

reprezintă alegerile lui P1. Sub a și b scriem 2, pentru că următoarea mutare

este a lui P2. Din fiecare vârf pornesc două muchii spre alte vârfuri a și b,

reprezentând alegerile lui P2 și sub aceste vârfuri scriem 1 deoarece P1 face următoarea mutare spre alte vârfuri notate a șib (care vor fi vârfuri terminale). Sub ele nu mai scriem nimic, dar fiecăruia îi asociem un vector

bidimensional (p1, p2) ale cărui componente reprezintă respectiv câștigurile celor doi jucători, decurgând din regulile jocului.

S-au obținut 8 vârfuri terminale ce vor determina tot atâtea partide, deoarece o partidă este reprezentată de un lanț ce leagă vârful 0 de unul din vârfurile terminale. Cele 8 partide sunt: (a, a, a), (a, a, b), (a, b, a), (a, b, b), (b, a, a), (b, a, b), (b, b, a) și (b, b, b).

Jocul nu este cu sumă nulă deoarece dacă, de exemplu, s-ar realiza partida (a, a, b) avem p1 = 2, p2 = 1 și p1 + p2 = 3 ≠ 0.

Mulțimea strategiilor jucătorului P1 este:

A = (a, a), (a, b), (b, a), (b, b) , unde primul element din fiecare pereche reprezintă numărul ales la prima mutare, iar al doilea element indică numărul ales la a treia mutare.

Mulțimea strategiilor lui P2 este:

B = (a), (b) , reprezentând alegerile la a doua mutare.

Asociem jocului considerat un tabel cu două intrări A = A1, …,A4

– strategiile lui P1 și B = B1, B2 , strategiile lui P2.

La intersecția liniei lui Ai cu coloana lui Bj avem un dreptunghi în care deasupra diagonalei am scris partida, iar dedesubt vectorul (pi, pj) al câștigurilor celor doi jucători, când aceștia aleg strategiile Ai, respectiv Bj.

Din acest exemplu observăm că există diferite moduri de reprezentare a unui joc, cu ajutorul unui arbore sau matricial.

Observație: Dacă în același joc considerăm câștigurile date de

următoarea corespondență:

(a, a, a) → (2, -2) (b, a, a) → (1, -1)

(a, a, b) → (-1, 1) (b, a, b) → (3, -3)

(a, b, a) → (4, -4) (b, b, a) → (-2, 2)

(a, b, b) → (5, -5) (b, b, b) → (-3, 3)

jocul va fi: finit, cu informație completă, cu mutări libere și cu sumă nulă, deoarece p1 + p2 = 0 pentru orice vector (p1, p2).

În acest caz reprezentarea matricială poate fi simplificată, scriind în locul vectorului (p1, p2) doar câștigul p1 al lui P1, deoarece cel al lui P2 e cunoscut, egal cu – p1.

Forma simplificată a matricei este:

2. Jocuri matriceale

Fie un joc finit între doi jucători, în care un jucător are m strategii pure, iar celălalt n strategii pure. Un astfel de joc se numește joc m × n sau joc matriceal. Dacă jocul este cu sumă nulă, el se va numi antagonist. În

acest din urmă caz, funcția de câștig se poate prezenta sub forma unui tabel de plăți, adică o matrice m × n, notată cu A, astfel:

a11

A = M

am1

Matricea A se numește matricea jocului (matricea câștigurilor). Elementul aij este câștigul jucătorului P1 când alege strategia Ai și jucătorul P2 alege strategia Bj. Această formă matriceală de prezentare a jocului se va numi forma normală.

i = 1, m , j = 1, n .

Imaginea prin f a produsului cartezian A × B este matricea A. Matricea A se scrie deci în raport cu un singur jucător și anume P1,

primul jucător (numit și jucătorul maximizant, din punct de vedere formal – ambii jucători urmărind același scop). Când P1 câștigă valoarea aij, P2 plătește lui P1 valoarea aij, i = 1, m , j = 1, n .

Pentru P2 toate elementele matricei au semn contrar (fiind un joc cu sumă nulă). P2 se mai numește jucător minimizant. Vom nota jocul definit în condițiile de mai sus prin tripletul: G = (A, B, f).

Exemplu

În jocul numit „aruncarea monedei”, fiecare jucător alege liber stema

(S) sau valoarea (V). Dacă alegerile coincid, jucătorul P1 primește de la P2 un euro. Dacă alegerile diferă, P2 primește de la P1 un euro.

Atunci forma normală a jocului pentru P1 este:

2.1 Jocuri cu punct șa

Fie un joc G = (A, B, f), cu matricea A = (aij), i = 1, m , j = 1, n . Jucătorii sunt considerați la fel de competenți. Ei aderă la un principiu de comportare, născut din raționalitate. Astfel, P1 va acționa așa încât cel mai mic câștig asigurat pe care îl poate obține de la P2 să fie cât mai mare, iar P2 urmărește să facă pe cât posibil mai mică, cea mai mare valoare pe care ar trebui să o dea lui P1. Acest principiu poartă numele de principiul minimax.

Dacă P1 va alege strategia Ai ∈ A, se așteaptă ca P2 să aleagă acea strategie Bj ∈ B care să ofere un câștig cât mai mic pentru P1. Fie acesta

αi = min aij, i = 1, m .

1≤j≤n

Dintre cele m strategii pure, P1 va alege acea strategie Ai care dă cea mai mare valoare a lui αi. Notând:

α = max αi = max min aij

i i j

α se va numi valoarea inferioară a jocului și se mai notează vG .

Strategia care asigură lui P1 un câștig egal cu vG se numește strategie maximin.

Dacă P2 alege strategia Bj ∈ B, se așteaptă ca P1 să aleagă strategia Ai ∈ A care îi asigură acestuia un câștig cât mai mare.

Fie

βj = max aij, j = 1, n .

1≤i≤m

Dintre cele n strategii pure, P2 va alege acea strategie Bj care dă cel mai mic câștig lui P1, adică cea care dă cea mai mică valoare lui βj. Notând

β se va numi valoarea superioară a jocului și se mai notează cu vG . Strategia care asigură lui P2 o pierdere egală cu vG se numește

strategie minimax.

Exemplu

Fie jocul caracterizat de matricea:

Dacă P1 alege strategia A1 vizând câștigul a14 = 2, P2 poate alege strategia B3, obligându-l pe P1 la un câștig a13 = -2 (adică o pierdere); când P1 alege A2, P2 poate răspunde cu B2 și P1 câștigă a12 = 0, iar când P1 alege A3, P2 poate alege strategia B3 și P1 câștigă atunci a31 = -3.

Să determinăm valorile inferioară și superioară ale jocului.

Calculând αi = min aij, i = 1,3 , obținem:

1≤j≤4

α1 = min 0,1,-2,2 = -2

1≤i≤3

α2 = min 1,0,3,2 = 0 α3 = min 2,4,-3,3 = -3

Valoarea inferioară a jocului este:

vG = max αi = max -2,0,-3 = 0 = α2.

Determinăm βj = max aij, j = 1,4 . Obținem:

1≤i≤3

β1 = max 0,1,2 = 2 β2 = max 1,0,4 = 4 β3 = max -2,3,-3 = 3 β4 = max 2,3 = 3.

Valoarea superioară a jocului este:

vG = min βj = min 2,4,3 = 2 = β1.

1≤j≤4

De aici rezultă că strategia maximin este A2, iar strategia minimax este B1.

Observație: Calculele de mai sus pot fi simplificate prin organizarea lor într-un tabel obținut din cel inițial, la care se adaugă coloana elementelor

αi și linia elementelor βj, astfel:

Dacă într-un joc avem: vG = vG = v

valoarea comună v se numește valoarea jocului. Elementul aij în care se realizează această egalitate se numește punct șa, iar jocul respectiv se va

numi joc cu punct șa. Strategiile Ai și Bj corespunzătoare punctului șa aij formează o pereche de strategii minimax și se vor numi strategii optime. Ele determină valoarea jocului care este egală cu elementul corespunzător punctului șa.

Exemplu

Fie jocul cu matricea:

Observăm că α = vG = 3 = vG = β

Elementul a21 = 3 va fi punctul șa. Strategiile A2 și B1 sunt strategii optime, iar valoarea jocului este v = 3.

Observații:

Și elementul a41 = 3 este punct șa, deci și strategiile A4 și B1 sunt optime, iar valoarea jocului este tot v = 3. Deci punctul șa nu este unic.

Abaterea de la strategia optimă poate duce la micșorarea câștigului lui P1. De exemplu, dacă P1 alege A3 și P2 îi răspunde cu B3, câștigul său este a33 = 0, deci scade (tentația fiind aceea de a obține câștigul maxim, egal cu 9).

Elementul a21 = 3 este cel mai mic de pe linia și cel mai mare de pe coloana pe care se află. La fel a41 = 3. Aceasta justifică și denumirea de punct șa.

Exemplu

Fie jocul cu matricea:

Observăm că strategia A1 are toate câștigurile respectiv mai mari ca ale strategiei A2. Jucătorul P1 care dorește un câștig cât mai mare nu va alege A2, pentru că poate câștiga mai mult prin A1 oricare ar fi strategia aleasă de P2. Spunem că strategia A1 domină strategia A2, care este dominată. A2 poate fi eliminată din joc.

Pentru jucătorul P2, strategia B4 domină strategiile B1 și B3, acestea din urmă conducând la pierderi mai mari pentru P2 decât B4. Deci se poate renunța la B1 și B3 și matricea A se reduce la:

În concluzie, o strategie pură domină o altă strategie pură dacă duce la câștiguri mai bune decât aceasta din urmă. Un jucător nu trebuie să folosească niciodată strategii dominate, acestea fiindu-i nefavorabile. Din matricea A se elimină liniile care au toate elementele respectiv mai mici sau egale cu ale altei linii și coloanele ce au toate elementele respectiv mai mari sau egale decât ale altei coloane. Acest principiu poartă numele de principiul dominării strategiilor. Aplicarea lui conduce la reducerea ordinului matricei A și a volumului de calcule. Se poate demonstra ca

eliminarea strategiilor dominate conduce la un joc care are aceeași valoare ca și jocul inițial.

Să observăm că jocul „redus”, rezultat prin eliminarea strategiilor dominate nu are punct șa, deci nici cel inițial.

2.2 Jocuri fără punct șa

În jocurile fără punct șa, un jucător își poate majora câștigul folosind altă strategie decât cea minimax dacă este informat asupra comportării adversarului. Informații asupra comportamentului adversarului se pot obține prin repetarea partidelor, dacă acesta își menține în toate partidele strategia minimax. Un jucător nu trebuie să folosească mereu aceeași strategie și nici să folosească strategiile după o regulă ce poate fi descoperită de adversar. Va fi necesară alternarea strategiilor pure, cu anumite probabilități.

În cele ce urmează vom vedea că, în cazul unui joc matriceal fără punct șa, valoarea jocului o vom determina folosind un alt joc matriceal asociat primului, numit joc mediat, notat Γ = (X, Y, ϕ), unde:

iar Y mulțimea strategiilor mixte pentru P2;

c) ϕ: X × Y → ℝ, cu:

m n

ϕ(x, y) = ∑∑aijxi yj dacă P1 folosește strategia mixtă

i=1 j=1

x = (x1, …, xm), iar P2 folosește strategia mixtă y = (y1, …, yn). Dacă introducem variabila aleatoare:

i=1

folosește strategia mixtă x = (x1, …, xm), iar P2 folosește strategia pură Bj. Analog, variabila aleatoare:

n

ϕ(i, y) = ∑aijyj și reprezintă câștigul mediu realizat de P1 când

j=1

folosește strategia Ai iar P2 folosește strategia mixtă y = (y1, …, yn).

Atunci, putem scrie că:

n

= ∑yjϕ(x, j) , de unde se vede

j=1

că ϕ(x, y) semnifică valoarea medie a jocului, care se mai scrie matriceal astfel: ϕ(x, y) = xAyT.

Pentru jocul mediat Γ = (X, Y, ϕ), vom defini valoarea inferioară vΓ

și valoarea superioară vΓ prin expresiile:

vΓ = max min ϕ(x, y)

x∈X y∈Y

vΓ = min max ϕ(x, y)

y∈Y x∈X

Prezentăm acum, cu sau fără demonstrație, câteva rezultate din teoria funcțiilor de mai multe variabile reale ce vor fundamenta principiile matematice ale jocurilor matriceale.

Teorema 1

Fie X, Y două subspații ale unor spații liniare și f: X × Y →ℝ. Dacă

există mărimile:

Demonstrație:

Notăm g(x) = min f(x, y), (∀) x ∈ X și h(y) = max f(x, y), (∀) y ∈Y.

y∈Y x∈X

Din definiția extremelor, avem:

g(x) ≤ f(x, y), (∀) y ∈Y și (∀)x ∈ X Atunci:

max g(x) ≤ max f(x, y) = h(y), (∀) y ∈Y, și deci:

x∈X x∈X

Revenind la semnificațiile lui g și h, rezultă relația (1).

Consecință 1. Pentru orice joc matriceal G = (A, B, f) există vG și

vG și vG ≤vG .

Demonstrație:

Existența celor două valori, vG și vG rezultă din faptul că f are o mulțime finită de valori. Și dacă în teorema 1 X = A, Y = B și f (Ai, Bj) = aij pentru orice Ai ∈ A și Bj ∈ B, atunci relația (1) devine vG ≤vG .

Teorema 2

În ipotezele teoremei 1, o condiție necesară și suficientă ca

este să existe x0 ∈ X și y0 ∈ Y și un număr w ∈ ℝ astfel încât: f(x, y0) ≤ w ≤ f(x0, y), pentru orice x ∈ X și y ∈ Y. (3)

Demonstrație:

Necesitatea: Presupunem relația (2) adevărată. Fie x0 ∈ X punctul

care maximizează expresia min f(x, y) și fie y0 ∈ Y punctul care

y∈Y

minimizează expresia max f(x, y), adică:

x∈X

De aici și din relația (2) rezultă că:

De unde, evident f(x0, y) ≥ w și f(x, y0) ≤ w, (∀) x ∈ X și (∀) y ∈ Y, adică relația (3).

Suficiența: Presupunem că există x0 ∈ X, y0 ∈ Y și w ∈ℝ astfel încât relația (3) să fie adevărată.

Din f(x0, y) ≥ w, (∀) y ∈ Y, rezultă că și min f(x0, y) ≥ w.

y∈Y

Analog, din f(x, y0) ≤ w, (∀) x ∈ X, rezultă că și max f(x, y0) ≤ w,

x∈X

deci max f(x, y0) ≤ w ≤ min f(x0, y), (∀) x ∈ X, (∀) y ∈ Y.

x∈X y∈Y

Dar min max f(x, y) ≤max f(x, y0) ≤ w

y∈Y x∈X x∈X

și de aici, în baza tranzitivității relației „≤”, rezultă că:

Această relație, împreună cu relația (1), implică

w = max min f(x,y) = min max f(x,y), fapt ce încheie demonstrația.

x∈X y∈Y y∈Y x∈X

Definiție: Fie f: X × Y →ℝ. Punctul (x0, y0) ∈ X × Y este punct șa

pentru f dacă:

f(x, y0) ≤ f(x0, y0) ≤ f(x0, y), (∀) x ∈ X și (∀) y ∈ Y.

Consecință 2: Dacă G = (A, B, fG) este un joc matriceal m × n, atunci o condiție necesară și suficientă ca vG = vG = w este ca fG să admită un punct șa.

Demonstrație:

Se aplică teorema 2, în care X = A, Y = B, fG(Ai, Bj) = aij, i = 1, m ,

j = 1, n , luând w = fG(Aio, Bj0).

Condiția necesară și suficientă de existență a punctului șa este să existe perechea de strategii pure Aio, Bjo astfel încât:

aiojo = max min aij = min max aij

i j j i

adică elementul aiojo este cel mai mic din linia i0 și în același timp cel mai mare din coloana j0.

Strategiile A i0 și B j0 corespunzătoare punctului șa sunt strategii optime.

Teorema 3. (teorema fundamentală de minimax)

Fie un joc G = (A, B, f) de două persoane, caracterizat de matricea

marginile pe X.

Deci există max ϕ(x, y) pentru orice y ∈Y, iar această funcție este

x∈X

liniară în y ∈ Y, deci este și continuă. Cum Y este o parte închisă a lui ℝn,

rezultă că există max min ϕ(x, y).

x∈X y∈Y

Analog se arată că există min max ϕ(x, y) și existența e demonstrată.

y∈Y x∈X

adică vΓ ≤vΓ .

Pentru demonstrarea inegalității inverse dăm, fără demonstrație:

Lema 1 (lema fundamentală a dualității):

Dacă A = (aij), i = 1, m , j = 1, n și x = (x1, …, xm), y = (y1, …, yn)

îndeplinesc condițiile:

asemenea vectori x, y pentru care numai una din următoarele situații este adevărată:

m

i) ∑aijxi ≥ 0, j = 1, n ;

i=1

n

ii) ∑aij y j ≤ 0, i = 1, m .

j=1

Aplicând această lemă pentru matricea jocului A, dacă are loc prima situație (i), înseamnă că există x = (x1, …, xm) astfel încât a1jx1 +…+amjxm ≥0, (∀) j = 1, n , de unde:

n

ϕ(x, y) = ∑(a1j x1 +… + a mj x m )y j ≥ 0, (∀) y ∈ Y, deci

j=1

Dacă situația (ii) din lemă este adevărată, există y = (y1, …, yn) ∈ Y astfel încât

ai1y1 + … + ainyn ≤ 0, i = 1, m , de unde:

m

ϕ(x, y) = ∑(ai1y1 +… + ain yn )xi ≤ 0, (∀) x ∈ X, deci și

i=1

max ϕ(x, y) ≤ 0, de unde rezultă că și min max ϕ(x, y) ≤ 0.

x∈X y∈Y x∈X

Cum numai una dintre cele două situații din lemă are loc, niciodată

Fie Gk = (A, B, fk) având matricea Ak = (aij – k); i = 1, m , j = 1, n ,

k ∈ℝ și jocul mediat corespunzător Γk = (X, Y, ϕk), ϕk fiind câștigul mediu în jocul mediat cu matricea Ak, adică:

m n m n m n

ϕk(x, y) = ∑∑(aij − k)xi yj =∑ ∑ aijxi y j − k∑∑xi yj .

i=1 j=1 i=1 j=1 i=1 j=1

Cum ∑∑xi y j = 1, obținem:

i j

ϕk(x, y) = ϕ(x, y) – k (6)

Pentru jocul Γk, rezultă din (5) că nu poate avea loc inegalitatea:

sau ținând seama de (6) nu poate avea loc relația

Negarea acestei ultime relații implică:

vΓ ≥vΓ , care, împreună cu (4), dau vΓ = vΓ .

Definiție. Valoarea unui joc matriceal G = (A, B, f) cu f(A × B) = A, A = (aij), i = 1, m , j = 1, n fără punct șa este dată de valoarea vΓ = vΓ = v a jocului mediat Γ = (X, Y, ϕ) asociat lui.

Consecință 3: Orice joc matriceal mediat are o valoare și deci și o soluție. În mulțimea strategiilor X și Y există cel puțin o pereche de strategii mixte x0, y0 pentru care:

ϕ(x0, y0) = max min ϕ(x, y) = min max ϕ(x, y).

x∈X y∈Y y∈Y x∈X

Teorema 4 [6]

Dacă G = (A, B, f) și Γ(X, Y, ϕ) jocul mediat asociat, atunci:

vG ≤ vΓ ≤ vΓ ≤ vG

Teorema 5 [6]

Asupra matricei A = (aij) a unui joc se pot efectua următoarele operații:

dacă se permută liniile (coloanele) între ele, valoarea jocului nu se

schimbă și nici probabilitățile de folosire a strategiilor de către jucătorul P1 (respectiv P2);

dacă la fiecare element aij din matricea A a unui joc matriceal de valoare v se adaugă același număr real k, atunci strategiile mixte optime rămân neschimbate, iar valoarea jocului devine v’ = v + k;

dacă toate elementele matricei A dintr-un joc matriceal de valoare v se înmulțesc cu același număr k > 0, atunci strategiile mixte optime rămân neschimbate, iar valoarea jocului devine v’ = kv.

2.3 Rezolvarea jocurilor matriceale

Teorema 3 (teorema minimax) asigură existența strategiilor optime în jocuri de două persoane cu sumă nulă. Ne preocupă să găsim modul cum

pot fi calculate aceste strategii. În cele ce urmează, vom prezenta câteva metode pentru soluția unor jocuri matriceale.

2.3.a Jocuri 2 × 2

Considerăm jocul matriceal cu:

Dacă jocul are punct șa, rezolvarea sa e banală. Presupunem că jocul nu are punct șa. Atunci strategiile optime x = (x1, x2) și y = (y1, y2) vor avea toate componentele pozitive. Valoarea jocului v este:

v = ϕ(x, y) = a11x1y1 + a12x1y2 + a21x2y1 + a22x2y2

Cum y este strategie optimă, fiecare expresie din paranteze este cel mult egală cu v. Dacă presupunem că una e strict mai mică decât v, de exemplu:

a11y1 + a12y2 < v a21y1 + a22y2 ≤ v

cum x1 > 0 și x1 + x2 = 1 ar rezulta că membrul stâng din (7) este mai mic ca v. Deci va trebui ca:

a11y1 + a12y2 = v a21y1 + a22y2 = v.

Raționând analog se obține: a11x1 + a21x2 = v

a12x1 + a22x2 = v.

Sau matriceal:

Notând J = (1, 1) și ținând seama că x1 + x2 = 1 și y1 + y2 = 1, găsim formulele de calcul pentru x, y și v.

Dacă A este nesingulară, din (8) avem:

xA = vJ și x = vJA-1. (8’) Dar x1 + x = 1 este echivalentă cu xJT = 1.

În (8’), înmulțind cu JT, avem: vJA-1JT = xJT = 1 de unde:

1

v = JA−1JT .

Atunci, din (8’) vom avea:

JA−1

x = JA−1JT .

Prima relație din (8) se mai scrie: AyT = vJT, de unde:

unde A* este matricea adjunctă a lui A, A determinantul lui A și J = (1,1). Aceste formule se verifică și când A este inversabilă.

Exemplu

Să se determine soluția jocului matriceal:

Introducând rezultatele obținute în (9) avem:

Observație: Metoda de mai sus poate fi aplicată în rezolvarea matriceală a jocurilor, în care dacă notăm matricea câștigurilor cu C = (cij), i = 1, m , j = 1, n , pentru jocul Γ = (X, Y, f), soluția și valoarea jocului se

determină ([9], [21]) cu ajutorul formulelor:

În relațiile (9’) avem:

A o matrice nesingulară a lui C, de ordinul r, 2 ≤ r ≤ min(m, n);

A este determinantul matricei A;

Jr = (1, …, 1), matrice de ordinul 1 × r;

Determinarea soluției se face astfel:

a) se caută toate submatricele nesingulare A, pornind de la r = min(m,n);

se rezolvă jocurile corespunzătoare matricelor de la a), care admit numai strategii pozitive;

în x și y se completează cu zerouri componentele

corespunzătoare liniilor și coloanelor din C care nu intră în A, obținând strategiile x0 și y0;

se verifică condițiile corespunzătoare relațiilor (8), date de

criteriul Neumann și anume x0A = vJ și AyT = vJT.

Dacă aceste relații sunt îndeplinite x0 și y0 sunt strategii optime ale jocului Γ, iar v este valoarea jocului.

2.3.b Jocuri 2 × n și m × 2

În acest caz presupunem că cel puțin un jucător posedă numai două strategii pure. Fie P1 jucătorul ce are numai două strategii pure, adică analizăm cazul 2 × n. Jocurile m × 2 se tratează într-un mod similar.

Dacă matricea jocului este:

și x = (x1, x2) e strategia jucătorului P1, atunci acesta urmărește să maximizeze funcția v(x) – valoarea jocului.

Modelul matematic al jocului pentru P1 este: a11x1 + a21x2 ≥ v

∶

a1nx1 + a2nx2 ≥ v x1 + x2 = 1

x1, x2 ≥ 0

și poate fi adus la forma matematică a unui model de programare liniară având necunoscutele x1, x2 și v, astfel:

[max]f = v

a11x1 + a21x2 – v ≥ 0

∶

a1nx1 + a2nx2 – v ≥ 0 x1 + x2 = 1

x1, x2 ≥ 0, v – oarecare.

Exemplu

Să se determine strategia optimă a jucătorului P1 în jocul definit de

Rezolvare

Strategiile lui P1 verifică sistemul: -2×1 + 8×2 ≥ v

4×1 – 6×2 ≥ v -4×1 + 16×2 ≥ v x1 +x2 = 1

x1, x2 ≥ 0, v – oarecare.

Forma matematică a modelului de programare liniară în necunoscutele x1, x2 și v va fi:

[max]f = v

-2×1 + 8×2 – v ≥ 0 4×1 – 6×2 – v ≥ 0 -4×1 + 16×2 – v ≥ 0 x1 +x2 = 1

x1, x2 ≥ 0, v – oarecare.

Cum x1 = 1 – x2, x1, x2 ∈ [0,1], modelul de mai sus devine: [max]f = v

10×2 – v ≥ 2

10×2 + v ≤ 4

20×2 – v ≥ 4

x2 ∈ [0,1], v – oarecare.

Rezolvăm grafic această problemă și obținem:

v 4

2

1

0

-1

-2

M(0,3; 1)

1 x2

v = 4-10×2

-4

Regiunea hașurată conține mulțimea punctelor ce satisfac restricțiile modelului de programare liniară. Punctul M aflat la intersecția dreptelor generate de restricțiile 1 și 2 (deci corespunzătoare coloanelor 1 și 2 din A) are abcisa x2 = 0, 3 și ordonata v = 1. Atunci strategia lui P1 este x = (x1, x2), unde x2 = 0, 3 și x1 = 1 – x2 = 0,7 și valoarea jocului este v = 1.

Observație: Aceste valori pot fi obținute cu formulele (9) pentru jocul matriceal 2 × 2 format din coloanele 1 și 2 ale matricei A. Fie

Am obținut astfel și strategia optimă a lui P2.

2.3.c Rezolvarea jocurilor matriciale prin programare liniară

Fie jocul G = (A, B, f) cu matricea A = (aij), i = 1, m , j = 1, n de valoare v, având jocul mediat corespunzător Γ = (X, Y, ϕ).

Dacă jucătorul P1 folosește strategiile Ai, cu probabilitățile xi, i = 1, m , poate spera la un câștig egal cel puțin cu valoarea v a jocului, pentru orice strategie Bj, j = 1, n , a lui P2.

Putem scrie sistemul de inecuații: a11x1 + … + am1xm ≥ v a12x1 + … + am2xm ≥ v

∶

a1nx1 + … + amnxm ≥ v x1 + … + xm = 1

xi ≥ 0; i = 1, m .

Dacă jucătorul P2 folosește strategiile Bj cu probabilitățile yj, j = 1, n , el se așteaptă la o pierdere cel mult egală cu valoarea v a jocului și putem scrie sistemul de inecuații:

a11y1 + … + a1nyn ≤ v a21y1 + … + a2nyn ≤ v

∶

am1y1 + … + amnyn ≤ v y1 + … + yn = 1

yj ≥ 0; j = 1, n .

Sistemul (I) corespunde condiției ϕ(x, j) ≥ v, j = 1, n , iar sistemul (II) corespunde condiției ϕ(i, y) ≤ v pe care trebuie să le verifice strategiile x = (x1, …, xm) și y = (y1, …, yn) pentru a fi optime.

[min]f =

mai mare valoare a lui

Pentru a transforma cele două sisteme în modele de programare liniară este necesar ca valoarea v a jocului să fie pozitivă. Deci vom

presupune v > 0 (în caz contrar se face modificarea matricei A în A = ( aij )

cu aij = aij + k > 0, (∀)i = 1, m , j = 1, n și k > 0.

Condițiile ca xi și respectiv yj să fie probabilități, devin: X1 + …+ Xm = 1v

Y1 + …+ Yn = 1v

Deoarece jucătorul P1 urmărește obținerea celei mai mari valori a câștigului v, deci a celei mai mici valori a lui 1v , el își propune să obțină

minf = X1 + … + Xm.

Jucătorul P2 urmărește obținerea celei mai mici pierderi v, adică cea

1v , deci își propune să obțină maxg = Y1 + …+ Yn.

Astfel sistemele (I) și (II) corespunzătoare celor doi jucători se pot scrie ca un cuplu de probleme duale de programare liniară și anume:

1v = X1 + …+ Xm

a11X1 + … + am1Xm ≥ 1

∶

a1nX1 + … + amnXm ≥ 1 Xi ≥ 0, i = 1, m

[max]g = 1v = Y1 + …+ Yn a11Y1 + … + a1nYn ≤ 1

∶

am1Y1 + … + amnYn ≤ 1

Yj ≥ 0, j = 1, n

Prin rezolvarea uneia dintre cele două duale se obțin strategiile mixte optime ale ambilor jucători precum și valoarea jocului v:

v = [min]1f = [max]1g .

Este de preferat rezolvarea lui II deoarece implică un volum mai mic de calcule.

Exemplu

O firmă A dorește să lanseze pe piață un anumit tip de produs în trei sortimente A1, A2, A3. Concurenta ei, firma B, prezintă produsul în sortimentele B1, B2, B3. Se cunoaște, din sondajele făcute că dacă

cumpărătorii trebuie să aleagă între sortimentul Ai, i = 1,3 și Bj, j = 1,3 , ei preferă fie produsele firmei A (situație notată cu 1), fie pe cele ale firmei B (situație notată cu -1), fie sunt indiferenți (situație notată cu 0), conform tabelului următor:

Să se determine strategia firmei A în fața concurentei B.

Rezolvare

Fie x1, x2, x3 probabilitățile corespunzătoare celor 3 strategii pure ale firmei A și y1, y2, y3 probabilitățile corespunzătoare strategiilor firmei B.

Determinăm valoarea inferioară α și valoarea superioară β a jocului.

α = max αi = 0 este valoarea inferioară a jocului și

β = min βj = 1 este valoarea superioară a jocului.

Deci jocul nu are punct șa, iar valoarea v a jocului are proprietatea că 0 ≤ v ≤ 1.

Modelele duale de programare liniară vor fi:

-x1 + x2 + x3 ≥ v -x2 + x3 ≥ v

xi ≥ 0, i = 1,3

sau cu notațiile Xi = xvi , i = 1,3 și [min]f = 1v

[min]f = 1v = X1 + X2 + X3

X1 – X2 ≥ 1

-X1 + X2 + X3 ≥ 1 -X2 + X3 ≥ 1

Xi ≥ 0, i = 1,3

pentru firma A, iar pentru firma B:

-y1 + y2 – y3 ≤ v y2 + y3 ≤ v

yj ≥ 0, j = 1,3

Cu notațiile Yj = yvj , j = 1,3 și [max]g = 1v , avem: [max]g = 1v = Y1 + Y2 + Y3

Y1 – Y2 ≤ 1

-Y1 + Y2 – Y3 ≤ 1 Y2 + Y3 ≤ 1

Yj ≥ 0, j = 1,3

Se rezolvă prin algoritmul simplex al doilea model, aducând problema la forma standard

Firma A va avea strategia mixtă

x = ( 13 , 0, 23 ), adică va trebui să producă 33, 33% produse din primul sortiment iar restul 66,66% din al treilea sortiment. Acest plan de producție îi asigură firmei A un câștig, fără nici un risc, de 13 în vreme ce

concurenta ei, firma B, va avea o pierdere de 13 .

În concluzie, în rezolvarea unui joc matricial se parcurg următorii

pași:

Pasul 1. Se determină valoarea inferioară α și valoarea superioară β

jocului:

dacă α = β, jocul are punct șa, se determină strategiile pure și valoarea jocului;

dacă α < β, jocul nu are punct șa; vor trebui determinate

strategiile mixte optime și valoarea jocului. Pasul 2. Se elimină strategiile dominate.

Pasul 3. Ne asigurăm ca valoarea v a jocului să fie un număr pozitiv,

știind că v ∈ [α, β].

Pasul 4. Scriem modelul de programare liniară pentru jucătorul P2 și rezolvăm prin algoritmul simplex problema din care citim [max]g, Y1,…,Yn și X1, …, Xm.

1

Pasul 5. Determinăm: v = [max]g , xi = vXi, i = 1, m și yj = vYj, j = 1, n , adică soluția optimă a problemei.

Observație: Dacă matricea jocului este de forma 2 × 2 sau 2 × n, în pasul 3 putem alege și alte metode în afara algoritmului simplex, cum ar fi cele prezentate la 2.3.a și 2.3.b.

3. Jocuri contra naturii

Până acum ne-am ocupat de jocuri în care alegerea strategiilor era determinată de matricea A a câștigurilor primului jucător P1. Sunt situații în care riscurile cu care se iau hotărâri nu pot fi cunoscute, deoarece jucătorul P2 nu acționează rațional. Un astfel de jucător poate fi considerată natura, de unde și denumirea de jocuri contra naturii. De analiza unor astfel de situații se ocupă teoria deciziilor.

În cele ce urmează vom prezenta unele criterii de alegere a deciziei jucătorului P1 (numit și statistician) în jocurile contra naturii (numite și jocuri în caz de incertitudine). Menționăm că atitudinea față de joc, diferită de la o persoană la alta, face ca în teoria deciziilor să nu existe criterii universal valabile. Aplicarea criteriilor poate conduce la rezultate diferite. Alegerea strategiei ar putea fi dată de rezultatul aplicării mai multor criterii.

Vom presupune că statisticianul – jucătorul P1, dispune de m strategii pure A1, …, Am, iar natura are n stări B1, …, Bn.

Fie matricea A = (aij), i = 1, m , j = 1, n , unde aij este câștigul lui P1 când alege strategia Ai, iar natura se află în starea Bj.

Criteriul lui Hurwicz (criteriul optimismului)

Optimismul jucătorului P1 se definește ca un număr α ∈ [0,1]. Se determină numerele reale:

mi = min aij și Mi = max aij , i = 1, m .

j j

Fiecărei strategii Ai îi asociem expresia:

αMi + (1 – α)mi, i = 1, m .

Strategia optimă va fi cea care corespunde la:

max [αMi + (1 – α)mi]

i

În folosirea acestui criteriu trebuie să se definească în prealabil optimismul jucătorului, adică numărul α ∈ [0, 1].

Exemplu

Se consideră jocul contra naturii a cărui matrice a câștigurilor lui P1

în orice strategie a sa Ai, i = 1,4 și în orice stare Bj, j = 1,4 a naturii este:

Să se determine în funcție de α strategia optimă a lui P1.

Pentru α = 23 care este strategia optimă?

Rezolvare

Atașăm matricei date coloanele elementelor: mi, Mi și

αMi + (1 – α)mi, unde mi este respectiv cel mai mic, iar Mi este cel mai mare număr de pe linia respectivă. Obținem astfel:

Ca să determinăm max [αMi + (1 – α)mi], știind că α ∈ [0,1],

i

observăm că α + 2 ≤ 2α + 2, (∀)α ∈ [0,1]. Merită studiate cazurile:

4α + 1 < α + 2, de unde α < 13 ;

α + 2 ≤ 4α + 1 < 2α + 2, de unde 13 ≤ α < 12 ;

2α + 2 ≤ 4α + 1, de unde α ≥ 12 .

Deci pentru α ∈ [0, 13 ), 2α + 2 este cea mai mare valoare și cum ea corespunde strategiei A1, aceasta este strategia optimă.

Pentru α ∈ [ 13 , 12 ), tot 2α + 2 este valoarea maximă deci A1 e strategie optimă.

Pentru α ∈ [ 12 , 1], 4α + 1 e valoarea maximă și A3 este strategia optimă.

În particular α = 23 ∈ [ 12 , 1], deci A3 este strategia optimă.

Criteriul Bayes – Laplace

În cazul acestui criteriu se va presupune că stările naturii sunt egal probabile. Și cum numărul lor este n, probabilitatea ca natura să se afle în

starea Bj este n1 , (∀) j = 1, n .

Dacă jucătorul P1 va alege strategia Ai, câștigul său va fi

Observația 1:

Dacă se cunosc totuși probabilitățile diferitelor stări ale naturii respectiv y1, …, yn, deci strategia y = (y1, …, yn) cu yj ≥ 0, j = 1, n și

n

∑y j =1, câștigul mediu al statisticianului P1 când folosește strategia Ai va

j=1

fi, conform formulei din paragraful 2.2:

n

ϕ(i, y) = ∑aijy j , iar câștigul mediu va fi maxim pentru strategia

j=1

corespunzătoare valorii:

max ϕ(i, y).

1≤i≤m

Observația 2:

Criteriul lui Laplace introduce toate neajunsurile valorii medii. Dacă estimările au fost făcute grosolan apar erori în apreciere, ce vor duce la decizii greșite. Criteriul devine uneori inacceptabil când elementele jocului sunt foarte dispersate.

Exemplu

Pentru jocul din exemplul precedent să se determine strategia optimă a lui P1 în cazurile:

când stările naturii sunt egal probabile;

când probabilitățile ca natura să se afle în stările ei sunt respectiv:

aceasta este strategia optimă, după criteriul Laplace.

b) Calculăm pentru fiecare strategie Ai valoarea expresiei date de

ϕ(i, y), i = 1,4 . Obținem:

ϕ(1, y) = 19 ⋅2 + 92 ⋅4 + 94 ⋅ 3 + 92 ⋅3 = 19 ⋅28;

1≤k≤m

ϕ(2, y) = 19 ⋅3 + 92 ⋅2 + 94 ⋅ 3 + 92 ⋅2 = 19 ⋅23; ϕ(3, y) = 19 ⋅1 + 92 ⋅5 + 94 ⋅ 2 + 92 ⋅1 = 19 ⋅21; ϕ(4, y) = 19 ⋅3 + 92 ⋅3 + 94 ⋅ 2 + 92 ⋅3 = 19 ⋅23.

Cea mai mare valoare este 19 ⋅ 28 și corespunde lui ϕ(1, y), deci A1 este strategia optimă.

Criteriul lui Savage (criteriul regretelor)

Savage compară rezultatul deciziei în cazul necunoașterii stării naturii cu cel care s-ar obține dacă s-ar cunoaște această stare. Diferența dintre câștigul realizat când se ia decizia fără a cunoaște stările naturii și cel realizat dacă se cunosc acestea reprezintă regretul sau ce s-ar fi câștigat dacă P1 ar fi cunoscut stările naturii.

Pornind de la matricea A = (aij), i = 1, m , j = 1, n , se formează o nouă matrice R = (rij), numită matricea regretelor, unde elementul:

rij = max akj – aij, i = 1, m , j = 1, n , adică rij este dat de diferența

dintre cel mai mare element de pe coloana j și elementul aij.

Se obține astfel un nou joc caracterizat de matricea R care va fi tratat după criteriul minimax. P1 va alege strategia pe linia căreia se obține:

min max rij , adică linia pe care cel mai mare regret este minim.

1≤i≤m 1≤j≤n

Exemplu

Pentru același joc din ultimele două exemple, aplicând criteriul regretelor, să se determine strategia ce va fi aleasă de P1.

Rezolvare

Se determină mai întâi matricea regretelor ale cărei elemente de pe o coloană se obțin scăzând din cel mai mare element al coloanei fiecare element al acesteia. Se obține:

Atunci min max rij = min 1, 3, 2, 2 = 1, ce corespunde strategiei

i j

A1, deci P1 alege această strategie.

Criteriul lui Wald

Dacă jocul are punct șa, statisticianul P1 alege strategia Ai determinată de condiția:

max ( min aij).

i j

Dacă jocul nu are punct șa, se determină strategia mixtă x = (x1, …, xm) pentru care:

Exemplu

Aplicarea criteriului lui Wald jocului cercetat și cu celelalte criterii ne duce la concluzia că jocul nu are punct șa. Procedând ca în paragraful 2.3.c, se determină strategia mixtă a statisticianului și se găsește vectorul:

x = (1/3, 1/3, 0, 1/3),

de unde rezultă că P1 poate alege oricare dintre strategiile sale A1, A2 sau A4.

Observație: Criteriile aplicate nu au dus mereu la aceeași decizie dar în majoritatea cazurilor s-a obținut că cea mai bună strategie este A1; statisticianul pe aceasta o va alege.

Aplicație

Patronul unui magazin achiziționează un număr de frigidere de un anumit tip pe o perioadă de 6 luni (primăvară – vară), pentru a le vinde. Din observațiile statistice, bazate pe cererea din ultimii doi ani, el estimează că va vinde un număr de frigidere cuprins între: 15 și 25 cu probabilitatea de 0,1; între 25 și 35 cu probabilitatea de 0,4; între 35 și 45 cu 0,3 și între 45 și 55 cu 0,2.

Costul unitar de achiziție este de 300 euro iar prețul unitar de vânzare este 400 euro (incluzând cheltuielile de transport și garanția de funcționare pe un an). Toate frigiderele nevândute până în toamnă se restituie furnizorului pentru 250 euro/bucata.

Să se stabilească numărul optim de frigidere pe care să le achiziționeze patronul pentru a obține un câștig cât mai mare.

Rezolvare

Determinăm matricea A = (aij), i, j = 1,4 , unde aij este câștigul

obținut de patron când aplică strategia Ai, i = 1,4 și cererea este în starea Sj,

j = 1,4 . Obținem astfel:

unde de exemplu elementul de pe linia A3 și coloana S2 se calculează astfel: din cele 40 frigidere achiziționate se vând 30.

Diferența dintre prețul unitar de vânzare și cel de achiziționare este de 100 euro pentru un frigider, ce reprezintă câștigul patronului. Pentru cele 30 frigidere vândute va câștiga 3000 euro. Dar alte 10 frigidere nevândute vor fi restituite furnizorului cu o pierdere unitară de 50 euro dată de diferența dintre costul de achiziție 300 și cel de restituire 250. Deci pierderea va fi de 500 euro și atunci beneficiul total va fi de: 3000 – 500 = = 2500 euro.

Deoarece în stabilirea deciziei contează consecințele economice se pot aplica în rezolvarea problemei criteriile: maximin, minimax, Savage, Bayes-Laplace:

a) Prin criteriul maximin se alege minimul fiecărei linii și dintre acestea se găsește maximul:

care este 2000 și recomandă strategia A1.

b) Criteriul minimax, bazat pe prudență, indică alegerea elementelor maxime pe fiecare linie și apoi determinarea celui mai mic dintre acestea.

Acest element este 2000 și arată că cea mai prudentă decizie este A1. c) Criteriul lui Savage este de fapt criteriul minimax aplicat pe

matricea regretelor, ce va avea forma:

pentru care vom căuta maximul pe fiecare linie și apoi cel mai mic dintre acestea. Găsim:

cel mai mic element este 1000 și recomandă strategia A3.

d) Criteriul Bayes-Laplace presupune calculul câștigului mediu pentru fiecare strategie folosind probabilitățile date în enunțul problemei și formulele din paragraful 2.2. Astfel:

ϕ(1,y) = 0,1⋅2000 + 0,4⋅2000 + 0,3⋅2000 + 0,2⋅2000 = 2000

ϕ(2,y) = 0,1⋅1500 + 0,4⋅3000 + 0,3⋅3000 + 0,2⋅3000 = 2850

ϕ(3,y) = 0,1⋅1000 + 0,4⋅2500 + 0,3⋅4000 + 0,2⋅4000 = 3100

ϕ(4,y) = 0,1⋅500 + 0,4⋅2000 + 0,3⋅3500 + 0,2⋅5000 = 2900 Cel mai mare câștig se obține când se aplică strategia A3.

4. Jocuri de două persoane cu sumă arbitrară (bimatriceale)

Jocurile de două persoane cu sumă oarecare extind în mod natural jocurile cu sumă nulă de care ne-am ocupat până acum. Ele produc și o schimbare calitativă importantă, în sensul că, dacă regulile jocului o permit, jucătorii pot căuta împreună căi (strategii) de îmbunătățire a câștigurilor lor, ceea ce, în cazul jocurilor antagoniste, era exclus din punct de vedere logic.

Obiectul teoriei jocurilor fiind dat de analiza situațiilor de tip competițional, regulile care reglementează concurența vor sta la baza dezvoltărilor ulterioare.

Astfel, vom studia separat jocurile cu sumă arbitrară de tip necooperativ, în care nu este permisă (sau nu există interes pentru) colaborarea între jucători și apoi jocurile de tip cooperativ, în care jucătorii își pot corela strategiile și/sau pot apela la transferul mutual al unor părți din câștiguri. Și într-un caz și în celălalt, preocuparea principală va fi de a defini un concept de soluție a jocului, de a cerceta condiții de existență și a identifica metode de determinare a acesteia.

Ca o trăsătură care distinge jocurile cu sumă arbitrară de cele cu sumă nulă se evidențiază interdependența strategiilor componente ale unei soluții a jocului.

4.1 Jocuri cu sumă arbitrară necooperative

Vom nota, ca și mai înainte, cei doi jucători cu P1 și P2 și vom presupune că strategiile lor (pure) sunt în număr finit:

= A1, …, Am reprezintă mulțimea strategiilor lui P1, iar

= B1, …, Bn , mulțimea strategiilor lui P2.

Definiție: Se numește joc de două persoane cu sumă arbitrară dat în formă normală, un sistem G = A, B; f1, f2 , unde A și B conțin strategiile celor doi jucători iar fi(⋅,⋅), i = 1,2 sunt funcții definite pe A × B cu valori reale, numite funcții de câștig, corespunzătoare fiecăruia dintre aceștia.

Pentru o pereche de strategii (Ai, Bj) vom nota f1(Ai, Bj) = aij și f2(Ai, Bj) = bij, i = 1, m , j = 1, n . În vederea unei scrieri compacte a

elementelor care definesc un joc de acest tip, apelăm la o reprezentare matriceală ca cea de mai jos:

Deoarece elementele tabloului de mai sus sunt perechi de numere reale care ar putea proveni din suprapunerea a două matrici de dimensiuni m × n conținând câștigurile celor doi jucători, luați separat, asemenea jocuri se mai numesc pe scurt jocuri bimatriceale.

Să remarcăm faptul că asupra valorilor sumelor f1(Ai, Bj) + f2(Ai,Bj),

i = 1, m , j = 1, n nu se impune nici o condiție. Considerăm, spre exemplificare, următorul joc:

G = A, B; f1, f2 ; A = A1, A2 , B = B1, B2 ; f1(A1, B1) = 3, f1(A2, B1) = 1, f1(A1, B2) = 1, f1(A2, B2) = 0; f2(A1, B1) = 0, f2(A2, B1) = 4, f2(A1, B2) = 2, f2(A2, B2) = 1.

Vom analiza jocul folosind forma sa matriceală. B1 B2

Se observă că pentru jucătorul P1 este preferabil să joace strategia A1 în raport cu A2, indiferent ce strategie adoptă P2 (B1 sau B2), deoarece avem f1(A1, ⋅) ≥ f1(A2, ⋅) (într-adevăr, 3 > 1 și 1 > 0).

Recunoaștem aici existența unei strategii dominate a jucătorului 1, în speță A2.

Referitor la strategiile lui P2, să observăm că nici una dintre ele nu o domină pe cealaltă (0 < 2, dar 4 > 1).

Obiectivul nostru fiind acela de a prevedea desfășurarea jocului, prin precizarea strategiilor pe care jucătorii, cel mai probabil, le vor folosi (în scopul rațional al maximizării câștigului), vom reduce matricea jocului renunțând la linia corespunzătoare strategiei dominate (pe care ar fi irațional să o adopte P1).

B1 B2

A1 (3,0) (1,2)

Este evident acum că jucătorul P2 va alege strategia B2, care îi asigură un câștig mai mare. În concluzie, perechea de strategii (A1, B2) se constituie într-o soluție a jocului, rezultată din confruntarea intereselor lui P1 și P2. Un efect, în acest caz, este acela că nici un jucător nu își realizează câștigul maxim admisibil (3, respectiv 4), fapt posibil din punct de vedere teoretic, în general.

În exemplul precedent, raționamentul utilizat a urmărit identificarea unei convenții la care jucătorii, în mod independent, sunt dispuși să adere, concretizate printr-o soluție unică a jocului necooperativ. Aceasta conduce la ideea folosirii perechii de strategii (A1, B2) în mod liber, în mai multe partide (repetări ale jocului), de către jucători raționali care așteaptă unul de la celălalt un astfel de comportament.

Ideea cristalizării unei convenții are, desigur, o latură ideală. Nu putem presupune că pentru un joc oarecare vom elimina pe rând, strategiile (strict) dominate, rămânând, în final, cu o singură pereche de strategii. Pe de altă parte, acest proces de eliminare poate să conducă la o mulțime terminală de perechi de strategii, dintre care unele nu au calitățile unei soluții.

În precizarea calităților pe care trebuie să le aibă o soluție a jocului, vom ține cont de faptul că tendința unilaterală de câștig a unui jucător poate fi amendată de opțiunile celuilalt, dar nu și anihilată. De aceea, apare naturală cerința ca strategia unui jucător, care este o componentă a soluției, să reprezinte cel mai bun răspuns la strategia aleasă de celălat jucător, care completează soluția. O astfel de soluție poate fi numită strategic – stabilă, deoarece nici un jucător nu are interesul să se abată de la strategia sa, atâta vreme cât nici ceilalți nu încearcă acest lucru. Ideea de echilibru pe care trebuie să îl realizeze strategiile care alcătuiesc soluția jocului este acum transparentă. Cele de mai înainte sunt redate în următoarea:

Definiție. Într-un joc bimatriceal dat în formă normală

G = A, B; f1, f2 , perechea de strategii (A*, B*) reprezintă un punct de echilibru Nash dacă au loc relațiile:

f1(A*, B*) ≥ f1(Ai, B*), oricare ar fi Ai ∈ A și

f2(A*, B*) ≥ f2(A*, Bj), oricare ar fi Bj ∈ B

Altfel spus, maxf1(Ai, B*) este atins în A*, iar maxf2(A*, Bj) e atins

Ai∈A Bj∈B

în B*.

Cum A* ∈ A și B* ∈ B, se obișnuiește, pentru mai multă claritate, să se spună că (A*, B*) este punct de echilibru Nash în strategii pure.

Observație: Noțiunea de punct de echilibru Nash o generalizează pe cea de punct șa de la jocurile matriceale (cu sumă nulă). Într-adevăr, condițiile:

f(Ai, Bjo) ≤ f(Aio, Bjo) ≤ f(Aio, Bj) (∀) Ai ∈ A, (∀) Bj ∈ B, care definesc punctul șa aiojo = f(Aio, Bjo) se mai pot scrie:

f(Aio, Bjo) ≥ f(Ai, Bjo), (∀)Ai ∈ A, -f(Aio, Bjo) ≥ -f(Aio, Bj), (∀)Bj ∈ B.

De aceea, unii folosesc termenul de punct de echilibru în loc de punct șa atunci când se referă la soluția unui joc matriceal G = (A, B, f).

Definiția precedentă se poate extinde, fără dificultate, la cazul a n jucători, ale căror funcții de câștig sunt funcții reale de n argumente.

Exemplu

Se consideră jocul în formă normală G, căruia îi corespunde

Determinarea punctelor de echilibru Nash ale jocului se va face în modul următor: pentru fiecare jucător și pentru fiecare strategie a acestuia, se determină răspunsul optim al celuilalt jucător la respectiva strategie. Pentru a-l marca, vom sublinia în acea linie / coloană câștigul maxim corespunzător.

Astfel, observăm că dacă P1 ar folosi strategia A1, atunci P2 ar trebui să folosească strategia B3 și vom scrie atunci (0,4) în poziția din matrice corespunzătoare perechii (A1, B3). Asemănător, pentru strategiile A2 și A3 ale lui P1, vom selecta răspunsurile B3, respectiv B1 și vom completa (3, 3), respectiv (2, 4) în locurile potrivite din tabel.

În privința replicilor lui P1 la alegerile posibile ale lui P2, strategiei B1 îi va corespunde A1 și vom scrie în prima coloană (4, 0) (deoarece 4 > 0

și 4 > 2). Pentru coloanele a doua, a treia și a patra, vom selecta strategiile de răspuns A1, A2 și A2, respectiv.

Se obține așadar, după procedura de marcare, următorul tabel:

Ținând seama de definiția dată anterior, deducem că punctele de echilibru corespund acelor perechi de câștiguri în care ambele componente apar subliniate (dacă există). În exemplul analizat, această situație apare doar în cazul perechii de strategii (A2, B3), care va reprezenta deci soluția Nash a jocului.

Vom clarifica în continuare legătura care există între eliminarea strategiilor strict dominate și existența punctelor de echilibru Nash. Au loc următoarele rezultate:

Propoziția 4.1

În jocul dat sub formă normală G = A, B; f1, f2 , dacă strategiile (S1* , S *2 ) reprezintă un punct de echilibru, atunci ele nu sunt afectate de procedeul de eliminare a strategiilor strict dominate.

Propoziția 4.2

Dat fiind jocul G = A, B; f1, f2 , dacă eliminarea succesivă a strategiilor dominate strict conduce la desființarea tuturor combinațiilor de strategii, cu excepția lui (S1* , S *2 ), atunci această pereche constituie unicul punct de echilibru Nash al jocului.

Vom justifica cele afirmate în propoziția 4.1, folosind reducerea la absurd. Să presupunem că (S1* , S *2 ) este un punct de echilibru al jocului, dar că una dintre strategiile componente, de exemplu S 1* , a fost eliminată la un moment dat (eventual precedată de alte strategii din A\ S 1* , sau B\ S *2 ,

eliminate și ele), fiind strict dominată. Să notăm cu S’1 o strategie din A care a „supraviețuit” eliminării succesive până la momentul dispariției lui S1* și care o domină strict pe aceasta. Are loc deci relația:

f1(S1* , B) < f1(S’1, B) pentru orice strategie B dintre cele rămase la

acest moment. Cum S 1* ar fi prima eliminată dintre strategiile de echilibru, din inegalitatea de mai sus rezultă:

f1(S1* , S *2 ) < f1(S’1, S *2 ).

Dar astfel este contrazis faptul că S1* este cel mai bun răspuns al lui P1 la strategia S *2 a lui P2, așa cum impune faptul că (S1* , S *2 ) e punct de echilibru. Cu aceasta, demonstrația se încheie.

Mai departe ne preocupă problema existenței punctelor de echilibru multiple ale unui joc bimatriceal. Conform propoziției 4.1, nu este posibil ca strategiile componente ale unuia dintre ele să fie evitate în procesul de eliminare succesivă a strategiilor strict dominate, iar altele, cu aceeași proprietate, nu. De aici rezultă că în propoziția 4.2 este suficient să arătăm că (S1* , S *2 ) este punct de echilibru Nash. (Demonstrația, asemănătoare cu cea precedentă, se sprijină pe ipoteza că mulțimile de strategii ale ambilor jucători sunt finite).

Ne vom servi în discuția noastră de exemplul jocului G = (A, B; f1, f2) cu matricea câștigurilor:

Se poate observa ușor că strategia A1 domină strict pe A3 și că B3 domină strict pe B2 după eliminarea lui A3. După ce suprimăm strategiile dominate, jocul are forma simplificată:

B1 B3

Urmând procedura descrisă anterior, sau prin verificare directă, folosind definiția, se deduce că (A1, B3) și (A2, B1) sunt puncte de echilibru Nash ale jocului.

Aceasta ne permite să remarcăm faptul că, spre deosebire de jocurile cu sumă nulă, în jocurile bimatriceale, prin interschimbarea strategiilor corespondente între două puncte de echilibru, perechile rezultate nu mai sunt puncte de echilibru, așa cum o demonstrează (A1, B1) și (A2, B3).

Problema principală însă este ce anume trebuie înțeles prin soluția unui astfel de joc. Examinând câștigurile fiecărui jucător în parte, constatăm că nu putem privilegia vreunul din punctele de echilibru, deoarece jucătorul P1 preferă, firesc, pe (A1, B3), iar P2 preferă pe (A2, B1).

Teoretic, putem conveni că soluția jocului este formată din ambele puncte de echilibru. Practic însă este nevoie de o negociere (uneori dură) între cei doi jucători sau de un arbitraj pentru a stabili pentru ce strategii vor opta fiecare. Șanse mai mari de concretizare ar putea avea în acest caz varianta care dă câștigurile (3, 4), dar elemente de ordin subiectiv nu trebuie ignorate.

O situație de incertitudine în alegerea strategiilor optime ca cea de față, este un teren propice pentru a testa utilitatea strategiilor de tip maximin.

Astfel, în ce privește strategia maximin a lui P1 vom găsi: min 2,2,4 = 2 → A1; min 3,1,2 = 1 → A2; min 1,0,3 = 0 → A3,

deci strategia căutată este A1. Analog, pentru P2 avem:

min 0,4,3 = 0 → B1; min 1,2,2 = 1 → B2; min 2,3,0 = 0 → B3, de unde rezultă că strategia maximin a lui P2 este B2.

După cum se observă, însă, perechea de strategii maximin (A1, B2) nu este un punct de echilibru. Oricare dintre jucători preferă câștigul care îi revine ca urmare a alegerii în comun a unuia din punctele de echilibru față de câștigul minim asigurat (într-adevăr (4, 2) > (2,1) și (3, 4) > (2, 1)). În fapt, are loc următorul rezultat general:

Propoziția 4.3

Orice punct de echilibru furnizează fiecărui jucător în parte, un câștig cel puțin egal cu câștigul său maximin.

Demonstrație:

Presupunem că (A*, B*) este punct de echilibru al jocului, în notațiile de mai înainte. Atunci avem, pentru P1:

f1(A*, B*) ≥ f1(Ai, B*) ≥ minf1(Ai, Bj) pentru orice strategie Ai ∈ A.

Bj∈B

De aici rezultă imediat:

maxminf1(Ai, Bj) ≤ f1(A*, B*).

Ai∈A Bj∈B

Pentru jucătorul P2, obținem folosind din nou definiția punctului de

echilibru: f2(A*,B*) ≥ f2(A*, Bj) ≥ minf2(Ai, Bj), (∀) Bj ∈ B, deci

Ai∈A

f2(A*,B*) ≥ maxminf2(Ai, Bj).

Bj∈B Ai∈A

În concluzie, într-un joc cu sumă arbitrară, strategiile maximin își pierd din importanță.

Puncte de echilibru în strategii mixte

Posibilitatea existenței mai multor puncte de echilibru Nash într-un joc bimatriceal, cu implicațiile sale în stabilirea soluției jocului nu este, totuși, lucrul care stânjenește cel mai mult. O problemă fundamentală care apare în acest context este faptul că există jocuri cu sumă arbitrară chiar dintre cele mai simple, care nu admit strategii pure de echilibru.

Să considerăm următorul joc:

Se poate observa pe acest exemplu că nici o pereche de strategii (Ai, Bj) nu poate realiza echilibrul. Astfel, pentru (A1, B1) observăm că jucătorul P2 are interesul să devieze de la strategia B1 către B2, care îi asigură un câștig superior. Analog, (A2, B1) nu poate fi punct de echilibru, pentru că jucătorul P1 va prefera strategia A1 lui A2, ș.a.m.d..

Este greu de admis ideea că astfel de jocuri nu admit soluție, în sensul echilibrului de tip Nash. Cheia de rezolvare stă și aici, ca și în cazul jocurilor cu sumă nulă, în lărgirea conceptului de strategie și definirea noțiunii de echilibru în această accepțiune mai largă.

Trebuie făcută precizarea că noul tip de strategie îl înglobează pe cel utilizat până acum în discuție și că identificarea unor puncte de echilibru corespunzătoare lui nu suprimă posibilitatea existenței, pentru un același joc, a punctelor de echilibru în strategii pure.

Obișnuim să numim strategie mixtă pe mulțimea A = A1, …, Am a strategiilor (pure) ale jucătorului P1 o repartiție de probabilități:

m

x = (x1, …, xm), unde xi ≥ 0, i = 1, m și ∑xi = 1.

i=1

Mulțimea tuturor acestor strategii o notăm prin X. Analog vom considera:

n

Y = y = (y1,…, yn) yj ≥ 0, ∑yj = 1 ca fiind ansamblul

j=1

strategiilor mixte pe mulțimea B, a strategiilor jucătorului P2.

Ideea de strategie mixtă se leagă, în mod natural, de alternarea strategiilor de către un jucător, în decursul mai multor partide. Cum probabilitățile pot fi interpretate ca limite ale unor frecvențe relative, se pune întrebarea dacă în situații reale putem considera ca acceptabilă repetarea (independentă) a jocului de un număr de ori suficient de mare.

Se poate încerca evitarea acestei dificultăți prin interpretarea unei strategii mixte a lui P2, y = (y1, …, yn) ca reprezentând probabilitățile (subiective) pe care le atribuie P1 utilizării uneia dintre strategiile pure B1, …, Bn de către P2 și, asemănător, a unei strategii mixte a lui P1 (x1, …, xm), schimbând rolurile între jucători. Impasul ce se profilează aici ține de tratarea jocurilor cu mai mult de doi jucători, caz în care doi jucători pot avea percepții diferite relative la comportarea unui terț.

Oricare ar fi interpretarea dată strategiilor mixte, ele ne ajută să punem în termeni corecți problema maximizării unui câștig incert, prin apelul la conceptul fundamental de medie a unei variabile aleatoare.

În condițiile alegerii independente și simultane a strategiilor de către fiecare jucător în parte, folosindu-ne de notațiile de mai înainte, vom defini câștigurile celor doi, în ipoteza folosirii strategiilor mixte x și y, respectiv,

m n

prin: ϕ1(x, y) = ∑∑aijxi yj ;

i=1 j=1

m n

ϕ2(x, y) = ∑∑bij xi y j ; ϕi: X × Y → ℝ, i = 1,2 ,

i=1 j=1

unde xi ⋅ yj reprezintă probabilitatea utilizării perechii de strategii (Ai, Bj), iar aij și bij sunt câștigurile asociate ei ale jucătorilor P1 și P2, respectiv.

Să observăm că de exemplu, câștigul mediu ϕ1(x, y) este o medie a unor câștiguri medii, considerând, pe rând, strategiile din A fixate față de cele din B, după cum o arată relația:

Cu aceste precizări, putem să dăm definiția extinsă a punctelor de echilibru ale unui joc bimatriceal în formă normală:

Definiție: Într-un joc bimatriceal G = A, B; f1, f2 , o pereche de strategii mixte (x*, y*) este un punct de echilibru Nash dacă au loc următoarele inegalități:

ϕ1(x*,y*) ≥ ϕ1(x, y*)

ϕ2(x*,y*) ≥ ϕ2(x*, y)

pentru orice strategii mixte x ∈ X și y ∈ Y.

Cu alte cuvinte, x* este cea mai bună strategie (mixtă) de răspuns a lui P1 la strategia y* a lui P2 și viceversa.

Se deduce din cele de mai sus că putem porni la determinarea strategiilor mixte de echilibru ale unui joc (a căror existență o vom afirma ceva mai târziu) prin găsirea celui mai bun răspuns (în strategii mixte sau pure) al unui jucător la o strategie mixtă a celuilalt.

În demersul nostru ne servim de următorul rezultat:

Propoziția 4.4

Pentru ca o strategie mixtă a lui P1 să fie un cel mai bun răspuns al acestuia la o strategie mixtă dată y a lui P2, este necesar și suficient ca ea să asigneze probabilități strict pozitive numai acelor strategii pure care sunt ele

însele un cel mai bun răspuns la strategia y (sau numai unei părți a acestora, restul primind probabilități nule).

Demonstrație:

Să notăm, pentru o strategie y dată, cu Imax mulțimea indicilor acelor strategii pure ale lui P1 care sunt un cel mai bun răspuns la y:

Să alegem un K0 ∈ Imax. Fie x = (x1, …, xm) o strategie mixtă a lui P1 și să presupunem că există l ∈ 1, n \ Imax astfel încât xl > 0. Notăm cu x’ strategia mixtă obținută din x prin asocierea probabilității x K0 + xl la strategia A K 0 și a unei probabilități nule la Al. Atunci vom avea:

unde deducem că x nu este cea mai bună strategie de răspuns la y.

Pentru probarea suficienței, se consideră I0 ⊆ Imax și o strategie mixtă x0 = (x i0 )im=1 care asignează probabilități nenule numai acelor strategii Ah, cu h ∈ I0. De aici rezultă:

fi strategia mixtă x ∈X. Deci x0 este răspuns optim al lui P1 la strategia y.

Un enunț similar celui din propoziția 4.4 caracterizează strategiile mixte ale lui P2 care sunt răspunsuri optime la o strategie mixtă x a lui P1, fixată.

Reamintim că orice strategie pură a unui jucător poate fi interpretată ca o strategie mixtă, exprimabilă printr-un vector binar cu 1 pe poziția corespunzătoare strategiei și având restul componentelor egale cu 0.

Revenind la exemplul de mai înainte al jocului bimatriceal 2 × 2, să încercăm determinarea unui punct de echilibru în strategii mixte. Pentru simplitate, vom nota strategiile mixte ale lui P1 prin x = (p, 1 – p) și strategiile mixte ale lui P2 cu y = (q, 1 – q), p, q ∈ [0, 1].

Într-o primă etapă, vom găsi strategiile pure optime de răspuns ale fiecărui jucător, la o strategie mixtă a adversarului.

Pentru o strategie mixtă dată (q, 1 – q) pe B = B1, B2 , câștigul mediu al lui P1 va fi 2q + 0(1 – q) = 2q, dacă folosește strategia A1 sau 1 ⋅ q + 3(1 – q) = 3 – 2q, dacă folosește strategia A2.

Rezolvând inecuația 2q > 3 – 2q pe intervalul [0, 1], deducem:

dacă q ∈ [0, 34 ), cel mai bun răspuns al lui P1 este A2;

dacă q = 34 , atunci A1 și A2 sunt răspunsuri la fel de bune;

dacă q ∈ ( 34 , 1], cel mai bun răspuns al lui P1 este A1.

Inversând rolurile, fie (p, 1 – p) o strategie mixtă pe A = A1, A2 . Câștigul mediu al lui P2 va fi 1 ⋅ p + 2(1 – p) = 2 – p, dacă folosește strategia B1 sau 2p, dacă utilizează strategia B2. Folosindu-ne de soluția inecuației 2 – p > 2p pe [0, 1], constatăm următoarele:

– pentru p ∈ [0, 23 ), răspunsul optim al lui P2 este B1;

pentru p = 23 , P2 poate răspunde atât cu B1, cât și cu B2;

pentru p ∈ ( 23 , 1], răspunsul optim al lui P2 este B2.

Căutăm acum o pereche de strategii mixte (x*, y*), x* = (p*, 1-p*), y* = (q*, 1 – q*) cu proprietățile din definiția extinsă a echilibrului Nash.

Vom analiza pe rând diversele situații posibile.

Dacă q* ar aparține intervalului [0, 34 ), atunci răspunsul optim al lui P1 ar fi strategia pură A2, căreia îi corespunde p = 0 ca strategie mixtă. Însă răspunsul optim al jucătorului P2 la această strategie este B1, corespunzând lui q = 1. Cum 1 ∉ (0, 34 ], acest

caz nu e compatibil cu existența unui punct de echilibru.

Dacă q* ∈ ( 34 , 1], cel mai bun răspuns al lui P1 este A1, pe care

îl identificăm cu strategia mixtă (1, 0). Cel mai bun răspuns al lui P2 la această strategie este strategia pură B2, pentru care avem q = 0. Dar 0 ∉ ( 34 , 1] și concluzia e identică celei de la

punctul precedent.

În cazul q* = 34 , ca răspuns optim al jucătorului P1 putem lua orice strategie mixtă (r, 1 – r) pe A1, A2 , r ∈ [0, 1], conform cu propoziția 4.4. Dar situațiile r ∈ [0, 23 ) și r ∈ ( 23 , 1] conduc la valori ale răspunsurilor corespunzătoare lui q = 1 și q = 0, respectiv, ambele diferite de 34 . Pentru r = 23 , răspunsul optim

fiind orice strategie mixtă (q, 1 – q) pe B1, B2 , în particular ( 34 , 14 ), rezultă că putem alege p* = 23 . În concluzie, punctul de echilibru al jocului, în strategii mixte, este:

(x*,y*) = (( 23 , 13 ), ( 34 , 14 )).

Importanța considerării strategiilor mixte în identificarea soluțiilor posibile ale unui joc bimatriceal reiese din următorul rezultat (pe care îl dăm într-un caz particular):

Teorema lui Nash

Orice joc finit de două persoane în formă normală, G = A, B; f1, f2 posedă cel puțin un punct de echilibru, în strategii pure sau mixte.

Demonstrația teoremei, al cărei enunț în formă generală se referă la jocuri de n persoane, are la bază o teoremă de punct fix.

(În cazul de față, (x*,y*) cu proprietatea T(x*, y*) = (x*,y*) este punct fix al unei transformări T). Deși în demonstrație nu se construiește efectiv un punct de echilibru, concluzia sa este suficient de elocventă.

Vom prezenta în cele ce urmează o procedură de determinare a punctelor de echilibru ale unui joc bimatriceal în formă normală, atunci când jucătorii P1, P2 au la dispoziție m și n strategii pure, respectiv, cu ajutorul unui exemplu concret. Vom avea în vedere cazul când câștigurile jucătorilor sunt nenegative, dar aceasta, după cum se constată, nu reprezintă o restricție importantă.

Sunt necesare câteva precizări și notații. Astfel, vom nota cu C1 matricea câștigurilor jucătorului P1 definită prin:

C1 = (aij) i=1,m , aij = f1(Ai, Bj), Ai ∈A, Bj ∈ B.

j=1,n

Asemănător, C2 va desemna matricea câștigurilor jucătorului P2:

C2 = (bij) i=1,m , bij = f2(Ai, Bj), Ai ∈ A, Bj ∈ B.

j=1,n

Pentru două strategii mixte, x = (x1, …, xm) a lui P1 și y = (y1,…, yn) a lui P2, se pot transcrie câștigurile medii ale fiecărui jucător în parte, astfel:

ϕ1(x, y) = xC1yT, ϕ2(x, y) = yC T2 xT, unde indicii T înseamnă operația de transpunere.

Notând Jm și Jn vectorii-linie cu m, respectiv n componente, toate

Să presupunem acum că (x, y) reprezintă o pereche de strategii de echilibru și să notăm, pentru simplitate, cu ϕ1 și ϕ2 câștigurile aferente ei ale celor doi jucători.

Introducem vectorii Φ1 = (ϕ1, …, ϕ1) ∈ℝn și Φ2 = (ϕ2, …, ϕ2) ∈ℝn, care ne permit o scriere matriceală a proprietății de echilibru. Astfel,

în care inegalitățile trebuie interpretate ca funcționând între oricare două componente corespondente ale vectorilor – coloană. Ele exprimă faptul că răspunsurile printr-o strategie pură la strategiile y, respectiv x pot să ducă, în cel mai bun caz, la egalarea câștigurilor ϕ1, respectiv ϕ2. Acestea sunt atinse efectiv în (x, y), ceea ce reiese din relațiile:

în care am ținut seama de (1).

Rezultă din cele de mai înainte că un punct de echilibru Nash, (x, y), al unui joc bimatriceal trebuie să satisfacă cele șase relații date, la care se adaugă condițiile x ≥ 0 și y ≥ 0.

Concret, vom găsi soluțiile următorului joc bimatriceal, folosind instrumentarul prezentat pentru cazul general.

Cele două matrici de câștiguri ale jucătorilor sunt:

Suntem în cazul a m = 2 strategii pure ale jucătorului P1 și a n = 3 strategii pure ale jucătorului P2.

Vom separa relațiile de tip liniar de cele neliniare și apoi le vom

Pentru jocul analizat, atât ϕ1 cât și ϕ2 sunt nenegative și ca atare, vom nota x3 = ϕ2 și y4 = ϕ1. De asemenea, vom transforma, în sistemele scrise anterior, inegalitățile în egalități, prin introducerea unor variabile-ecart, notate θi, i = 1,2 , respectiv µj, j = 1,3 .

Relațiile (3) vor avea drept corespondent următoarele egalități:

x1θ1 + x2θ2 = 0

y1µ1 + y2µ2 + y3µ3 = 0

Căutarea soluțiilor jocului bimatriceal se structurează așadar în:

rezolvarea în domeniul numerelor nenegative a sistemului liniar (I), în necunoscutele x1, x2, x3, µ1, µ2, µ3;

rezolvarea în domeniul numerelor nenegative a sistemului liniar (II), în necunoscutele y1, y2, y3, y4, θ1, θ2;

„filtrarea” soluțiilor, prin verificarea, de tip încrucișat, a îndeplinirii condițiilor (III).

În fapt, obiectivul nostru principal este să deducem soluțiile posibile de bază pentru fiecare din sistemele (I) sau (II), deoarece soluția generală se poate obține ca o combinație liniară convexă a soluțiilor de bază. Probarea condițiilor (III) o vom face așadar pentru diferite perechi de soluții de bază.

Să considerăm matricea sistemului liniar (I), în care fiecare coloană

este notată cu ak, k = 1,6 :

a6

0

0

0

1

Procedura este cea cunoscută de la programarea liniară: se aleg patru

coloane din cele 6 astfel încât ele să formeze o bază în ℝ4,

B = a k1 , a k 2 , a k3 , a k 4 .

Atunci soluția de bază va fi dată de (x, µ) = (B-1b, 0), unde b = (1, 0,0,0)T este coloana termenilor liberi și toate variabilele ale căror coloane asociate nu au intrat în bază iau valoarea 0.

Fie de exemplu mulțimea a1, a2, a3, a5 . Deoarece:

B = a1, a2, a3, a5 este o bază. Alegem µ1 = µ3 = 0. Avem de rezolvat sistemul:

x1 + x2 = 1 12×2 – x3 = 0

x1 + 10×2 – x3 + µ2 = 0 6×1 + 9×2 – x3 = 0

Se deduce ușor că x3 = 12×2, x2 = 2×1. Cum x1 + x2 = 1, rezultă x1 = 13 , x2 = 23 , x3 = 8 și µ2 = 1.

Soluția de bază va fi deci (x, µ)1 = ( 13 , 23 ,8,0,1,0), având toate

componentele pozitive sau nule.

Repetând procedeul pentru alte baze și testând nenegativitatea componentelor soluțiilor, vom găsi încă două soluții posibile de bază.

(x, µ)2 = (1,0,6,6,5,0), corespunzând bazei a1, a3, a4, a5 și (x, µ)3 = (0,1,12, 0,2,3), corespunzând bazei a2, a3, a5, a6 . Matricea sistemului (II) este:

b1 b2 b3 b4 b5 b6

Putem alege o bază formată din coloanele b1, b2 și b4, deoarece determinantul corespunzător lor are valoarea -2. Alegem y3 = θ1 = θ2 = 0. Din sistemul:

y1 + y2 = 1

4y1 + 2y2 – y4 = 0 6y1 + 2y2 – y4 = 0

deducem y1 = 0, y2 = 1 și y4 = 2, care ne dau soluția posibilă de bază: (y, θ)1 = (0,1,0,2,0,0).

Pentru bazele b1, b3, b4 , b3, b4, b6 și b1, b4, b5 , vom obține alte soluții posibile de bază ale sistemului:

(y, θ)2 = ( 23 , 0, 13 , 163 , 0, 0), (y, θ)3 = (0,0,1,8,0,4),

(y, θ)4 = (1, 0,0,6,2,0).

Înainte de a trece la verificarea condițiilor (III), observăm că, în ipotezele de nenegativitate a componentelor, x1θ1 + x2θ2 = 0 este echivalentă cu x1θ1 = 0 și x2θ2 = 0 și similar y1µ1 + y2µ2 + y3µ3 = 0 e îndeplinită dacă și numai dacă y1µ1 = 0, y2µ2 = 0 și y3µ3 = 0.

În consecință, dacă un θ (µ) este nenul, atunci componenta x

(y) cu același indice trebuie să fie egală cu zero.

Pentru facilitarea examinărilor necesare, vom construi două tabele în care marcăm în prima coloană cuplul de strategii (x, y) examinat, prin indicii corespunzători ordinilor date, iar în ultima coloană, prin *, dacă perechea (x, y) respectă condiția impusă. Primul tabel este:

Referitor la modul de completare a tabelului, am marcat cu * perechea (2,3), deoarece θ1×1 = 0 ⋅ 1 = 0 și θ2×2 = 4 ⋅ 0 = 0, în timp ce pentru

cuplul (3, 2) va fi marcat cu – (respins), deoarece µ1y1 = µ2y2 = 0, însă µ3y3 = 3 ⋅ 13 = 1 ≠ 0.

Vom extrage din fiecare tabel perechile de strategii marcate cu asterisc și apoi vom intersecta cele două mulțimi. Astfel obținem:

(1,1), (2,1), (3,1), (1,2), (2,2), (3,2), (2,3), (3, 4) ∩ ∩ (1,2), (1,3), (1,4), (2,3), (3, 4) = (1,2), (2,3), (3, 4) .

Intersecția găsită conține strategiile de echilibru Nash (pure sau mixte) ale jocului considerat. Acestea sunt (respectând ordinea):

Se observă că avem o pereche de strategii mixte (prima) și două perechi de strategii pure, mai exact (A1, B3) și (A2, B1).

În încheierea discuției despre punctele de echilibru ale unui joc bimatriceal, facem următoarele observații:

În situația în care elementele matricelor de câștiguri nu sunt toate pozitive sau nule, trebuie să considerăm că ϕ1 și ϕ2 sunt numere reale. Pentru a putea să ne folosim în continuare de procedeul descris mai înainte, putem proceda în două moduri:

să exprimăm fiecare variabilă ϕi, i = 1,2 ca diferența a două

variabile cărora li se impune să ia valori nenegative: ϕi = ϕ’i – ϕ”i, ϕ’i ≥ 0, ϕ”i ≥ 0, i = 1,2 ;

să adunăm la matricile C1 sau C2 o matrice (m × n) formată din constante identice între ele, suficient de mari, transformarea neafectând decât valorile câștigurilor medii, nu și determinarea strategiilor de echilibru;

În exemplul rezolvat mai înainte, trebuiau considerate cel mult

C 64 = 15 situații care conduc la o bază pentru matricea sistemului

(I) și cel mult C 36 = 20 situații de același tip în cazul sistemului (II). Pentru un număr mai mare de strategii ale fiecărui jucător, pentru a fi aplicabilă, metoda face apel la un program care generează soluții posibile de bază și le testează în mod automat;

Asupra elementelor matricilor de câștiguri pot fi operate și alte tipuri de transformări, ca de pildă scalarea (înmulțirea cu un factor pozitiv). De asemenea se poate discuta despre o strategie pură

dominată de o strategie mixtă, care ar putea să o disloce, fără a afecta esențial găsirea punctelor de echilibru, (Cititorul este îndemnat să compare ultimul joc analizat cu unul prezentat anterior și să tragă concluziile de rigoare).

4.2 Jocuri bimatriceale cooperative

Așa cum arătam la începutul discuției privind jocurile cu sumă arbitrară, un joc cooperativ este acela în care regulile sale permit alegerea în comun a strategiilor și transferul de câștiguri între jucători, în scopul cointeresării lor într-o anumită acțiune comună.

Ne vom servi de exemplul câtorva jocuri, pentru a ilustra situații în care jucătorii au interesul să coopereze între ei. Punctul de plecare îl va constitui, în ideea continuității, noțiunea de cuplu de strategii de echilibru Nash.

Să considerăm jocul bimatriceal următor: B1 B2 B3

Se observă cu ușurință că perechea de strategii (A2, B3) reprezintă un punct de echilibru al jocului (în strategii pure). În particular, câștigurile corespunzătoare ale jucătorilor (6, respectiv 3) sunt valorile maxime ale funcțiilor de câștig ale fiecăruia, deci și suma câștigurilor (care nu mai poate fi îmbunătățită prin considerarea strategiilor mixte) este maximă, între toate combinațiile posibile de strategii. Într-un asemenea caz, ipoteza cooperării între cei doi jucători nu are nici un efect.

Dacă însă analizăm jocul:

vom constata că, deși (A1, B1) este punct de echilibru al jocului, câștigurile care le revin jucătorilor nu îi pot mulțumi. Chiar suma lor, 5, ia valoarea cea mai mică posibilă. Eliminând perechile (A2, B1) și (A1, B2), care favorizează un jucător și îl defavorizează pe celălalt, rămâne perechea (A2, B2), ale cărui câștiguri aduc un plus amândurora față de ce le oferă strategiile de echilibru. Ea este însă instabilă.

Ieșirea din această dilemă se face prin modificarea regulilor jocului, prin acceptarea cooperării. Odată acceptată, ea aduce cu sine însă o altă problemă, aceea a împărțirii între cei doi jucători a câștigului comun, egal cu 12. Teoretic, se poate impune interzicerea plăților laterale între jucători, situație în care distribuția câștigurilor poate să rămână cea de la început. Nu vom adopta o asemenea ipoteză în cele ce urmează.

Jocurile de tip cooperativ au o problematică specifică și rezolvarea lor presupune atât introducerea unor noțiuni noi cât și revalorizarea altora mai vechi.

Se pune astfel o primă întrebare: sub ce limită a câștigului nu poate să accepte să coboare fiecare jucător?

Răspunsul îl furnizează acel câștig pe care îl poate obține un jucător, acționând în mod independent, indiferent de strategia (pură sau mixtă) aleasă de celălalt jucător. Referindu-ne la primul jucător, obținem valoarea maximin a jocului corespunzătoare lui, dată de expresia:

u* = max min ϕ1(x,y),

x∈X y∈Y

unde x și y sunt strategii mixte pe mulțimea strategiilor lui P1, respectiv ale lui P2. Analog, pentru P2 valoarea maximin va fi:

v* = max min ϕ2(x,y).

y∈Y x∈X

Deci, notând cu (u, v) o pereche de câștiguri ale celor doi jucători, ea ar putea constitui o soluție a jocului cooperativ numai dacă avem

(u, v) ≥ (u*, v*).

La întrebarea unde trebuie căutată soluția jocului, răspunsul îl dă noțiunea fundamentală de mulțime admisibilă. Aceasta, notată cu S, este mulțimea tuturor perechilor de câștiguri (u, v) pe care le pot obține, prin cooperare în alegerea strategiilor, cei doi jucători. Datorită faptului că sunt acceptate strategiile mixte și, mai mult, ele pot fi corelate, această

submulțime a lui ℝ2 are proprietatea de convexitate. Este de presupus că forma lui S va avea o influență asupra găsirii soluției jocului.

O altă noțiune importantă este aceea de frontieră Pareto-optimală a mulțimii admisibile S. Astfel, un punct (u, v) ∈ S aparține acesteia dacă oricare ar fi ε > 0, δ > 0 rezultă (u + ε, v) ∉ S și (u, v + δ) ∉ S.

Vom ilustra noțiunile introduse mai înainte și vom schița metoda de găsire a soluției, folosindu-ne de exemplul următorului joc bimatriceal.

Presupunem că regulile jocului permit cooperarea între jucători (dar nu ca o consecință a faptului că jocul nu admite puncte de echilibru în strategii pure).

Inversând ordinea de mai înainte, vom determina mai întâi mulțimea admisibilă S, precizând frontiera sa Pareto-optimală, folosindu-ne de o reprezentare grafică. Dacă notăm cu W11 punctul din plan de coordonate

(1, 2) și, mai departe, W12 = (3, 8), W21 = (2, 0), W22 = (4, 5), W31 = ( 32 , 6),

W32 = (5, 3), unde legătura dintre perechile de indici și perechile de câștiguri este evidentă, atunci S va fi reprezentată prin așa-numita „acoperire convexă” a punctelor W11, …, W32 (adică cea mai mică mulțime convexă plană care le conține), dată în figura următoare prin mulțimea hașurată:

W31

W22

S

W32

W11

0 W21 u

Să precizăm că există cazuri în care unele puncte – câștiguri W pot să fie situate în interiorul poligonului convex determinat de restul punctelor, caz în care mulțimea S va fi generată folosind numai aceste din urmă puncte.

Frontiera Pareto-optimală a lui S va fi formată, în mod firesc, din laturi ale poligonului W11W21 … W31. Singurele care satisfac condiția dată sunt W12W22 și W22W32. (Pentru puncte (u, v) aparținând altor segmente,

cum ar fi W21W32 sau W31W12 este suficient să luăm (u, v + δ) sau (u + ε, v), cu ε, δ > 0 alese corespunzător, pentru a constata că punctele obținute fac parte din S). Această frontieră Pareto [W12, W22, W32] va constitui, de fapt, zona de interes în identificarea soluției jocului, deoarece ea corespunde cursului de creștere, atât în u cât și în v, a punctelor (u, v) din S, favorabil ambilor jucători.

În continuare vom găsi valorile maximin ale jocului (în strategii mixte). Pentru a ușura calculele, să facem observația că atunci când dorim să minimizăm ϕ1(x, y) în raport cu y ∈ Y, pentru un x ∈ X fixat, este suficient să considerăm strategiile pure y = (1, 0) și y = (0, 1) deoarece putem scrie:

ϕ1(x, y) = xC1yT = (x1, x2, x3)C11 y1 + (x1, x2, x3) C12 y2

unde y = (y1, y2), y1, y2 ≥ 0, y1 + y2 = 1, iar C11 și C12 sunt respectiv prima și a doua coloană a matricei de câștiguri a jucătorului P1, notată C1. Concret, vom avea:

vârful (0,1,0) al lui X.

Cu un argument asemănător, folosind egalitatea ϕ2(x, y) = yC T2 xT, unde C2 este matricea câștigurilor lui P2, vom obține:

min ϕ2(x, y) = min 2y1 + 8y2, 5y2, 6y1 + 3y2 .

x∈X

Dar y2 = 1 – y1, deci vom calcula:

min -6y1 + 8, -5y1 + 5, 3y1 + 3 pentru y1 ∈ [0, 1].

Expresia acestuia este egală cu 3y1 + 3, dacă y1 ∈ [0, 14 ] și egală cu

-5y1 + 5, dacă y1 ∈ [ 14 , 1]. În final, avem:

(u – u*)(v – v*) pentru acele perechi (u, v) cu u ≥ 2 (în cazul în care există (u, v) ∈ S cu u > u* și v > v*). Ea va aparține frontierei Pareto-optimale a lui S.

Se demonstrează că punctul căutat (unic prin construcție) are proprietatea că dreapta tangentă la frontiera lui S, dusă prin el, are panta (coeficientul unghiular) egală cu opusul pantei dreptei care unește (u*,v*) cu ( u , v ). Evident, această tangentă trebuie să existe, drept pentru care punctele W12, W22 și W32 sunt tratate (eventual) separat.

Cum coeficientul unghiular al dreptei care unește (2, 154 ) cu un

(u, v) de pe frontieră este o mărime care variază continuu, analiza decurge după cum urmează.

Panta dreptei care conține segmentul [W32W22] (și care joacă rolul tangentei la frontiera lui S pentru punctele din interiorul său) este:

α1 = 54 −−35 = -2.

constatăm că panta dreptei – suport a acestuia este α2 =

Unind punctul (2, 154 ) cu (5, 3) se obține o dreaptă cu panta egală

(4, 5) are panta egală cu 85 . Așadar, făcându-l pe (u, v) să varieze în interiorul lui [W32W22] obținem o dreaptă cu panta β care parcurge intervalul (- 14 , 85 ). Cum opusul lui α1 nu se găsește în această plajă de

valori (2 ∉ (- 14 , 85 )), rezultă că ( u , v ) nu aparține interiorului segmentului

menționat.

Continuând analiza cu punctele din interiorul segmentului [W22W12],

8 −5 = -3. Dacă

3 − 4

unim pe (2, 154 ) cu (3, 8) obținem o dreaptă având panta egală cu 174 . Deci, atunci când (u, v) variază între capetele W22 și W12, dreapta care îl unește cu (u*,v*) are panta β ∈ ( 85 , 174 ).

În acest caz, – α2 = 3 ∈ ( 85 , 174 ) și rămâne să îl determinăm pe

( u , v ) ca un punct situat între W22 și W12.

Dreapta care trece prin punctele (4, 5) și (3, 8) are ecuația:

v 3−5 = u−−14 ⇔ v = -3u + 17. Ea se va intersecta cu o dreaptă care trece prin (2, 154 ), de pantă egală cu β2 = 3, în ( u , v ).

La acest moment se cuvine a fi făcută o observație referitoare la transferul câștigurilor. Astfel, din ecuația:

v = -3u + 17, rezultă că o unitate valorică cedată de P1 se transferă în 3 unități valorice ale lui P2, deoarece avem:

-3(u – 1) + 17 = -3u + 17 + 3 = v + 3.

Putem vorbi deci de o rată de transfer a câștigurilor de la P1 către P2, egală cu 3(3 la 1).

Să facem diferențele între câștigul dat de soluția Nash și valoarea maximin pentru fiecare jucător în parte:

7724 – 2 = 2924 ; 598 −154 = 298

Raportul lor (în ordinea P2 / P1) este 298 ÷ 2924 = 3, deci coincide cu

rata de transfer. Aceasta ne arată că părțile de câștig obținute prin cooperare, în plus față de câștigul maximin, de către fiecare jucător, se situează într-o

proporție egală cu rata de transfer în punctul ( u , v ).

Să nu pierdem din vedere faptul că scopul fiecărui jucător este ca să-și îmbunătățească câștigul, inclusiv prin cooperare, dar neexcluzând influențele subiective. În acest context, putem observa că suma câștigurilor Nash:

u + v ≈ 3.208 + 7.375 = 10.583,

este strict inferioară sumei 3 + 8 = 11 ce rezultă dacă cei doi jucători convin să aplice strategiile A1 și B2, respectiv. Diferența rezultată ar putea să fie obiectul unui transfer de câștig în scopul amintit. Trebuie să acceptăm din această cauză concluzia că soluția Nash nu e cea mai bună?

Să observăm că în calculele de mai sus nu am ținut seama de rata de transfer, egală cu 3 pentru toți (u, v) ∈ [W12, W22]. Acestea ar fi trebuit să arate astfel (în unități ale lui P2):

3 × 3 + 1 × 8 = 9 + 8 = 17 3 × 3.208 + 1 × 7.375 = 9.624 + 7.375 = 16.999 ≈ 17.

În încheiere să menționăm că există și un alt mod de producere a soluției jocului cooperativ, bazat pe așa-numitele strategii de amenințare. Pentru lămuriri, îndrumăm cititorul către referințele bibliografice date.

5. Jocuri de n persoane. Valoare Shapley

În cele ce urmează vom considera jocul de n persoane, în care notăm cu N = 1, 2, …, n mulțimea tuturor jucătorilor și presupunem permisă cooperarea între aceștia.

Definiția 1. Orice submulțime nevidă a lui N (inclusiv N și toate submulțimile formate dintr-un singur jucător) se numește coaliție.

Definiția 2: Se numește funcție caracteristică a unui joc de n jucători funcția v, definită pe mulțimea părților lui N, care asociază fiecărei coaliții S ⊂ N valoarea maximin (corespunzătoare lui S) a jocului de două persoane jucat între coalițiile S și N – S.

Deci notăm prin v(S) câștigul pe care jucătorii din S îl pot obține în joc (acționând în cooperare), indiferent de ceea ce fac restul jucătorilor.

Dacă S și T sunt coaliții disjuncte, unindu-și forțele, ele pot realiza un câștig cel puțin tot atât ca în cazul când acționează separat. Acest lucru se

și înseamnă că funcția caracteristică v are proprietatea de superaditivitate. Dacă în jocul de două persoane elementul esențial era studiul

strategiilor mixte, în jocul de n persoane acest element esențial este formarea de coaliții. Funcția caracteristică dă posibilitățile diferitelor coaliții și este cea mai potrivită pentru studiul acestora.

Definiția 3: Prin joc de n persoane în formă caracteristică se înțelege o funcție v cu valori reale definită pe submulțimile lui N și care satisface condițiile (1) și (2).

Prin definiție, v(S) este valoarea maximin a jocului între S și N – S. Dacă presupunem că jocul este cu sumă constantă, adică suma câștigurilor tuturor jucătorilor este constantă, indiferent de desfășurarea jocului, atunci:

v(S) + v(N-S) = v(N).

v(N) este valoarea ce se poate obține prin cooperare generală și se mai numește valoare totală.

se numește imputație.

Notăm cu v( i ) valoarea pe care jucătorul i o poate obține acționând independent. Evident jucătorul i va intra în coaliția S dacă valoarea câștigului este cel puțin v( i ).

Definiția 4: Într-un joc v de n persoane vectorul x = (x1, …, xn), cu

condițiile:

a) ∑xi = v(N) și

i∈N

b) xi ≥ v( i ), (∀) i ∈ N,

Evident, din a) și b), rezultă că:

v(N) ≥ ∑v({}i) .

i∈N

Definiția 5: Un joc v se numește esențial, dacă

v(N) > ∑v({}i) și neesențial în caz contrar.

i∈N

Jocurile esențiale sunt acelea ce prezintă interes.

Deoarece jocurile în forma caracteristică (definiția 3) sunt funcții cu valori reale, are sens să vorbim despre suma a două sau mai multe jocuri.

Definiția 6: Se numește suport al unui joc v o coaliție T cu proprietatea:

v(S) = v(S ∩ T) pentru orice coaliție S.

Aceasta înseamnă că orice jucător care nu aparține unui suport al jocului este lipsit de importanță, adică nu aduce nimic unei coaliții.

Definiția 7: Fie v un joc de n persoane și π o permutare arbitrară a mulțimii N. Prin πv înțelegem jocul obținut din v în care s-au interschimbat rolurile jucătorilor prin permutarea π.

Axiomele Shapley

Numim valoare a unui joc v de n persoane, vectorul

ϕ[v] = (ϕ1[v],…, ϕn[v]), unde ϕi[v] reprezintă partea care trebuie atribuită jucătorului i, i = 1, n , din câștigul total v(N), cu proprietățile:

a1) pentru orice suport S al lui v avem: ∑ϕi [v] = v(S) ;

i∈S

a2) pentru orice permutare π și orice jucător i ∈ N, ϕπ(i)[πv] = ϕi[v]; a3) pentru oricare două jocuri u și v avem: ϕ[u + v] = ϕ[u] + ϕ[v]. Aceste trei proprietăți sunt axiomele lui Shapley și ele sunt suficiente

pentru a determina o funcție valoare ϕ, definită pentru toate jocurile. Dăm fără demonstrație următoarea:

Teoremă [16]

Există o funcție unică ϕ, definită pentru toate jocurile, care satisface axiomele a1, a2, a3 și anume:

unde t este numărul jucătorilor din coaliția T.

Semnificația termenului v(T) – v(T – i ) este câștigul primit de jucătorul i, sau valoarea cu care acest jucător contribuie la câștigul total al coaliției T din care face parte.

Dacă vom presupune că termenul v(T) – v(T – i ) poate lua numai valorile 0 sau 1, și anume ia valoarea 1 dacă și numai dacă T este o coaliție câștigătoare, dar T – i nu este câștigătoare, atunci jocul v este un joc

unde sumarea se face pentru toate coalițiile câștigătoare T pentru care T – i nu este câștigătoare.

Aplicație [16]

O societate pe acțiuni are 4 acționari ce posedă respectiv 10, 20, 30 și 40% din acțiuni. Toate deciziile privind activitatea societății se iau cu majoritatea simplă (cel puțin 51% voturi, care sunt proporționale cu numărul de acțiuni posedate). Considerând această situație ca un joc simplu de 4 persoane se cere:

să se găsească toate coalițiile câștigătoare;

să se scrie coalițiile câștigătoare T pentru care T – 1 nu este câștigătoare;

să se determine valoarea Shapley ϕ = (ϕ1, ϕ2, ϕ3, ϕ4), unde ϕi este partea ce se atribuie jucătorului i, i = 1,4 , din câștigul total;

să se facă observații asupra rezultatului obținut la punctul c).

Rezolvare

a) Coalițiile câștigătoare sunt:

2, 4 , 3, 4 , 1, 2, 3 , 1, 2, 4 , 1, 3, 4 , 2, 3, 4 , 1, 2, 3, 4 .

Dintre coalițiile câștigătoare ce îl conțin pe primul acționar singura care devine necâștigătoare când este scos din coaliție acesta este coaliția: 1, 2, 3 , în care t (numărul acționarilor) este egal cu 3.

Aplicând formula (4), unde t = 3, n = 4, i = 1, avem:

ϕ1 = 24!!1! = 121 .

Analog, coalițiile câștigătoare, care își pierd această proprietate dacă acționarul 2 este înlăturat sunt:

2, 4 , 1, 2, 3 , 1, 2, 4 .

Formula (4) va da pentru ϕ2 suma a trei termeni, fiecare corespunzând uneia din coalițiile de mai sus.

Astfel pentru coaliția 2, 4 , t = 2, n = 4, i = 2, primul termen din (4)

acționarul 2. Acționarul 3 nu are posibilități mai mari decât acționarul 2 de a

participa la o coaliție câștigătoare. Importanța acționarului 4 este mai mare decât cea corespunzătoare procentului acțiunilor sale, iar a jucătorului 1 este mai mică decât cea corespunzătoare acțiunilor sale.

Dacă acționarii ar deține respectiv 10, 30, 30, 30% din acțiuni, oricare doi dintre acționarii 2, 3, 4 pot forma coaliții câștigătoare în timp ce acționarul 1 este lipsit de orice importanță neputând aduce nimic nici unei coaliții. Atunci valoarea jocului este vectorul:

ϕ = (0, 13 , 13 , 13 ).

6. Probleme

1. Să se stabilească valoarea jocului și strategiile pure optime pentru

jocul:

Rezolvare

coloanele αi, respectiv βj. Și deoarece α = max αi = 5 = α2, iar β = min βj =

1≤i≤3 1≤j≤4

= 5 = β3 rezultă că jocul are punct șa, iar strategiile pure optime ale celor doi jucători sunt respectiv A2 și B3, iar valoarea jocului v = a23 = 5.

2. Să se rezolve jocul de ordinul 2 × 2 cu matricea:

Rezolvare

Jocul nu are punct șa deoarece 6 și 1 nu sunt minime pe liniile lor. Vom folosi relațiile (9) de la 2.3.a. Cum A = -6 ≠ 0 și:

3. Să se rezolve pe cale grafică jocul a cărui matrice este:

Rezolvare

Observăm că linia a cincea este dominată de linia a treia, deci vom renunța la linia a cincea și jocul va fi de forma 4 × 2,

Strategiile jucătorului P2 verifică relațiile: 6y1 – 2y2 ≤ v

5y1 + y2 ≤ v

3y1 + 4y2 ≤ v -y1 + 5y2 ≤ v y1 + y2 = 1

Punând y1 = 1 – y2 în primele 4 inegalități, acestea devin: 6 – 8y2 ≤ v

5 – 4y2 ≤ v y2 + 3 ≤ v 6y2 – 1 ≤ v

și sunt reprezentate grafic mai jos:

unde am asociat fiecărei inegalități (i), dreapta di, i = 1,4 , ce împarte semiplanele determinate de inegalitatea (i). Porțiunea din plan cuprinsă între y2 = 0 și y2 = 1 (y2 este o probabilitate), și dedesubtul liniei frânte îngroșate conține mulțimea punctelor (y2, v) ce verifică cele 4 inegalități. Linia îngroșată conține punctele cu cea mai mare valoare a lui v, iar dintre acestea punctul cu cea mai mică valoare dintre cele de pe linia frântă este M = d2 ∩ d3 și deci va avea coordonatele date de soluția sistemului:

5 – 4y2 = v y2 + 3 = v

de unde y2 = 52 , y1 = 53 iar v = 3, 4, deci y2 și v satisfac restricțiile 2 și 3 cu

egalități. Teorema ecarturilor ne spune că atunci componentele x2 și x3 din problema duală vor fi pozitive.

Deci strategia lui P2 este y = ( 53 , 52 ).

Soluția optimă a jucătorului P1 verifică relațiile: 6×1 + 5×2 + 3×3 – x4 ≥ v

-2×1 + x2 + 4×3 + 5×4 ≥ v x1 + x2 + x3 + x4 = 1

în care x2, x3 > 0 iar x1 = x4 = 0. Atunci eliminând prima și a patra linie din A va rezulta un joc redus cu matricea:

Determinarea strategiei lui P1 o vom face cu ajutorul formulelor (9) din 2.3.a, unde:

54 și strategia lui

4. Să se determine prin metodele cunoscute valoarea jocului și strategiile jucătorilor pentru cazul în care matricea plăților este:

Rezolvare

Aplicând principiul strategiilor dominate observăm că linia a doua are elementele respectiv mai mari ca linia a patra, deci o vom șterge pe aceasta din urmă. Coloana a treia domină coloana a patra, care va fi ștearsă și matricea jocului se va restrânge la:

Cercetăm dacă jocul este cu punct șa, adăugând matricei A coloana

αi (a celor mai mici elemente pe linie) și linia βj (a celor mai mari elemente pe coloană).

Obținem:

de unde α = maxαi = 1, β = minβj = 3, deci α ≠ β, jocul nu are punct șa, iar valoarea jocului v ∈ (1, 3).

a) Rezolvăm întâi problema pe cale matriceală, folosind formulele (9’) din observația dată în paragraful 2.3.a.

A = -30;

Deci x și y sunt o soluție a jocului cu v = 2 .

b) Rezolvăm problema prin programare liniară. Modelul matematic al jocului scris din punctul de vedere al celui de al doilea jucător cu strategia y = ( y 1 , y2 , y3 ), va fi:

y1 + y2 + y3 =1; y j ∈[0,1], j =1,3 .

Cum v ∈(1,3 ) deci este pozitiv, împărțim relațiile de mai sus prin v

și notăm:

Aducem problema la forma standard și aplicăm algoritmul simplex

Am ajuns la soluția optimă care va fi: max g = 1v = 12 , de unde v = 2 .

Y1 =1/ 3, Y3 =1/ 6 de unde y1 = v Y1 = 2 ⋅1/ 3 = 23 ;

X1 = 16 , X2 = 13 , X3 = 0 de unde :

Observaț ie: Prin metoda b) strategia lui P1 este aceeași cu cea din a), dar strategia lui P2 diferă. Acest lucru a apărut deoarece în rezolvarea prin simplex a problemei, în etapa de optim ∆2 = 0 deși a2 ∉ B. În acest caz problema are o infinitate de soluții. Să mai găsim una continuând simplexul cu încă o iterație prin introducerea în bază a lui a2 și eliminarea lui a6.

metoda a).

Dar dacă o problemă de programare liniară are două soluții optime:

de combinația liniară convexă de y' și y''. Deci P2 are o infinitate de strategii date de:

Observație: Dacă la metoda matriceală de la punctul a) am fi aplicat procedeul dat în paragraful 2.3.a, am fi găsit și altă soluție pentru jocul considerat și orice combinație liniară convexă de soluțiile găsite ar fi fost tot o soluție a jocului, de unde infinitatea de soluții dată de algoritmul simplex.

5. Să se rezolve jocul G = (A, B, f) în care matricea plăților A este:

Rezolvare

Determinăm valoarea inferioară și valoarea superioară ale jocului:

α1 = min 3, -1, 0,7 = -1 α2 = min 6, 8, 3,5 = 3 α3 = min 2, 5, 1,3 = 1

de unde α = max -1, 3, 1 = 3 = vG .

β1 = max 3, 6, 2 = 6; β2 = max -1, 8, 5 = 8;

Cum vG = vG = 3, rezultă că jocul are punct șa și P1 va alege numai strategia A2 iar P2 numai B3, indiferent de numărul partidelor ce se joacă.

6. Să se rezolve jocul matriceal G = concurență a două firme, dacă s-a stabilit că

(A, B, f) asociat unei situații de matricea jocului este:

Rezolvare

Determinăm vG și vG pentru a vedea dacă jocul are punct șa. Avem:

v ∈ (-1, 1).

Căutăm strategiile mixte x = (x1, x2, x3) pentru P1 și y = (y1, y2, y3) pentru P2, prin intermediul programării liniare.

Mai întâi transformăm elementele matricei A, pentru a avea v > 0.

E suficient să adunăm 2 la elementele matricei inițiale și avem:

optime ca jocul inițial, doar valoarea jocului este v = v + 2, adică cu 2 mai mare decât valoarea jocului inițial.

Pentru P2 problema de programare liniară ce trebuie rezolvată va fi: 2y1 – 3y2 + 4y3 ≤ v

4y2 + y3 ≤ v

3y1 + y2 + 3y3 ≤ v y1 + y2 + y3 = 1 yj ≥ 0, j = 1,3

Cu v > 0, Yj = yvj și 1v = [max]g, avem:

[max]g = 1v = Y1 + Y2 + Y3

2Y1 – 3Y2 + 4Y3 + Y4 = 1 4Y2 + Y3 + Y5 = 1

3Y1 + Y2 + 3Y3 + Y6 = 1 Yj ≥ 0, j = 1,6 .

Rezolvăm problema aplicând algoritmul simplex.

Teoria jocurilor

Am ajuns la soluția optimă care este:

Echilibrul realizat se manifestă aici prin anularea câștigului fiecărui participant.

7. O familie se aprovizionează pentru iarnă cu cărbune de un anumit

tip. Cantitatea necesară și condițiile de aprovizionare sunt date în următorul tabel [10]:

Dacă aprovizionarea se face vara, prețul unitar este de 60 u.m./t. Se cere:

să se scrie matricea plăților știind că aprovizionarea se face în timpul verii;

să se decidă strategia prin criteriul maximin;

să se decidă strategia prin criteriul minimax;

să se decidă strategia prin criteriul Savage;

să se decidă strategia când stările iernii sunt egal probabile; alternativ, când probabilitățile sunt respectiv 0,2; 0,5 și 0,3;

pentru α = 0,75 să se determine strategia optimă prin criteriul Hurwicz.

Rezolvare

a) Matricea asociată jocului generat de problema dată va fi:

unde, de exemplu, elementul de pe linia lui A2 și coloana lui S3 s-a calculat astfel: s-au cumpărat 5t a câte 60 u.m. pentru care s-au plătit 300 u.m.; iarna

fiind grea, mai este nevoie de o tonă ce se cumpără iarna cu prețul de 80 u.m., deci în total cheltuielile vor fi de 380 sau în matricea câștigurilor lui P1 vom scrie -380.

b) În aplicarea criteriului maximin se alege minimul elementelor de pe fiecare linie și dintre acestea se determină maximul, astfel:

Cel mai mare este -360 și indică alegerea strategiei A3.

c) Criteriul minimax recomandă alegerea elementului maxim de pe fiecare linie și apoi determinarea celui mai mic dintre acestea.

Cel mai mic este -360 și corespunde strategiei A3.

d) Formăm matricea R a regretelor din A scăzând din cel mai mare element al unei coloane toate elementele coloanei respective. Obținem:

Determinăm apoi în R cel mai mare element pe fiecare linie și apoi cel mai mic dintre acestea. Obținem:

Cel mai mic este 60 și recomandă strategia A2.

e) În ipoteza că stările Si, i = 1,3 , sunt egal probabile, vom calcula

cheltuielile medii pentru fiecare strategie Ai, i = 1,3 . Astfel:

ϕ(1, y) = 13 (-240) + 13 (-315) + 13 (-400) = – 9553

ϕ(2, y) = – 9803 și ϕ(3, y) = – 10803 .

Cea mai mare dintre aceste sume este ϕ(1, y) și recomandă A1. Dacă stările nu sunt egal probabile ci au respectiv probabilitățile: 0,2; 0,5; 0,3,

și cea mai mică cheltuială este ϕ(2, y) și recomandă A2.

Pentru α = 0,75, corespunzător lui A1, obținem pe ultima coloană 160 ⋅ 0,75 – 400 = – 280; pentru A2, 80 ⋅ 0,75 – 380 = -320 și pentru A3, – 360. Cea mai mică cheltuială este pentru A1.

8. Să se elimine strategiile dominate și să se cerceteze existența punctelor de echilibru Nash (în strategii pure) pentru următorul joc bimatriceal.

Rezolvare

Se observă mai întâi că strategia A4 a jucătorului P1 domină strict strategia A2 (oricare ar fi strategia de răspuns Bj a lui P2, avem a4j > a2j). După eliminarea lui A2, care nu afectează punctele de echilibru, observăm că strategia B4 a lui P2 domină strict pe B3 (deoarece 2 > 0, 5 > 2 și 6 > 4). După ce B3 este suprimată și ea, obținem un tabel restrâns.

În această fază nu vom mai găsi strategii dominate. Urmând procedura de determinare a răspunsurilor optime, pe linii și pe coloane, vom obține marcările de mai jos:

Cum singurele perechi de câștiguri cu două sublinieri sunt (6,8) și (4,7), rezultă că (A3, B1) și (A4, B2) sunt puncte de echilibru ale jocului (în strategii pure). Observând câștigurile corespunzătoare, se poate spune că

(A3, B1) este preferabil lui (A4, B2) pentru ambii jucători și deci poate constitui soluția jocului.

9. Să se construiască un joc bimatriceal care să admită un punct de

echilibru format din strategii pure de tip maximin.

Rezolvare

Fie jocul cu sumă arbitrară dat prin matricea:

Se observă, fără dificultate, că (A1, B1) și (A2, B2) sunt puncte de echilibru Nash al jocului. În același timp, avem valorile maximin:

max min aij = max min 4,3 , min 2,5 = max 3,2 = 3

i=1,2 j=1,2

max min bij = max min 5,6 , min 4,7 = max 5,4 = 5

i=1,2 j=1,2

Deci A1 e strategia maximin a lui P1 și B1 e strategia maximin a lui P2. Se confirmă, pe de altă parte, faptul că orice punct de echilibru îi promite fiecărui jucător un câștig mai mare sau egal cu valoarea maximin corespunzătoare lui a jocului.

10. Să se arate că jocul în formă normală de mai jos nu admite puncte de echilibru Nash în strategii mixte:

Rezolvare

Fie (p, q, 1 – p – q) o strategie mixtă pe B = B1, B2, B3 .

Avem deci p, q ≥ 0 și p + q ≤ 1. Căutăm răspunsul optim al lui P1 la această strategie a lui P2. Dacă P1 folosește strategia A1 atunci îi revine un câștig mediu egal cu p + q, iar dacă folosește strategia A2, câștigul mediu este 2(1 – p – q). Comparându-le, se deduce imediat că dacă p + q ∈ [0, 2/3) cel mai bun răspuns este A2 în timp ce pentru p + q ∈ (2/3, 1], cel mai bun răspuns este A1.

Cazul p + q = 23 nu face deosebire între A1 și A2 ca replici optime

ale lui P1. Dacă vom considera o strategie mixtă (r, 1 – r) pe A = A1, A2 , 0 ≤ r ≤ 1, câștigurile medii ale lui P2 vor fi egale cu 3 – 3r, r + 1 sau r, după cum folosește strategiile pure B1, B2 sau B3, respectiv. Din inegalitățile

3 – 3r > r + 1 > r reiese că răspunsul optim al lui P2 este B1, pentru r < 12 și B2, pentru r > 12 . În cazul r = 12 , se rețin ca cel mai bun răspuns

oricare dintre strategiile B1 sau B2.

Să presupunem că punctele de echilibru ale jocului sunt de forma ((r*, 1 – r*), (p*, q*, 1 – p* – q*)). Vom analiza situațiile posibile pentru r*:

Dacă r* ∈ [0, 12 ), răspunsul optim al lui P2 este B1, căruia i-ar corespunde ca strategie mixtă valorile p* = 1, q* = 0, ceea ce

înseamnă că p* + q* = 1 > 23 și, în replică, am avea strategia optimă A1 a lui P1. Cum A1 poate fi identificată cu strategia mixtă (1, 0), rezultă r* = 1, contrazicând ipoteza inițială;

II. În cazul r* = 12 , orice strategie mixtă a lui P2 de forma (λ, 1-λ, 0), 0 ≤ λ ≤ 1 este un răspuns optim. Discuția continuă ca mai înainte și se ajunge la concluzia r* = 1 ≠ 12 ;

Dacă r* ∈ ( 12 , 1), replica cea mai bună a lui P2 este B2; ei îi corespund valorile p* = 0, q* = 1 și cum p* + q* > 23 , răspunsul

optim al lui P1 e din nou A1. Obținem, ca mai sus, r*= 1∉( 12 ,1);

IV. Ultima posibilitate, r* = 1 ne conduce la o strategie de răspuns cu p* = 0, q* = 1 și, de această dată, cu răspunsul în oglindă al lui P1, lanțul deducțiilor se închide. Am obținut astfel un punct de echilibru în strategii pure, ((1,0), (0,1,0)), fapt ce clarifică cerința problemei vis-à-vis de teorema lui Nash. Să mai observăm că, deoarece strategia B3 este strict dominată, componenta corespunzătoare ei într-o strategie optimă a lui P2 nu putea fi decât nulă.

11. ([12]) Două firme cu profile asemănătoare de activitate oferă fiecare câte un loc de muncă. Să presupunem că se plătesc salarii diferite: firma i plătește salariul si, unde (1/2) s1 < s2 < 2s1. Să presupunem că există doi lucrători ce doresc să se angajeze, dar fiecare nu poate opta decât pentru o singură firmă, acest lucru făcându-se simultan. Dacă numai câte un singur lucrător își oferă serviciile unei firme, el este angajat.

Dacă ambii lucrători optează pentru aceeași firmă, aceasta angajează pe unul dintre ei, la întâmplare, iar celălalt rămâne, pe mai departe, fără serviciu (și cu o plată presupusă nulă). Să se găsească soluția în strategii de echilibru Nash a acestui joc.

Rezolvare

Vom construi pentru început forma normală a jocului descris. Jucătorii sunt cei doi lucrători, strategiile lor constând din opțiunile pe care le fac pentru firma 1 sau firma 2 și pe care le notăm cu A1, A2, respectiv B1, B2. Vom nota, ca de obicei, cu f1(⋅,⋅) și f2(⋅,⋅) respectiv, funcțiile de câștig ale jucătorilor. Considerând utilitățile imediate ale celor doi lucrători, rezultate în urma alegerilor făcute, putem construi următoarea matrice de plăți (în ipoteza șanselor egale):

ceea ce arată că și (A2, B1) este un punct de echilibru Nash.

Faptul că fiecare lucrător este angajat dacă se optează pentru una sau cealaltă dintre perechile de strategii discutate vine în acord cu ideea de echilibru, chiar dacă unul dintre jucători poate să nu fie mulțumit pe deplin cu salariul pe care îl obține.

Dacă fiecare jucător ține la șansa sa de a fi angajat și de a primi un salariu mai bun, atunci are sens considerarea strategiilor mixte.

Fie (y, 1-y) o strategie mixtă a lui P2. Atunci câștigul mediu al lui P1 va fi dat de:

12 ys1 + (1 – y)s1 = s1 – 12 ys1, sau

ys2 + 12 (1 – y) s2 = 12 s2 + 12 ys2, după cum folosește strategia pură A1 sau A2.

echivalent cu 2s1 – s2 < s1 + s2).

O analiză similară se face pornind de la o strategie mixtă (x, 1 – x) pe A1, A2 . Urmând procedeul de rezolvare descris în soluția la problema 10, vom obține următorul punct de echilibru Nash în strategii mixte:

Desigur că în acest exemplu de joc nu se pune problema repetării sale de un număr de ori care să permită alternarea strategiilor.

Metoda de decizie pentru oricare jucător este să folosească un generator de numere aleatoare (de tipul funcției RND a unui calculator de

atunci el va alege strategia A1(B1), altfel va juca A2(B2).