INTRODUCERE IN TEORIA JOCURILOR STRATEGICE

Teoria jocurilor este o ramura a matematicii care are ca scop sa determine metodele de alegere a celor mai bune hotarari in situatiile de conflict, in care se ciocnesc interesele unor parti ce urmaresc scopuri opuse.

Teoria jocurilor se poate defini ca o teorie matematica a situatiilor de conflict. Situatii de conflict se intalnesc in toate sectoarele de activitate unde apare notiunea de interese contrarii. Desigur, in domeniul militar teoria jocurilor are o pondere deosebita si isi confirma superlativ utilitatea.

In general, o situatie de conflict apare atunci cand in fata mai multor ipoteze ce se pot realiza cu anumite probabilitati urmeaza sa se faca o alegere dintre mai multe solutii pentru o aceeasi ipoteza, dupa un anumit criteriu de eficienta. Ipotezele pot fi actiuni ale unui adversar care nu-si divulga intentiile, astfel incat in momentul in care trebuie sa luam o hotarare nu putem cunoaste in fata carei actiuni ale acestuia ne aflam.

Un exemplu de situatie conflictuala apare in procesul de analiza a situatiei, care precede luarea hotararii. Dupa cum se stie, pentru luarea hotararii comandantul, analizand toti factorii care pot influenta succesul unitatii sale in lupta, ajunge la mai multe ipoteze de actiune ale inamicului si, in raport de acestea, la diferite solutii, corespunzatoare fiecarei ipoteze de actiune a inamicului. Din toate aceste situatii el trebuie sa o aleaga pe aceea care-i asigura cel mai bine executarea misiunii. Nu trebuie scapat din vedere ca la fiecare hotarare ce ar putea-o lua este obligatoriu sa tina seama si de actiunile cu care inamicul i se poate opune.

Aceasta analiza evidentiaza o situatie de conflict care se poate rezuma intr-un tablou in care sa fie cuprinse castigurile in functie de probabilitatile pe care le are inamicul de a impiedica indeplinirea misiunii.

Printre exemplele din aceasta categorie de situatii conflictuale se numara si acelea cunoscute sub numele de jocuri de repartitie a fortelor.

Sa presupunem ca trebuie distruse o serie de obiective aparate de n unitati ale adversarului. Pentru distrugerea obiectivelor se dispune de m unitati. Se pune intrebarea : cum trebuie repartizate pe obiective cele m unitati, astfel incat sa se produca adversarului cele mai mari pierderi, daca nu se cunoaste dinainte cum sunt repartizate pe obiective cele n unitati ale adversarului?

Din cele aratate mai sus, rezulta ca prin situatii de conflict, (conflictuale) se inteleg situatiile in care se intalnesc cel putin doua parti, persoane fizice, colective, sisteme dirijate etc., a caror activitate urmareste un scop bine determinat si in care interesele partilor sunt contrarii. Astfel de situatii apar in conflictele militare, in concurenta economica, in unele jocuri de noroc etc., precum si atunci cand activitatea desfasurata intra in conflict cu caracterul intamplator al evenimentelor naturale, cand se spune ca s-a intrat in conflict cu natura.

Pentru a putea fi studiate cu ajutorul instrumentului matematic, situatiile de conflict trebuie modelate, schematizate, abstractizate. Desigur, aceste modele reduse ale situatiilor reale nu pot contine toate complicatiile unei situatii conflictuale ci doar caracteristicile lor generale. Prin studierea acestor modele insa se pot trage concluzii asupra modului cum trebuie rezolvat conflictul real. Acest lucru a fost urmarit prin exemplele si aplicatiile prezentate in lucrare. Ele vor permite extinderea studiului situatiilor conflictuale la cele mai variate procese. De altfel, ca in orice alta stiinta, trebuie mai intai sa se plece de la cazurile particulare simplificate care se preteaza la studiu si calcul, pentru ca apoi sa se treaca la situatii complexe si la generalizari. In acest fel teoria jocurilor poate fi aplicata in cele mai variate domenii de activitate. Denumirea de joc va ramane rezervata modelelor matematice ale situatiilor de conflict, iar teoria jocurilor studiaza aceste modele schematice.

Asadar, prin joc vom intelege orice situatie conflictuala reala pe care o analizam schematic: de exemplu, atacul unui obiectiv, lupta aeriana, lupta dintre nave maritime de suprafata si submarine, contraactiunea radio, duelurile etc.

Termenul de joc, precum si alti termeni folositi in teoria jocurilor au fost imprumutati de la jocurile pure de noroc, ceea ce creeaza la inceput o confuzie intre aceste doua categorii de jocuri.

Prin jocuri pure de noroc se inteleg acele jocuri in care numai intamplarea determina castigul: se joaca exclusiv contra intamplarii. Jucatorii nu pot influenta cu nimic rolul intamplarii. Teoria jocurilor nu se ocupa de jocurile pure de noroc cum ar fi ruleta, loteriile, jocurile cu zaruri, jocul de risca etc.

Prin jocuri in sensul teoriei jocurilor se inteleg schemele acelor situatii de conflict in care intervin capacitatile intelectuale ale jucatorilor si in care rolul intamplarii este limitat prin modul de comportare al acestora. In aceasta categorie sunt cuprinse si unele jocuri propriu-zise cum ar fi jocul de sah, jocul de dame, ca si unele jocuri cu carti cum sunt bridge-ul, poker-ul, in care, evident, rolul intamplarii este limitat de modul de actiune al jucatorilor.

Intrucat in jocurile de care ne ocupam este vorba de un plan de actiune constient al jucatorilor, de o anumita strategie pe care acestia trebuie sa o intocmeasca si sa o urmeze, le vom numi jocuri de strategie sau, pe scurt, jocuri strategice.

In sensul teoriei jocurilor, prin castig se intelege rezultatul confruntarii dintre adversari si consta in dobandirea unor drepturi ale unor jucatori in dauna altora. Aceste drepturi pot fi morale sau materiale, in toate cazurile insa masurabile.

Realizarea unui joc poarta numele de partida. Orice partida se termina cu obtinerea castigului de catre unul din jucatori.

Sunt jocuri care se pot realiza de un numar oarecare de ori - deci pot da nastere la mai multe partide - si jocuri care nu se pot realiza decat sub forma unei singure partide. De exemplu, jocul de sah se poate realiza prin mai multe partide, in timp ce jocul corespunzator unui atac aerian sau unei lupte navale nu se mai poate repeta in aceleasi conditii.

Totusi anticipam sa spunem ca recomandarile teoriei jocurilor se fac pentru ipoteza ca numarul partidelor jucate poate fi nemarginit, dar se pot aplica si jocurilor care nu se realizeaza decat printr-o singura partida.

Persoanele cu interese contradictorii care participa la un joc poarta numele de parti, jucatori, parteneri, adversari, inamici, toate avand aceeasi acceptiune. In raport cu numarul jucatorilor care participa cu interese antagoniste, jocurile se pot imparti in jocuri cu doi parteneri sau jocuri cu n parteneri. Numarul jucatorilor nu este dat de numarul persoanelor fizice care participa la joc, ci de multimea intereselor contrarii care se confrunta. Astfel, la jocul de bridge sunt doi jucatori, desi numarul persoanelor fizice participante este de patru. De asemenea, un atac este considerat un joc cu doi adversari, desi numarul celor care participa la aceasta lupta este mare.

In jocurile cu mai multi parteneri, apare posibilitatea unor coalitii; in acest caz, se va vedea ca jocul se poate reduce la jocuri intre doi adversari. Mentionam ca jocurile cu o singura persoana nu sunt jocuri de competitie. Chiar atunci cand aparent este vorba de o singura persoana care are de ales intre mai multe alternative exista un adversar si anume natura, care joaca rolul de potrivnic.

Actiunile intreprinse de jucatori in cadrul unei partide poarta numele de mutari. Unele mutari pot fi efectuate cu ajutorul unui mecanism aleator (zar, moneda, urna cu bile, ruleta etc.); in acest caz, mutarile se numesc intamplatoare. Mutarile facute de jucatori in mod deliberat, cu latitudinea de a alege intre mai multe variante pe care le au la dispozitie, se numesc mutari libere. Jocurile de noroc contin numai mutari intamplatoare. Jocurile strategice trebuie sa contina neaparat si mutari libere, facute constient si care trebuie sa reflecte capacitatile intelectuale ale jucatorilor.

Cand jocurile contin si mutari intamplatoare, trebuie sa se cunoasca repartitia probabilitatilor rezultatelor posibile, pentru a se putea determina castigul mediu corespunzator acestor mutari.

Legata nemijlocit de mutarile libere este notiunea de strategie. In mod curent, prin strategie se intelege arta de a folosi cu dibacie toate mijloacele disponibile in vederea asigurarii succesului.

In sensul restrans al teoriei jocurilor, prin strategie vom considera manunchiul de reguli care permit alegerea unei decizii din cele pe care un jucator le are la dispozitie. El reprezinta un procedeu predeterminat care fixeaza pentru fiecare jucator modul in care poate face alegerile.

