Lucrarea de față își propune să prezinte aplicații ale teoremelor de dualitate din programarea [612256]

Cuvânt înainte

Lucrarea de față își propune să prezinte aplicații ale teoremelor de dualitate din programarea
liniară în jocurile de producție liniară.Pentru aceasta,lucrarea este structurată în trei capitole:
I. Introducere în teoria jocurilor
Se urmărește o scurt ă prezentare a c âtorva noțiuni de bază a teoriei jocuril or,ilustrate cu
exemple, structurată în următoarele subcapitole:
 Scurt istoric al teoriei jocurilor
Este vorba despre situații care au făcut să fie simțită nevoia modelării lor în cadrul unei teorii
ce poartă acum numele de teoria jocurilor (situații precum jocurile de noroc și comportamentul
economic);astfel de situații au fost studiate de numeroși intelectuali înainte de apariția teoriei
jocurilor pentru ca ulterior domeniul să fie fundamentat și dezvoltat.Sunt punctate câteva repere
istorice importante și descrise succint situații care au contribuit la apariția și dezvoltarea teoriei
jocurilor.

 Formalizarea teoriei jocurilor
Aici se stabilește cadrul matematic aferent teoriei jocurilor:ipotezele care sunt adoptate în
cadrul acestei teor ii,definiția jocului,câteva proprietăți,definițiile unor noțiuni fundamentale
precum strategia unui jucător,starea de informație a jocului,jocuri matriceale și
bimatriceale,strategie mixtă (toate noțiunile prezentate fiind adesea însoțite de pasaje care
descriu nevoia introducerii acestor noțiuni cât și de exemple ilustratoare),clasificare precum și
exemple de jocuri.
 Jocuri necooperative
Se prezintă pe scurt categoria de jocuri în care jucătorii nu cooperează între ei,anume jocurile
necooperative;se def inesc jocurile necooperative,se reprezintă printr -o matrice jocurile
necooperative sub formă normală cu sumă nulă respectiv arbitrară,se definește noțiunea de punct
șa (punct de echilibru) și se oferă o modalitate de calcul al acestuia (strategia
minimax /maximin);analog pentru jocurile bimatriceale,se definește noțiunea de echilibru Nash
(în strategii pure) și se oferă o modalitate de calcul pentru acesta.Toate noțiunile introduse sunt
ilustrate prin exemple;rolul acest subcapitolul este înțelegerea urmă torului subcapitol: Jocuri
cooperative.
 Jocuri cooperative

Aici problematica jocului este diferită de cea a jocurilor necooperative,aceasta fiind
reprezentată de împărțirea câștigului obținut prin cooperare de către un grup de jucători.Se
definește jocu l cooperative împreună cu alte noțiuni de bază precum:coaliție,alocare a bunurilor
(imputație),condițiile în care o imputație se poate considera soluție a jocului cooperativ:pentru
aceasta se consideră noțiunea de nucleu și de joc balansat care conduc la t eorema ce asigură
existența nucleului nevid.Toate noțiunile prezentate în cadrul acestui subcapitol sunt însoțite de
exemple și de observații teoretice.
II. Dualitate în programare liniară
Deoarece nu de puține ori problemele de teoria jocurilor își găsesc rezolvarea apelând la
noțiuni de programare liniară,suntem nevoiți să considerăm acest capitol.Aici sunt prezentate
câteva elemente de bază din dualitatea în programarea liniară:problema primală,problema
duală,teoremele de dualitate,algoritmul simplex dual ,toate noțiunile fiind însoțite de exemple.
III. Aplicații ale teoremelor de dualitate în teoria jocurilor de producție liniară
Ultimul capitol este dedicat aplicațiilor teoriei de până acum.Sunt demonstrate câteva rezultate
ce fac uz în special de teoria jo curilor cooperative și dualitatea în programarea liniară.

I. Introducere in teoria jocurilor

I.1 Scurt istoric al teoriei jocurilor

În viața de zi cu zi ne confruntăm deseori cu situații de tip
conflictual:interpersonale,profesionale,la scară economică etc.;astfel de conflicte pot căpăta
forme mai grave,ajungăndu -se la confruntări mari sau războaie.
Pentru a exemplifica astfel de situații,să considerăm jocurile de societate(precum table,jocul de
cărți,șah),jocurile sportive (fotbal,ten is,baschet) ,jocuri de divertisment etc.Să observăm câteva
elemente comune ale acestor jocuri:
i. Participa nții la joc (jucătorii);în funcție de fiecare situație în parte ,jucătorii pot f i
reprezentaț i de:persoane,firme,echipe,țări,computer etc.
ii. Regulile ;cu aju torul lor sunt stabilite posibilitățile de comun icare între jucători,condițiile
în care se joacă jocul,informația de care dispune fiecare jucător despre ceilalți jucători.

iii. Posibili tățile strategice de care dispune fiecare jucător :acțiuni,decizii respecti v strategii
aferente fiecărui jucător .
iv. Rezultatele posibile: obținerea de câștiguri ce constă în plăți numerice sau de altă natură
(utilități).
v. Preferințele jucătorilor în ceea ce privește rezultatele posibile.

Pentru a ”rezolva” astfel de situații,trebuie să adoptăm decizii care servesc în scopul satisfacerii
propriului interes,deci a unui obiectiv pe care dorim să -l realizăm.Aceasta presupune că suntem
factori de decizie raționali și dorim optimizarea unui rezu ltat posibil al unei situații conflictuale.
Mulțimea aspectelor ce țin de deciziile unor entități presupuse conștiente în cadrul unor situații
conflictuale (deci situații în care jucătorii au interese contrarii) reprezintă obiectul u nei teorii
matematic e care se aplică în economie,științe politice,psihologie,știința calculatoarelor,anume
teoria jocurilor. În cadrul teoriei jocurilor se studiază modele matematice simplificate ale
situațiilor de conflict și de cooperare între factori de decizie raționali ( pe care îi vom numi
jucători).Intervine aici noțiunea naturală de strategie a unui jucător :intuitiv,strategia unui
jucător reprezintă succesiunea de acțiuni ale acestuia a cărui rezultat este un anume câștig.
Să discutăm puțin despre câteva repere istor ice în teoria jocurilor:
 1713
Se presupune că prima problemă de teoria jocurilor,ce poartă numele de ”problema lui
Waldegrave”, a apărut în 1713 având la bază jocurile de noroc. În acest an a fost prezentată
pentru prima oară de către James Waldergrave o strategie utilă pentru a câștiga un joc de cărți
între doi jucători și mai târziu s -a generalizat pentru cazul mai multor jucători.Problema este
următoarea (pentru cazul generalizat):se presupune că jocul are loc între n + 1 jucători și fiecare
jucător a daugă o unitate monetarăîntr -o cutie ori de câte ori pierde. Pr imii doi jucători joacă
împreună , iar câștigătorul joacă împreună cu al treilea jucător. Jocul continuă analog și se încheie
în momentul în care un jucător a învins pe rând restul de jucători.N e intesează acum să găsim
probabilitatea ca unitățile monetare din cutie sa fie câștigate într-un anumit număr de
jocuri ,unde este specificat de către un jucător.
 1838
