Aplicații ale teoremelor de dualitate în jocurile de producție [612258]
Universitatea din București
Facultatea de Matematică și Informatică
Specializarea Matematică
Lucrare de licență
Aplicații ale teoremelor de dualitate în jocurile de producție
liniară
Coordonator științific :
Lector dr . Monica Patriche
Absolvent: [anonimizat]
2017
Motivație
Lucrarea de față are drept sursă de inspirație optimalitatea deciziilor studiată de către mine în
anul 3 de facultate la cursul de Cercetări Operaționale. Din dorința de a a profunda rezultatele de
programare liniară studiate la curs, am căutat să mă documentez și să înțeleg noțiuni de bază ale
domeniului numit Teoria Jocurilor pentru ca mai apoi să înțeleg jocuri cooperative de producție
liniară (adică jocuri cu resurse în cadrul cărora modelul de producție este liniar) . Am observat
astfel c ă, spre exemplu, interacțiunile dintre oam eni pot fi modelate cu ajutorul teoriei jocurilor
din perspectiva interesului individual; mai mult, teoria jocurilor ne învață cum să luăm o decizie
care să ne maximizeze satisfacția în raport cu o anumită situație, astfel că nu de puține ori
problemele de teoria jocurilor revin la problem e de programare liniară. Mai mult, astfel de
interacțiuni se generalizează: entitățile care interacționează pot fi agenți economici, țări,
computere, chiar și condiții meteo. Am mai observat că , dacă jocul implică existenț a unor resurse
individuale pentru fiecare participant la joc, se pot formula probleme ce sunt modelate cu
ajutorul programării liniare (în speță, dualitatea în programarea liniară ).
Se observă astfel că optimalitatea deciziilor ( în contextul cercetări lor operaționale) prezintă o
varietate largă de aplicații întrucât este strâns legată de teoria jocurilor; este astfel inevitabil
folosită în studiul interacțiunilor economice și politice, putând fi aplicată și în psihologie
(deoarece contribuie la maxi mizarea nivelului de satisfacție ).
Rezumat introduct iv
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 sc urtă prezentare a câtorva noțiuni de bază a teoriei jocuril or, ilustrată cu
exemple, structurată în următoarele subcapitole:
▪ Scurt istoric al teoriei jocurilor
Vorbim aici 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
Stabilim aici cadrul matematic aferent teoriei jocurilor: ipotezele care sunt adoptate în cadrul
acestei teorii, definiția jocului, câteva proprietăți, definițiile unor noțiuni fundamentale precum
strategia unui jucător, starea de in formaț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 definesc 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 s e oferă o modalitate de calcul pentru acesta. Toate noțiunile introduse sunt
ilustrate prin exemple; rolul acest subcapitolul este de a face trecerea către următorul 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 jocul cooperativ împreună cu alte noțiuni de bază precum: coaliție, alocare a bunurilor
(impu taț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 teorema ce asigură
existența nucleului nevid. Toate noțiunile prezentate în cadrul ace stui 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ă: pro blema primală, problema
duală, teoremele de dualitate, modalitatea de obținere a problemei duale din problema primală,
toate noțiunile fiind însoțite de exemple.
III. Aplicații ale teoriei jocurilor și ale teoremelor de dualitate în jocurile 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 jocurilor cooperative și dualitatea în programarea liniară.
Cuprins :
Capitolul I : Introducere in teoria jocurilor
I. 1 Scurt istoric al teoriei jocurilor ……………………………………… . . 1
I. 2 Formalizarea teoriei jocurilor ……………………………………… . 5
I. 3 Jocuri necooperative …………………………………………………15
I. 4 Jocuri cooperative …………………………………………………22
Capitolul II : Dualitate în programarea liniar ă …………………………………32
Capitolul III : Aplicații ale teoriei jocurilor și a teoremelor de dualitate în jocurile
de producție liniară ………………………………………… …………………47
Bibliografie ………………… …………………………………………………58
Lista tabelelor folosite :
• Tabelul 1 : matricea corespunzătoare jocului Morra ;
• Tabelul 1 . 1: matricea corespunzătoare jocului Morra realizată în raport cu
pierderile/câștigurile jucătorului A 1.
• Tabelul 2 : matricea corespunzătoare jocului „Dilema prizonierului” .
• Tabelul 3 : matricea corespunzătoare jocului prezentat în exemplul 1 . 1;
• Tabelul 4 : matricea corespunzătoare jocului „Bătălia sexelor” ;
• Tabelul 4 . 1: matricea corespunzătoare jocului „Bătălia sexelor” unde s -au completat
strategiile mixte ale jucătorilor ;
• Tabelul 5 : matricea corespunzătoare jocului „Avantaj competitiv” ;
• Tabelul 6 : matricea corespunzătoare jocului prezentat la începutul secțiunii „Soluția
unui joc cu sumă nulă : punct șa (punct de echilibru)
• Tabelul 6 . 1: matricea corespunzătoare tabelului 6 care s -a completat cu strategiile
maximin respectiv minimax ;
• Tabelul 6 . 2: matricea corespunzătoare unui exemplu de joc ce nu admite punct șa în
strategii pure ;
• Tabelul 6 . 3: matricea corespunzătoare unui exemplu de joc ce admite mai mult de un
punct șa ;
• Tabelul 7 : matricea corespunzătoare unui joc bimatriceal prezent at la începutul secțiunii :
„Echilibrul Nash în cazul jocurilor bimatriceale” ;
• Tabelul 7 . 1: matricea corespunzătoare jocului de la tabelul 7 la care s -au marcat cele
mai bune răspunsuri la strategia adversarului pentru fiecare jucător ;
• Tabelul 8 : matricea corespunzătoare jocului prezentat la începutul secțiunii „Jocuri
cooperative” ce ilustrează o situație pentru care nu există interesul jucătorilor de a
coopera ;
• Tabelul 9 : matricea corespunzătoare unui exemplu de joc în care există interesul
jucăto rilor de a coopera ;
• Tabelul 10 : matricea jocului majorității ;
1
I. Introducere in teoria jocurilor
I. 1 Scurt istoric al teoriei jocurilor
Deseori omenirea s -a confruntat cu situații d e tip conflictual , spre exemplu , conflicte
interpersonale , profesionale , economice și chiar forme mai grave ale situațiilor conflictuale , cum
ar fi războaie le.
1Să considerăm și alte exemple de astfel de situații , cum ar fi jocurile de societate (precum
table , jocul de cărți , șah), jocurile sportive (fotbal , tenis, baschet) , jocuri de divertisment etc . Să
observăm câteva elemente comune ale acestor jocuri :
i. Entitățile care iau parte la joc (jucătorii) ; în funcție de fiecare situație în parte , jucătorii
pot fi reprezentaț i de: persoane , firme, echipe , țări, condiții meteo etc.
ii. Regulile ; cu ajutorul lor sunt stabilite posibilitățile de comun icare între jucători ,
condițiile în care se joacă jocul (inclusiv condițiile în care se încheie un joc) , informația
de care dispune fiecare jucător despre ceilalți jucători și despre istoricul jocului ;
iii. Posibili tatea de a acționa disponibilă fiecărui jucător : decizii respectiv strategii aferente
fiecărui jucător .
iv. Rezultatele ce se pot obține : câștiguri ce constau în bani sau alte utilități (cum ar fi
combustibil , haine , bijuterii etc . )
Pentru a câștiga un joc precum cele expuse mai devreme , 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 rezultat
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ăt orii au interese contrarii) reprezintă obiectul u nei teorii
matematice 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
1
Rodica Brânzei Teoria Jocurilor, Editura Universității „Al. I. Cuza”, Iași , 2006.
2
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 istorice în teoria jocurilor :
• 11713
Se presupune că p rima 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 adaugă o unitate monetară într-o cutie ori de câte ori pierde . Primii doi jucători
joacă împreună , iar câștigătorul joacă împreună cu al treilea jucător . Jocul con tinuă analog și se
încheie în momentul în care un jucător a învins pe rând rest ul de jucători . Problema revine la a
găsi probabilitatea ca unitățile monetare din cutie sa fie câștigate într-un anumit număr k( k∈
ℕ) de jocuri , unde k este specifi cat de către un jucător .
• 1838
Antoine Augustin Cou rnot, matematician și economist , absolvent al prestigioase instituții
„Școala Normală Superioară” , este considerat primu l intelectual care a introdus „ instrumentele ”
matematice de analiză și proba bilități în economie , fiind o personalitate de referință in analiza
economică și în științ a 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ă f irme A și B care
produc un același tip de bun , să-l numim K . Fie q A și q B cantitatea 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 din tre 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ă situ ație fiind foarte asemănătoare cu noțiunea de
„echilibrul lui Nash ”, care a fost „redescoperit” mai târziu de către John Nash .
• 1883
1 Victorița Dolean http: //clujaxio. ro/2017/02/27/teoria -jocurilor -matematica -in-viata -de-zi-cu-zi-i/
[Interactiv] // http: //clujaxio. ro/. – 27 Februarie 2017. – 5 Mai 2017.
4 Mihai Roman http: //www. asecib. ase. ro/Roman/PDF/CAP2. pdf [Interactiv] // http: //www. asecib.
ase. ro/Roman/MR. html. – 20 Iunie 2017.
3
4; 6Joseph 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 compo rtamentului concurenț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 uă produse (și
nu a cantităților , ca în cazul duopolului Cournot) . Se pun e problema găsirii celor mai
convenabile 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) .
• 1; 51929
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 a: fie două magazine de înghețată M1
și M 2 situate pe o plajă care oferă spre vânzare aceeași marfă . Pentru simplitate , lucrăm în
următoarele ipoteze :
➢ distanța dintre cele d ouă 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 [0,1].
➢ 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 .
1 Mihai Roman http: //www. asecib. ase. ro/Roman/PDF/CAP2. pdf [Interactiv] // http: //www. asecib.
ase. ro/Roman/MR. ht ml. – 20 Iunie 2017.
2 Victorița Dolean http: //clujaxio. ro/2017/02/27/teoria -jocurilor -matematica -in-viata -de-zi-cu-zi-i/
[Interactiv] // http: //clujaxio. ro/. – 27 Februarie 2017. – 5 Mai 2017.
5 Daniela Constantin Luminița http: //cse. uaic.
ro/_fisiere/Documentare/Suporturi_curs/III_Economie_politici_regionale. pdf [Interactiv]. – 26 Iunie
2017.
6 https: //www. britannica. com/biography/Joseph -Bertrand [Online]. – Iunie 19, 2017.
4
Cumpărătorii , în alegerea magazinului , vor ține cont de cos tul de transport (costul de transport
poate însemna benzină , timp etc . ). Prin urmare , strategia pentru maximizarea câștigurilor
magazinelor este reprezentată de relocalizarea acestora .
• 1; 21944
Deși în ultimele două secole a fost un domeniu exploatat de alți cercetători sau p rofesori , se
consideră că John von Neumann alături de Oscar Morgenstern , un economist celebru , au pus
bazele teorie i jocurilor odată cu lucrarea intitulată „Theory of games and economic behavior”
(apăr ută în 1944) după ce au observa t 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 domenii precum matematică , economie ,
informa tică, fizică . În cadrul teoriei jocurilor , Neumann a demonstrat primele teoreme ce țin de
echilibrul unui jo c de două persoane cu sumă nulă în informație perfectă (adică jocurile în care
fiecare jucător cunoaște strategiile de care dispune celălalt juc ător cât și istoricul jocului iar
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 cunoscut sub 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 pe rsoane fără cunoștinț e de
specialitate : fie un joc cu un număr finit de jucători (entități raționale) 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 m ai puțin . De
menționat faptul că echilibrul Nash nu reprezintă neapărat strategia optimă pent ru fiecare jucător
în parte , însă este o situație avantajoasă pentru toți jucătorii în ansambl u.
Să explicăm noțiunea de echilibru Nash în cazul celebrului jo c numit „dile ma prizonierului” :
Doi tâlhari au comis o crimă și se află în prezent în închisoare în celul e sep arate , fără
posibilitatea de a comunica între ei . Avocatul acuzării le propune acestora un aranjament
1 Victorița Dolean http: //clujaxio. ro/2017/02/27/teoria -jocurilor -matematica -in-viata -de-zi-cu-zi-i/
[Interactiv] // http: //clujaxio. ro/. – 27 Februarie 2017. – 5 Mai 2017.
2 Mihai Roman http: //www. asecib. ase. ro/Roman/PDF/CAP2. pdf [Interactiv] // http: //www. asecib.
ase. ro/Roman/MR. html. – 20 Iunie 2017.
5
comun : dacă ambii mărturisesc , fiecare va primi pedeapsă de 7 ani de închisoare . Dacă doar
unul dintre ei mărturisește și celă lalt tace (deci își neagă fapta) primu l va fi eliberat iar al doilea
va fi condamnat la 10 ani de închisoare . Și, în fine , dacă ambii tac , atunc i fiecare va fi
condamnat la câte un an de închisoare . Singura soluție a acestui joc este reprezentată de singurul
său punct de e chilibru „Nash” : în care ambii mărturisesc fapta , această situație fiind cel mai
bun răspuns la strategia adversarului , deoarece nici unul nu poate risca să tacă neștiind ce va face
adversarul , însă echilibrul Nash nu reprezintă neapărat cea m ai favorabilă situație pentru fiecare
din cei doi „ jucători” , dar pentru ansamblul jucătorilor este cea mai convenabilă situație .
Echilibrul lui Nash a fost utili zat pentru analiza diverse lor de situații de co nflict sau pentru a
studia în ce măsură poate exista cooperarea între oamenii cu pre ferințe diferite , analiza
strategii lor de mark eting , acestea din urmă fiind doar câteva exemple de aplicabilitate a
echilibrului Nash .
În cele ce urmează , vom formaliza noțiu nea de joc și ne vom familizariza cu noțiuni de bază
din teoria jocurilor .
I. 2 Formalizarea teoriei jocurilor
Ce este un joc?
1 De multe ori se intamplă ca noi , oamenii , sa fim nevoiți sa alegem o decizie dintr -o mulț ime
de decizii pentru a realiza un anume deziderat . Este fir esc să ne punem problema găsirii celei mai
bune decizii după ce au fost analizate si comparate toate decizi ile posibile . Ne propunem deci să
găsim decizia „optimă” însă ne vom referi la „optimalitatea” acceptată în cadrul unui model
matematic deoarece , în sens larg , optimalitatea reprezintă o noțiune foarte complexă . Un cadru
riguros de modelare a optimalității deciziilor este oferit de cercetările operaționale .
1 Guillermo Owen Teoria jocurilor , Editura Tehnică, București , 1974.
6
Teoria jocurilor modelează s ituațiile conflictuale între doi sau mai mulți jucători (numiți si
factori /entități raționali /e); 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 consecinț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 raț ionale) unde fiecare jucător are interesul să atingă un anumit obiectiv ,
interes care contravine intereselor celorlalți jucători , deci intră în „ conflict” cu acestea .
1Formal , vom înțelege prin joc de n persoane o situație în care acționează mulțimea N={1 , 2, . .
. , n} de jucători , care conform unui set de reguli (cunoscut de toți jucătorii) aleg 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 recompensat , deci va avea un „ câștig” . Vom presupune că
fiecare jucător își analizează raț ional (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 j ucătorului i ∈N reprezintă alegerea unei decizii dintr -o mulțime de
decizii notată cu Iij la fiecare din momentele tij, j ∈{1,2,…,pi}. Vom nota cu Sij (ș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 σi
așa încât σi(Sij)∈ Iij , ∀ j=1,…,pi, unde σi reprezintă strategia pură a jucătorului i . Vom
nota cu Σi mulțimea strategiilor pure ale jucătorului i . Să observă m că mulțimea strategiile pure
ale lui i reprezintă mulțimea deciziilor corespunzătoare jucătorului i în cadrul jocului respe ctiv.
În cuvinte simple , strategiile pure ale 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 ceilalț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 Σi; cum fiecare jucător i ∈ N alege o strat egie
pură σi∈ Σi, se va determina astfel desfășurarea jocului , adică partida realizată (deci un joc
incheiat) σ=(σi)i∈N și câștigurile aferente , adică ui(σ) (unde u: ∏Σi→ℝN n
i=1 se numește
funcția de câștig , iar ui(σ) reprezintă câștigul obținut de jucătorul i) . Vom numi joc de n
persoane î n formă normală sistemul Γ={Σi,σi}i∈N .
1 Guillermo Owen Teoria jocurilor , Editura Tehnică, București, 1974.
7
În funcție de câștig , vom distinge :
• Jocuri cu sumă nulă : Γ se numește joc cu sumă nulă dacă ∑ui(σ)n
i=1 =0, pentru orice σ∈
Σ; în acest caz , pierderea 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 .
1Definiți a 1: Vom spune că Γ este joc finit dacă mulțimile strategiilor pure Σi sunt finite , orice
i∈N.
Observația 1 : 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 Σi 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ă Σ1={σ1,…,σm} și Σ2={s1,…,sn}, atunci jocul în forma sa normală poate fi reprezentat
prin două matrice de tip (m , n), A=(aij) și B=(bij), așa încât aij=u1(σi,sj) și bij=
u2(σi,sj),i={1,…,m},j={1,…,n} .
Î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)
Exemplul 1 :
i) Joc de două persoane cu sumă nulă (joc matriceal)
2Jocul 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)
1 Guillermo Owen Teoria jocurilor , Editura Tehnică, București, 1974.
2https: //www. academia.
edu/31298488/CERCET%C4%82RI_OPERA%C5%A2IONALE_%C5%9EI_TEORIA_DECIZIEI_CAPITOLUL_7_MODELUL_J
OCURILOR_MATRICEALE [Interactiv]. – 1 Septembrie 2017.
8
B. 1 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âștigurilor 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 Σ1=Σ2=
{(1,1)(1,2),(2,1),(2,2)}, unde fiecare paranteză de forma (i , j) (i=1 , 2 și j=1 , 2) are pe
prima poziție numărul de degete arătate de fiecare jucător și pe a doua poziție numărul
de 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
strategiile pure ale lui A1. Restul de celule ale matricei reprezintă câștigul/pierderea lui
A2 când jucătorul A 1 joacă strategia s iar A 2 joacă strategia p , unde s ∈Σ1și p∈Σ2.
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
Tabelul 1
Observația 1 . 1: Matricea 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
Tabelul 1 . 1
1 https: //www. academia.
edu/31298488/CERCET%C4%82RI_OPERA%C5%A2IONALE_%C5%9E I_TEORIA_DECIZIEI_CAPITOLUL_7_MODELUL_J
OCURILOR_MATRICEALE[Interactiv]. – 1 Septembrie 2017
9
ii) Joc bimatriceal
1Să 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 , Σ1=Σ2={A,
N} ( cu A = Acuză , N = Neagă) , iar funcțiile de câștig sunt :
2u1(A,A)=−7; u1(A,N)=0; u1(N,A)=−10; u1(N,N)=−1
u2(A,A)=−7; u2(A,N)=−10; u2(N,A)=0; u2(N,N)=−1
Vom reprezenta acest joc în formă normală și sub formă matricială :
Prizonier 2
Prizonier 1
Liniile și coloanele matrice i indică strategiile realizabile ale jucătorilor (strateg iile pure) , iar
celulele matricei conțin câștigurile fiecărui jucător , în funcție de strategiile alese , cu primul
număr indicând câștigul jucătorului 1, iar al doilea pe cel al jucătorul ui 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 Σ1={σ1,…,σm},Σ2={σ1,…,σn} strategiile pure ale lui J1 respectiv J 2. Ce s -ar
întâmpla dacă J 1 ar folosi doar strategia σ1, presupunând că jocul se repetă de mai multe
1 Mihai Roman http: //www. asecib. ase. ro/Roman/PDF/CAP2. pdf [Interactiv] // http: //www. asecib.
ase. ro/Roman/MR. html. – 20 Iunie 2017.
-7, -7 0, -10
-10, 0 -1, -1
Tabelul 2
A N
N A
N
10
ori?Evident , J2 ar observa faptul că J 1 folosește exclusiv strategia σ1 și ar alege numai strategii
care să -i maxi mizeze câștigul personal și care îl pot dezavantaja pe J1.
Exemplu l 1. 1
Tabelul 3
1; 2Să 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 Σ1={σ1,…,σm} 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 fol osesc 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ă :
1 Dragomira Baz și Sorin Dragoș Baz http: //www. biblioteca -digitala. ase. ro/biblioteca/pagina2.
asp?id=cap4 [Interactiv] // http: //www. biblioteca -digitala. ase. ro/biblioteca/carte2. asp?id=261&idb=.
– 14 Iunie 2017.
2 Mihai Roman http: //www. asecib. ase. ro/Ro man/PDF/CAP2. pdf [Interactiv] // http: //www. asecib.
ase. ro/Roman/MR. html. – 20 Iunie 2017.
J2
J1 B1 B2 B3
A1 (1, 2) (2, -2) (3, 1)
A2 (2, 2) (4, -1) (1, 6)
11
Definiția 1 . 1:
Strategia mixtă a jucătorului i ( se mai numește și strategie aleatoare ) reprezintă un set de
probabilități notat prin vectorul x=(x1,…,xm) (care are toate componentele pozitive și
∑xk=1m
k=1 ) unde xp reprezintă probabilitatea ca jucătorul i să aleagă strategia (pură) σp,p∈
{1,…,m} (în ipoteza că jucătorul i dispune de mulțimea finită de strategii pure Σi={σ1,…,σm}).
În acest caz , notăm mulți mea strategiilor sale mixte cu Σĩ={x∈ℝm: x≥0,∑xk=1m
k=1},
1Observația 1 . 2:
• 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 σk este media variabilei aleatoare Xk=(c1k…cmk
x1…xm),
unde cij este câștigul obținut când J 1 folosește strategia i și J 2 folosește strategia j .
• Condiția ∑xk=1m
k=1 are loc deoarece strategia mixtă x=(x1,…,xm) 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ă pj∶=(0, 0, . . , 1, . . , 0), cu probabilitatea 1 corespunzăto are strategiei
pure σjși 0 pe ntru toate celelate , deci Σi⊂Σĩ. Presupunem că sunt folosite strategiile
mixte σĩ∈Σĩ; în acest caz , câștigul fiecărui jucător este o variabilă aleatoare cu media
ui(̌σ̃), unde σ̃=(σĩ)i∈N. Vom numi jocul Г̌={Σĩ,uǐ} extensia aleatoare a jocului Г.
Definiția 1 . 2:
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 x reprezintă strategia mixtă a jucătorului J 1 și y reprezintă strategia mixtă a
jucătorului J 2. Atunci vom numi cantitățile u1(̌x,y)=∑∑aijxiyjn
j=1m
i=1 și u2(̌x,y)=
1 Dragomira Baz și Sorin Dragoș Baz http: //www. biblioteca -digitala. ase. ro/biblioteca/pagina2.
asp?id=cap4 [Interactiv] // http: //www. biblioteca -digitala. ase. ro/biblioteca/carte2. asp?id=261&idb=.
– 14 Iunie 2017.
12
∑∑bijxiyjn
j=1m
i=1 câștigul mediu al lui J 1 respectiv câștigul mediu al lui J 2, unde xiyj este
probabilitatea ca perechea de strategii ( σi,σj) să fie utilizată și aij,bij reprezintă câștigurile
aferente jucătorilor J 1 respectiv J 2 când utilizeză cuplul de strategii ( σi,σj).
1Pentru exemplificare strategiilor mixte să considerăm jocul bimatriceal numit “ Bătălia sexelor ”:
1Soț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
Tabelul 4
Mulțimea jucătorilor este J∶={Soție,Soț}
Mulțimea strategiilor ambilor jucători este aceeași : Σ1=Σ2={F,T}, 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
Tabelul 4 . 1
1 Mihai Roman http: //www. asecib. ase. ro/Roman/PDF/CAP2. pdf [ Interactiv] // http: //www. asecib.
ase. ro/Roman/MR. html. – 20 Iunie 2017.
13
Am adăugat tabelul ui aferent jocului probabilitatățile pentru strategia fiecărui jucător în parte .
Să notăm cu x=(p1,1−p1) strategia mixtă la care se așteaptă Soția să fie jucată de Soț și cu
y=(p2,1−p2) 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 :
1u2(F)=2p1+0(1−p1)=2p1, adică media variabilei aleatoare X1=(20
p1(1−p1));
Analog , câștigul pe care se așteaptă soția să îl obțină când ea folosește strategia T este :
u2(T)=0∙p1+4∙(1−p1)=4∙(1−p1), adică media variabilei aleatoare X2=
(04
p1(1−p1));
În cele ce urmează ne propunem să găsim câteva criterii care să ne permită o clasificare a
jocurilor :
2Clasificarea jocurilor
Dispunem de mai multe criterii pentru a clasifica un joc . Avem :
a) relativ la cantitatea de informație
• Jocuri în informație completă
• Jocuri în informație incompletă
Jocul în informați e completă este cel în care toț i jucători cunosc numărul celorlalți jucători ,
strategiile de care dispune fiecare , câștigul ce poate fi obținut de fiecare jucător în parte , precum
și regulile jocului .
Jocul în informaț ie incompletă este cel în care măcar unul dintr e jucători nu cunoaște cel puțin
una din funcțiile de câștig ale celorlalți jucători ; se presupun cunoscute restul elementelor
(numărul celorlalți jucători , strategiile fiecăruia și regulile jocului) .
b) relativ la desfășura rea în timp a jocului
1 Mihai Roman http: //www. asecib. ase. ro/Roman/PDF/CAP2. pdf [Interactiv] // http: //www. asecib. ase.
ro/Roman/MR. html. – 20 Iunie 2017
2 Mihai Roman http: //www. ase cib. ase. ro/Roman/PDF/CAP1. pdf [Interactiv] // http: //www. asecib.
ase. ro/Roman/MR. html. – 21 Mai 2017.
14
• Jocuri statice
• Jocuri dinamice
1Jocul static este cel în cadrul căruia jucătorii decid simultan , după care jocul ia sfârș it.
Jocul dinamic este cel în care deciziile jucătorilor evoluează în timp .
c) relativ la câștiguri
• Jocuri cu sumă nulă
• Jocuri cu sumă arbitrară
Jocul cu sumă nulă cel în care suma câștigurilor este nulă , deci câștigul unor jucători reprezintă
pierderea altor jucători și invers .
Jocul cu sumă arbitrară este cel în car e suma câștigurilor este arbitrară .
d) relativ la starea de informație (pentru jocurile dinamice)
• Jocuri cu informație completă
• Jocuri cu informație incompletă
Jocu l dinamic în informație completă este acela în care fiecare jucător știe regulile jocului ,
număru l de jucători , strategiile core spunzătoare fiecăruia și istoricul jocului ( deci evoluția în
timp a jocului)
Jocul dinamic în informație i ncompletă este acela în care măcar un jucător nu știe istoricul
jocului , dar știe regulile jocului , numărul de j ucători si strategiile corespunzătoare acestora .
e) relativ la numărul de jucători
• Jocuri de două persoane
• Jocuri de n persoane , unde n este cel puțin 3 .
• Jocuri contra naturii
f) relativ la modul în care se realizează comunica rea între jucă tori
• Jocuri cooperative ;
• Jocuri necooperative .
1 Mihai Roman http: //www. asecib. ase. ro/Roman/PDF/CAP1. pdf [Interactiv] // http: //www. asecib.
ase. ro/Roman/ MR. html. – 21 Mai 2017.
15
1Jocurile cooperative sunt cele în cadrul cărora jucătorii au libertatea de comunica între ei
înainte de alegerea strategiilor , deci jucătorii „cooperează” .
Jocurile necooperative sunt cele în care jucătorii nu comu nică între ei înainte de a lua decizii .
Ne vom ocupa de ultima categorie de jocuri , cu precădere de jocurile cooperative .
I. 3 Jocuri necooperative
2Spunem că un joc este necooperativ dacă nu permite comunicarea între jucători pentru luar ea
în comun a deciziilor și nu are loc transfe rul 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 nu 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 N={1,2,…,n} de jucători .
• Mulțimea strategiilor pure a jucătorului i , notată Σi
• Funcția de plată (sau funcția de câștig ) a jucătorului i,ui: ∏Σi→ℝN n
i=1 .
Un joc necooperativ în formă normală este finit dacă mulțimea jucătorilor este finită și
mulțimea strategiilor 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 afla t 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 .
1 Mihai Roman http: //www. asecib. ase. ro/Roman/PDF/CAP1. pdf [Interactiv] // http: //www. asecib.
ase. ro/Roman/MR. html. – 21 Mai 2017.
2 Guillermo Owen Teoria jocurilor , Editura Tehnică, București, 1974.
16
1Exemple de jocuri necooperative :
Exemplul 1 . 2: Jocul „Avantaj competitiv”
Două companii ce vând același tip de servicii trebuie să deci dă simultan și independent dacă
vor introduce o nouă tehno logie (care permite o calitate mai bună a serviciilor oferite)
(strategia A) sau nu (strategia B) . În situația în care nu 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 monetare , iar profitul celeilalte companii (care nu a introdus noua tehnolog ie) scade cu p
unități monetare .
A B
A 0, 0 p, –
p
B -p,
p 0, 0
Tabelul 5
Exemplul 1 . 3: Jocul monedei
Doi jucători pun pe masă câte o monedă de același fel , simultan și independent unul de celălalt .
Dacă ambii jucători au ales aceeași față , atunci cele două monede revin primului jucător , altfel
monedele revin celui de-al doilea .
Notăm primul jucător cu 1 și pe al doilea cu 2 . Obținem mulțimea de jucători N={1,2}.
Fiecare jucător dispune de două strategii : alege ”banul” sau ”stema” . Notăm cu σ1 strategia
”alege banul” și cu σ2 strategia ”alege stema” . Avem : Σ1={σ1,σ2} mulțimea strategiilor
jucătorului 1 și Σ2={σ1,σ2} mulțimea strategiilor jucătorului 2 .
1 Marius Iosifescu, G Ciucu și R Theodorescu Teoria Jocurilor, Editura Tehnică, Bucuresti , 1965
17
Soluția unui joc cu sumă nulă : punct șa (punct de echilibru)
Să considerăm următorul joc cu sumă nulă reprezentat matricea l.
Tabelul 6
1Mulțimea jucătorilor este J∶={J1,J2}; notăm cu C=(cij)i=1,3̅̅̅̅
j=1,4̅̅̅̅ matricea câștigurilor .
Mulțimea strategiilor pure ale lui J 1 este Σ1={A1,A2,A3} , iar mulțimea strategiilor pure ale lui J 2
este Σ2={B1,B2,B3,B4}.
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 p roblema 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)
1 Dragomira Baz și Sorin Dragoș Baz http: //www. biblioteca -digitala. ase. ro/biblioteca/pagina2. asp?id=cap4
[Interactiv] // http: //www. biblioteca -digitala. as e. ro/biblioteca/carte2. asp?id=261&idb=. – 14 Iunie 2017. J2
J1 B1 B2 B3 B4
A1 1 2 3 2
A2 5 7 2 2
A3 4 3 8 3
18
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
(max (min
j=1,4̅̅̅̅cij)), adică 3 în cazul de față .
Strategia aleasă de către J1 prin p rocedura descrisă mai devreme poartă numele de strategie
maximin .
Privitor la J2, acesta va analiza jocul din punct 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ă)
• 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 strateg ia B 3, atunci 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 posibil , el va c onsidera 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 p rocedura descrisă mai devreme care îi ofe ră cea mai mica
pierdere cu putință (min (max
i=1,3̅̅̅̅cij) ), respectiv B2 sau B 4, poartă numele de strategie minimax .
Pentru mai multă claritate , să facem următoarele notații :
αi∶=min
j=1,4̅̅̅̅cij și βj∶=max
i=1,3̅̅̅̅cij, deci αi reprezintă minimul de pe fiecare linie iar βj este maximul
de pe fiecare coloană .
Vom completa tabelul de mai devreme astfel :
19
Tabelul 6 . 1
1În cazul acestui joc,să observăm că:
max (αi)=min (βj)=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ția 1 . 3: Considerăm un joc matriceal . Fie C=(cij)i=1,m̅̅̅̅̅
j=1,n̅̅̅̅ matricea câștigurilor . Dacă are
loc următoarea relație :
λ1=max
i=1,m̅̅̅̅̅min
j=1,n̅̅̅̅cij=min
j=1,n̅̅̅̅max
i=1,m̅̅̅̅̅cij=λ2, atunci perechea ( λ1,λ2) reprezintă un punct șa sau punct
de echilibru în strategii pure al jocului .
Observația 1 . 4:
I. Nu orice joc cu sumă nulă admite punct șa în strategii pure .
Exemplu l 1. 5: Joc cu sumă nulă ce nu ad mite punct șa în strategii pure
1 Dragomira Baz și Sorin Dragoș Baz http: //www. biblioteca -digitala. ase. ro/biblioteca/pagina2.
asp?id=cap4 [Interactiv] // http: //www. biblioteca -digitala. ase. ro/biblioteca/carte2. asp?id=261&idb=.
– 14 Iunie 2017.
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
max (𝛼𝑖)
min (𝛽𝑗)
20
Î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 :
Tabelul 6 . 2
Deoarece 0=max
i=1,m̅̅̅̅̅min
j=1,n̅̅̅̅cij≠min
j=1,n̅̅̅̅max
i=1,m̅̅̅̅̅cij=2, avem că jocul considerat nu admite punct șa în
strategii pure .
II. Punctul șa , dacă există , nu este neapărat unic .
Exemplu l 1. 6: 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 :
Tabelul 6 . 3
Observăm că în acest caz avem două puncte șa :
(A2, B1) și (A4, B1).
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
max (𝛼𝑖)
max (𝛼𝑖) min (𝛽𝑗)
min (𝛽𝑗)
21
Echilibrul Nash în cazul jocurilor bimatriceale
Să consideră m urmă torul joc bimatriceal in forma normală , pe care il vom numi Г, împreună cu
matricea aferentă :
Tabelul 7
1Ne punem acum pr oblema gă sirii soluț iei jocului de mai sus , deci a unei perechi de strategii
optime . Vom ț ine cont de câștigul unilateral al unui jucător , care este o componentă a soluției .
Acesta , câștigul unilateral al unui jucător , este influenț at de strategiile pe care le are la dispoziție
celalalt jucă tor. Prin umare , vom cere ca strategia unui jucă tor (care reprezintă o componentă a
soluț iei) sa fie cel mai bun ră spuns la strategia celuilalt jucă tor (care reprezintă ceal altă
componentă a soluției) . Putem spune ca o soluț ie care respectă descrierea de mai sus este
strategic -stabilă , deoarece niciun jucător nu va fi interesat sa renunțe la strategia sa cât timp
celălalt jucător (respectiv ceilalți jucă tori, in cazul j ocurilor cu mai mult de doi jucă tori) nu se va
abate de la stra tegia aleasă , întrucâ t alegerea unilateral ă a une i alte strategii poate afecta câș tigul.
Soluția care îndeplineș te criteriile de mai sus poarta numele de echilibru Nash . Să formalizăm
noțiunea de echilibru Nash :
Definiția 1 . 4: Fie Г un joc bimatriceal necooperativ in forma normala . Perechea de strategii
(A∗,B∗) se numeste echilibru Nash daca au loc urmatoarele relaț ii:
i. u1(A∗,B∗)≥u1(Ai,B∗),∀ Ai∈Σ1, adica max
Ai∈Σ1(Ai,B∗)=A∗
ii. u2(A∗,B∗)≥u2(A∗,Bj),∀ Bj∈Σ2, adica max
Bj∈Σ2(A∗,Bj)=B∗
1 Dragomira Baz și Sorin Dragoș Baz http: //www. biblioteca -digitala. ase. ro/biblioteca/pagina2.
asp?id=cap4 [Interactiv] // http: //www. biblioteca -digitala. ase. ro/biblioteca/carte2. asp?id=261&idb=.
– 14 Iunie 2017.
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)
22
Să determină m acum punctele de echilibru Nash ale jocului nostru . Pentru acea sta, vom
proceda dupa cum urmează : considerăm jucă torul J 1 cu strategiile aferente ; pentru fiecare
strategie a lui J 1 vom determina cel mai bun ră spuns a lui J 2 pe care î l vom marca prin
subliniere cu o linie simplă , de culoare neagră ; vom proceda analog pentru J 2, subliniind cu o
linie dublă de culoare neagră , cel mai bun ră spuns al lui J 1 pentru fiecare strategie de care
dispune J 2. Astfel , perechile de strategii cu ambele componente subliniate reprezintă
punctele de echibru Nash (în strategii pure) ale jocului .
Tabelul 7 . 1
Analizâ nd tabelul de mai sus ș i cele spuse mai devreme , deduce m că perechea de strategii (A 2,
B3) reprezintă echilibrul Nash al jocului .
I. 4 Jocuri cooperative
1Datorită 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 . În cele ce urmează , vom prezenta exemple de situații
care ilustrează nevoia jucă torilor de a coopera :
În acest sens , să considerăm urmă torul joc :
1 Dragomira Baz și Sorin Dragoș Baz http: //www. biblioteca -digitala. ase. ro/biblioteca /pagina2.
asp?id=cap4 [Interactiv] // http: //www. biblioteca -digitala. ase. ro/biblioteca/carte2. asp?id=261&idb=.
– 14 Iunie 2017.
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)
23
Tabelul 8
Ne propunem să determinăm echilibrul Nash (î n strategii pure) al jocului . Aplică m procedura
de mai devreme , constatăm că perechea de strategii (A 2, B3) reprezintă punctul de echilibru
Nash al jocului . Relativ la câștigul unilateral , se observă că valoarea câștigului aferentă fiecărui
jucător î n parte (6 pentru J 1 respectiv 3 pentru J 2) este maximă iar suma câștigurilor ( adică
9=6+3) este de asemenea maximă . În această situaț ie, niciunul dintre jucători nu are interesul să
se abată de la strategia sa, prin urmare nu ar avea de ce sa coopereze în vederea unui câș tig mai
mare .
Să considerăm însă alt joc :
Tabelul 9
1 Se observă ușor că perechea ( A1, B1) este pun ct de e chilibru Nash al jocului , însă câștigurile
ce revin fiecărui jucător î n parte (3 pentru J 1 respectiv 2 pentru J 2) sunt destul de mici față de
1 Dragomira Baz și Sorin Dragoș Baz http: //www. biblioteca -digitala. ase. ro/biblioteca/pagina2.
asp?id=cap4 [Intera ctiv] // http: //www. biblioteca -digitala. ase. ro/biblioteca/carte2. asp?id=261&idb=.
– 14 Iunie 2017. J2
J1 B1 B2 B3
A1 (1, 2) (2, -2) (3, 1)
A2 (2, 2) (4, -1) (6, 3)
J2
J1 B1 B2
A1 (3, 2) (9, 1)
A2 (2, 8) (7, 5)
24
câștigurile unilaterale pe care le-ar putea oferi alte combinații de strategii și , în plus , suma
câștigurilor est e minimă . Vom elimina din discuț ie cupluri le de strategii care avantajează un
jucător si îl dezavantajează pe celă lalt, respectiv cuplurile (A2, B1) și (A1, B2). Rămâne eligibilă
perechea (A2, B2) care oferă câș tiguri unilaterale mai mari fa ță de (A1, B1) iar suma câș tigurilor
este 12 . Pentru ca perechea de strategii (A2, B2) să fie adoptată , este necesară cooperarea între
jucători , care implică modificarea reg ulilor jocului . Apare apoi o altă problemă : împărțirea
câștigului comun . Deși putem cere c a distribuția câștigurilor să rămână aceeași ca la început , noi
vom lucra în ipoteza că se poate împărți câștigul comun și ne va interesa o distribuție a câștigului
cât mai satisfăcătoare cu putință .
1 Î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
problemele de repartizare (redistribuire) a câștigului obținut în urma cooperării .
Vom analiza deci acele jocuri care per mit anumite forme de cooperare între jucători . Vor fi
utilizate două forme de cooperare ,considerate elementare :
• Stabilirea acorduri lor între jucători în scopul formării unor coaliții stabile , deci
realizabile, și implici t, alegerea în comun a strategii lor.
• Acceptare a transferului de câștiguri (utilități) între jucători .
Definiția 1 . 5: Spunem că jocul Г este cooperativ dacă prin regulile sale permit e alegerea
comună a strategiilor și transferul de câștiguri între jucători î n scopul in teresului acestora la o
anumită acțiune comună .
2 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ția 1 . 6:
Fie N={1 , 2, . . . , n} mulțimea tuturor jucă torilor din cadrul unui joc . Numim coaliț ie orice
submulțime nevidă a lui N .
Dacă jocul este de două persoane , atunci este posibilă formarea unei singure coaliții . Dacă jocul
este de n persoane , n≥3, sunt posibile mai m ulte coaliții . Pentru formarea unei coaliț ii este însă
necesar ca membri săi să se afl e într -o stare de „stabilitate” , în sensul că posibilii membri ai unei
coaliții trebuie să aibă siguranța că respectiva coaliție se poate forma .
1 Guillermo Owen Teoria jocurilor , Editura Tehnică , București , 1974
2 Dragomira Baz și Sorin Dragoș Baz http: //www. biblioteca -digitala. ase. ro/biblioteca/pagina2.
asp?id=cap4 [Interactiv] // http: //www. biblioteca -digitala. ase. ro/biblioteca/carte2. asp?id=261&idb=.
– 14 Iunie 2017.
25
Vom încerca să ilustrăm ide ea de stabilitate în contextul teoriei jocurilor prin următorul
exemplu :
1Exemplu l 1. 7: Fie un joc de 3 persoane în cadrul căruia jucătorii doresc să coalizeze după
următoarea regulă : dacă doi dintre jucători se coalizează , atunci al treilea jucător trebuie să
plătească și d acă nu se formează nicio coaliție de două persoane , nimeni nu câștigă nimic .
Fără a face nicio presupune re relativ la relațiile per sonale dintre cei trei jucători , obținem că
se pot forma 3 astfel de coaliții . Câștigurile aferente pentru fiecare coaliție în parte sunt:
(−2,1,1),(1,−2,1),(1,1,−2) . Presupunem următoarea modificare a jocului : dacă se
formează coaliția {2,3}, atunci jucă torul 1 plătește 1 , 1 unități monetare jucătorului 2 și 0 , 9
unități monetare jucătorului 3 . Se observă că în această situație coaliția {2,3} este aproape
imposibil de format , pentru că jucătorii 1 și 3 au de câștigat dacă vor coali za, deci jucătorul 2
este mai dezavantajat decât înainte de modificarea jocului deoarece una din tre coalițiile în care
poate face parte nu este stabilă .
Am ilustrat astfel importanța existenței stabilității unei coaliții .
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ția 1 . 7:
2 Fie S⊂N o coaliț ie si 𝓋 o funcție definită pe mulțimea părților lui N care asociază lui S
valoarea maximin a jocului de două persoane jucat între coalițiile S ș i N−S; 𝓋(𝑆) reprezintă
câștigul (utilitatea) pe car e jucătorii din S o pot obține cooperând î n cadrul jocului , indiferent de
acțiunile celorlalți jucă tori.
Observația 1 . 5:
A. 𝓋(S) 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 tre cele două coaliții are rol
de jucător) .
B. Prin definiție , considerăm 𝓋(∅)=0 (1)
1 Guillermo Owen Teoria jocurilor , Editura Tehnică , București , 1974 .
2 Dragomira Baz și Sorin Dragoș Baz http: //www. biblioteca -digitala. ase. ro/biblioteca/pagina2.
asp?id=cap4 [Interactiv] // http: //www. biblioteca -digitala. ase. ro/biblioteca/carte2. asp?id=261&idb=.
– 14 Iunie 2017.
26
C. Dacă S∩T=∅ (deci S și T sunt coaliț ii dis juncte) , atunci ele pot realiza î mpreuna un
câștig cel puț in la fel de mare ca în cazul în care ar fi acț ionat separat ; avem deci
urmatoarea proprietatate a funcț iei caracteristice (numita proprietatea de super –
aditivitate) :
𝓋(S∪T)≥ 𝓋(S)+ 𝓋(T) (2)
D. În studiul jocurilor 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 cooperative de n persoane , n≥3 , 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 .
1Definiția 1 . 8:
Fie 𝓋: 𝒫(N)→ℝ (𝒫(N) reprezintă mulțimea părților lui N) așa încâ t 𝓋 satisfa ce condiț iile
(1) si (2) . Spunem atunci ca 𝓋 este un joc de n persoane în formă caracteristic ă.
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 : 𝓋(S)+ 𝓋(N−S)=𝓋(N), unde 𝓋(N) este câștigul total maxim care poate fi
obținut prin acțiunea comună a tuturor jucăto rilor, deci 𝓋(N)=max
σi∈Σi∑ui(σi)i∈N , unde N={1 ,
2, . . . , n} este mulțimea tuturor jucă torilor din cadrul unui joc .
2 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ția 1 . 5:
Fie un joc 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
1 Guillermo Owen Teoria jocurilor , Editura Tehnică , București , 1974
2 Dragomira Baz și Sorin Dragoș Baz http: //www. biblioteca -digitala. ase. ro/biblioteca/pagina2.
asp?id=cap4 [Interactiv] // http: //www. biblioteca -digitala. ase. ro/biblioteca/carte2. asp?id=261&idb=.
– 14 Iunie 2017.
27
împărțirea utilității totale 𝓋(𝑁), aceasta putând fi împărțită în orice mod ; 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
𝓋(N) așa încât repartiția să fie cât mai satisfăcătoare cu putință pentru ansamblul
jucătorilor care au cooperat .
Fie θ=(θ1,θ2,…,θn) vector cu n elemente , vectorul de „ câștiguri” al unui joc de n persoane ,
unde θ=𝓋(N) și θi reprezintă câștigul alocat jucăt orului i . Se pune acum problema condițiilor
pe care trebuie să le satisfacă repartiția (alocarea) θ=(θ1,θ2,…,θn) pentru a putea fi
considerată soluție a unui joc cooperativ :
În ipoteza că fiecare jucător este rațional (deci va dori să aibă de pe urma unei 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 θi≥
𝓋({i}),∀ i ∈N. Vom mai cere și ∑θii∈N=𝓋(N).
Avem următoarea :
1Definiția 1 . 9:
Fie 𝓋 un joc de n persoane . Fie θ=(θ1,θ2,…,θn) vector cu n elemente ca re satisface :
1) ∑θii∈N=𝓋(N)
2) θi≥𝓋({i}),∀ i ∈N
Atunci θ se nume ște imputație (alocare) .
2Vom nota cu E(𝓋) mulțimea imputațiilor jocului . Ne întrebăm acum care din aceste imputații
reprezintă soluția jocului . Desigur , în cazul trivial când E(𝓋) 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 imputațiilor conține un singur element)
1 Guillermo Owen Teoria jocurilor , Editura Tehnică, București , 1974.
2 Dragomira Baz și Sorin Dragoș Baz http: //www. biblioteca -digitala. ase. ro/biblioteca/pagina2.
asp?id=cap4 [Interactiv] // http: //www. biblioteca -digitala. ase. ro/biblioteca/carte2. asp?id=261&idb=.
– 14 Iunie 2017.
28
Să observăm că 𝓋(N)≥∑θii∈N (am aplicat de n ori proprietatea de aditivitate) . Dăm
următoarea definiție :
Definiția 1 . 10: Spunem că 𝓋 este joc esențial dacă 𝓋(N)>∑θii∈N și neesențial în caz
contrar .
Ne vor interesa în continuare jocurile esențiale .
2 Fie θ1 și θ2 doua imp utații intr -un joc 𝓋. Jucătorii au de ales între θ1 și θ2. Există oare un
criteriu pentru a determina care va fi imputația preferată de jucători?Bineînțeles că în cazul în
care θ1 ≠θ2 , acei jucători i pentru care θ1i>θ2i vor prefera imputația θ1; de asemenea ,
jucătorii i pentru care θ2i>θ1i vor prefera imputația θ2. Ne va interesa să vedem dacă jucătorii
care preferă imputația θ1 pot impune alegerea lui θ1 ( sau invers , cei care preferă imputația
θ2 pot impune alegerea lui θ2) și dacă da , în ce condiții .
Definiția 1 . 11:
Fie θ1 și θ2 doua imputații și S o coaliție . Dacă :
1) θ1i≥θ2i,∀ i ∈ S
2) ∑θ1i
i∈S≤𝓋(S)
Spunem că θ1 domină pe θ2 in S și notă m θ1≻Sθ2.
Observația 1. 6:
• Condiția 1) spune că fiecare membru din S preferă imputația θ1; 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
θ1.
• Relația de dominare din definiția precedentă se poate interpreta as tfel: jucătorii din S ,
având la dispoziție două moduri de alocare a câștigurilor reprezentate prin vectorii θ1 si
θ2 trebuie să aleagă una din ele . Evident atunci că vor prefera și vor insista să fie aleasă
imputația θ1 în defavoarea imputației θ2, având în vedere condițiile 1) și 2) .
Să exemplificăm noțiunile de imputație și de dominare a imputațiilor în cadrul unui mic
exercițiu :
29
1Exercițiul 1 : Considerăm un joc cooperativ 𝓋 și notăm mulțimea jucătorilor săi cu
N={1,2,3,4,5} așa încât 𝓋(1,2)=𝓋(4,5)=𝓋(N)=1 și pentru orice S⊂N, S≠{1,2}, S≠
{4,5} avem 𝓋(S)=0. Fie vectorii θ1=(1
4,1
4,1
2,0,0) și θ2=(0,0,,1
2,1
4,1
4). Să se arate că
vectorii θ1 și θ2 sunt imputații .
Soluție :
Verificăm condițiile din definiția imputației . Avem :
θ1i≥𝓋({i})=0 și ∑θ1i5
i=1= 𝓋(N),,∀ i∈N, deci θ1 este o imputație .
Analog obținem : θ2i≥𝓋({i})=0 și ∑θ2i5
i=1= 𝓋(N),,∀ i∈N, deci θ2 este o imputație .
În privința relațiilor de dominare ale imputațiilor , să facem următoarele observații :
• În cadrul coaliției {1,2}: θ11≥θ21 , θ12≥θ22 și θ11+θ12≤ 𝓋(1,2)=1, deci
θ1≻{1,2}θ2.
• În cadrul coaliției {4,5}: θ21≥θ11 , θ22≥θ12 și θ21+θ22≤ 𝓋(4,5)=1, deci
θ2≻{4,5}θ1.
Deci relația de dominare a imputațiilor nu este tranzitivă .
Observația 1 . 7:
Fie S o coaliție și θ o repartiție . Dacă ∑θii∈S<𝑣(S), 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 ∑θii∈N=𝓋(N).
În plus , vom ține cont de relația de dominare a imputațiilor și vom considera drept soluții
optime imputațiile nedominate .
Se obține următoarea :
1 Boris Hâncu, Nicolae Prodan și Ludmila Novac Bazele teoriei jocurilor cooperatiste: Prelegeri ,
Centrul editorial poligrafic USM, Chișinău, 2005.
30
1Definiția 1 . 12:
Se numeste nucleul jocului multimea imputațiilor (alocă rile) sale cu proprietatile :
i) ∀ S⊂N,∑θii∈S≥𝓋(S)
ii) ∑θii∈N=𝓋(N)
Vom nota nucleul jocului cu 𝒞(𝓋).
Observația 1 . 8: 𝒞(𝓋) este o mulțime de imputații nedominate (nu vom demonstra însă acest
fapt) , deci nu există o repartiție a câștigului 𝓋(S) care să fie mai convenabilă simultan tuturor
jucătorilor în afară de repartițiile din nucleu .
Dacă o repartiție θ=(θ1,θ2,…,θn) satisface condițiile din definiția nucleului și este nevidă ,
atunci ea va fi acceptată drept soluție a jocului .
Pentru o mai bună înțelegere a jocurilor cooperative , să considerăm câteva exemple de jocuri
cooperative :
Exemple de jocuri cooperative :
2Exemplul 1 . 8: Jocul mânușii
Fie N={1,2,3} mulțimea jucătorilor ; jucătorii 1 ș i 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, 𝓋 ({1})=𝓋({2})=𝓋({3})=0,𝓋({1,2})=
0,𝓋({2,3})=𝓋({1,3})=𝓋(N)=10.
Exemplul 1 . 9: S⊂N, S≠∅; uS joc de unanimitate . Funcția caracteristică
uS={1,daca S⊂N
0,în caz contrar
1 Guillermo Owen Teoria jocurilor , Editura Tehnică, București, 1974.
2 Alparslan -Gok S. Z. https: //iam. metu. edu.
tr/system/files/iamData/LectureNotes/lecture_notes_on_cooperative_game. pdf [Online]. – Februarie
2, 2017.
31
Exemplul 1 . 10: S⊂N, S≠∅; uS∗ dualul jocului de unanimi tate din exemplul anterior . Funcția
caracteristică uS∗={1,daca S∩N≠∅
0,în caz contrar
Exemplul 1 . 11: Joc de cost
𝒸: 𝒫(N)→ ℝ,c(S) reprezintă cheltuielile care se fac dacă membrii coaliției S lucrează
impreună .
Exemplul 1 . 12: Doamna cu geantă
Doi jucători sunt necesari pentru a transporta un bagaj in schimbul a 20 lei ;
𝓋({i})=0,i∈N,𝓋({i,j})=20,pentru i≠j; 𝓋(N)=20.
Nucleul acestui joc este 𝒞(𝓋)=∅ deoarece :
x1+x2≥20
x1+x3≥20
x2+x3≥20}⇒x1+x2+x3≥30>𝓋 (N)
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 .
1Jocuri cooperative balansate
Definiția 1 . 13: Fie 𝓋 un joc cooperativ și N mulțimea sa de jucători . O mulțime de valori
𝓌(S),0≤𝓌(S)≤1,∀ S⊂N este o secvență balansată (sau mulțime de valori balansată) dacă
pentru orice i∈N avem :
∑𝓌(S)
S,i∈S= 1
Putem gândi aceste valori drept fracțiuni de timp pe care fiecare jucător le dedică implicării în
coaliția din care face parte .
1 http: //www. econ. ohio -state. edu/jpeck/gametheory/gameL10. pdf [Interactiv]. – 3 Mai 2017.
32
Definiția 1 . 14 : Fie 𝓋 un joc cooperativ și N mulțimea sa de jucători . Spunem că 𝓋 este un joc
balansat dacă și numai dacă pentru orice mulțime de valori balansate 𝓌 avem :
∑𝓌(S)
∅≠S⊂N𝓋(S)≤𝓋(N)
Într-un joc balansat , orice mod de „împărțire a timpului” fezabil pentru coaliții diferite este
fezab il de asemenea pentru coaliția „ mare” .
1, 4Interpretare pentru jocul balansat : Un joc este balansat dacă nu exis tă o alocare a t impului
printre coaliții care să genereze o valoare a jocului mai mare decât val oarea jocului obținută prin
cooperarea tuturor jucătorilor , deci a marii coaliții .
2Exemplu l 1. 13: Secvențe bal ansate pentru jocul majorității
Fie un joc cooperativ cu funcția caracteristică 𝓋(S)={1,dacă |S|≥2
0,dacă |S|≤1 și N={1,2,3}
mulțimea jucătorilor . Fie F matricea jocului ; liniile matricei F sunt indexate după numărul de
jucători iar coloanele după coalițiile care se pot forma . Fiecarărei coloane i se asociază un
element din secvența balansată 𝓌.
Tabelul 10
1 Boris Hâncu, Nicolae Prodan și Ludmila Novac Bazele teoriei jocurilor cooperatiste: Prelegeri ,
Centrul editorial poligrafic USM, Chișinău , 2005.
2Bruno Codenotti http: //wwwold. iit. cnr. it/staff/bruno. codenotti/lecture5p. pdf [Online]. – Aprilie
10, 2017
4 Mihai Manea https: //ocw. mit. edu/courses/economics/14 -126-game -theory -spring -2016/lecture –
notes/MIT14_126S16_cooperative. pdf [Online]. – Iunie 20, 2017
Coaliții
Jucători {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}
1 1 0 0 1 1 0 1
2 0 1 0 1 0 1 1
3 0 0 1 0 1 1 1
𝓌{1} 𝓌{2} 𝓌{3} 𝓌{1,2} 𝓌{1,3} 𝓌{2,3} 𝓌{1,2,3}
33
1 Elementul (i,j) al matricei F este egal cu 1 dacă jucătorul i aparține coaliției indexate după j
și 0 în caz contrar . Pentru ca o secvență să fie balansată , trebuie să avem :
∑fijj𝓌j=1, pentru orice i∈{1,2,3}.
Evident că secvența (0,0,0,1
2,1
2,1
2,0) este balansată , fiecare jucător (reprezentat de unul din
rândurile matricei) este implicat cu exact două elemente nenule ale secvenței , deci pe fiecare
rând se obține 1
2+1
2=1. Pe de altă parte ,
𝓌{1,2}+𝓌{1,3}+𝓌{2,3}=3
2> 𝓋(N), deci jocul in ansamblu nu este balansat .
Putem enunța acum teorema ca re caracterizea ză nucleul nevid (a cărei demonstrație o vom
prezenta la sfârșitul capitolului al II -lea)
Teoremă (Bondareva -Shapley) : Jocul cooperativ 𝓋 are nucleul nevid dacă și numai dacă este
balansat .
1 Bruno Codenotti http: //wwwold. iit. cnr. it/staff/bruno. codenotti/lecture5p. pdf [Online]. – Aprilie
10, 2017
34
35
Capit olul II: Dualitate în programarea liniară
Problema duală
1În această secțiune ne propunem să studiem problema duală în programarea liniară .
Avem însă nevoie de existența altei probleme de programare liniară , anume problema primală ,
care ne asigură existența problemei duale . În cele ce urmează , ne propunem să prezentăm
problemele primală și duală și să studiem legătura dintre cele două probleme .
Problema generală a programării liniare
{ min(max)(c1x1+c2x2+⋯+cnxn)
a11x1+a12x2+⋯+a1nxn≥b1
…
aq1x1+aq2x2+⋯+aqnxn≥bq
aq+1,1×1+aq+1,2×2+⋯+aq+1,nxn=bq+1
…
ar1x1+ar2x2+⋯+arnxn=br
ar+1,1×1+ar+1,2×2+⋯+ar+1,nxn≤br+1
…
am1x1+am2x2+⋯+amnxn≤bm
x1,x2,…,xk≥0; x1,xk+1,…,xp≤0; xp+1,xp+2,…,xn liberi de semn
Aceasta are următoarele componente :
➢ Funcția c1x1+c2x2+⋯+cnxn care se numește funcție obiectiv , unde x1,x2,..,xn
sunt variabilele funcției obiectiv iar c1,c2,…,cn sunt coeficienții funcției obiectiv .
➢ Expresiile de tipul aq1x1+aq2x2+⋯+aqnxn≥,≤,=bq care se numesc restricții .
➢ Condiții asupra variabilelor (ca de exemplu : x1,x2,…,xk≥,≤0 );
➢ Termenii liberi ai restricțiilor , anume b1,b2,…,bm;
Se disting mai multe tipuri de restricții :
• Restricție concordantă în următoarele două situații :
o aq1x1+aq2x2+⋯+aqnxn≥bq într-o problemă de minim
1 Dorin Mitruț și Eugen Țigănescu http: //asecib. ase. ro/Mitrut%20Dorin/Curs/bazeCO/html/24DUALA.
htm [Interactiv] // http: //asecib. ase. ro/cursuri_online. htm. – 5 Mai 2017.
36
o aq1x1+aq2x2+⋯+aqnxn≤bq într-o problemă de maxim
• Restricție neconcordantă în următoarele două situații :
o aq1x1+aq2x2+⋯+aqnxn≥bq într-o problemă de maxim
o aq1x1+aq2x2+⋯+aqnxn≤bq într-o problemă de minim
• Restricție de tip egalitate :
aq1x1+aq2x2+⋯+aqnxn=bq
1În funcție de tipul restricțiilor , distingem :
1) Problemă de programare liniară în formă standard :
Dacă o problemă de programare liniară are toate restricțiile de tip egalitate și toate variabilele
pozitive , o vom numi problemă de programare liniară în formă standard .
Un astfel de program arată în felul următor :
{min(max)ctx
Ax=b
x≥0
Unde ct=(c1,c2,…,cn),A=(a11⋯a1n
⋮⋱⋮
am1⋯amn),b=(b1
…
bm),x=(x1
…
xn).
2) Problemă de programare liniară în formă canonică
Dacă o problemă de programare liniară are una din expresiile următoare
a. {minctx
Ax≥b
x≥0 sau b . {maxctx
Ax≤b
x≥0
Atunci vom spune că problema este în formă canonică .
Observația 1 . 9: Orice problemă de programare liniară poate fi adusă în forma canonică sau
forma standard printr -o serie de transformări :
1 Dorin Mitruț și Eugen Țigănescu http: //asecib. ase. ro/Mitrut%20Dorin/Curs/bazeCO/html/24DUALA.
htm [Interactiv] // http: //asecib. ase. ro/cursuri_online. htm. – 5 Mai 2017.
37
• Dintr -un program de minimizare putem obține un program de maximizare (și
invers) folosind următoarele relații : minf(x)=−(max(−f(x)) și
maxf(x)=−(min(−f(x)).
• Sensul unei inegalități se schimbă prin înmulțirea cu -1;
• Fie o restricție de forma aq1x1+aq2x2+⋯+aqnxn≤bq(1); putem obține
o res tricție egalitate prin adunarea unei variabile ecart yp≥0 la (1):
obținem aq1x1+aq2x2+⋯+aqnxn+yp=bq.
• 1Fie o restricție de forma aq1x1+aq2x2+⋯+aqnxn≥bq(2); putem obține
o restricție egalitate prin scăderea unei variabile ecart yp≥0 la (2):
obținem aq1x1+aq2x2+⋯+aqnxn+yp=bq.
• Dintr-o restricție egalitate aq1x1+aq2x2+⋯+aqnxn+yp=bq (deci o
ecuație) se pot obține două inecuații : aq1x1+aq2x2+⋯+aqnxn≥bq și
aq1x1+aq2x2+⋯+aqnxn≤bq.
• O variabilă pozitivă x1≥0 se transformă într -o variabilă negativă x11 prin
înmulțirea cu -1 (și invers) .
• Fie x2 o variabilă oarecare poate fi înlocuită cu diferența a două variabile
pozitive x12 și x22, deci x2=x12−x22.
Definiția 1 . 15:
Fie o problemă de programare liniară . Spunem că un vector x=(x1,…,xn)T este soluție de
bază a sa dacă x verifică sistemul Ax=b și coloanele matricei A corespunzătoare elementelor
nenule ale lui x sunt liniar independente .
Definiția 1 . 16:
Fie o problemă de programare liniară . Spunem că un vector x=(x1,…,xn)T este soluție de
admisibilă a sa dacă x verifică sistemul Ax=b și are toate componentele pozitive .
Definiția 1 . 17:
Fie o problemă de programare liniară și x=(x1,…,xn)T soluție de de bază și admisibilă a sa.
Spunem că x este soluție nedegenerată dacă are toate componentele nenule și degenerată dacă
are cel puțin o componentă nulă .
1 Dorin Mitruț și Eugen Țigănescu http: //asecib. ase. ro/Mitrut%20Dor in/Curs/bazeCO/html/24DUALA.
htm [Interactiv] // http: //asecib. ase. ro/cursuri_online. htm. – 5 Mai 2017.
38
Definiția 1 . 18:
Fie o problemă de programare liniară și A matricea coeficienților restricțiilor . O matrice
pătratică nesingulară format din coloane ale matricei A se numește bază iar componentele
vectorului x=(x1,…,xn)T corespunzătoare coloanelor bazei se numesc variabile de bază .
O matrice de bază formată din coloane a lui A o vom nota cu B și cu xB vom nota vectorul
coloană al variabilelor de bază .
Problema duală
Definiția 1 . 19:
1 Fie următoarea problemă de programare liniară în formă generală :
(P)
{ min(c1x1+c2x2+c3x3)
a11x1+a12x2+a13x3≥b1
a21x1+a22x2+a23x3=b2
a31x1+a32x2+a33x3≤b3
x1≥0,×2≤0,×3 arbitrar
Se numește problema duală a problemei (P) (pe care o vom nota cu (D)) :
(D)
{ max(b1u1+b2u2+b3u3)
a11u1+a21u2+a31u3≤c1
a12u1+a22u2+a32u3≥c2
a13u1+a23u2+a33u3=c3
u1≥0,u2arbitrar,u3≤0
Observația 1 . 10:
2 Problema duală a lui (D) este problema primală (P) .
Ne propu nem să construim problema duală . Aceasta se obține astfel :
1 Dorin Mitruț și Eugen Țigănescu http: //asecib. ase. ro/Mitrut%20Dorin/Curs/bazeCO/html/24DUALA.
htm [Interactiv] // http: //asecib. ase. ro/cursuri_online. htm. – 5 Mai 2017.
2 Cătălin Ioan Angelo Matematică Aplicată în Economie, Editura Universitară Danubius, Galați, 2011
39
Mai întâi , introducem următorul set de notații :
Cu uT notăm vectorul variabilelor problemei duale ;
Cu cDT notăm vectorul coeficienților funcției obiectiv ai problemei duale ;
Cu bDT notăm vectorul termenilor liberi ai restricțiilor din problema duală ;
Cu AD notăm matricea coeficienților combinațiilor liniare din restricțiile
problemei duale ;
1Suntem acum pregătiți să descriem modul de obținere a l problemei duale :
▪ 2Dacă problema primală este de minim , atunci duala va fi de maxim și i nvers ;
▪ Termenii liberi ai restricțiilor problemei primale devin coeficienții funcției obiectiv ai
dualei (adică cDT= bT);
▪ Coeficienții funcției obiectiv ai problemei primale devin termeni liberi ai restricțiilor
dualei (a dică cT= bDT)
▪ Transpusa matricei coeficienților din problema primală devine matricea coeficienților din
problema duală (adică AD = AT);
▪ Variabilele problemei duale ce corespund restricțiilor concordante în problema primală
sunt pozitive (adică ui 0 dacă restricția aferentă din primală este concordant ă)
▪ Variabilele problemei duale ce corespund restricțiilor neconcordante în problema primală
sunt negative (adică ui 0 dacă restricția aferentă din primală este neconcordant ă);
▪ Variabilele problemei duale ce corespund restricțiilor de tip egalitate în problema primală
sunt arbitrare (adică variabila ui este oarecare dacă restricția aferentă din primală este de
tip egalitate ;
▪ Variabilelor pozitive din primal ă le corespund rest ricții concordante în duală ;
▪ Variabilelor negative din primală le corespund restricții neconcordante în duală ;
▪ Variabilelor arbitrare din primală le corespund restricții de tip egalitate în duală ;
Pentru o mai bună înțelegere a modului în care se formează problema duală , să considerăm
următorul exemplu :
Exemplu :
Vom construi duala problemei următoare :
1 Cătălin Ioan Angelo Matematică Aplicată în Economie, Editura Universitară Danubius, Galați, 2011
2 Dorin Mitruț și Eugen Țigănescu http: //asecib. ase. ro/Mitrut%20Dorin/Curs/bazeCO/html/24DUALA.
htm [Interactiv] // http: //asecib. ase. ro/cursuri_ online. htm. – 5 Mai 2017.
40
(max ) f = 2x 1 – 5×2 + 4x 3
{ x1 –x2 + 4×3 7
x2 –5×1 + 3×3=6
x1 + 2×3≤ 3
−x3+2×1 − 5×2 8
x1 0,×2 oarecare ,x3 0
Conform regulilor de mai sus , avem :
❖ Cum primala este o problemă de maxim , duala este de minim ;
❖ Variabilele dualei sunt :
1u1 corespunde restricției : x1 – x2 + 4x 3 7
u2 corespunde restricției : x2 – 5×1 + 3x 3 = 6
u3 corespunde restricției : x1 + 2x 3 3
u4 corespunde restricției : –x3 + 2x 1 – 5×2 8
❖ Funcția obiectiv a dualei va fi produsul scalar dintre vectorii bT și uT (adică dintre
vectorul termenilor liberi ai restricțiilor primalei cu vectorul variabilelor corespunzătoare
din duală) ; obținem astfel funcția obiectiv g = 7u 1 + 6u 2 + 3u 3 + 8u 4
❖ Restricțiile dualei , în număr de 3 (numărul de variabile ale primalei) , se obțin astfel :
Restricția 1 (corespunzătoare variabilei x 1):
▪ Să notăm cu a1T=(1,1,1,−1) vectorul coeficienților variabilei x1 din cele 4
restricții ale problemei primal e. Termenul stâng al restricției se obține efectuând
produsul scalar dintre vectorii a1T și uT (adică produsul scalar dintre vectorul
coeficienților variabilei x 1 din cele 4 restricții ale primalei cu vectorul variabilelor
corespunzătoare acestora din duală) . Obținem :
u1 –5u2 + u 3 + 2u 4
▪ Termenul liber al restricției este coeficientul lui x 1 din fu ncția obiectiv a
problemei primale , deci c1 = 2
▪ Restricția este neconcordantă deoarece variabila ce corespunde acestei restricții , x1, este
negativă .
Prin urmare , prima restricție este u1 –5u2 + u 3 + 2u 4 2
Restricția 2 (corespunzătoare variabilei x 2):
1 Dorin Mitruț și Eugen Țigănescu http: //asecib. ase. ro/Mitrut%20Dorin/Curs/bazeCO/html/24DUALA.
htm [Interactiv] // http: //asecib. ase. ro/cursuri_online. htm. – 5 Mai 2017.
41
▪ Să notăm cu a2T=(−1,1,0,−5) vectorul coeficienților variabilei x2 din cele 4
restricții ale problemei primale . Termenul stâng al restricției se obține
efectuând produsul scalar dintre vectorii a2T și uT (adică produsul scalar dintre
vectorul coeficienților variabilei x 2 din cele 4 restricții ale primalei cu
vectorul variabilelor corespunzătoare acestora din duală) . Obținem :
-u1 + u 2 – 5u4
▪ Termenul liber al restricției este coeficientul lui x 2 din funcția obiectiv a primalei ,
adică c 2 = -5
▪ Restricția va fi egalitate pentru că variabila ce corespunde acestei restricții , x2,
este arbitrară .
1Prin urmare , cea de -a doua restricție va fi: -u1 + u 2 – 5u4 = -5
Restricția 3 (corespunzătoare variabilei x 3):
▪ Să notăm cu a3T=(4,3,2,−1) vectorul coeficienților variabilei x3 din cele 4 restricții ale
problemei primale . Termenul stâng al restricției se obține efectuând produsul scalar
dintre vectorii a3T și uT (adică produsul scalar dintre vectorul coeficienților variabilei x 3
din cele 4 restricții ale primalei cu vectorul variabilelor corespunzătoare acestora din
duală) . Obținem :
4u1 +3u 2 + 2u 3 – u4
▪ Termenul liber al restricției este coeficientul lui x 3 din fiuncția obiectiv a
primalei , adică c 3 = 4
▪ Restricția va fi concordantă deoarece variabila corespunzătoare acestei restricții , x3,
este pozitivă .
Prin urmare , a treia restricție va fi : 4u1 + 3u 2 + 2u 3 – u4 4
Determinăm restricțiile asupra variabilelor dualei :
▪ u1 0, pentru că restricția asociată este neconcordantă ;
▪ u2 arbitrară , pentru că restricția asociată este egalitate ;
▪ u3 0, pentru că restricția asociată este concordantă ;
▪ u4 0, pentru că restricția asociată este neconcordantă .
1 Dorin Mitruț și Eugen Țigănescu http: //asecib. ase. ro/Mitrut%20Dorin/Curs/bazeCO/html/24DUALA.
htm [Interactiv] // http: //asecib. ase. ro/cursuri_online. htm. – 5 Mai 2017.
42
Prin urmare , problema duală este :
(min) g = 7u 1 + 6u 2 + 3u 3 + 8u 4
{ u1 –5u2 + u3+2u4≤2
−u1+u2 − 5u4=−5
4u1 + 3u2+2u3−u4 4
u1 0,u2 oarecare,u3 0,u4 0
1În cele ce urmează , vom prezenta câteva rezultate menite să ilustreze legătura dintre
problemele primal ă și duală :
Lema 1: Fie o problemă primală (P) și duala sa (D) . Atunci d uala problemei duale (D)
este problema primală (P) .
Lema 2 :
Fie ( P1) și (P2) două probleme de programare liniară echivalente . Atunci și dualele lor (D1) și
(D2) sunt echivalente , unde p rin probleme echivalente înțelegem două probleme de programare
liniară care se pot obține una din cealalt ă prin transformări elementare . Transformările
elementare realizează un izomorfism între mulțimile soluțiilor celor două probleme și un
homeomorfism în tre funcțiile lor obiectiv .
Teorema fundamentală a dualității .
Fie cuplul de probleme primală -duală . Atunci una și numai una din afirmațiile următoare este
adevărată :
a) Una din cele două probleme are soluție optimă finită atunci și cealaltă are soluție
optimă finite . În acest caz , valorile funcțiilor obiectiv corespunzătoare celor două
soluții sunt egale ;
b) Una din cele două probleme are soluție , iar cealaltă nu are . Atunci problema care
admite soluție are optim infinit .
c) Una din cele două probleme nu are soluții admisibile ; în acest caz , cealaltă are
optim infinit sau nu are soluții admisibile .
Demonstrație :
Vom presupune cele două probleme în forma canonică :
1 Dorin Mitruț și Eugen Țigănescu http: //asecib. ase. ro/Mi trut%20Dorin/Curs/bazeCO/html/24DUALA. htm
[Interactiv] // http: //asecib. ase. ro/cursuri_online. htm. – 5 Mai 2017.
43
problema primală , (P) {(max) cTx
Ax b
x 0
și duala (D) : {(min) bTu
ATu c
u 0
1Observația 1 . 11:
Presupunerea făcută nu influențează rezultatul , pentru că , dacă problemele nu ar fi fost
aduse la forma canonică , se puteau obține probleme în formă canonică echivalente cu cele
inițiale utilizând transformările prezentate în paragraful
Pentru a continua demonstrația Teoremei fundamentale a dualității , vom demonstra o
lemă ajutătoare :
Lema 3 .
Fie cuplul de probleme primal ă-duală . Dacă există soluții admisibile pentru fiecare
problemă din acest cuplu , atunci pentru orice x soluție admisibilă a primalei și orice u s oluție
admisibilă a dualei are loc inegalitatea :
cTx bTu
Demonstrație :
Avem :
ATu c (ATu)T cT uTA cT
1xc Axu
0xcAuT TT T
De asemenea , obținem :
2ubbu Axu0 u 0ub AxT T T
T
Astfel , din ambele relații , obținem :
q.e.d.xcub xc Axuub21T T T T T
1 Dorin Mitruț și Eugen Țigănescu http: //asecib. ase. ro/Mitrut%20Dorin/Curs/bazeCO/html/24DUALA. htm
[Interactiv] // http: //asecib. ase. ro/cursuri_online. htm. – 5 Mai 2017.
44
Vom presupune în continuare că am rezolvat una din tre cele două probleme , aceasta
fiind considerată problema primală . Sunt posibile următoarele situații :
a)Problema are optim finit
1 Mai întâi , vom presupune că lucrăm cu primala sub formă standard . Considerăm xB o soluție
de bază a primalei , deci care oferă optimul problemei , adică cTxB=
xc maxT
adm isibilax . Cum toate
valorile j corespunzătoare acestei baze sunt nenegative și ținând seama de expresia lui j,
obținem :
cBTB-1A cTAT(cBTB-1)T c
Astfel obținem că vectorul u* = (cBTB-1)T este o soluție admisibilă de ba ză a problemei duale .
Din lema 3, avem că cTxB uTb pentru orice soluți e admisibilă a problemei duale .
Deoarece cTxB = cTB-1b = (u*)Tb, avem că pentru orice soluție admisibil ă a problemei duale are
loc inegalitatea :
(u*)Tb uTb
Astfel obținem că u* este soluția optimă a dualei și că f(xB) = g(u*).
b)Problema are optim infinit
Să presupunem că duala ar avea soluții admisibile u , atunci g(u) ar fi un majorant al mulțimii
D∶={f(x)/ x admisibilă }, contradicție cu ipoteza de optim infinit .
c)Problema nu are soluții
Presupunem că duala ar avea optim finit. Atunci , din a) , obținem că primala are optim finit , ceea
ce contrazice cu ipoteza .
Deoarece am analizat toate situațiile posibile și ținând seama de faptul că nu a contat
problema aleasă spre rezolvare , teorema este demonstrată .
Suntem a cum în măsură să prezentăm demontrația Teoremei Bondareva -Shapley :
Demonstrație (Bondareva -Shapley) :
1 Dorin Mitruț și Eugen Țigănescu http: //asecib. ase. ro/Mitrut%20Dorin/Curs/bazeCO/html/24DUALA. htm
[Interactiv] // http: //asecib. ase. ro/cursuri_online. htm. – 5 Mai 2017.
45
1Necesitatea : Fie următorul program liniar :
2
{ min(∑xi
i∈N)
∑xi
i∈N≥𝓋(S),∀S⊂N
Să considerăm dualul programului de mai sus :
{
max(∑𝓌(S)𝓋(S)
S∈2N)
𝓌(S)≥0
∑𝓌(S)
i∈S≤1,∀S⊂N,∀ i∈N
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 𝓋(N). Deoarece programul primal are soluție , atunci ,
conform teoremelor de dualitate , obținem că ambele pr obleme au aceeași soluție și valorile
optime ale funcțiilor obiectiv sunt egale .
Suficiența :
Fie x un vector din nucleu și colecția balansată de valori (𝓌(S))S∈2N. Atunci :
∑𝓌(S)𝓋(S) {S,S⊂N} ≤∑𝓌(S)xS {S,S⊂N} =∑xii∈N∑𝓌(S)i∈S=∑xii∈N=𝓋(N),unde xS=
∑xii∈S , deci jocul este balansat .
1 Mihai Manea https: //ocw. mit. edu/courses/economics/14 -126-game -theory -spring -2016/lecture –
notes/MIT14_126S16_cooperative. pdf [Online]. – Iunie 20, 2017.
2 Mihai Manea https: //ocw. mit. edu/courses/economics/14 -126-game -theory -spring -2016/lecture –
notes/MIT14_126S16_cooperative. pdf [Online]. – Iunie 20, 2017.
46
III: Aplicații ale teoremelor de dualitate teoriei jocurilor în jocurile de
producție liniară
47
În cele ce urmează , vom prezenta câteva rezultate ce fac uz de teoria jocurilor și de dualitatea
din programarea liniară .
1 Considerăm un joc de producție liniară de următorul tip : fiecare din cei n jucători primește un
vector bi=(b i1, . . . bim) de resure . Resurele în sine nu au un preț anume , adică nu există o
cerință primară pentru ele . Dar totuși există următoarea cerință pentru acestea : ele pot fi
folosite pentru a produce bunuri care se pot vinde la un preț dat .
Lucrăm în ipoteza că modelul de producție este liniar și că o unitate al celui de -al j-lea bun
necesită a kj unități din cea de -a k resursă și că poate fi vândută la prețul c j.
Fie S o submulțime a mulțimii N={1 , 2, . . . n}. Această submulțime va avea un total de
bk(S)=∑bki
i∈S
unități din resursa k . Folosind toate resursele , membrii lui S pot produce orice vector de bunuri
(x1, . . , xp) de bunuri ce satisface următoarele condiții :
{ a11x1+a12x2+⋯+a1pxp≤b1(S)
a21x1+a22x2+⋯+a2pxp≤b2(S) (2)
…………………………………………..
am1x1+am2x2+⋯+ampxp≤bm(S)
x1,x2,…,xp≥0 (3)
Dacă doresc maximizarea resurselor , ei vor căuta deci un x care să maximizeze prețul total al
acestor bunuri . Prin urmare , profitul lor maxim este 𝓋(S)=max(c1x1+. . . +cpxp) (4)
( depinzând de restricțiile ( 2) –(3) )
Funcția 𝓋 poate fi acum gândită drept funcția caracteristică a unui joc de n persoane . Ar
trebui , firește , să demonstrăm că această funcție este supra aditivă , deci că reprezintă un joc
netrivial . De fapt , se poate arăta mai mult , anume că este funcția caracteristi că a unui joc
balansat .
1 Guillermo Owen On the core of linear production games , Mathematical Programm ing 9 (1975) ,358-
370
48
Să demonstrăm următoarea :
Teorema 1 . Jocul dat de condițiile (2) -(4 ) este balansat .
Demonstrație . Fie B o coaliție balansată , cu ponderi 𝛾𝑆. Pentru orice k , k=1, . . , m, avem :
∑γS(S)bk(S)=
S∈B∑∑
i∈SγSbki
S∈B=∑{∑γS
S∈B
i∈S}
i∈Nbki=∑bki
i∈N=bk(N)
1Acum , din (4)
𝓋(S)=c1x1(S)+. . . + cpxp(S)
unde x(S)=( x1(S), . . . , xp(S)) este un vector care depinde de S și care satisface condițiile (2)-
(3). Atunci
∑γS(S)𝓋(S)=
S∈B∑{γS∑cjxj(S)p
j=1}=
S∈B∑cj{∑γSxj(S)
S∈B}p
j=1=∑cjxĵp
j=1
unde 𝑥̂ este vectorul definit de xĵ=∑γSxj(S) S∈B .
Se vede ușor că ∑akj(∑γSxj(S) S∈B) j ≤∑γSxj(S) S∈B . Prin urmare ,
∑akj
jxĵ≤bk(N)
Evident , xĵ≥0 pentru că xj(S)≥0 și γS≥0. Atunci vectorul x̂ satisface condițiile (2) -(3)
pentru S=N și deci este necesar să avem
1 Guillermo Owen On the core of linear production games , Mathematical Programming 9 (1975) ,358 –
370
49
𝓋(N)≥c1x1̂+c2x2̂+⋯cpxp̂
deoarece 𝓋(𝑁)este maximul acestor forme . Vedem deci că 𝓋 este un joc balansat . q. e. d.
Am demon strat că 𝓋 este balansat și deci are un nucleu nevid . Este, totuși , important să găsim
puncte în nucleu . Pentru a face asta , considerăm programul dual -liniar (2)-(4):
{ min (b1(S)y1+b2(S)y2+⋯+bm(S)ym)
a11y1+a21y2+⋯+am1ym≥c1 (5)
a12y1+a22y2+⋯+am2ym≥c2 (6)
…………..…………………………………….
a1py1+a2py2+⋯+ampyp≥cp
y1,y2,…,ym≥0 (7)
1După cum este se ș tie deja, 𝓋(𝑆) va fi egal cu minimul program ului ( 5)-(7). Să observăm că
restricțiile (6) -(7) sunt independente de S ; vectorul soluțiilor va depinde însă de S .
În particular , fie (y1*, . . . ym*) vectorul soluțiilor pentru (5) -(7 ) unde S=N (marea submulțime) .
Atunci , firește ,
𝓋(N)=b1(N)y1 ∗+⋯+bm(N)ym ∗ (8)
În timp ce , pentru orice S ,
𝓋(S)≤b1(S)y1 ∗+⋯+bm(S)ym ∗(deoarece 𝓋(𝑆) este minimul p entru toți vectorii posibili
y)
Considerăm acum vectorul de plăți u= (u 1, . . . un) definit de ui=b1iy1 ∗+b2iy2 ∗+⋯+bmiym ∗
(10)
Pentru orice coaliție S , avem
1 Guillermo Owen On the core of linear production games , Mathematical Programming 9 (1975) ,358 –
370
50
∑ui=∑∑bkiyk ∗=m
k=1i∈Si∈S∑∑bkiyk ∗
i∈S=m
k=1b1(S)y1 ∗+⋯+bm(S)ym ∗
Și deci din (8) avem :
∑uii∈S= 𝓋(S)
Și din (9) :
∑uii∈S≥𝓋(S) (pentru orice S inclus în N) . În acest caz , u este o imputație a nucleului .
Deținem deci o metodă de a obține un punct din nucleu : calculăm vectorul y* prin rezolvarea
unui program liniar de dimensiuni rezonabile (m variabile și p condiții) : aceasta dă o imputație
u din (10) .
Euristic vorbind , componentele y i* pot fi gân dite ca prețuri de echilibru pentru m resurse .
Fiecare jucător este atunci plătit pentru resursele lui conform prețului de echilibru y* ; plațile
rezultante vor da mereu un vector cu valori în nucleu .
Observăm că orice vector de prețuri balansate y* formează un punct în nucleu (poate exista
mai mult de un vector de echilibru și deci mai mult de un punct în nucleu . ) Ne punem problema
dacă reciproca este adevărată , adică dacă toate punctele din nucleu se pot obține astfel .
1Se poate arăta, considerând un tip special de programare liniară – o problemă de distribuire – în
care bunurile produse sunt schimburi . În ac est caz , toate punctele din nucleu se pot obține prin
rezolvarea problemei duale – de fapt , restricțiile programului dual se re duc la inegalități dar
acesta este strict din cauza faptului că este un tip special de program . Pentru jocuri ceva mai
generale această conjectură nu e adevărată .
Ca un contraexemplu trivial , să considerăm un joc de două persoane cu resurse
b1=(1, 0) b2=(0, 2) și un singur produs finit , din care o unitate costă o unitate din fiecare resursă
și care se vinde cu un dolar . Atunci programul (2)-(4 ) ia forma
{𝓋(S)=maxx
x≤b1(S)
x≤b2(S)
x ≥0
ceea ce ne dă 𝓋(1)= 𝓋(2)=0 , (𝓋{1, 2})=1 . Nucleul constă aici din to ate punctele (u 1, u2) cu
0≤u 1≤1, u1+u2=1.
Dacă S=N , avem b(N)=(1 , 2). Atunci programul dual (5)-(7 ) ia forma
1 Guillermo Owen On the core of linear production games , Mathematical Programming 9 (1975) ,358 –
370
51
{min(y1+2y2)
y1+y2≥1
y1,y2≥0
Acesta are soluția unică y 1*=1, y2*=0. Atunci prețul de echilibru nu dă nimic pentru a doua
resursă ; deoarece jucătorul doi începe doar cu această resursă , nu poate obține nimic din această
schemă . Atunci doar plata u=(1 , 0) se poate obți ne în acest mod , în timp ce nucleul poate
conține și alte puncte .
Să presupunem acum că jocul este crescut p rin replicare de r ori , adică acum avem r jucători
cu resursele inițiale (bi1, bi2 , . . . , bmi ).
Efectul va fi multiplicarea resurselor inițiale cu factorul r . Deci , dacă N este mulțimea
originală de n jucători , și rN este noua mu lțime de jucători , vom avea
bk(rN)=rb k(N)
și în consecință
𝓋(rN)=r 𝓋(N),
1deoarece vectorul de maximizare x care definește 𝓋(rN) este evident vecto rul de maximizare
care definea 𝓋(N) înmulțit cu r .
Vom spune că doi jucători sunt de același tip dacă au aceleași resurse inițiale .
Atunci avem :
Teorema 2 . Dacă r≥2 , doi jucători de același tip vor primi plăți eg ale în orice imputație a
nucleului .
Demonstrație :
Mulțimea rN este reuniunea a r mulțimi disjuncte , N’, N’’, . . . N(r), fiecare fiind o copie a
mulțimii inițiale N . Dacă u este o imputație oarecare a nucleului , atunci u(N(t))≥ 𝓋 (N), pentru
orice t de la 1 la r .
Atunc i u(r N)=∑u(N(t))=r𝓋(N)m
t=1
Și deci u(N(t))= 𝓋 (N) , pentru orice t de la 1 la r . Atunci orice copie a mulțimii orig inale
primește exact cantitatea 𝓋(N) . Totuși , dacă S este o replică a lui N , și i este înlocuit de un
jucător de același tip i” , atunci S -{i}∪ {i”} este o copie a lui N . Atunci S și S -{i}∪ {i”} trebuie
1 Guillermo Owen On the core of linear production games , Mathematical Programming 9 (1975) ,358 –
370
52
să primească aceeași cantitate și deci u i=ui”. Acest lucru este adevărat pentru orice jucători de
același fel . q. e. d.
Deoarece nucleul dă plăți egale pentru toți jucătorii de același tip , reiese că putem reprezenta
orice imputare asupra nucleului printr -un vector u=(u 1, . . . , un) unde se înțelege că toți jucă torii
de tip i primesc cantitatea u i.
Trebuie să observăm că (u1, . . . , un) nu apare explicit în nucleul jocului de replicare . De fapt ,
u este proiecția în n-spațiu a unei imputări în nucleu . Punctul din nucleu este de fapt (u1, . . . ,
un; u1, . . . , un; . . . u1, . . . , un). Vom spune totuși că (u 1, . . . , un) este punctul din nucleu
printr -un abuz de limbaj – acest lucru ne va permite să discutăm convergența nucleului .
Următoarea teore mă tratează convergența nucleului . Mai exact , spune că dacă r tinde la infinit ,
nucleul converge la mulțimea plăților echilibrate .
Teorema 3: Dacă u= (u1, . . . , un) este în nucleul unui joc replicat de r ori , atunci u este
obținut dint r-un vector de prețuri balansat y*.
Demonstrație :
1 Fie (u 1, . . . , un) o imputație . Considerăm sistemul
{ a11y1+a21y2+⋯+am1ym≥c1
………………………………………….. (11)
a1py1+a2py2+⋯+ampyp≥cp
b11y1+b21y2+⋯+bm1ym≤u1
…………………………………………. (12)
b1ny1+b2ny2+⋯+bmnym≤un
y1,y2,…,ym≥0 (13)
Să presupunem că acest sistem are o soluție y* . Adunând inegalitățile (12) , avem că
b1(N)y1∗+b2(N)y2∗+⋯+b1(N)y1∗≤ 𝓋(N) (14)
Dar din (5) -(7) avem că 𝓋(𝑁) este valoarea minimă a membrului stâng din relația (14) ,
relativ la restricțiile (12) și (13) . Atunci , y* este un vector de minimizare , adică un vector
balansat de prețuri .
1 Guillermo Owen On the core of linear production games , Mathematical Programming 9 (1975) ,358 –
370
53
Să presupunem acum că acest sistem nu are nicio soluție . Sistemul poate fi gândit ca un
program liniar cu funcția trivială obiectiv 0 care trebuie să fie minimizată . Programul dual este
este următorul :
(funcția obiectiv de maximizat) : c1x1+⋯+ cpxp− u1z1−⋯− unzn (15)
Relativ la sistemul de restricții :
{a11x1+a12x2+⋯+a1pxp−b11 z1−⋯−b1n zn≤0, (16)
am1x1+am2x2+⋯+ampxp−bm1 z1−⋯−bmn zn≤0
x1,…,xp,z1,…,zn≥0 (17)
Acest program este clar fezabil (vectorul 0 este fezabil) și , deoarece este dualul unui program
care nu este fezabil , trebuie să fie nemărg init. Atunci există vectorii (x 1, . . . , xp), (z1, . . . , zn)
astfel încât
1
{ c1x1+⋯+cpxp>u1z1+⋯+unzn
a11x1+a12x2+⋯+a1pxp≤b11 z1+⋯+b1n zn(18)
…………………………………………………………….
am1x1+am2x2+⋯+ampxp≤bm1 z1+⋯+bmn zn
xk,zi≥0 (20)(19)
Atunci z i poate fi ales ca fiind rațional ; înmulțirea lui x k și z i cu numitorii comuni va
transforma z i în întregi pozitivi . Considerăm , atunci , o coaliție S conținând z 1 jucători de tip 1 ,
z2 jucători de tip 2 și z n jucători de tip n .
Cantitatea de resurse totale ale lui S este dată de membrii drepți ai inegalităților 19 și deci 𝓋(𝑆)
trebuie să fie cel puțin egal cu membrul stâng al inegalității 18 . Dar imputația (u 1, . . . , un) dă
pentru S doar membrul drept al inegalității (18). Atunci , dacă r es te mai mare decât max (z1, . . .
zn) , u nu este în nucleul jocului r -replicat .
Teorema de mai sus este de fapt un r ezultat bine cunoscut ; garanteaz ă convergența limitei . Un
caz interesant este cel în care vectorul y* este unic .
Teorema 4 : Să presupunem că vectorul y* este unic . Atunci , pentru r suficient de mare ,
nucleul jocului r -replicat conține doar vectorul u dat de (10)
Demonstrație :
1 Guillermo Owen On the core of linear production games , Mathematical Programming 9 (1975) ,358 –
370
54
Să considerăm din nou programul (5)-(7) cu S=N . Cum acesta are soluția y* , știm că pentru
orice punct extrem y” al programului , funcția obie ctiv este strict mai mare ca 𝓋(𝑁). Cum
există un număr finit de astfel de puncte de extrem , știm că există ε≥0 pentru care , pentru orice
punct de extrem y” diferit de y* , avem
b1(N)y1′+⋯+bm(N)ym′≥𝓋(N)+ε
Fie r suficient de mare astfel încât să aibă loc :
(r−1)ε>𝓋(N)
și fie jocul replicat de r ori având mulțimea de jucători rN . Fie l un jucător oarecare și fie
coaliția S=rN -{l}. Are loc :
𝓋(S)=b1(S)y1+⋯+bm(S)ym
unde (y 1, . . . , ym) este vectorul de minimizare al programului (5) -(7) și deci un punct de extrem
al programului .
1Avem în continuare :
bk(S)≥(r−1)bk(N), și deci :
𝓋(S)≥(r−1)[b1(N)y1+⋯+bm(N)ym]
Vom presupune că y” diferit de y* . Atunci :
𝓋(S)≥(r−1)[𝓋(N)+ε]>(r−1)𝓋(N)+𝓋(N)=r𝓋(N)=𝓋(rN)
Totuși , avem că S este inc lus în N și deci că nu se poate c a 𝓋(S) să fie mai mare ca 𝓋(rN).
Deci , conchidem că y”=y* este vectorul minimal pentru programul cu S= N -{l}. Atunci :
𝓋(S)=b1(S)y1∗+⋯+bm(S)ym∗
și dacă u este orice imputație a nucleului ,
∑ui
S≥b1(S)y1∗+⋯+bm(S)ym∗
Totuși
∑ui
rN≥b1(rN)y1∗+⋯+bm(rN)ym∗
1 Guillermo Owen On the core of linear production games , Mathematical Programming 9 (1975) ,358 –
370
55
și deci , scăzând , obținem că :
ul≤b1ly1∗+⋯+bmlym∗
Prin urmare , niciunul dintre jucători nu poate primi mai mult decât cantitatea dată de (10) .
Dar, dacă oricare din ei ar primi mai puțin de cantitatea aferentă restricției (10) , atunci toți
jucătorii ar primi mai puțin de . Conchidem că fiecare jucător primește exact cantitatea dată de
(10).
Să observăm că, în cazul nedegenerat , putem gara nta convergența finită a nucleulu i, în timp
ce, în cazul degenerat , în care există mai mult de un vector de echilibru , putem gara nta do ar
convergența limitei . Mai precis , teorema 5 de mai sus se generalizează , pentru cazul degenerat ,
astfel : dacă r este suficient de mare , atunci pentru imputări în nucleu , plata oricărui jucător va
fi dată de (10) în concordanț ă cu un vector de prețuri y* . Problema este că jucători de tipuri
1diferite pot fi plătiți în conco rdanță cu vectori diferiți , deci nu există un echilibru care să
determine o plată dată . Următorul contraexem plu ilustrează acest fapt .
Exemplu
Considerăm un joc de producție cu două resurse și trei tipuri de jucători cu resursele inițiale
b1=(6, 1), b2=(4-√2, 4), b3=(√2, 5). Să presupunem că exită un s ingur produs , a cărui
producție costă câte o unitate din fiecare resursă și care se vinde pentru 2 dolari .
Atunci b(N)=(10 , 10) și problema duală (5)-(7) ia forma
𝓋(S)=min 10y 1+10y 2 raportat la y 1+y2 ≥2, y1, y2≥0. Echilibrul aici nu este unic ; de fapt , orice
vector
y1+y2 =2, y1, y2≥0 va rezolva programul . În particular , y1=y2=1 va rezolva programul cu
plățile u 1=7, u2=8-√2, u3=5+√2.
Considerăm , acum , plata
u(ε)=(7+ε1,8−√2+ε2,5+√2+ε3), unde prin εi vom înțelege numere mici care satisfac
ε1+ ε 2+ ε 3=0. Vom demonstra că pentru orice ε suficient de mic u(ε) va face parte din nucleu .
Să presupunem că S are z i jucători de tip 1 unde z i≤r. Atunci
1 Guillermo Owen On the core of linear production games , Mathematical Programming 9 (1975) ,358 –
370
56
b1(S)=6z1+(4−√2)z2+√2z3
b2(S)=z1+4z2+5z3
Deoarece orice unitate de produs se vinde cu doi dolari , avem că :
𝓋(S)=min{12z1+(8−2√2)z2+2√2z3
2z1+8z2+10z3
Cum 𝓋(S) este minimul acestor cantități , nu poate fi mai mare decât jumătate din suma lor , de
unde inegalitatea :
𝓋(S)≤7z1+(8−2√2)z2+(5+√2)z3 (21)
Cu egalitate dacă și numai dacă :
112z1+(8−2√2)z2+2√2z3=2z1+8z2+10z3
Sau : 10z1+2√2z2+(2√2−10)z3=0
Cum z i sunt întregi , acest lucru e poate întâmpla doar dacă z 2=z3 (deoarece asta va elimina
termenii iraționali) . Dacă z 2=z3, avem că 10z 1-10z 3=0
Atunci vom avea 𝓋(S) =20z 1 și, luând u(S) fiind plata totală a coaliției S ,
u(S)=(7+ε1)z1+(8−√2+ε2)z2+(5+√2+ε3)z3
Dar cu z 1=z2=z3, aceasta ia forma :
u(S)=20z1+(ε1+ε2+ε3)z1
Am lucrat însă în ipoteza că că ε 1+ ε2+ ε3=0, și deci u(S)=20z 1.
Atunci 𝓋 (S)≤ u (S).
Să presupunem acum că egalitatea nu are loc în (20) . Atunci avem
u(S)=(7+ε1)z1+(8−√2+ε2)z2+(5+√2+ε3)z3
1 Guillermo Owen On the core of linear production games , Mathematical Programming 9 (1975) ,358 –
370
57
u(S)= 𝓋(S)+δ+ε1z1+ε2z2+ε3z3
Alegem acum ε i care satisface :
|εi|<δ
3r (22)
Cum z i≤r, avem :
|ε1z1+ε2z2+ε3z3|<δ
3r(z1+z2+z3)≤δ
Și deci u(S)≤ 𝓋(S)
Așadar , indiferent cât de mare este r , vectorul u(ε) va fi în nucleu pentru orice ε care satisface
(22) cu ε 1+ ε 2+ ε 3=0. Dar asta dă o mulțime bidimensională de imputări ale nucleului . Cum
plățile balansate formează un set 1 -dimensional , este clar că funcția (10) nu poate da naștere
1unui set 2 -dimensional și conchidem că , pentru orice ε, nucleul n u va conține plăți
nebalansate . Altfel spus , convergența necesită un număr in finit de pași , spre deosebire de cazul
teoremei 5 .
Câteva remarci :
Este interesant faptul că demonstrațiile noastre folosesc metode de programare liniară (mai
ales, teoria dualități i) și că vectorii y* pot fi obținuți prin algoritmul simplex . (De observat că
teoria jocurilor balansate este o consecință a dualității) . Teorema 4 , pe de a ltă parte , este un
rezultat nou ; convergența finită a nucleului nu este întâlnită în genera l și, în cazul nostru ,
depinde de liniaritatea sistemului .
1 Guillermo Owen On the core of linear production games , Mathematical Programming 9 (1975) ,358 –
370
58
Bibliografie :
[1]Alparslan -Gok S . Z. https : //iam . metu . edu.
tr/system/files/iamData/LectureNotes/lecture_notes_on_cooperative_game . pdf [Online] . – Februarie
2, 2017 .
[2]Boris Hâncu , Nicolae Prodan și Ludmila Novac Bazele teoriei jocurilor cooperatiste : Prelegeri ,
Centrul editorial poligrafic USM , Chișinău, 2005 .
[3]Bruno Codenotti http : //wwwold . iit. cnr. it/staff/bruno . codenotti/lecture5p . pdf [Online] . – Aprilie
10, 2017 .
[4]Cătălin Ioan Angelo Matematică Aplicată în Economie , Editura Universitară Danubius , Galați, 2011
[5]Daniela Constantin Luminița http : //cse . uaic.
ro/_fisiere/Documentare/Suporturi_curs/III_Economie_politici_regionale . pdf [Interactiv] . – 26 Iunie
2017 .
[6]Dorin Mitruț și Eugen Țigănescu http : //asecib . ase.
ro/Mitrut%20Dorin/Curs/bazeCO/html/24DUALA . htm [Interactiv] // http : //asecib . ase.
ro/cursuri_online . htm. – 5 Mai 2017 .
[7]Dragomira Baz and Sorin Dragoș Baz http : //www . biblioteca -digitala . ase. ro/biblioteca/pagina2 .
asp?id=cap4 [Online] // http : //www . biblioteca -digitala . ase. ro/biblioteca/carte2 . asp?id=261&idb= . –
Iunie 14 , 2017 .
[8]Guillermo Owen On the core of linear production games , Mathematical Progr amming. 9 (1975) 358 –
370
[9]Guillermo Owen Teoria jocurilor , Editura Tehnică , București 1974 .
[10]http : //www . econ . ohio -state . edu/jpeck/gametheory/gameL10 . pdf [Online] . – Mai 3 , 2017 .
[11]https : //www . academia .
edu/31298488/CERCET%C4%82RI_OPERA%C5%A2IONALE_%C5%9EI_TEORIA_DECIZIEI_CAPITOLUL_7_
MODELUL_JOCURILOR_MATRICEALE [Interactiv] . – 1 Septembrie 2017 .
[12]https : //www . britannica . com/biography/Joseph -Bertrand [Online] . – Iunie 19 , 2017 .
[13]Marius Iosifescu , G Ciucu și R Theodorescu Teoria Jocurilor, Editura Tehnică ,București, 1965
[14]Mihai Manea https : //ocw . mit. edu/courses/economics/14 -126-game -theory -spring -2016/lecture –
notes/MIT14_126S16_cooperative . pdf [Online] . – Iunie 20 , 2017 .
[15]Mihai Roman http: //www . asecib . ase. ro/Roman/PDF/CAP1 . pdf [Online] // http : //www . asecib .
ase. ro/Roman/MR . html . – Mai 21 , 2017 .
59
[16]Mihai Roman http : //www . asecib . ase. ro/Roman/PDF/CAP2 . pdf [Interactiv] // http : //www .
asecib . ase. ro/Roman/MR . html . – 20 Iunie 2017 ;
[17]Rodica Brânzei Teoria Jocurilor [Carte] . – Iași : Editura Universității „Al . I. Cuza” , 2006 .
[18]Victorița Dolean http : //clujaxio . ro/2017/02/27/teoria -jocurilor -matematica -in-viata -de-zi-cu-zi-i/
[Interactiv] // http : //clujaxio . ro/. – 27 Februarie 2017 . – 5 Mai 2017 .
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Aplicații ale teoremelor de dualitate în jocurile de producție [612258] (ID: 612258)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.