Von Neumann, care a fundamentat teoria jocurilor, face urmatoarele consideratii cu privire la strategie :

"Sa ne imaginam ca jucatorii, in loc de a lua fiecare decizia in momentul in care ea devine necesara, cuprind dinainte in gand toate posibilitatile care se pot ivi, adica fiecare jucator incepe jocul cu un plan complet; in acest plan este prevazuta alegerea pe care jucatorul o va avea de facut in fiecare situatie si pentru fiecare clasa posibila de informatie pe care ar putea-o avea in fiecare moment, in conformitate cu regulile jocului. Un astfel de plan reprezinta o strategie. Faptul ca jucatorul porneste de la inceput cu un plan gata pregatit nu trebuie interpretat ca o restrangere a libertatii lui de actiune, intrucat nu i se pretinde sa-si fundamenteze deciziile pe baza unor informatii mai putin complete decat acelea pe care le-ar avea practic la dispozitie in momentul mutarii. Strategia presupune intocmirea unei liste de decizii particulare care sunt functie de cantitatea de informatii pe care jucatorul o are la dispozitie in momentul cand trebuie sa ia decizia.

Singura greutate impusa jucatorilor este sarcina intelectuala de a elabora o regula de comportare pentru toate eventualitatile cand ei nu vor juca in fond decat o singura partida. O data elaborata strategia, adica o data ce listele au fost intocmite, ele pot fi predate unui arbitru care poate juca singur."

In concluzie, strategia poate fi considerata ca o multime de instructiuni care poate fi transmisa unei masini pentru ca ea sa actioneze exact cum ar fi facut jucatorii.

In teoria jocurilor se intalneste notiunea de strategie pura, ca si aceea de strategie mixta sau ponderata. Daca, pentru realizarea unui joc, unul din adversari are la dispozitie m alternative, iar partida se incheie printr-o alegere se spune ca jucatorul are la dispozitie m strategii pure.

In general, daca un jucator are de ales unul din numerele multimii , se spune ca are m strategii pure; alegerea fiecaruia din aceste numere constituie o strategie pura.

In functie de numarul strategiilor pure, jocurile se impart in doua categorii: jocuri finite, care contin pentru fiecare jucator un numar finit de strategii pure si jocuri infinite in care numarul strategiilor pure este nemarginit. Un joc finit intre doi jucatori, in care un jucator are m strategii pure, iar adversarul sau n strategii pure, poarta numele de joc mn.

Cand partidele se repeta, jucatorii pot alege strategiile pure cu anumite frecvente; in acest caz, se spune ca se foloseste o strategie mixta sau o strategie ponderata. Asadar, o strategie mixta provine din alternarea strategiilor pure cu anumite frecvente.

Fiecare jucator urmareste aplicarea unei strategii care sa-i aduca maximum de avantaje, cu alte cuvinte cauta o strategie optima. Aceasta strategie reprezinta un plan iscusit si inteligent manevrat, astfel incat sa nu poata fi stricat de actiunile adversarului.

Jocurile pure de noroc nu au strategii. Din acest motiv este inutil sa se caute metode de castig, de exemplu la ruleta, loterie etc.

In jocurile strategice, prin castigul realizat la sfarsitul unei partide se intelege rezultatul confruntarii a doua strategii pure alese de jucatori. Intrucat adversarii nu urmaresc realizarea aceluiasi eveniment, obiectivele lor sunt diferite, ceea ce conduce la castiguri diferite.

Pentru determinarea castigului, trebuie cunoscut rezultatul confruntarii strategiilor pure ale celor doi jucatori. Deci o operatie obligatorie prealabila determinarii castigului este stabilirea strategiilor pure de care dispune fiecare jucator.

De asemenea, trebuie cunoscuta repartitia castigului, adica plata ce ar trebui facuta de unii jucatori in favoarea altora in urma confruntarii fiecarei perechi de strategii pure.

Din punctul de vedere al castigului, jocurile pot fi cu suma nula, cand la sfarsitul unei partide suma pierduta de o parte din jucatori este castigata de ceilalti jucatori, cu alte cuvinte cand jucatorii isi fac plati reciproce.

Cand o parte din sumele varsate de catre jucatori se rezerva altor scopuri decat acela de a li se plati jucatorilor castigatori, jocurile poarta numele de jocuri fara suma nula.

Un joc cu suma nula intre doi jucatori care au un numar finit de strategii pure mai poarta numele si de duel si intra in categoria jocurilor mn. Majoritatea jocurilor militare sunt dueluri.

Pentru oricare categorie de jocuri cu doi parteneri, castigul face legatura intre multimea strategiilor pure ale unui jucator si multimea strategiilor pure ale adversarului sau. Castigul este exprimat printr-o functie de castig, f, numita si nucleul jocului, care trebuie cunoscuta de toti jucatorii, o data cu celelalte reguli ale jocului.

In jocurile strategice mn cu suma nula intre doi jucatori functia de castig se poate prezenta sub forma urmatorului tabel de plati:

Pentru a scoate in evidenta matricea jocului, vom prezenta tabelul de plati sub forma:

adica:

De exemplu, in tabelul de mai sus elementul a_ij reprezinta castigul jucatorului A in ipoteza ca, alegand strategia pura A_i (linia i), jucatorul B a ales strategia pura B_j (coloana j), elementul a_ij figureaza la intersectia liniei i cu coloana j.

Elementele a_ij sunt cunoscute si rezulta din regulile jocului.

Datorita formei de tabel a functiei de castig, tabel pe care il vom numi pe viitor matricea castigurilor sau matricea platilor sau, simplu, matricea jocului, jocurile mn prezentate astfel mai poarta numele de jocuri dreptunghiulare sau matriceale. Forma matriceala de prezentare a jocurilor poarta numele de forma normala. Matricea jocului caracterizeaza jocurile aduse la forma normala. Asadar, prin forma normala se intelege prezentarea unui joc, astfel incat sa iasa in evidenta atat strategiile pure, cat si corespondenta castigurilor pentru acele strategii.

In consecinta, un joc in forma normala se caracterizeaza prin trei elemente:

- o multime X= reprezentand cele m strategii pure ale jucatorului A;

- o multime Y= reprezentand cele n strategii pure ale jucatorului B;

- o functie reala f definita pe multimea XY, numita functia de castig.

Daca jucatorul A alege strategia x_iIX, iar jucatorul B alege strategia y_jIY, atunci f(x_i,y_j)=a_ij si jucatorul B plateste jucatorului A aceasta valoare. In acest caz, jocul matriceal m n se noteaza: J = (X,Y,f).

Matricea de plati definita prin a_ij = f (x_i,y_j), in care i = 1, . . .,m, iar j = 1,. . .,n se intocmeste in raport cu un singur jucator, denumit pe viitor jucatorul A sau jucator maximizant. Partenerul sau va fi numit jucatorul B sau jucator minimizant. Intr-un joc m n, jucatorul care are m strategii este considerat jucator maximizant.

Intrucat jocul este cu suma nula, o matrice intocmita pentru evidentierea castigurilor jucatorului B va contine aceleasi elemente ca matricea intocmita pentru castigurile jucatorului A, dar cu semn schimbat.

In tehnica teoriei jocurilor, se obisnuieste ca matricea de plati sa se intocmeasca in raport cu jucatorul A, cu jucatorul maximizant. Faptul ca o matrice se intocmeste in raport cu castigurile unui anumit jucator nu influenteaza castigurile acestuia.

Dupa modul de prezentare a jocurilor finite cu suma nula intre doi parteneri A si B, forma normala se caracterizeaza prin exprimarea nucleului ca o corespondenta intre multimea strategiilor pure ale unuia dintre jucatori si multimea strategiilor pure ale celuilalt jucator. Aceasta corespondenta se reflecta intr-un tabel contabil numit matricea jocului, care va fi de tipul mn, daca jucatorul maximizant A are m strategii pure, iar jucatorul minimizant B are n strategii pure. In acest caz, asa cum s-a aratat, jocul se numeste joc matriceal de tipul (ordinul, forma) mn sau, simplu, joc mn.

Daca ne referim la matricea de plata de mai jos:

prin strategie pura se intelege alegerea unei linii sau a unei coloane. In cazul repetarii partidelor apare notiunea de strategie mixta legata de folosirea strategiilor pure cu anumite frecvente. Acest lucru este necesar pentru ca adversarul sa nu poata banui strategia pura aleasa in fiecare partida. Asadar, un joc in forma normala este definit prin multimea strategiilor pure ale fiecarui jucator, precum si prin matricea de plata.

Daca un joc se desfasoara pe intinderea unei singure partide, jucatorul A castiga de la jucatorul B suma a_ij, in ipoteza ca jucatorul A a ales strategia corespunzatoare liniei i, iar jucatorul B a ales strategia corespunzatoare coloanei j.

1. Consideratii asupra matricei jocului

Elementele a_ij ale matricei jocului sunt cunoscute fie ca sunt date direct, fie ca se deduc din regulile jocului. Corespondenta dintre multimea strategiilor pure ale jucatorului A si multimea strategiilor pure ale jucatorului B se poate exprima in mai multe moduri si anume :