Antoine Augustin Cou rnot, matematician și economist,absolvent al prestigioase instituții
“Școala Normală Superioară”, este considerat primul intelectual care a introdus “instrumentele”
matematice de analiza și proba bilități în economie,personalitate de referință in analiza e conom ica
și în știinta numită econometrie .Cournot este cel care a gândit conceptul matematic care-i poarta
numele, “Modelul duopolului lui Cournot”, ce reprezintă model ul economic al următoarei
situații:presupunem că pe piață există doar două firme A și B care produc un același tip de
bun,să -l numim K.Fie q A și q Bcantitatea de bun K produsă de A,respectiv B.În ipoteza că cele

două firme decid simultan și independent cantitățile de bun K pe care le vor produce,se pune
problema valorilor cantităților q A și q B așa încât fiecare dintre cele două firme să -și maximizeze
câștigul.Soluția acestei probleme este dată de o situație de „echilibru”,noțiunea de echilibru din
această situație fiind foarte asemănătoare cu echilibrul lui Nash,care a fost „redescoperit” mai
târziu de către John Nash.
 1883
Joseph Bertrand, matematician și istoric francez care s -a remarcat prin lucrări de istoria
matematicii și prin contribuții în geometrie și teoria probabilităților,propune în 1883 un alt
model pentru studiul compotamentului con curenței a două firme pe piață numit „Modelul
duopolului Bertrand”;acesta prezintă următoarea situație:două firme aflate pe aceeași piață
produc produse omogene (adică diferite,dar substituibile).Strategiile de care dispun cele două
firme sunt reprezentate de alegerea simultană și independentă a prețurilor celor doă produse (și
nu a cantităților,ca în cazul duopolului Cournot).Se pune problema găsirii celor mai c onvenabile
prețuri (deci care maximizează câștigul fiecărei firme).Soluția acestui joc este dată un punct de
echilibru Nash ( evident, altul decât în cazul duopolului Bertrand).
 1929
Harold Hotteling ,unul dintre pionierii statisticii matematice și economiei al secolului
XX,propune în 1929 un model al concurenței economice care îi poartă numele,anume „Modelul
Hotteling”.Situația descrisă de acest model este următoare:fie două magazine de înghețată M 1 și
M2situate pe o plajă care oferă spre vânzare aceeași mar fă.Pentru simplitate,lucrăm în
următoarele ipoteze:
 distanța dintre cele două magazine este egală cu o unitate și M 1 este situat la
coordonata x=0 iar M 2 se află la coordonata x=1;
 cumpărătorii se află între cele două magazine și au o repartiție uniformă de
densitate egală cu 1 în intervalul .
 Prețul unitar al unui produs este același,indiferent de magazin.
 Relocalizarea unui magazin se presupune a avea loc instantaneu și fără
costuri.
Cumpărătorii,în alegerea magazinului,vor ține cont de costul de transport (costul de transport
poate însemna benzină,timp etc.).Prin urmare,strategia pentru maximizarea câștigurilor
magazineloreste reprezentată de relocalizarea acestora.
 1944
Deși în ultimele două secole a fost un domeniu exploatat de alți cercetători sau profesori,se
consideră că John von Neumann alături de Oscar Morgenstern, un economist celebru,au pus
bazele teoriei jocurilor odată cu lucrarea intitulată „Theory of games and economi c behavior”

(apărută în 1944) după ce au observant asemănarea dintre situațiile conflictuale ce apar în
jocurile de noroc și cele din domeniul economiei. John von Neumann,intelectual considerat
pionier în diferite domenii, a adus importante contribuții în d omenii precum matematică,
economie, informatica, fizica.În cadrul teoriei jocurilor,Neumann a demonstrat primele teoreme
ce țin de echilibrul unui joc de două persoane cu sumă nulă în informație perfectă (adică jocurile
în care fiecare jucător cunoaște st rategiile de care dispune celălalt jucător cât și istoricul jocului
și câștigul unui jucător este pierderea celuilalt și invers). Spre exemplu,Pokerul și jocurile de
noroc sunt jocuri cu sumă nulă , deoarece totalul sumelor câștigate de unii jucători este egal cu
pierderile altor jucători. Bilanțul total este deci nul.
Totuși, numele lui John Nash este unul deosebit de important în teoria jocurilor ;Nash, intelectual
care a primit premiul N obel pentru economie pentru conceptul cunoscutsub numele
de „echilibrul lui Nash” ,acesta fiind reprezentat de un rezultat publicat doar pe o pagină,
demonstrează o idee destul de simplă și ușor de explicat unei persoane fără cunoștințe de
specialitate:fie un joc cu un număr finit de jucători (entități raționa le)care se bazează doar pe
informațiile asupra acțiunilor celorlalți jucători (deci jocul este în informație completă),fiecare
jucător dispune de un număr finit de strategii, se poate atinge o stare de echilibru. Soluția de
echilibru a lui Nas h reprezintă o situație în care niciunul dintre jucători nu va fi tentat să își
schimbe strategia,în caz contrar jucătorul care își schimbă strategia va câștiga mai puțin.De
menționat faptul că echilibrul Nash nu reprezintă neapărat strategia optimă pentru fiecare juc ător
în parte,este însă o situație avantajoasă pentru toți jucătorii în ansamblu.
Să explicăm noțiunea de echilibru Nash în cazul celebrului joc numit „dile ma prizonierului”:
Doi tâlhari au comis o crimă și se află în prezent în închisoare în celul e sepa rate, fără a să aibă
posibilitatea să comunice între ei. Aceștia primesc același aranjament din partea avocatul ui
acuzării: dacă ambii mărturisesc, fiecare va primi pedeapsă de zece ani de închisoare. Dacă doar
unul dintre ei mărturisește și celalalt nu spune nimic, primu l va primi o recompensă iar al doilea
își va primi închisoare pe viață.Și,în fine,dacă ambii sunt discreți,atunci fiecare va primi o taxă
minoră. Singura soluție la dilema prizonierului sau singurul punct de e chilibru a lui „Nash” este
situația în care amândoi mărturisesc. Acesta reprezintă cel mai bun răspuns la strategia celuilalt
deoarece nici unul nu poate risca să tacă neștiind ce va face celă lalt. Lipsa de comunicare duce la
o stare de echilibru, darechilibrul Nash nu reprezintă neapă rat cea mai bună soluție pentru cei doi
“jucători”. Echilibrul lui Nash a fost utili zat pentru a analiza diverse tipuri de situații de co nflict
sau pentru a studia măsura în care oamenii cu pre ferințe diferite pot coopera, organizarea
licitațiilor, anal iza de strategii de marketing, pentru a numi doar câteva.

În cele ce urmează,vom formaliza noțiunea de joc și ne vom familizariza cu noțiuni de bază din
teoria jocurilor.

Ce este un joc?

De multe ori se intamplă ca noi,oamenii,sa fim nevoiți sa alegem o decizie dintr -o multime de
decizii pentru a realiza un anume deziderat.Este firesc sa ne punem problema găsirii celei mai
bune decizii după ce au fost analizate si comparate toate deciz iile posibile.Ne propunem deci sa
gasim decizia ”optima”,insa ne vom referi la ”optimalitatea” definită în cadrul unui model
matematic deoarece,în sens larg,optimalitatea reprezintă o noțiune foarte complexă .Teoria care
modelează optimalitatea deciziilor (dintr -o anumită privință) este reprezentată de cercetările
operaționale.
Teoria jocurilor modelează s ituațiile conflictuale între doi sau mai mulți jucători(numiți si
factori raționali);fiecare jucător u rmărește să atingă un anume obiectiv(ce poate fi reprezentat de
bani sau alte utilități;în general,obiectivele urm ărite de jucători le vom numi câștiguri) iar aceștia
(jucătorii) nu depind unii de alții în alegerea deciziilor individuale,dar depind de mulțimea
tuturor deciziilor jucătorilor si de conseci nțele acestora.
Observație:
Prin situație conflictuală vom înțelege,în sensul teoriei jocurilor,o “întâlnire ” între doi sau mai
mulți jucători(entități rationale) unde fiecare jucător are interesul să atingă un anumit
obiectiv,interes care contravine celor lalți jucători,deci intră în “conflict” cu acestea.
Formal ,vom înțelege prin joc de n persoane o situație în care acționează mulțimea N={1,2,…,n}
de entități rationale (numite și jucători),care conform unui set de reguli (cunoscut de toți
jucătorii) al eg independent si succesiv câte o decizie(mai spunem ca ”efectuează o acțiune sau
mutare”) dintr -o mulțime de decizii.În funcție de condițiile în care jocul se termină (aceste
condiții fiind specificate de regulile jocului),fiecare jucător va fi recompensa t,deci va avea un
”câștig”.Vom presupune că fi ecare jucător își analizează rational(conștient) acțiunile așa încât să
obțină un câștig cât mai mare cu putință.
Vom spune că acțiunea jucătorului i reprezintă alegerea unei decizii dintr -o mulțime de
decizii notată cu la fiecare din momentele ,j .Vom nota cu (și vom numi
”starea de informație”) mulțimea acțiunilor jucătorilor N-{i} care preced acțiunea jucătorului
i(presupunând că i cunoaște acțiunile celorlați jucători).Vom formaliza noțiunea de ”acțiune a
unui jucător” și vom spune că acțiunea globală a jucătorului i reprezintă alegerea unei funcții
așa încât , ,unde reprezintă strategia pură a jucătorului i.Vom
nota cu mulțimea strategiilor pure ale jucătorului i.Se observă că o strategie pură reprezintă
mulțimea deciziilor corespunzătoare jucătorului i în cadrul jocului respectiv.În cuvinte
simpl e,strategia pură a jucătorului i reprezintă un plan de acțiune (pentru jucătorul i) în funcție
de care se alege o decizie la fiecare moment al jocului ținând seama de starea la care se află

jocul la fiecare astfel de moment (adică deciziile luate de ceila lți jucători până la momentul
respectiv) .
Ținând cont de noțiunile prezentate mai sus,putem spune că alegerea deciziilor de către jucătorul
i revin e la alegerea unui element din ;cum fiecare jucător alege o strategie pură
,se va determ ina astfel desfășurarea jocului,adică partida realizată (adică un joc incheiat)
și câștigurile aferente,adică (unde
se numește funcția de
câștig,iar reprezintă câștigul obținut de jucătorul i).Vom numi joc de n persoane in formă
normală sistemul .
În funcție de câștig,vom distinge:
 Jocuri cu sumă nulă: se numește joc cu sumă nulă dacă
=0,pentru orice
;în acest caz,p ierderea unor jucători reprezintă câștigul celorlalți.
 Jocuri cu sumă nenulă:în acest caz,jucătorii,dacă aleg strategii potrivite, își pot îmbunătăți
simultan câștigurile.
În funcție de numărul de strategii disponibile pentru fiecare jucător,distingem jocuri finite și
jocuri infinite ;în cele ce urmează,ne vom ocupa de jocurile finite ,cele infinite fiind mai dificil
de formalizat.
Definiție :Vom spune că este joc finit dacă mulțimile strategiilor pure sunt finite,orice .
Observație: Dacă este joc finit,atunci numărul de jucători este finit(dacă numărul de jucători ar
fi infinit,atunci mulțimea strategiilor pure ar fi infinită,ceea ce contrazice definiția jocului
finit)
Dacă este un joc finit de două persoane,vom mai spune că este un joc bimatriceal deoarece
dacă ,atunci f orma sa normală este formată din două matrice
de tip (m,n),A= și B= ,așa încât și ,
.
În cazul unui joc de două persoane finit și cu sumă nulă,forma sa normală se reduce la o singură
matrice (deoarece A+B=0,deci A= -B)
Exemple:
i) Joc de două persoane cu sumă nulă(joc matriceal)

Jocul Morra practicat în Roma Antică

Considerăm doi jucători care arată în același timp unul sau două degete de la mâna stângă; fiecare
jucător încearcă apoi să ghicească numărul de degete arătate de adversar.Au loc următoarele
situații:
A. Niciunul dintre jucători nu ghicește sau ghicesc amândoi:în acest caz,nimeni nu câștigă
(câștigul este nul pentru fiecare jucător)
B. Unul dintre jucători ghicește iar celălalt nu:atunci cel care a ghicit câștigă un număr de
unități monetare egal cu numărul de degete arătate (atat de jucătorul care ghicește cât și
de adversar).
Vom întocmi matricea câștiguri lor pentru acest joc:
Notăm cu A 1 și A 2 cei doi jucători,deci mulțimea jucătorilor { A1, A2 } este finită.
Mulțimea strategiilor pure este aceeași pentru fiecare jucător,anume
,unde fiecare paranteză de forma (i,j) (i=1,2 și j=1,2) are
peprima poziție numărul de degete arătate de fiecare jucător și pe a doua poziție
numărulde degete pe care jucătorul crede că le -a arătat adversarul său.
Pe prima linie respectiv prima coloană am trecut strategiile pure ale lui A 2 respectiv
strateg iile pure ale lui A1.Restul de celule ale matricei reprezintă câștigul/pierderea lui A 2
când jucătorul A 1 joacă strategia s iar A 2 joacă strategia p,unde s și p .

A2
A1 (1,1) (1,2) (2,1) (2,2)
(1,1) 0 2 -3 0
(1,2) -2 0 0 3
(2,1) 3 0 0 -4
(2,2) 0 -3 4 0

Observație: MatriceaA 1a câștigurilor pentru jocul Morra este realizată mai sus relativ la
câștigurile respectiv pierderile lui A2.Matricea câștigurilor se poate realiza și relativ la
câștigurile/pierderile jucătorului A 1.În acest caz,ea va arăta astfel:

A1
A2 (1,1) (1,2) (2,1) (2,2)
(1,1) 0 2 -3 0
(1,2) -2 0 0 3
(2,1) 3 0 0 -4
(2,2) 0 -3 4 0

ii) Joc bimatriceal
Să formalizăm jocul prezentat în introducere numit “Dilema prizonierului” :
Să observăm că avem toate elementele necesare unui joc sub formă normală. Mulțimea
jucătorilor este finită, i {1,2} , mulț imea strategiilor pentru fiecare jucător , (
cu A = Acuză, N = Neagă) , iar funcțiile de câștig sunt :

Vom reprezenta acest joc în formă normal ă și sub formă matricială:

Prizonier 2

Prizonier 1

Liniile și coloanele matricii indică strategiile realizabile ale jucătorilor (strategiile pure), iar
celulele matricii vor conține câștigurile fiecărui jucător, în funcție de strategiile alese, cu primul
număr indicând câștigul jucătorului1, iar al doilea pe cel al jucătorului 2.