a) Sub forma unei functii analitice f (a_i,b_j) de doua variabile, in care:

a_iIX

si:

b_iIY = sunt puse in corespondenta biunivoca.

Multimile X, Y reprezinta multimile strategiilor pure ale celor doi jucatori. Spre exemplu, jucatorul A alege unul din numerele multimii X = , iar jucatorul B, unul din numerele multimii Y = .

De pilda, daca plata urmeaza a fi facuta dupa conventia

matricea jocului este :

b) In cazul cand jucatorul A alege un numar din multimea:

X= , iar jucatorul B, un numar din multimea:

Y= , cu conventia ca perechea (i, j) formata din alegerea numarului i de catre jucatorul A si a numarului j de catre jucatorul B sa aduca jucatorului A castigul a_ij, se spune ca jucatorul A         a ales strategia pura A_i sau, mai simplu, strategia i, iar jucatorul B a ales strategia pura B_j sau, pe scurt, strategia j. Matricea de plata evidentiaza caracterul de formular contabil al castigurilor, iar a_ij = f (i, j).

Multimea X reprezinta spatiul strategiilor jucatorului A, iar multimea Y reprezinta spatiul strategiilor jucatorului B.

Pentru un joc matriceal mn, se vor obtine puncte in spatiul castigurilor. Daca:

,      cu si ,

se obtine o multime de puncte discrete.

Pentru jocurile infinite, numarul strategiilor fiind nemarginit, multimea punctelor C [x, y, f (x, y)], unde xX, yY determina o suprafata.

Valorile elementelor a_ij nu sunt totdeauna determinate de un castig fix; ele exprima de cele mai multe ori un castig probabil sau un castig mediu. Pentru a intelege acest lucru sa urmarim cateva exemple.

Exemplul 1: Problema cautarii bombardierului purtator

Partea A trimite in raionul de dispunere al inamicului, notat cu B, doua avioane de bombardament A₁ si A₂, primul zburand in fata celui de al doilea. Dintre aceste avioane numai unul poarta mijlocul de nimicire. In raionul inamicului, avioanele de bombardament sunt atacate de un avion de vanatoare al partii B. Avioanele de bombardament sunt inzestrate cu tunuri cu diferite viteze de tragere. Daca avionul de vanatoare ataca bombardierul A₂, atunci asupra avionului de vanatoare trag numai tunurile acestui bombardier; daca insa avionul de vanatoare ataca bombardierul A₁, asupra sa se executa trageri cu tunurile ambelor bombardiere. In primul caz, probabilitatea de lovire a avionului de vanatoare este egala cu 0,3 iar in al doilea caz cu 0,7. Daca avionul de vanatoare nu este doborat de focul bombardierelor, el loveste tinta pe care a ales-o cu probabilitatea 0,6. Misiunea avioanelor de bombardament este sa duca mijlocul de distrugere la tinta; misiunea avionului de vanatoare este sa impiedice acest lucru, adica sa doboare purtatorul mijlocului de nimicire.

Jocul este de tipul 22, in care jucatorul A are doua strategii (sa transporte bomba fie cu avionul A₁, fie cu avionul A₂) iar jucatorul B are de asemenea doua strategii (sa atace ori avionul A1, ori avionul A2).

In urma calcularii probabilitatilor de nelovire a avionului purtator (castigul corespunzator fiecarei perechi de strategii), matricea jocului este:

Matricea s-a intocmit pe baza urmatoarelor calcule facute in ipoteza ca partea A castiga un punct prin nedoborarea avionului purtator:

- elementul a₁₁ corespunde confruntarii strategiei A₁ (mijlocul de nimicire este purtat de avionul din fata) cu strategia B₁ (avionul de vanatoare ataca bombardierul A₁). Purtatorul nu va fi lovit daca avioanele de bombardament vor dobori avionul de vanatoare sau avionul de vanatoare nu va atinge tinta. Deci :

.

- elementele a₂₁ si a₁₂ sunt egale cu l, intrucat ambele strategii ale avionului de vanatoare constau in atacarea avionului nepurtator.

elementul a₂₂ corespunde strategiei A₂ (mijlocul de nimicire este purtat de avionul din spate) confruntata cu strategia B₂ (avionul de vanatoare ataca din spate). In acest caz:

.

Privita din punctul de vedere al avionului care ataca, problema consta in distrugerea bombardierului purtator. Daca avionul de vanatoare reuseste sa atace purtatorul mijlocului de distrugere, probabilitatea de succes este egala cu β.

Daca ataca primul bombardier, avionul de vanatoare are un risc egal cu α de a fi doborat inainte de a-si fi indeplinit misiunea. Daca atacul a reusit, incercarile urmatoare sunt indreptate contra celui de-al doilea bombardier, pana cand acesta va fi distrus sau avionul de vanatoare isi va epuiza potentialul sau de atac.

Daca cel de-al doilea bombardier n-a fost nimicit, distrugerea primului se va face mai greu. In cazul cand este nimicit cel de-al doilea bombardier, probabilitatea de distrugere a primului este egala cu β.

Daca al doilea bombardier n-a fost lovit, probabilitatea de distrugere a primului este .

Castigul avionului de vanatoare consta numai din speranta matematica de distrugere a bombardierului purtator al mijlocului de nimicire. Matricea intocmita in raport cu castigul avionului de vanatoare este:

Importanta acestei probleme face ca apararea sa foloseasca mai multe avioane de vanatoare. In cazul cand participa doua avioane de vanatoare jocul devine 42 si are matricea:

Semnificatia notatiei A_i A_j (i=1,2; j=l,2) este ca primul avion de vanatoare ataca bombardierul A_i, iar cel de-al doilea avion de vanatoare ataca bombardierul A_j.

Exemplul 2: Folosirea avioanelor de bombardament in functie de mijloacele de combatere ale adversarului

Partea A are la dispozitie trei feluri de armament A₁, A₂, A_3, iar adversarul are trei tipuri de avioane: B₁, B₂, B₃. Sarcina partii A consta in doborarea avioanelor care ataca, iar a partii B sa fereasca avioanele de a fi lovite. Daca se intrebuinteaza armamentul A₁, avioanele B₁, B₂, B₃ vor fi lovite cu probabilitatile 0,9; 0,4 si respectiv 0,2. Daca se intrebuinteaza armamentul A₂, probabilitatile de lovire devin: 0,3; 0,6; 0,8, iar daca se foloseste armamentul A₃, probabilitatile sunt: 0,5; 0,7; 0,2. Castigul jucatorului A este egal cu 1 daca doboara avionul si egal cu 0 daca nu il doboara; deci valoarea medie a elementului a_ij este insasi probabilitatea de lovire.

Se asteapta de la teoria jocurilor, pe de o parte, sa recomande ce tipuri de avioane sa se foloseasca pentru ca atacul sa fie cat mai eficace, iar, pe de alta parte, ce fel de armament sa fie folosit pentru ca atacul sa fie cat mai ineficace.

Jocul are forma 3 x 3 si este caracterizat de matricea:

Elementele a_ij pot marca atat reusita, cat si nereusita alegerii strategiilor pure respective si, in acest caz, valoarea lor se noteaza cu 1. De exemplu, un avion cauta un submarin care poate fi gasit in unul din locurile M_l, M₂. Cautarea si gasirea submarinului in locul in care se ascunde echivaleaza cu un succes, evaluat cu +1; negasirea submarinului se noteaza cu - 1.

Matricea acestui joc 2 X 2 este :

In situatia cand esecul se noteaza cu zero si submarinul se poate gasi in unul din locurile M_i (i = 1,2, . . . , m), jocul este de forma m m si are ca matrice, matricea unitate:

Proiect: Infiintarea filialelor si sediilor secundare ale societatii comerciale pe actiuni Lucrare: Analiza rentabilitatii

Cele m strategii ale avionului sunt de a cauta submarinul in fiecare din cele M_i, locuri, iar cele m strategii ale submarinului, sa se ascunda in unul din aceste locuri. Desigur, jocul este lipsit de orice informatie.

Jocurile de mai sus intra in categoria jocurilor asa-numite ale cautarii obiectelor ascunse. Daca jucatorul care cauta obiectul in unul din aceste locuri isi asuma anumite riscuri, iar gasirea se face cu un anumit grad de incertitudine, matricea jocului este de forma:

Daca obiectul este cautat de mai multe persoane, jocul nu mai este de ordinul 2 2, ci de ordin superior, asa cum s-a aratat in exemplul 1.

Adesea greutatea de a preciza valorile lui a_ij face ca matricea sa contina numai elemente calitative, cu greu de transpus in valori numerice. Sunt numeroase exemplele in care dilema unui jucator face ca alegerea sa sa fie subiectiva, mai ales cand cel de-al doilea jucator este natura. Citam un exemplu cu circulatie in literatura de specialitate:

Este vorba de dilema - conflictul sufletesc - al unui sot care, nefiind sigur ca este ziua de nastere a sotiei sale, nu stie daca sa-i duca sau nu flori. Daca nu este ziua sotiei si nu duce flori, nu se intampla nimic; aceasta situatie o notam cu 0. In cazul cand este ziua sotiei si nu duce flori, sotul se gaseste intr-o situatie penibila, notata cu rau. Daca aduce flori si nu este nici o aniversare, gestul este apreciat ca satisfacator, desi ar putea fi interpretat ca o incercare de a preveni un eventual repros. In sfarsit, daca aduce flori si este intr-adevar aniversarea sotiei, castigul realizat este notat cu bine.

Acest joc, de forma 2 2, in care adversarul este natura are matricea:

In cercetarea situatiilor de conflict se resimte greutatea stabilirii strategiilor pure si intocmirii matricei de plati; aceasta greutate poate fi asemanata aceleia intampinata la punerea in ecuatie a problemelor de algebra. Numai dupa efectuarea acestei prime etape se poate trece la rezolvarea jocului.

Exemplificam parcurgerea acestei prime etape, la urmatoarele jocuri:

Jocul Morra. Jocul consta in ridicarea simultana de catre cei doi jucatori a unu sau doua degete, strigand in acelasi timp numarul de degete pe care crede ca le-a ridicat adversarul. Jucatorul care ghiceste castiga o suma egala cu suma formata de numarul degetelor ridicate de ambii jucatori; daca ambii ghicesc corect sau nici unul dintre jucatori nu ghiceste, castigul este egal cu zero.

Fiecare dintre jucatori dispune de cate patru strategii pure si anume:

sa ridice un deget si sa spuna unu (numarul de degete pe care presupune ca le-a ridicat adversarul), notand aceasta strategie cu (1, 1);

sa ridice un deget si sa spuna doi (1, 2);

sa ridice doua degete si sa spuna unu (2, 1);

sa ridice doua degete si sa spuna doi (2,2).

Conform conventiei, matricea acestui joc 4 4 este:

Echivalentul militar al jocurilor Morra este jocul Blotto[1], pe care-l particularizam pentru a inlesni formarea unei matrice de forma 5

Blotto comanda 4 companii, iar adversarul sau, Kije, 3 companii. Blotto poate ataca un sector pe doua directii diferite, pe care isi repartizeaza la alegere companiile sale. In mod analog, Kije poate sa apere sectorul, dispunand companiile sale pe aceleasi directii. In momentul alegerii strategiilor, nici una din parti nu cunoaste dispozitivul de lupta adoptat de adversar. Blotto castiga daca a folosit pe oricare din directii mai multe companii decat Kije. Castigul se va exprima prin adunare de puncte: un punct pentru castigarea bataliei, plus cate un punct de fiecare companie nimicita; castigurile finale egale se noteaza cu zero. Companiile se considera nimicite daca pe directia respectiva comandantul plaseaza un numar mai mare de companii decat adversarul. Desigur, lupta se duce simultan pe ambele directii si castigul este format din suma castigurilor pe cele doua directii.

Daca prin notatia (a b) intelegem ca pe prima directie s-au repartizat a companii, iar pe a doua, b companii, Blotto are 5 strategii pure A_i si anume:

A₁ = (4, 0), A₂ = (0, 4), A₃ = (3, 1), A₄ = (1, 3), A₅ = (2, 2),

iar Kije are urmatoarele patru strategii pure:

B_l = (3, 0), B₂ = (0, 3), B₃ = (2, 1), B₄ = (1, 2).

Matricea are forma:

Elementele matricei se calculeaza cu usurinta. Astfel, elementul a₁₁= 4, intrucat, pe directia unde s-au infruntat companiile, Blotto obtine 1 punct corespunzator castigului bataliei si 3 puncte corespunzatoare celor 3 companii nimicite ale lui Kije; a₅₂= -2, intrucat atit Blotto, cat si Kije au castigat pe cate o directie, dar Blotto nu a nimicit nici o companie, in timp ce Kije a nimicit doua companii; a₃₄ = 0, deoarece atat Blotto cat si Kije castiga cate un punct de fiecare batalie plus cate un punct de fiecare companie nimicita, deci castigurile sunt egale.

Formarea matricei depinde si de cantitatea de informatie de care dispun jucatorii. Sa presupunem ca jucatorul A poate alege sau mutarea X sau mutarea Y, iar jucatorul B poate alege fie mutarea x, fie mutarea y. In ipoteza ca jucatorii executa simultan mutarile, astfel incat nici unul sa nu poata fi informat de mutarea adversarului, avem de-a face cu un joc 2 x 2, a carui matrice este :

Daca insa jucatorul B poate lua cunostinta de mutarea facuta de jucatorul A, atunci are la dispozitie patru strategii pure si anume:

sa aleaga x daca A a ales X, strategie notata cu (X, x);

sa aleaga y daca A a ales X, strategie notata cu (X, y);

sa aleaga x daca A a ales Y, strategie notata cu (Y, x);

sa aleaga y daca A a ales Y, strategie notata cu (Y, y).

Jocul este deci de forma 2 4, iar daca platile se fac dupa conventia:

f(X, X, x)=a₁₁                            f(Y, X, x)=a₂₁

f(X, X, y) = a₁₂              f(Y, X, y) = a₂₂

f(X, Y, x) = a₁₃              f(Y, Y, x) = a₂₃

f(X, Y, y) = a₁₄              f(Y, Y, y) = a₂₄

matricea jocului este :

Valoarea inferioara si valoarea superioara a jocului

Daca jucatorul A alege strategia A_i, corespunzatoare liniei i, trebuie sa se astepte ca jucatorul B va raspunde cu aceea dintre strategiile sale pentru care castigul lui A va fi cel mai mic. Aceasta strategie a lui B corespunde numarului a_ij, avand in linia i a matricei m n valoarea cea mai mica.

Sa notam acest numar: , unde j reprezinta coloana in care figureaza cel mai mic element al liniei i. Deci, daca A a ales strategia pura A_i, sa nu se astepte sa castige mai mult decat a_i (bineinteles, in ipoteza ca B alege actiunile sale cele mai logice). Dar A are la dispozitie m strategii pure, asadar el va cauta sa aleaga pe aceea din ele in care a_i este cel mai mare. Daca , adica , atunci aceasta valoare reprezinta valoarea inferioara a jocului sau castigul maximin al jucatorului A.

Un rationament analog se poate face si pentru jucatorul B. El urmareste sa reduca pe cat mai mult posibil castigul maxim pe care 1-ar putea realiza jucatorul A. Deci, alegand strategia B_j (corespunzatoare coloanei j), el este sigur ca va castiga cel putin min (- a_ij) = - max a_ij, adica A nu poate castiga mai mult decat .

Se noteaza elementul cu cea mai mare valoare situat in coloana j. Jucatorul B are la dispozitie n strategii pure, asa incat acesta va alege coloana in care elementul b_j are cea mai mica valoare, adica va cauta:

care reprezinta valoarea superioara a jocului.

Valoarea inferioara si valoarea superioara a jocului exista intotdeauna intr-o matrice. Sa consideram elementul a situat la intersectia liniei care contine pe a cu coloana care-l contine pe b

Pentru ca elementul a face parte din coloana lui β, aβ, iar pentru ca face parte din linia lui α, aα, deci:

αaβ; αβ.

Fiecare matrice contine aceste doua elemente α, β, care se pot scoate in evidenta daca marginim matricea de plati cu o coloana reprezentand valorile α_i si cu o linie reprezentand valorile b_j

Exemplu

Matricea de mai sus are valoarea inferioara a jocului egala cu zero, iar valoarea superioara, egala cu 3.

Strategiile maximin si minimax

Stabilirea valorilor inferioare si superioare permite jucatorilor sa cunoasca sumele pe care in orice caz le au asigurate. Astfel, jucatorul A nu va putea castiga mai putin decat a, iar jucatorul B nu va putea pierde mai mult decat b. Aceste sume sunt asigurate numai in cazul cand jucatorii respecta strategiile corespunzatoare valorilor a si b

Strategia care garanteaza jucatorului A castigul egal cu valoarea inferioara, a, se numeste strategie maximin. Strategia care asigura jucatorului B o pierdere, b, egala cu valoarea superioara a jocului se numeste strategie minimax. Vom vedea ca aceste strategii, pe care pentru usurinta exprimarii le vom numi strategii minimax, au caractere diferite, in functie de natura jocurilor.

De exemplu, jocul avand matricea:

are valoarea inferioara a=4, egala cu valoarea superioara b

Strategia A₃ asigura jucatorului A castigul minim de 4, iar strategia B₂ asigura jucatorului B o pierdere de cel mult 4, deci aceste strategii sunt strategii minimax.

In toate cazurile in care valoarea inferioara a jocului este egala cu valoarea superioara, adica a b, pe baza principiului minimax, teoria recomanda jucatorilor folosirea strategiilor minimax, indiferent de numarul partidelor jucate. Cu alte cuvinte, in conditiile repetarii multiple a jocului, jucatorii trebuie sa se mentina pe aceleasi strategii minimax care le asigura castigul egal cu valoarea comuna a b

Pentru aceste jocuri:

,

iar valoarea comuna v reprezinta valoarea jocului.