Strategii mixte
Să considerăm următoarea situație:fie un joc finit de două persoane și J 1,J2 cei doi jucători și
mulțimile , strategiile pure ale lui J1 respectiv J 2.Ce s -ar
întâmpla dacă J 1 ar folosi doar strategia ,presupunând că jocul se repetă de mai multe
ori?Evident, J2 ar observa faptul că J 1 folosește exclusiv strategia și ar alege numai strategii
care să -i maximizeze câștigul personal și care îl pot dezavantaja pe J1.
Exemplu: -7,-7 0,-10
-10,0 -1,-1
J2
J1 B1 B2 B3 A N
N A
N

Să presupunem că în cazul jocului de mai sus J 1 folosește doar strategia A2.Atunci J2 va folosi
strategia B3 la fiecare repetare a jocului;astfel J2 are parte de cel mai mare câștig cu putință și J 1
de cel mai mic câștig pe care îl poate obține.Apare astfel nevoia de a alterna strategiile pentru ca
niciun jucător să nu își dea seama ce strategie urmează să folosească un alt jucător.
Să considerăm acum situația în care un joc finit de n persoane se repetă de mai multe ori,deci
au loc mai multe partide.Știm că fiecare jucător dispune de o mulțime de m strategii pure.Fie J 1
unul din jucători și mulțimea sa de strategii pure.În cazul repetării jocului de un
număr suficient de ori, J1 va avea experiența partidelor anterioare și va observa cam ce strategii
folosesc ceilalți jucători și frecvența lor,astfel că J 1,în încercarea de a intui strategiile folosite de
adversari,se va aștepta la un anume câștig în funcție de strategiile folosite de ceilalți jucători și își
va folosi strategiile cu o anumită probabilitate așa încât,evident,să își maximizeze câștigul.
Să formalizăm conceptul de strategie mixtă :
Definiție:
Strategia mi xtă a jucătorului i ( se mai numește și strategie aleatoare ) reprezintă un set de
probabilități notat prin vectorul (care are toate componentele pozitive și

) unde reprezintă probabilitatea ca jucătorul i săaleagă strategia (pură)
(în ipoteza că jucătorul i dispune de mulțimea finită de strategii pure
= ).În acest caz,notăm mulțimea strategiilor sale mixte cu =

,
Observații:
 Strategia mixtă a jucătorului J1 poate fi gândită drept un set de probabilități asociat de
către jucătorul J k lui J 1.

 Fie un joc de două persoane cu sumă nulă.Câștigul pe care se așteaptă J 2 să îl obțină
atunci când folosește strategia este media variabilei aleatoare

,unde este câștigul obținut când J 1 folosește strategia i și J 2 folosește
strategia j.
A1 (1,2) (2,-2) (3,1)
A2 (2,2) (4,-1) (1,6)

 Condiția
are loc deoarece strategia mixtă reprezintă o
distribuție de probabilitate (întrucât o strategie mixtă reprezintă o modalitate de alegere a
unei strategii pure în cadrul unui experiment aleator).

 Putem privi strategiile mixte drept generalizări ale strategiilor pure astfel:considerăm
strategia mixtă (0,0,..,1,..,0), cu probabilitatea 1 corespunzătoare strategiei pure și
0 pentru toate celelate,deci .Presupunem că sunt folosite strategiile mixte
în acest caz,câștigul fiecărui jucător este o variabilă aleatoare cu media unde
.Vom numi jocul extensia aleatoare a jocului Г.
Definiție:
Considerăm un joc finit de două persoane în care jucători i J1 și J 2 dispun de m respectiv n
strategii pure,iar reprezintă strategia mixtă a jucătorului J 1 și reprezintă strategia mixtă a
jucătorului J 2.Atunci vom numi cantitățile

și

câștigul mediu al lui J 1 respectiv câștigul mediu a l lui J 2,unde este
probabilitatea ca perechea de strategii ( ) să fie utilizată și , reprezintă câștigurile
aferente jucătorilor J 1 respectiv J 2 când utilizeză cuplul de strategii ( ).
Pentru exemplificare strategiilo r mixte să considerăm jocul bimatriceal numit “ Bătălia sexelor ”:
Soțul și soția vor să iasă în oraș pentru a se distra și au de ales între teatru și un meci de
fotbal.Soțul preferă să meargă la fotbal iar soția la teatru.În cazul în care unul dintre ei
cedează,acesta va avea câștigul 2 iar cel care nu cedează va avea câștigul 4.Dacă niciunul nu
cedează,atunci vor rămâne amândoi acasă(deci fiecare va avea câștigul 0).
Vom reprezenta jocul sub formă matriceală:
Soție
Soț F T
F 4,2 0,0
T 0,0 2,4

Mulțimea jucătorilor este
Mulțimea strategiilor ambilor jucători este aceeași: ,unde strategia notată cu F
reprezintă alegerea meciului de fotbal iar strategia notată cu T reprezintă alegerea teatrului.

Să presupunem acum că soția crede că soțul va alege strategia F cu probabilitatea p 1 și strategia
T cu probabilitatea 1 -p1,în vreme ce soțul crede că soția va alege strategia F cu probabilitatea p 2
și strategia T cu probabilitatea 1 -p2.
Soție
Soț F
p2 T
1- p2
F
p1 4,2 0,0
T
1- p1 0,0 2,4

Am adăugat tabelului aferent jocului probabilitatățile pentru strategia fiecărui jucător în parte.
Să notăm cu strategia mixtă la care se așteaptă Soția să fie jucată de Soț și cu
strategia mixtă la care se așteaptă soțul să fie jucată de soție.
Câștigul pe care se așteaptă soția să îl obțină când ea folosește strategia F este:
,adică media variabilei aleatoare
;
Analog,câștigul pe care se așteap tă soția să îl obțină când ea folosește strategia T este:
,adică media variabilei aleatoare
;

În cele ce urmează ne propunem să găsim câteva criterii care să ne permită o clasificare a
jocurilor:
Clasificarea jocurilor
Dispunem de mai multe criterii pentru a clasifica un joc.Avem:
a)în raport cu natura informației
-Jocuri în informație completă
-Jocuri în informație incompletă
Jocul în informatie completa este acel joc în care toti jucători cunosc numărul celor lalți jucători,
strategiile fiecăruia, funcțiile de câstig ale fiecăruia, precum și regulile jocului. Jocul în
informatie incompletă este jocul în care cel puțin unul dintre jucători nu cunoaște una sau mai
multe funcții de câștig ale celorlalți jucători, r estul elementelor (numărul celorlalți jucători,
strategiile fiecăruia și regulile jocului) fiind cunoscute.

b)în raport cu desfășurarea în timp a jocului
-Jocuri statice
-Jocuri dinamice
Jocul static este acel joc în care deciziile jucătorilor se iau simult an, după care jocul ia sfârsit.
Jocul dinamic este acel joc în care deciziile jucătorilor sunt secvențiale, adica evolueaza în timp.
c)în raport cu structura câștigurilor
-Jocuri cu sumă nulă
-Jocuri cu sumă nenulă
Jocul cu sumă nulă reprezintă jocul în care suma câștigurilor este nulă.
Jocul cu sumă nenulă reprezintă jocul în care suma câștigurilor este nenulă.
d)în raport cu starea de informație,în cazul jocurilor dinamice
-Jocuri în informație perfectă
-Jocuri în informație imperfectă
Jocul dinamic în informație perfectă reprezintă jocul dinamic în care fiecare jucător cunoaște
regulile jocului,numărul de jucători și strategiile lor și istoria jocului (evoluția în timp a jocului)
Jocul dinamic în informație imperfectă reprezintă jocul dina mic în care cel puțin un jucător
nu cunoaște istoria jocului,dar cunoaște regulile jocului precum și numărul de jucători si
strategiile acestora.
e)în raport cu numărul de jucători
-jocuri de două persoane
-jocuri de n persoane,unde n este cel puțin 3.
-jocuri contra naturii
f)în raport cu modul în care comunica jucatori între ei avem
– jocuri cooperative;
– jocuri necooperative.
Jocurile cooperative sunt acele jocuri în care jucătorii comunică liber între ei înainte de luarea
deciziilor și pot face pro misiuni (care vor fi respectate) înainte de alegerea strategiilor.