Abaterea de la aceste strategii minimax nu ramane nesanctionata. Daca jucatorul A, considerandu-se mai inteligent decat B, spera sa obtina un castig mai mare decat 4 si alege orice alta strategie decat strategia maximin, jucatorul B, mentinand strategia sa minimax, B₂, face ca jucatorul A sa castige mai putin decat 4, intrucat confruntarea strategiei B₂ cu orice alta strategie a lui A conduce la elemente a_i2 mai mici decat Spre exemplu, cu strategia A₄ se castiga 2 iar cu oricare din strategiile A₁, A₂, A₅ se castiga 3.

Asadar, prin strategia minimax jucatorul B impiedica pe jucatorul A sa castige mai mult decat valoarea superioara a jocului si nici macar aceasta valoare, daca jucatorul A nu respecta strategia sa maximin. In cazul jocurilor pentru care a b, faptul ca strategiile minimax trebuie sa ramana aceleasi, indiferent de cate partide se joaca, constituie caracterul de stabilitate al strategiilor minimax. Nu tot acelasi caracter il prezinta strategiile minimax pentru jocurile in care a b; in aceste jocuri strategiile trebuie ascunse si manevrate astfel incat nici chiar jucatorul care le utilizeaza sa nu le cunoasca dinainte.

2. Jocuri cu punct sa

In jocul din exemplul precedent s-a vazut ca valoarea inferioara este egala cu valoarea superioara. Asadar, elementul a₃₂ este in acelasi timp egal si cu a si cu b

Jocurile in care un element al matricei se bucura de proprietatea ca este in acelasi timp minim pe linie si maxim pe coloana formeaza o categorie particulara de jocuri, numite jocuri cu punct sa. In aceste jocuri valoarea inferioara este egala cu valoarea superioara si corespunde unui element al matricei numit punct sa. Valoarea acestui element reprezinta valoarea jocului. Denumirea de punct sa nu este intamplatoare. In general, pe o suprafata punctul care se bucura de proprietatea ca este in acelasi timp punct de minim pe o directie si punct de maxim pe directia perpendiculara se numeste punct sa, intrucat suprafata respectiva se prezinta geometric sub forma de sa.

Daca f(x,y) este o functie reala definita pentru orice xIX si yIY, X si Y fiind submultimi ale multimii numerelor reale R, conditia necesara si suficienta pentru ca functia f(x,y) sa aiba un punct sa este:

(bineinteles ca aceste marimi sa existe).

Daca x₀, y₀ sunt coordonatele punctului sa atunci:

Pentru cazul particular unde f(x,y) = a_ij - intrucat o matrice este o functie de doua variabile, i si j - definitia punctului sa corespunde elementului minim pe linie si maxim pe coloana.

Punctului sa ii corespunde o pereche de strategii minimax. Aceste strategii se numesc strategii optime sau echilibrate, iar perechea lor determina valoarea jocului, care este egala cu elementul a_ij corespunzator punctului sa din matrice.

Rezolvarea unui joc cu punct sa se considera terminata cand au fost gasite strategiile optime si valoarea jocului. Prin solutie se va intelege nu numai valoarea jocului, ci si modul cum se poate obtine aceasta valoare, adica determinarea strategiilor optime.

Un exemplu de joc cu punct sa, care reprezinta totodata o aplicatie efectiva a teoriei jocurilor in operatiile militare, o constituie luptele pentru Noua Guinee din timpul celui de-al doilea razboi mondial.

Japonezii trebuiau sa transporte un convoi de trupe si alimente din portul Rabaul, situat la extremitatea estica a Noii Britanii, la Lae aflat in Noua Guinee. Convoiul putea sa treaca fie pe la nord de Noua Britanie, unde se prevedea aproape sigur o vizibilitate proasta, fie spre sud de insula, unde se astepta vreme buna.

In ambele cazuri, navigatia ar fi durat trei zile. In vederea distrugerii convoiului, comandamentul american putea sa concentreze principalele forte ale aviatiei sale fie pe o cale, fie pe cealalta. Evident, dupa descoperirea lui, convoiul putea fi bombardat inainte de a ajunge la Lae.

Grupa de cercetare operationala a comandamentului american a stabilit urmatoarea matrice, corespunzatoare tuturor ipotezelor:

In aceasta matrice, ale carei elemente sunt zile de bombardament, punctul sa il constituie elementul a₁₁=2.

In consecinta, teoria jocurilor recomanda comandamentului japonez sa trimita convoiul pe calea de nord, iar comandamentului american sa-si concentreze fortele pe aceeasi cale. Alegerea acestei rute nu a insemnat o greseala operativa, intrucat daca japonezii ar fi ales calea de sud ar fi riscat sa fie bombardati toate cele trei zile cat dura transportul, nu numai doua zile.

De asemenea, are punct sa si jocul care se refera la aniversarea sotiei. In consecinta, teoria jocurilor recomanda sotilor sa duca flori acasa .

Un alt exemplu de joc cu punct sa este urmatorul:

Cunoscandu-se ca trebuie sa se actioneze impotriva a trei tipuri de bombardiere T₁, T₂, T₃ avand caracteristicile:

tipul T₁ cu putere de foc redusa;

tipul T₂ cu viteza de zbor medie;

tipul T₃ cu viteza de zbor mare,

avioanele de vanatoare ale adversarului se pot echipa cu 4 categorii de mijloace de lupta (M₁, M₂, M₃, M₄) a caror eficacitate in raport cu tipurile de bombardiere este data in matricea de mai jos:

Punctul sa al matricei este dat de valoarea 0,17, ce se gaseste la intersectia strategiei M₃ cu strategia T₃.

In legatura cu cantitatea de informatie facem urmatoarele observatii: in jocurile cu punct sa, informatia cu privire la strategia optima aleasa de adversar nu influenteaza rezultatul jocului. Fenomenul se datoreaza faptului ca valoarea jocului este determinata de punctul sa, indiferent daca unuia dintre jucatori i se anunta ca adversarul a ales strategia optima.

Desigur, daca un jucator nu se multumeste cu valoarea jocului determinat de punctul sa, adversarul sau are numai de castigat; daca se multumeste cu acest castig, adversarul nu poate sa-l impiedice sa si-l realizeze. Strategiile optime corespunzatoare punctelor sa garanteaza un nivel maxim sau minim, iar teoria jocurilor recomanda aceste strategii consultativ nu deliberativ.

In raport cu cantitatea de informatie pe care o au jucatorii despre strategiile folosite de adversari, trebuie subliniat ca toate jocurile cu informatie completa au punct sa. Prin jocuri cu informatie completa se inteleg jocurile in care fiecare parte executa mutarile libere cunoscand rezultatele tuturor mutarilor precedente (atat ale sale, cat si ale adversarului).

Majoritatea jocurilor care au o importanta practica nu apartin clasei jocurilor cu informatie completa, deoarece necunoasterea intentiilor adversarului constituie elementul esential al situatiilor de conflict. Cu alte cuvinte, jocurile cu punct sa formeaza o minoritate in multimea jocurilor strategice.

Un joc poate avea mai multe puncte sa. Spre exemplu, jocul a carui matrice este:

are doua puncte sa: a₁₁ = 4 si a₁₃ = Se poate demonstra ca, in cazul cand un joc are mai multe puncte sa, toate aceste puncte sunt egale intre ele.

Asadar, existenta concomitenta a mai multor puncte sa nu modifica valoarea jocului, deoarece aceasta este determinata de valoarea punctului sa. Prezenta in matrice a mai multor puncte sa conduce la multiple perechi de strategii optime. Perechile sunt echivalente si se pot schimba intre ele, permitand astfel jucatorilor sa aleaga pe cele convenabile si dupa alte criterii. In concluzie, valoarea jocului care are puncte sa este determinata de valoarea comuna a b= a_ij, unde a_ij reprezinta elementul din matrice cu proprietatea minim pe linie si maxim pe coloana.

A. Principiul dominarii

Adesea matricea de plata cuprinde unele strategii pure care sunt de-a dreptul dezavantajoase pentru jucatori.

In matricea:

se vede ca strategiile B_l si B₃ sunt dominate de strategia B₄, iar strategia A₃ este dominata de strategia A Prin eliminarea acestor strategii se obtine jocul avand matricea:

Din exemplul de mai sus se desprinde necesitatea gasirii strategiilor neavantajoase, pentru a se reduce de la inceput matricea initiala a jocului la o matrice mai simpla; operatia constand din indepartarea acestor strategii neavantajoase, poarta numele de cercetarea dominarii.

Dominarea este stricta daca toate elementele unei linii sau ale unei coloane sunt respectiv mai mari sau mai mici decat acelea corespunzatoare altor linii sau coloane.

O strategie corespunzatoare liniei i (strategia A_i), ale carei elemente sunt mai mici decat elementele liniei k, se spune ca este dominata de strategia A_k sau ca strategia Ak domina strategia A_i sau ca strategia A_k este dominanta in raport cu strategia A_i; acest lucru se scrie A_k< A_i unde semnul < exprima un raport de preferinta.

Daca dominatia nu este stricta, semnul < este dublat de semnul =, in care caz unele elemente ale liniei k pot fi si egale cu elementele corespunzatoare liniei i.