Jocurile necooperative sunt jocurile în care jucătorii nu comunică între ei înainte de luarea
deciziilor.
Ne vom ocupa de ultima categorie de jocuri,cu precădere de jocurile cooperative.

I.2 Jocuri necooperative

Spunem că un joc este necooperativ dacă nu permite comunicarea între jucători pentru luar ea
în comun deciziilor și nu are loc transfererul de câștiguri (utilități ),deci fiecare jucător joacă pe
cont propriu împotriva celorlalț i,acțiunile posibile ale fiecărui jucător fiind cunoscute de toți
ceilalți jucători.
Fiecare jucător își alege planul de acțiune în situația dată (acesta este ales o dată pentru
totdeauna,nu poate fi schimbat pe parcursul jocului) și niciun alt jucător n u cunoaște planul de
acțiune al altui jucător.Jucătorii acționează simultan și independent și primesc câștiguri în funcție
de strategia aleasă.
Un joc necooperativ în formă normală este constituit din următoarele elemente:
 O mulțime de jucători.
 Mulțimea strategiilor pure a jucătorului ,notată
 Funcția de plată (sau funcția de câștig) a jucătorului ,
.
Un joc necooperativ în formă normală este finit dacă mulțimea jucătorilor este finită și mulțimea
strategi ilor pure este de asemenea finită.Un astfel de joc se reprezintă (ne vom referi la cazul
particular de joc necooperativ de două persoane),de regulă,printr -un tablou ale cărei linii sunt
însoțite de etichete ale strategiilor primului jucător și coloanele de etichete ale strategiilor celui
de-al doilea jucător și fiecare element aflat la intersecția unei linii cu o coloană reprezintă
câștigul primului jucător urmat de câștigul celui de -al doilea jucător pentru combinația de
strategii pure ce corespund liniei și coloanei respective.
Exemple de jocuri necooperative:
1) (Avantaj competitiv)
Două companii ce au același tip de activitate trebuie să decidă simultan și independent
dacă să introducă o tehnologie nouă (strategia A) sau nu (strategia B).În cazul în care n u
se introduce tehnologia nouă sau ambele companii adoptă tehnologia,profitul niciuneia
dintre companii nu va fi afectat.Dacă una dintre companii decide să introducă tehnologia
nouă,atunci profitul respectivei companii va crește cu p unități valorice,iar p rofitul
celeilalte companii (care nu a introdus noua tehnologie) scade cu p unități valorice.

A B
A 0,0 p,-p
B -p,p 0,0

2) Jocul monedei
Doi jucători ,independent unul de celălalt, pun pe masă câte o monedă de același fel.Dacă ambii
jucători au ales aceeași față,atunci primul jucător ia ambele monede,altfel cel de -al doilea jucător
ia monedele.
Notăm primul jucător cu 1 și pe al doilea cu 2.Obținem mulțimea de jucători .
Fiecare jucător dispune de două strategii:alege ”banul” sau ”stema”.Notăm cu strategia
”alege banul” și cu strategia ”alege stema”.Avem: mulțimea strategiilor
jucătorului 1 și mulțimea strategiilor jucătorul ui 2.
Fie acum un joc necooperativ oarecare care se repetă de mai multe ori.Analizând exemplul
anterior,constatăm că nu este avantajos pentru niciun jucător să aplice permanent aceeași
strategie pură.De exemplu,dacă jucătorul 1 ar aplica mereu strategia ,jucătorul 2 ar observa
asta și ar aplica la rândul său strategia ,deci jucătorul 1 ar pierde permanent.Situație similară
s-ar obține dacă jucătorul 1 ar aplica permanent strategia .Analog se obține dacă jucătorul 2 ar
aplica permanent aceeași strategie,de unde nevoia de a considera conceptul de
strategiemixtă ,prezentat mai devreme.

Soluția unui joc cu sumă nulă:p unct șa(punct de echilibru)

Să considerăm următorul joc cu sumă nulă reprezentat matriceal:
J2
J1 B1 B2 B3 B4

Mulțimea jucătorilor este ;notăm cu
matricea câștigurilor.
Mulțimea strategiilor pure ale lui J 1 este = iar mulțimea strategiilor pure ale lui J 2
este = .
Vom presupune că matricea este realizată în raport cu jucătorul J 1(deci relativ la
câștigurile/pierderile lui J 1).Se pune acum problema câștigului maxim ce îi este asigurat lui
J1;evident,acesta(câștigul maxim asigurat lui J1) depinde de strategia aleasă de J 2.Să observăm
următoarele:
 Dacă J1 alege strategia A 1,atunci câștigul maxim asigurat este 1(este valoarea minimă de
pe prima linie)
 Dacă J1 alege strategia A 2,atunci câștigul maxim asigurat este 2 (este valoarea minimă de
pe cea de -a doua linie)
 Dacă J1 alege strategia A 3,atunci câștigul maxim asigurat este 3(este valoarea minimă de
pe cea de -a treia linie)
Cum J1 dorește maximizar ea câștigului,va considera că este cel mai convenabil să aleagă
strategia A2 deoarece aceasta îi asigură câștigul egal cu maxi mul minimelor de mai
sus( ),adică 3 în cazul de față.
Strategia aleasă de către J1 prin procedura descrisă mai devreme poartă numele de strategie
maximin .
Privitor la J2,acesta va analiza jocul din pu nct de vedere al pierderilor(întrucât câștigul lui J1
reprezintă pierderea lui J2).Evident,pierderea lui J2 depinde de strategia aleasă de
adversar.Astfel, J2 va analiza pierderea minimă garantată aferentă fiecărei strategii de care
dispune:
 Dacă J2 alege strategia B 1,atunci pierderea minimă asigurată este 3 (este valoarea
maximă de pe prima coloană) A1 1 2 3 2
A2 5 7 2 2
A3 4 3 8 3

 Dacă J2 alege strategia B 2,atunci pierderea minimă asigurată este 1 (este valoarea
maximă de pe cea de -a doua coloană)
 Dacă J2 alege strategia B 3,atun ci pierderea minimă asigurată este 5 (este valoarea
maximă de pe cea de -a treia coloană)
 Dacă J2 alege strategia B 4,atunci pierderea minimă asigurată este 1 (este valoarea
maximă de pe cea de -a patra coloană)
Deoarece J2 dorește o pierdere cât mai mica p osibil,el va considera că este cel mai convenabil să
aleagă una din strategiile B 2 sau B 4,întrucât acestea îi oferă cea mai mica pierdere
posibilă,respectiv 1.
Strategia aleasă de către J2 prin procedura descrisă mai devreme care îi oferă cea mai mica
pierd ere cu putință ( ),respectivB 2 sau B 4, poartă numele de strategie
minimax.
Pentru mai multă claritate,să facem următoarele notații:
și ,deci reprezintă minimul de pe fiecare linie iar este
maximul de pe fiecare coloană.
Vom completa tabelul de mai devreme astfel:

În cazul acestui joc,observăm că
=3 și vom spune că perechea de strategii (A 3,B4) este punctul șa sau
punctul de echilibru în strategii pure al jocului.Vom considera cuplul (A 3,B4) soluția
jocului ;aceasta (soluția jocului) are semnificația strategiei optime pentru fiecare jucător în
parte.
Să definim noțiunea de punct șa al unui joc:
Definiție: Considerăm un joc matriceal.Fie
matricea câștigurilor.Dacă are loc
următoarea relație: J2
J1 B1 B2 B3 B4
A1 1 2 3 2 1
A2 5 7 2 2 2
A3 4 3 8 3 3
5 7 8 3 3
3

= ,atunci perechea ( reprezintă un
punct șa sau punct de echilibru în strategii pure al jocului.
Observații:
I. Nu orice joc cu sumă nulă admite punct șa în strategii pure.
Exemplu de joc cu sumă nulă ce nu admite punct șa în strategii pure:
În baza aceluiași set de notații privitoare la mulțimea jucătorilor,strategiilor,matricei câștigurilor
ș.a.m.d ca în exemplul anterior,considerăm următorul joc matriceal:

Deoarece ,avem că jocul considerat
nu admite punct șa în strategii pure.
II.Punctul șa,dacă există, nu este neapărat unic .
Exemplu de joc matriceal care admite mai mult de un punct șa:
La fel ca mai devreme,considerăm același set de notații pentru jocul matriceal de mai jos

J2
J1 B1 B2 B3 B4
A1 0 1 -2 2 -2
A2 1 0 3 2 0
A3 2 4 -3 3 -3
2 4 3 3 0
2
J2
J1 B1 B2 B3 B4
A1 1 6 0 3 0
A2 3 3 5 6 3
A3 2 1 0 9 0
A4 3 4 5 7 3
3 6 5 9 3
3

Observăm că în acest caz avem două puncte șa:
(A2,B1) și (A4,B1).

Echilibrul Nash în cazul jocurilor bimatriceale

Sa consideram urmatorul joc bimatriceal in forma normală,pe care il vom numi Г,impreuna cu
matricea aferenta:

Ne punem acum problema gasirii solutiei jocului de mai sus,deci a unei perechi de strategii
optime .Vom tine cont de castigul unilateral al unui jucator,care este o componenta a
solutiei.Acesta,castigul unilateral al unui jucator, este influentat de strategiile pe care le are la
dispozitie celalalt jucator.Prin umare,vom cere ca strategia unui jucator (care reprezinta o
componenta a solutiei) sa fie cel mai bun raspuns la strategia celuilalt jucator (care reprezinta
cealalta componenta a solutiei).Putem spune ca o solutie care respecta descrierea de mai sus este
strategic -stabila, deoarece niciun jucator nu va fi interesat sa renunte la strategia sa cat timp
celalalt jucator (respectiv ceilalti jucatori,in cazul jocurilor cu mai mult de doi jucatori) nu se va
abate de la strategia aleasa,intrucat alegerea unilaterală a unei alte strategii poate afecta
castigul.Solutia care indeplineste criteriile de mai sus poarta numele de echilibru Nash. Sa
formalizam notiunea de echilibru Nash:
Definitie: Fie Г un joc bimatriceal necooperativ in forma normala.Perechea de strategii
se numeste echilibru Nash daca au loc urmatoarele relatii:
i. ,adica

ii. ,adica

Sa determinam acum punctele de echilibru Nash ale jocului nostru.Pentru aceasta,vom
proceda dupa cum urmeaza:consideram j ucatorul J 1 cu strategiile aferente;pentru fiecare
strategie a lui J 1 vom determina cel mai bun raspuns a lui J 2 pe care il vom marca prin J2
J1 B1 B2 B3 B4
A1 (4,0) (2,1) (0,4) (1,1)
A2 (0,1) (2,0) (3,3) (5,2)
A3 (2,4) (1,3) (1,2) (0,2)

subliniere cu o linie simpla,de culoare neagra;vom proceda analog pentru J 2,subliniind cu o
linie dubla de culoare n eagra,cel mai bun raspuns al lui J 1 pentru fiecare strategie de care
dispune J 2. Astfel,perechile de strategii cu ambele componente subliniate reprezinta punctele
de echibru Nash (in strategii pure) ale jocului.

Analizand tabelul de mai sus si cele spuse mai devreme,deducem ca perechea de strategii (A 2,B3)
reprezinta echilibrul Nash al jocului.

I.3 Jocuri cooperative

Datorită necesității utilizării capacității de cooperare a jucătorilor,suntem nevoiți să gândim un
model matematic pentru situațiile în care este permisă cooperarea jucătorilor.Acesta reprezintă
obiectul jocurilor cooperative.In cele ce urmeaza,vom prez enta exemple de situatii care
ilustreaza nevoia jucatorilor de a coopera:
In acest sens,sa consideram urmatorul joc:

Ne propunem sa determinam echilibrul Nash (in strategii pure) al jocului.Aplicam procedura de
mai devreme,constatam ca perechea de strategii (A 2,B3) reprezinta punctul de echilibru Nash al J2
J1 B1 B2 B3 B4
A1 (4,0) (2,1) (0,4) (1,1)
A2 (0,1) (2,0) (3,3) (5,2)
A3 (2,4) (1,3) (1,2) (0,2)
J2
J1 B1 B2 B3
A1 (1,2) (2,-2) (3,1)
A2 (2,2) (4,-1) (6,3)

jocului.Relativ la castigul unilateral,se observa ca valoarea castigului aferenta fiecarui jucator in
parte (6 pentru J 1 respect iv 3 pentru J 2) este maxima iar suma castigurilor ( adica 9=6+3) este de
asemenea maxima.In aceasta situatie,niciunul dintre jucatori nu are interesul sa se abata de la
strategia sa,prin urmare nu ar avea de ce sa coopereze in vederea unui castig mai mare.
Sa consideram insa alt joc:

Se observa usor ca perechea ( A1,B1) este punct de echilibru Nash al jocului,insa castigurile ce
revin fiecarui jucator in parte (3 pentru J 1 respectiv 2 pentru J 2) sunt destul de mici fata de
castigurile unilaterale pe care le -ar putea oferi alte combinatii de strategii si,in plus,suma
castigurilor este minima.Vom elimina din discutie cuplurile de strategii care avantajeaza un
jucator si il dezavantajeaza pe celal alt,respectiv cuplurile (A2,B1) si (A1,B2).Ramane eligibila
perechea (A2,B2) care ofera castiguri unilaterale mai mari fata de (A1,B1) iar suma castigurilor
este 12.Pentru ca perechea de strategii (A2,B2) sa fie adoptata,este necesara cooperarea intre
jucatori,care implica modificarea regulilor jocului.Apare apoi o alta problema: impartirea
castigului comun. Desi putem cere ca distributia castigurilor sa ramana aceeasi ca la inceput,noi
vom lucra in ipoteza ca se poate imparti castigul comun si ne va interesa o distributie a castigului
cat mai satisfacatoare cu putinta.
În cele ce urmează,vom prezenta numai o clasă de aplicații a jocurilor cooperative,domeniul de
aplicare a jocurilor cooperative fiind unul foarte vast.Mai precis,ne vom ocupa de p roblemele de
repartizare (redistribuire) a câștigului obținut în urma cooperării.
Vom analiza deci,acele jocuri care permit anumite forme de cooperare între jucători.Vor fi
utilizate două forme elementare de cooperare:
 Închei erea acorduri lor între jucăto ri în scopul formării unor coaliții stabile și
implici t,alegerea în comun a strategiilor .
 Acceptare transferului de câștiguri (utilități) între jucători.

Definiție: Spunem ca jocul Г este cooperativ daca prin regulile sale permit alegerea comună a
strategiilor si transferul de castiguri intre jucatori in scopul interesului acestora la o anumita
actiune comuna. J2
J1 B1 B2
A1 (3,2) (9,1)
A2 (2,8) (7,5)

Cum jocul cooperativ permite „unirea” forțelor unui „grup de jucători” în vederea obținerii unui
câștig mai bun,ne propunem să formaliz ăm ceea ce am numit „grup de jucători”:
Definiție:
Fie N={1,2,…,n} multimea tuturor jucatorilor din cadrul unui joc.Numim coalitie orice
submultime nevida a lui N.
Dacă jocul este de două persoane,atunci este posibilă formarea unei singure coaliții.Dacă jocul
este de n persoane,n sunt posibile mai multe coaliții.Pentru formarea unei coaliții este însă
necesar ca membrii să Am văzut că în cadrul jocurilor coop erative este permisă cooperarea,deci
putem dis cuta despre formarea de coalitii.
Vom încerca să ilustrăm idea de stabilitate în acest context prin următorul exemplu:
Exemplu: Fie un joc de 3 persoane;jucătorii doresc să formeze coaliții.Dacă doi dintre jucători
se coalizează,atunci al treilea jucător trebuie să plătească.Dacă nu se formează nicio coaliție de
două persoane,nimeni nu câștigă nimic.
Nu vom presupune nimic față de relațiile personale dintre cei trei jucători,deci se pot forma 3
astfel de coaliții.Câștigurile aferente sunt: și fiecare din acestea
pot fi considerate soluție a jocului.
Presupunem următoarea modificare a jocului:dacă se formează coaliția ,atunci jucătorul 1
plătește 1,1 unități lui 2 și 0,9 unități jucătorului 3.Se observă că în această situație coaliția
este aproape imposibil de format,pentru că jucătorii 1 și 3 au de câștigat dacă vor coaliza.Astfel
jucătorul 2 este mai dezavantajat decât înainte:una dintre coalițiile în care poate intra nu este
stabilă.Dacă presupunem că jucătorul 2 ar putea plăti jucătorului 3 0,1 unități din câștigul
său,atunci situația sa s -ar îmbunătăți și jocul s -ar reduce la situația precedentă.
S-a ilustrat în exemplul anterior importanța plăților laterale și necesitatea existenței stabilității
între diferitele câștiguri din cadrul unei soluții.Deci utilitatea obținută de o coaliție poate fi
împărțită între membri săi în orice mod posibil.Ne va interesa utilita tea totală ce poate fi obținută
de fiecare coaliție.
Deoarece jocul cooperativ este strâns legat de formarea de coaliții,avem nevoie de un
instrument util pentru studiul acestora (coalițiilor).Acesta poartă numele de funcție
caracteristică:
Definiție:
Fie S N o coalitie si o functie definita pe multimea partilor lui N care asociaza lui S valoarea
maximin a jocului de doua persoane jucat intre coalitiile S si N S; reprezinta castigul

(utilitatea) pe care jucatorii din S o pot obtine cooperand in ca drul jocului,indiferent de actiunile
celorlalti jucatori.
Observații :
A. este câștigul maxim garantat care poate fi obținut de S în cadrul jocului de două
persoane ce are loc între coalițiile S și N -S (aici,fiecare din cele două coaliții are rol de
jucător).
B. Prin definiție,considerăm =0 (1)
C. Daca S T= (deci S si T sunt coalitii disjuncte),atunci el e pot realiza impreuna un câștig
cel putin la fel de mare ca in cazul in care ar fi actionat separat;avem deci urmatoarea
proprietatate a functiei caracteristice(numita proprietatea de super -aditivitate):
(2)
D.În studiul joc urilor de două persoane este de bază studiul strategiilor mixte,deoarece
acestea ne permit să prevedem desfășurarea jocului și astfel putem maximiza un câștig incert.În
cazul jocurilor de n persoane este însă este formarea de coaliții (și nu folosirea strategiilor
mixte).Vom identifica jocul cu funcția sa caracteristică și vom studia jocul sub această formă
deoarece funcția caracteristică este mai potrivită pentru studiul coalițiilor.

Definitie:
Fie ( reprezinta multimea partilor lui N) asa incat satisfa ce conditiile (1)
si (2).Spunem atunci ca este un joc de n persoane in forma caracteristica .
Dacă lucrăm în ipoteza că jocul între coalițiile S și N -S este cu sumă constantă,în sensul că suma
câștigurilor tuturor jucătorilor rămâne aceeași independent de condițiile în care se desfășoară
jocul,avem: ,unde este câștigul total maxim care poate fi
obținut prin acțiunea comună a tuturor jucătorilor ,deci
,unde
N={1,2,…,n} este multimea tuturor jucatorilor din cadrul unui joc .Se observă că problematica
jocurilor cooperative este diferită de cea a jocurilor necooperative;în cazul jocurilor cooperative
nu mai putem discuta de strategie optimă ,deoarece aici este permisă colaborarea între
jucători,drept pentru care jocurile cooperative se mai numesc și nestrategice.
Observație:
Un joc (în forma sa caracteristică ) poate avea sumă constantă fără să aibă sumă constantă în
forma sa normală.Fie un j oc de n persoane în cadrul cărora s -au format coaliții și vrem să știm
toate alocările posibile(vectorii de câștig).Într -un joc cu sumă constantă nu este necesară o
înțelegere pentru împărțirea utilității totale aceasta putând fi împărțită în orice mo d;evident

însă că,jucătorii fiind raționali,nu vor accepta un câștig mai mic decât cel ce poate fi obținut
acționând independent.

În cele ce urmează ne va interesa modul în care va fi împărțit (repartizat) câștigul comun
așa încât repartiția să fie cât mai satisfăcătoare cu putință pentru ansamblul
jucătorilor care au cooperat.
Fie vector cu n elemente,vectorul de ”câștiguri” al unui joc de n
persoane,unde și reprezintă câștigul alocat jucă torului i.Se pune acum problema
condițiilor pe care trebuie să le satisfacă repartiția (alocarea) pentru a putea fi
considerată ”soluție” a unui joc cooperativ:
În ipoteza că fiecare jucător este rațional(adică va dori să aibă de pe urma un ei cooperări un
câștig cel puțin la fel de mare decât ar fi avut dacă ar fi participat pe cont propriu) avem
.Vom mai cere și .
Avem următoarea:
Definitie:
Fie un joc de n persoane.Fie vector cu n elemente ca satisface:
1)
2) ,
Atunci se nume ște imputație (alocare).
Vom nota cu mulțimea imputațiilor jocului.Ne întrebăm acum care din aceste imputații
reprezintă soluția jocului.Desigur,în cazul trivial când conține un singur element,atunci
imputația respectivă este soluția jocului.
Distingem astfel între jocuri esențiale (cele în care mulțimea imputațiilor are cel puțin două
elemente) și jocuri neesențiale (cele în care mulțimea imput ațiilor conține un singur element)
Să observăm că (am aplicat de n ori proprietatea de aditivitate).Dăm
următoarea definiție:
Definiție: Spunem că este joc esențial dacă și neesențial în caz contrar.
Ne vor interesa în continuare jocurile esențiale .
Fie si doua imputatii intr -un joc Jucătorii au de ales între si .Există oare un criteriu
pentru a determina care va fi imputația preferată de jucători?Bineînțeles că în cazul în care