De exemplu, in jocul avand matricea:

strategia A₁ nu este dominata strict de strategia A₂. Acest lucru se observa si in jocul:

unde strategiile A₁ si A₂ se repeta.

Daca a_ir a_is pentru oricare valoare a lui i, se spune ca strategia B_r este dominata de strategia B_s (B_r<B_s) sau, prescurtat, coloana r este dominata de coloana s. Asadar, este de recomandat jucatorului B sa elimine strategia B_r.

Uneori, dominatia poate fi ascunsa; aceasta situatie se intalneste cand elementele unei linii, fara a fi mai mici decat elementele corespunzatoare, sunt mai mici decat o anumita combinatie liniara convexa a elementelor corespunzatoare acelor linii.

Daca

,          j=1, . ,n

adica:

a_kj<a_1jx₁+ a_2jx₂+ . + a_mjx_m

si

, x_i i

se va spune ca strategia A_k este dominata ascuns de celelalte strategii sau ca strategia A_k este dominata de o strategie mixta.

Spre exemplu, in jocul care se caracterizeaza prin matricea:

linia a treia este dominata de o combinatie liniara convexa a celorlalte doua linii, intrucat

De asemenea, o coloana este dominata ascuns de celelalte daca exista relatia:

,             i=1, . ,m

unde

, x_j j

De exemplu, in jocul avand matricea:

coloana a treia este dominata ascuns de primele doua coloane, deoarece:

Un alt tip de dominare este dominarea matriceala. Daca o matrice se poate descompune in partitia

in care A₁, A₂, A₃ si A₄ sunt submatrice ale matricei A. Daca fiecare coloana a matricei A₂ domina strict o combinatie liniara convexa a coloanelor matricei A_l, iar fiecare linie a lui A3 este dominata strict de o combinatie liniara convexa a liniilor matricei A_l, atunci jocul avand matricea A se poate inlocui cu un joc caracterizat de matricea A_l.

Prin partitia de mai jos a matricei A care caracterizeaza jocul 7

acesta se reduce la un joc 3 2 avand matricea:

In teoria jocurilor se demonstreaza ca prin eliminarea strategiilor dominate se obtine un joc avand aceeasi valoare cu jocul initial. De asemenea se demonstreaza ca la manevrarea strategiilor pure ale jocului initial trebuie sa se tina seama de solutia jocului redus in ceea ce priveste folosirea strategiilor pure ale acestuia.

In concluzie, inainte de a se trece la rezolvarea unui joc se recomanda eliminarea tuturor strategiilor dominate.

3. Jocuri fara punct sa

In multimea jocurilor matriceale, jocurile cu punct sa reprezinta o submultime restransa. Intrucat majoritatea jocurilor au valoarea inferioara diferita de valoarea superioara (maximin minimax), se pune intrebarea daca, in ipoteza repetarii partidelor, poate fi gasita o strategie prin aplicarea careia jucatorul A sa obtina un castig mai mare decat minimul asigurat de strategia maximin.

Aceasta intrebare este logica, deoarece in cazul jocurilor fara puncte sa, strategiile minimax au un caracter deosebit de caracterul strategiilor minimax ale jocurilor cu puncte sa.

Pentru jocurile cu punct sa, indiferent daca unul din jucatori cunoaste strategia minimax a celuilalt jucator, valoarea jocului nu se modifica, daca jucatorul se mentine pe strategia sa minimax. Acest fapt caracterizeaza strategiile jocurilor cu punct sa si poarta numele de stabilitatea strategiilor minimax. Nu tot astfel se petrec lucrurile in jocurile fara puncte sa. Strategiile minimax recomandate ca un prim mijloc de a obtine un minim garantat se dovedesc neavantajoase in cazul repetarii partidelor.

De indata ce un jucator cunoaste ceva din comportarea adversarului, valoarea jocului se modifica in favoarea jucatorului informat, deoarece acesta, abandonand strategia sa minimax, reuseste sa-si majoreze castigul. Aceasta proprietate, care caracterizeaza strategiile minimax ale jocurilor fara punct sa, poarta numele de instabilitate a strategiilor minimax. Strategiile minimax trebuie sa se schimbe cand devine cunoscut ceva din comportarea adversarului. Asadar, in cazul jocurilor fara punct sa strategiile minimax trebuie abandonate, locul lor fiind luat de strategiile mixte. In multimea strategiilor mixte se va gasi o pereche care sa se bucure de caracterul de stabilitate al strategiilor minimax intalnit la jocurile cu punct sa. Aceste strategii se numesc strategii mixte optime si determina prin confruntarea lor punctul sa strategic al jocului.

Informatiile despre modul de comportare a adversarului se pot obtine usor in cazul repetarii partidelor, daca, de exemplu, unul din jucatori - respectand recomandarea de a mentine aceeasi strategie minimax - repeta in toate partidele.

Spre exemplu, in jocul Blotto avand matricea:

valoarea inferioara este a=0, iar valoarea superioara este b

Daca Blotto observa ca adversarul sau repeta strategia minimax B₃, recomandata acestuia de asigurarea unei pierderi de cel mult 3 puncte, desigur va abandona strategia sa maximin A₁, care-i garanteaza castigul zero, si va alege strategia A₃, care-i mareste castigul garantat pana la valoarea superioara a jocului. In cazul in care Kije nu ar repeta strategia minimax si ar repeta strategia B_l sau B₂, Blotto ar putea obtine un castig chiar mai mare decat valoarea superioara a jocului.

In mod analog, Kije nu se poate consola sa piarda 3 puncte, daca stie ca Blotto foloseste mereu strategia sa maximin A₁ si atunci va abandona strategia sa minimax si va folosi strategia B₂, care-l face sa nu mai piarda nimic.

Asadar, in cazul repetarii partidelor, in jocurile fara punct sa, manevrarea strategiilor se impune datorita caracterului de instabilitate al strategiilor minimax.

Pe de alta parte, sunt jocuri in care recomandarea strategiilor minimax nu este de nici un folos.

De exemplu, in jocul avand matricea:

valoarea inferioara este a= -l, iar valoarea superioara, b=1. Aceste valori sunt determinate de oricare din strategiile pure pe care le au cei doi parteneri.

Orice alegere facuta de jucatorul A nu-l poate face pe B sa castige mai mult decat l; orice alegere facuta de jucatorul B nu-i poate aduce lui A o pierdere mai mare decat l. Asadar, nici una din strategiile avute la dispozitie nu poate fi considerata mai avantajoasa decat alta, desi atat strategiile A₁ si A₂ cat si strategiile B_l si B₂ sunt strategii minimax. Desigur, in acest caz este usor de inteles ca folosirea numai a uneia din strategii este o greseala; singura solutie este data de alternarea neregulata a celor doua strategii, pentru ca un jucator sa nu poata ghici cu ce anume strategie a adversarului va avea de a face in fiecare partida.

Alternarea neregulata a strategiilor se impune sa se faca cu atata precautie, incat nu numai adversarul, dar nici chiar jucatorul care executa mutarea sa nu stie dinainte ce strategie va alege de fiecare data. Acest lucru s-ar putea realiza, de exemplu, alegand una din cele doua strategii in functie de cum apare stema in aruncarea unei monede sau cu ajutorul unui alt mecanism aleator.

B. Strategii mixte

Revenind la intrebarea pusa, daca prin alternarea strategiilor pure nu se poate obtine un castig mai mare decat valoarea inferioara a jocului, descoperim aspectul functional al strategiilor mixte, introduse de Borel in anul 1923.

Vom numi strategie mixta o strategie combinata din alternarea intamplatoare si cu probabilitati determinate a mai multor strategii pure. Rolul strategiei mixte este, pe de o parte, sa impiedice pe adversar sa descopere strategia aleasa, iar pe de alta parte, sa mareasca castigul garantat jucatorilor de valoarea inferioara sau superioara a jocului.

Notiunea de strategie mixta a aparut in conditiile jocurilor care se repeta prin mai multe partide. Prin partida se intelege o executare izolata a jocului. Totusi, concluziile obtinute in ipoteza repetarii partidelor pot fi folosite chiar pentru jocurile in care nu se poate juca decat o singura partida.

Precizam ca orice strategie pura constituie un caz particular de strategie mixta, in care toate strategiile pure se folosesc cu probabilitatea zero, in afara de una singura, care se foloseste cu probabilitatea unu.

Revenind la jocul:

sa urmarim ce ar realiza jucatorul A daca va alterna in mod intamplator strategiile sale cu probabilitatea 1/2, dupa cum apare stema sau banul in jocul de risca.

Daca jucatorul B a ales strategia B_l, valoarea medie a castigului jucatorului A este egala cu:

Daca jucatorul B a ales strategia B₂, valoarea medie a castigului ramane tot zero, deoarece:

Jocul fiind simetric, se obtine tot castigul zero si pentru jucatorul B, in ipoteza ca-si alterneaza strategiile sale cu aceeasi probabilitate.

O prima constatare este ca, recurgand la strategii mixte, jucatorii si-au ameliorat castigurile garantate de valoarea inferioara si valoarea superioara a jocului. Logic se pune intrebarea: jucatorii folosind strategiile pure cu alte probabilitati isi pot garanta castiguri superioare celor obtinute cand strategiile pure se manevreaza cu probabilitatea 1/2?

Pentru aceasta, presupunem ca jucatorul A foloseste strategia A₁ cu probabilitatea x, iar strategia A₂, cu probabilitatea 1-x (0 x 1). Scopul urmarit este de a gasi valoarea lui x care sa permita jucatorului A sa-si maximizeze castigul garantat.

In acest caz speranta de castig a jucatorului A devine:

x+(-1) (1-x) = 2x-1,

in ipoteza ca jucatorul B a ales strategia B_l si

(-1)x+1 (1-x) = 1-2x,

in ipoteza ca jucatorul B alege strategia B₂.

Singura solutie care fereste jucatorul A de la pierdere este x=1/2, deoarece daca x 1/2 una din cele doua sperante de castig devine negativa si jucatorul A risca sa piarda. Rezulta ca strategia mixta cea mai buna pentru jucatorul A este sa aleaga strategiile A₁ si A₂, fiecare cu probabilitatea 1/2; in acest fel are asigurat castigul egal cu zero si nu este supus nici unui risc. Faptul ca alternarea strategiilor pure se face cu probabilitatile ½, pentru determinarea celei mai bune strategii mixte nu este lege pentru jocurile 2 2; el este un rezultat propriu doar jocului studiat.

Pe viitor, in vederea desemnarii modului de folosire a fiecarei strategii pure si pentru ca exprimarea sa fie mai intuitiva, vom utiliza termenul de frecventa relativa in locul aceluia de probabilitate.

C. Frecvente relative

Se numeste frecventa relativa corespunzatoare lui x_i raportul dintre numarul de aparitii p_i ale valorii x_i si numarul N, in care N reprezinta numarul de experiente facute pe o variabila aleatoare X care poate lua valorile x₁, x₂, . , x_i, . ,x_n.

Vom nota f_i=p_i/N, de unde rezulta ca: .

D. Functia de plata

Valoarea medie sau speranta matematica a unei variabile X=(x_l, x₂, . , x_n) este data de:

In cazul unei matrice a castigurilor in care valoarea a_ij se realizeaza cu probabilitatea x_iy_j, vom nota speranta matematica a castigului jucatorului A cu:

Pentru jucatorul B aceasta speranta de castig este -E(X, Y). Am notat cu X=(x­₁,x₂, . ,x_m) si Y=(y₁,y₂, . ,y_n) frecventele relative cu care cei doi jucatori folosesc strategiile lor pure, in cazul repetarii partidelor. Va trebui ca:

In acest caz strategiile mixte S_A si S_B ale celor doi jucatori ar putea fi scrise (X,Y) sau

aparand vizibil frecventele cu care fiecare jucator isi alterneaza strategiile pure.

Multimea X, numita pe viitor strategia mixta X, este compusa asadar din frecventele relative cu care jucatorul A isi manevreaza strategiile sale pure, iar multimea Y, numita strategia mixta Y, este compusa din frecventele cu care jucatorul B isi manevreaza strategiile sale pure.

Scrierea X_i=(0, 0, . , 0, l, 0, . , 0), unde toate elementele sunt nule cu exceptia elementului care ocupa locul i, exprima faptul ca jucatorul A foloseste numai strategia pura A_i, astfel incat adesea vom nota aceasta strategie prin X=(i).

In mod analog, Y_j = (0, 0, . , 0, l, 0, . , 0)=(j) exprima faptul ca jucatorul B foloseste numai strategia sa B_j. Rezulta ca E(i, j)=a_ij.

Strategiile mixte optime vor fi notate in continuare cu X^* si Y^*.

Pentru jocul:

strategiile mixte optim sunt:

,

iar castigul realizat (v), numit si valoarea jocului este .

Cu alte cuvinte, daca jucatorul A va alterna strategiile sale in raportul 8/9, iar jucatorul B va alterna strategiile sale in raportul 10/7, si alternarea se va face fara nici o regularitate, adica in mod cu totul intamplator, valoarea jocului va fi 5/17.

Pentru jucatorul A, un mecanism aleator capabil sa indice care anume din cele doua strategii trebuie aleasa la fiecare partida ar putea fi o urna continand 17 bile identice, din care 8 bile sunt albe, iar 9 sunt negre. Din aceasta urna jucatorul A urmeaza sa extraga la fiecare partida cate o bila, alegand strategia A₁ daca a iesit bila alba, iar strategia A₂, daca a iesit bila neagra. Dupa fiecare extragere bila trebuie reintrodusa in urna.

Concluzii:

alternarea strategiilor mareste castigul garantat jucatorilor de strategiile minimax si maximin (valoarea inferioara si valoarea superioara a jocului). De aici ideea folosirii strategiilor mixte;

scopul urmarit este gasirea acelor frecvente cu care, daca se alterneaza strategiile, se ajunge ca minimul de castig garantat jucatorului A sa fie egal cu maximul de pierdere pentru jucatorul B. In acest exemplu am vazut ca nu experienta cu moneda este aceea care conduce la solutie; alternarea strategiilor trebuie facuta dupa alte criterii, si anume acelea care rezulta din:

.

Daca jucatorul A alterneaza strategiile sale cu frecventele relative 8/17 si 9/17, castigul sau minim garantat este de 5/17; de asemenea, pierderea jucatorului B nu poate fi mai mare decat 5/17.

jucatorul A nu poate sa castige mai mult decat 5/17, decat daca este informat ca jucatorul B nu intelege sa-si manevreze strategiile sale cu frecventele 10/17 si 7/17. In acest caz, daca jucatorul B ar manevra strategiile sale cu frecventele 1/2, 1/2, adica     Y= (1 /2, 1 /2), jucatorul A ar putea, renuntand la minimul garantat, sa obtina un castig de 1/2, jucand strategia A₂ care-i asigura acest castig. Dar jucatorul A nu vrea sa riste, intrucat s-ar putea ca informatiile sa nu fie exacte si jucatorul B sa joace strategia pura B_l, facandu-l astfel sa piarda 3, si de aceea joaca strategia optima.

Prin faptul ca jucatorii sunt considerati destul de inteligenti pentru a nu risca pierderi daca se abat de la recomandarile teoriei jocurilor, s-a ajuns la stabilirea punctului de echilibru strategic care determina valoarea jocului. In cazul exercitiului analizat valoarea jocului este v = 5/17.

Din modul cum a fost gasita valoarea aceasta, rezulta ca, indiferent cum ar alterna unul din jucatori strategiile sale pure, daca celalalt jucator le foloseste dupa strategia sa mixta optima, valoarea jocului ramane neschimbata, intrucat:

E(i,Y^*)=E(X^*,j)=E(X^*,Y^*)=v,

E(X,Y^*)=E(X^*,Y)=E(X^*,Y^*)=v,

Valoarea medie a castigului jucatorului A este:

Un aspect interesant al teoriei jocurilor, caruia trebuie sa i se acorde o atentie deosebita, il constituie jocurile cu mai multi parteneri (avand interese contradictorii), precum si jocurile fara suma nula. Avantajul studierii acestor jocuri rezida din urmatoarele consideratii:

- existenta mai multor parteneri ofera posibilitatea realizarii unor coalitii, cu obtinerea unor rezultate superioare;

- jocurile fara suma nula sunt interesante deoarece nu intotdeauna ceea ce pierde un jucator este castigat de celalalt, existand posibilitatea ca suma castigurilor celor doi jucatori sa fie mai mare decat 0.

Aplicatii militare ale teoriei jocurilor strategice

Inainte de a se fi pus bazele teoriei jocurilor, Borel, schitand modelele primelor jocuri, a intrezarit aplicatiile acestora in domeniul militar. Marile posibilitati de aplicare a teoriei jocurilor in domeniul militar se datoreaza caracterului conflictual al actiunilor de lupta.

De la inceput trebuie precizat ca nu se urmareste cu tot dinadinsul ca solutiile teoriei jocurilor sa fie substituite hotararilor comandantilor. Modelele de joc analizate nu pot cuprinde toate elementele corespunzatoare situatiilor complexe reale, intrucat numarul mare de strategii face aproape imposibila rezolvarea acestora. De aceea, din analiza modelelor de jocuri create se trag doar concluzii calitative, de care comandantii pot sau nu sa tina seama.

Teoria jocurilor vine in ajutorul comandantilor, in sensul ca se pot compara principii teoretice sau strategice, fara idei preconcepute asupra celor traditional acceptate. In acest sens, teoria jocurilor apare ca un instrument de cercetare in stiinta militara. Rezultatele aplicarii teoriei jocurilor in domeniul militar ar deveni evident mai pregnante daca ea s-ar folosi coordonat cu tehnica simularii, cunoscuta sub numele de jocuri de razboi.