jucătorii pentru care vor prefera imputația ;de asemenea jucătorii pentru care
vor prefera imputați a .Ne va interesa să vedem dacă jucătorii care preferă imputația
pot impune alegerea lui ( sau invers,cei care preferă imputația pot impune alegerea lui
și dacă da,în ce condiții.
Definitie:
Fie si doua imputatii si S o coalitie.Daca:
1) , i S
2)

Spunem ca domina pe in S si notam .
Observații:
 Condiția 1) spune că fiecare membru din S preferă imputația ;condiția 2) spune că
membri coaliției S pot obține un câștig cel puțin la fel de bun ca cel oferit de imputația
.
 Relația de dominare din definiția precedentă se poate interpreta astfel:jucăt orii din
S,având la dispoziție două moduri de alocare a câștigurilor reprezentate prin vectorii si
trebuie să aleagă una din ele.Evident atunci că vor prefera și vor insista să fie aleasă
imputația în defavoarea imputației ,având în vedere cond ițiile 1) și 2).
Să exemplificăm noțiunile de imputație și de dominare a imputațiilor în cadrul unui mic
exercițiu:
Considerăm un joc cooperativ și notăm mulțimea jucătorilor săi cu N= așa încât
și pentru orice S N,S ,S avem .Fie
vectorii

și

.Să se arate că vectorii și sunt imputații.
Soluție:
Verificăm condițiile din definiția imputației.Avem:
și
= , ,deci este o imputație.
Analog obținem: și
= , ,deci este o imputație.
În privința relațiilor de dominare ale imputațiilor,să facem următoarele observații:
 În cadrul coaliției , și ,deci
.

 În cadrul coaliției , și ,deci
.
Deci relația de dominare a imputațiilor nu este tranzitivă.

Fie S N o submulțime de jucători a lui N care formează o coaliție,deci cooperează în cadrul
unui joc.S fiind o mulțime de jucători raționali,va dori să obțină un câștig cel puțin la fel de mare
ca în cazul în care s-ar fi obținut prin forțele proprii ale fiecărui jucător din S ,adică

Observație:
Fie S o coaliți e și o repartiție.Dacă ,atunci jucătorii din S,fiind raționali,nu vor
dori repartiția deoarece S poate obține un câștig mai mare decât suma componentelor
imputației .Vom mai cere ca .
În plus,vom ține cont de relația de d ominare a imputațiilor și vom considera drept soluții optime
imputațiile nedominate.
Se obține următoarea:
Definitie:
Se numeste nucleul jocului multimea imputatiilor (alocarile) sale cu proprietatile:
i)
ii)
Vom nota nucleul jocului cu
Observație: este o mulțime de imputații nedominate ,deci nu există o repartiție a câștigului
care să fie mai convenabilă simultan tuturor jucătorilor în afară de repartițiile din nucleu.

Dacă o repartiție satisface condițiile din definiția nucleului și este
nevidă,atunci ea va fi acceptată drept soluție a jocului.

Exemple de jocuri cooperative:
1.1) (Jocul mânușii)

N= ;jucătorii 1 si 2 au câte o mânușă stângă iar jucătorul 3 are o mânușă dreaptă.O pereche
de mânuși valorează 10 lei,o singură mânușă nu valorează nimic.Funcția caracteristică
este: =0,
Mulțimea imputațiilor acestui joc este
Nucleul acestui joc este
1.2) S N,S ; joc de unanimitate.Functia caracteristica =

1.3) S N,S ; dualul jocului de unanimitate din exemplul anterior.Functia caracte ristica
=

1.4) Joc de cost
reprezintă cheltuielile care se fac dacă membrii coaliției S lucrează
impreună.
1.5)Doamna cu geantă
Doi jucători sunt necesari pentru a transporta un bagaj in schimbul a 20 lei;

Nucleul acestui joc este deoarece:

Am văzut în ultimul exemplu de joc cooperative,anume „ Doamna cu geantă ” un neajuns al
nucleului unui joc cooperativ:poate fi vid.Prin urmare,ne va interesa să găsim condiții în care
nucleul este nevid .Pentru aceasta,avem nevoie de câteva noțiuni pregătitoare.

Jocuri cooperative balansate
Def e Fie u joc cooper t v ul e s de jucător O ul e de v lor
este o secve ă b l s tă s u ul e de v lor b l s tă
d că pe tru or ce avem:

Pute gâ d ceste v lor drept fr c u de t p pe c re f ec re jucător le de d că
co l e d c re f ce p rte Me o ă că pe tru o co l e d t ce stă fr c u e este
cee pe tru e br co l e
Def e Fie u joc cooper t v ul e s de jucător pu e că este un joc
balansat d că u d că pe tru or ce ul e de v lor b l s te avem:

Într-u joc b l s t or ce od de ”î păr re t pulu ” fez b ll pe tru co l d fer te
este fez b l de se e e pe tru co l ” re”
Interpretare pentru jocul b l s t U joc este b l s t d că u e stă o loc re
t pulu pr tre co l c re să producă o v lo re joculu re decât v lo re
joculu ob ută pr cooper re tuturor jucător lor dec r co l
Exemplu: secve e b l s te pe tru jocul jor tă
e u joc cooper t v cu fu c c r cter st că ă
ă
ul e jucător lor e o tr ce joculu l le tr ce su t de te după
u ărul de jucător r colo ele după co l le c re se po t for ec răre colo e
se soc ză u ele e t d secve b l s tă
Co l

Jucător
1 1 0 0 1 1 0 1
2 0 1 0 1 0 1 1
3 0 0 1 0 1 1 1

Elementul l tr ce este eg l cu d că jucătorul p r e co l e de te
după î c z co tr r Pe tru c o secve ă să f e b l s tă trebu e să ve
,pentru orice .
Ev de t că secve

este b l s tă f e c re jucător repreze t t de u ul
râ dur le tr ce este pl c t cu e ct două ele e te e ule le secve e dec pe
f ec re râ d se ob e

Pe de ltă p rte

deci jocul in ansamblu nu este balansat.

Putem enunța acum teorema care caracterizează nucleul nevid:
Teoremă (Bondareva -Shapley): Jocul cooperativ are nucleul nevid dacă și numai dacă este
balansat.
Demonstrație:
Necesitatea: Fie următorul program liniar:

Să considerăm dualul programului de mai sus:

Din definiția jocului balansat deducem că jocul este balansat atunci și numai atunci când soluția
programului dual nu depășește valoarea .Deoarece programul primal are
soluție,at unci,conform teoremelor de dualitate,obținem că ambele probleme au aceeași soluție și
valorile optime ale funcțiilor obiectiv sunt egale.
Suficiența:
Fie un vector din nucleu și colecția balansată de valori .Atunci:
,deci jocul este
balansat.