Teoria jocurilor nu trebuie confundata cu jocurile de razboi, ale caror inceputuri pot fi cautate la sfarsitul secolului al XVII-lea, nici chiar atunci cand in jocurile de razboi sunt folosite calculatoare electronice. In general, jocurile de razboi simuleaza conditiile de razboi si constituie atat un mijloc de exersare sau de verificare a noilor idei despre comanda, cat si un mijloc de pregatire a operatiilor viitoare. Ignorand comportarea adversarului, teoria matematica a jocurilor recomanda hotarari rationale, prin folosirea unor elemente care influenteaza sansa. Ea confirma sau infirma intuitia. Desi jocurile de razboi reprezinta una din tehnicile abstracte folosite in studierea problemelor militare aceste tehnici nu au o origine comuna cu tehnica teoriei jocurilor.

Aplicatiile teoriei jocurilor la jocurile militare introduc un suflu matematic nou, de care nu se poate sa nu se tina seama. Prin folosirea teoriei jocurilor surprinderea, atat de importanta in actiunile de lupta, este asigurata intr-o masura apreciabila prin succedarea neasteptata de inamic a procedeelor actiunilor noastre.

Exemplu 1 Identificarea avionului propriu

a) Pe baza semnalelor - raspuns emise de avioanele aflate in zbor, un observator aflat la sol trebuie sa decida daca avionul chestionat este avion propriu sau inamic. Sa presupunem ca a fost adoptat un anumit cod pentru semnalizarea "propriu". Fie p probabilitatea, stabilita pe baza datelor anterioare, ca avionul interogat sa fie avion propriu. Pentru solutionarea jocului se introduc urmatoarele castiguri simbolice pentru observator:

a, daca identifica un avion propriu drept avion propriu;

b, daca va considera un avion propriu drept avion inamic;

c, daca identifica un avion inamic ca avion inamic;

d, daca va considera un avion inamic drept un avion propriu;

unde a>b, d, c>b, d.

Pentru observator sunt posibile urmatoarele patru strategii:

O_l=(P,I) P P;               I I;

O₂=(I,I) P I;                I I;

O₃=(I,P)            P I;                I P;

O₄=(P,P)           P P;               I P;.

S-a notat cu P P identificarea avionului propriu ca propriu, iar I P considerarea avionului inamic drept avion propriu. Inamicul are doua strategii posibile:

P, sa semnalizeze "avion propriu";

I, sa semnalizeze "avion inamic".

Matricea acestui joc de forma 4 2 este:

in care: q=1-p.

Elementele matricei sunt usor de calculat. Spre exemplu, daca observatorul alege strategia O₃=(I,P), iar inamicul foloseste strategia I, observatorul va considera avionul propriu drept avion inamic si va primi suma b cu probabilitatea p; totodata el va primi si suma d cu probabilitatea q, intrucat a considerat un avion inamic drept avion propriu.

Intrucat conform ipotezei strategia O₄ este dezavantajoasa fata de strategia O_l, iar strategia O₃ este dezavantajoasa fata de strategia O₂, matricea jocului se reduce la forma:

Din punctul de vedere al inamicului, intrucat strategia I este dezavantajoasa fata de strategia P, rezulta ca intotdeauna acesta va trebui sa semnalizeze "avion propriu".

Observatorul va folosi fie strategia O₁, fie strategia O₂, si anume:

daca , va folosi strategia O₁ si valoarea jocului va fi v=ap+dq;

daca , va folosi strategia O₂, in care caz valoarea jocului este v=bp+cq.

Aceasta varianta de joc corespunde faptului ca avioanele proprii folosesc un semnal necodificat, datorita caruia avioanele proprii emit totdeauna semnalul "propriu".

b) Daca semnalele sunt codificate astfel incat avioanele proprii in anumite zile folosesc semnalul "propriu", iar in alte zile folosesc semnalul "inamic", jocul capata o alta infatisare.

Pentru zilele in care este fixat semnalul "propriu" observatorul are numai doua strategii rationale (nedominate), si anume (P,I) si (I,I). Daca in aceste zile semnalul conventional este "inamic", atunci cele doua strategii pure rationale ale observatorului sunt (P,P) si (I,P). In aceasta varianta matricea jocului este:

Sa admitem ca probabilitatea cu care inamicul foloseste strategia pura I este y. Se deosebesc doua cazuri:

Cazul l. Daca , atunci , iar strategia optima a observatorului este:

;

Cazul 2. Daca , inamicul poate alege oricum strategiile sale; pentru observator orice combinatie a strategillor (I,I ) si (P,P) este optima, adica X^*=(0,a a,0), in caro 0 a

Exemplul 2 Alegerea si repartizarea rationala a armamentului

Avem la dispozitie trei feluri de armament, A_l, A₂, A₃, iar adversarul dispune de trei tipuri de avioane B_l, B₂, B₃. Sarcina noastra consta in doborarea avioanelor, iar a adversarului, sa fereasca avioanele de a fi lovite. Daca se intrebuinteaza armamentul A_l, avioanele B_l, B₂, B₃ vor fi lovite, respectiv cu probabilitatile 0,8; 0,2; 0,4; daca se intrebuinteaza armamentul A₂, probabilitatile devin 0,4; 0,5; 0,6, iar daca se intrebuinteaza armamentul A₃, probabilitatile sunt: 0,1; 0,7 si 0,3.

Se cere sa se elaboreze comenzile pentru comportarea cea mai logica.

Matricea acestui joc este :

Daca se noteaza cu x_l, x₂, x₃ frecventele relative cu care se vor folosi categoriile de armament, iar cu y_l, y₂, y₃ frecventele relative de folosire a avioanelor, sistemele corespunzatoare matricei jocului sunt:

Rezolvarea se reduce la cuplul de probleme duale din programarea liniara, si anume:

Sa se minimizeze functia f=X₁+X₂+X₃, in conditiile:

Sa se maximizeze functia: g=Y₁+Y₃+Y₃, in conditiile:

unde s-a notat:

Solutia celor doua probleme duale este:Y₁=3/32, Y₂=1/8, Y₃=0, g_max=7/32; X₁=1/32, X₂=6/32, X₁=0, f_min=7/32.

In concluzie:

Interpretarea rezultatelor este urmatoarea:

Armamentul A₃ nu trebuie folosit; de asemenea nici avioanele B₃. Tipurile de armament A₁ si A₂ trebuie utilizate in raportul 1/6. Avioanele B₁ si B₂ trebuie folosite in raportul 3/ Probabilitatea optima la care putem spera este de 0,457, ceea ce inseamna doborarea a circa 50% din numarul avioanelor inamice.

Exemplu 3 Atacul obiectivelor

Partea A ataca din aer un obiectiv, partea B il apara. Partea A are doua avioane, partea B are 4 complexe antiaeriene; fiecare avion este purtator al unui mijloc de nimicire; pentru ca obiectivul sa fie lovit este suficient ca la acesta sa ajunga un singur avion.

Pentru zborul catre obiectiv, avioanele partii A pot sa aleaga oricare din cele 4 directii D_l, D₂, D₃, D Partea B poate sa dispuna complexele sale pe oricare dintre directii; fiecare complex antiaerian acopera numai spatiul aferent directiei respective si nu si acela al directiilor vecine. Fiecare complex poate sa traga numai asupra unui singur avion; avionul asupra caruia se executa tragerea este nimicit cu probabilitatea 1. Partea A nu cunoaste unde sunt dispuse complexele antiaeriene; partea B nu cunoaste directia din care vin avioanele. Misiunea partii A este de a lovi obiectivul; misiunea partii B, de a nu permite lovirea acestuia. Se cer deciziile celor doua parti.

Partea A are doua strategii pure:

strategia A_l, care consta din trimiterea celor doua avioane, cate unul pe o anumita directie;

strategia A2, care consta in trimiterea ambelor avioane pe o aceeasi directie.

Partea B are 5 strategii pure :

strategia B₁, sa dispuna cate un complex pe fiecare directie;

strategia B₂, sa dispuna cate 2 complexe numai pe doua directii;

strategia B₃, sa dispuna doua complexe pe o directie si cate unul pe alte doua directii;

strategia B₄ sa dispuna trei complexe pe una din directii si un complex pe alta directie;

strategia B₅, sa dispuna toate cele 4 complexe pe o singura directie.

Matricea acestui joc 2 5 este:

Se noteaza cu x₁ frecventa relativa a misiunilor in care se tine seama de strategia A₁, iar cu x₂, frecventa relativa a misiunilor in care se tine seama de strategia A₂.

Sistemul care trebuie rezolvat este:

Solutia este:

Asadar, se recomanda ca din 8 misiuni, 3 sa foloseasca strategia A₁, iar 5 sa foloseasca strategia A₂. In acest fel se poate spera la o probabilitate de succes mai mare de 1/2. Din punctul de vedere al partii B, trebuie rezolvat sistemul:

in care y_j reprezinta frecventele relative corespunzatoare alegerii strategiilor B_j.

Solutia este:

desigur, cu acelasi v = 5/8.

In concluzie, nu trebuie folosite strategiile B₃, B₄ si B₅ iar strategiile B₁ si B₂ trebuie alternate in raportul 1/3. De altfel, din examinarea matricei jocului se vede ca strategiile B₄ si B₅ sunt cu totul dezavantajoase.