TEORIA JOCURILOR

Rodica Branzei

Contents

PREFATA 5

LISTA FIGURILOR 8

1 INTRODUCERE 91.1 Forme de reprezentare a jocurilor . . . . . . . . . . . . . . . . 101.2 Modelarea situatiilor decizionale interactive ca jocuri . . . . . 13

2 JOCURI NECOOPERATIVE 152.1 Jocuri ın forma normala si echilibre Nash . . . . . . . . . . . . 162.2 Jocuri ın forma extensiva si echilibre Nash perfecte pe subjoc 292.3 Forma extensiva si forma normala . . . . . . . . . . . . . . . . 372.4 Extensia mixta si echilibre Nash ın strategii mixte . . . . . . . 442.5 Informatie si jocuri necooperative . . . . . . . . . . . . . . . . 51

3 JOCURI COOPERATIVE 573.1 Jocuri cooperative ın forma strategica . . . . . . . . . . . . . . 583.2 Jocuri cooperative ın forma functiei caracteristice si samburele 613.3 Valoarea Shapley si AL-valoarea . . . . . . . . . . . . . . . . . 683.4 σ-valoarea si τ -valoarea . . . . . . . . . . . . . . . . . . . . . . 723.5 Nucleolul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753.6 Comunicare si informatie ın jocuri cooperative . . . . . . . . . 78

ANEXA A. Demonstratii privind Capitolul 2 81

ANEXA B. Demonstratii privind Capitolul 3 85

BIBLIOGRAFIE 87

3

PREFATA

Teoria jocurilor este o teorie matematica care se ocupa cu modelarea si ana-liza situatiilor decizionale interactive care implica conflict de interese indi-viduale sau de grup. Primele lucrari dedicate teoriei jocurilor sunt cele alelui Borel (1921) si von Neumann (1928), dar bazele teoriei matematice ajocurilor au fost puse prin monografia avand ca autori pe von Neumann siMorgenstern (1944). Dupa o perioada mai putin fructuoasa, teoria jocurilora cunoscut si cunoaste o perioada de ınflorire si recunoastere pe plan mon-dial. Exista un mare numar de cercetatori si cadre didactice ın domeniulteoriei jocurilor, iar numarul studentilor ın programe de masterat si doc-torat dedicate teoriei jocurilor sau frontierei dintre teoria jocurilor si altedomenii este ın crestere. Societatea de Teoria Jocurilor (”Game TheorySociety”) ısi largeste numarul de membri si a avut deja doua congrese mon-diale la: Bilbao (Spania), 2000; Marsilia (Franta), 2005. In 2005 a fost inau-gurat la Maastricht (Olanda) un ciclu de conferinte anuale la nivel europeanSING (Spain-Italy-Netherlands Games) care continua traditia conferinteloranuale dedicate teoriei jocurilor ın Italia si Spania ıncepand din 1983 (Ber-gamo (Italia)); SING2 a avut loc anul acesta la Foggia (Italia). In lunaiulie a fiecarui an, la Stony Brook (Statele Unite) se tine asa-numitul ”GameTheory Festival” unde se ıntalnesc cercetatori si studenti din lumea ıntreaga.Numeroase workshop-uri, conferinte si seminarii dedicate unor ramuri par-ticulare ale teoriei jocurilor au loc anual, bianual, trimestrial sau lunar ındiferite centre universitare sau de cercetare stiintifica. Numeroase manifes-tari stiintifice cu spectru larg (spre exemplu EJOR Conference) si cu spe-cific economic sau de informatica includ o sectie pentru teoria jocurilor.Exista un numar mare de jurnale internationale care publica articole de teoriajocurilor si aplicatii ale sale, dintre care mentionam aici: International Jour-nal of Game Theory, Games and Economic Behavior, European Journal ofOperational Research, Mathematics of Operations Research, MathematicalMethods of Operations Research, International Game Theory Review, TOP.

5

Recunoasterea importantei teoriei jocurilor este materializata de asemeneaprin acordarea unor Premii Nobel pentru Economie pentru contributii ındomeniul teoriei jocurilor: Nash, Harsanyi si Selten (1994), Vickrey (1996),Aumann si Schelling (2005). In ultimii ani, teoria jocurilor se bucura de oatentie crescanda ın informatica teoretica si aplicata pe plan mondial. LaFacultatea de Informatica a Universitatii ”Alexandru Ioan Cuza” din Iasi,studentii anului 2 pot opta pentru cursul de Teoria Jocurilor pentru o in-troducere ın domeniul teoriei jocurilor si al interactiunii dintre aceasta siinformatica. Prezentul material este conceput ca un suport de curs pentrustudentii sectiei Invatamant la Distanta, care a fost solicitat autoarei pe 8iulie 2006 pentru a fi gata pentru tipar la sfarsitul lunii august 2006.

Am organizat materialul ın trei capitole: Introducere, Jocuri necoope-rative si Jocuri cooperative. Am muncit din greu sa fac acest curs ”self-contained” si posibil de citit pentru studenti fara vreo cunoastere prealabilaa teoriei jocurilor. Accentul este pe exemple care ilustreaza folosirea mode-lelor matematice de joc si calcularea solutiilor jocurilor necooperative si coo-perative corespunzand unor situatii practice variate. Selectarea rezultatelor(leme, propozitii, teoreme) din cadrul teoriei jocurilor s-a facut pe baza ideiide a furniza studentilor fundamentele teoriei jocurilor fara a solicita un efortmatematic deosebit. Studentii interesati ın demonstratiile rezultatelor dincapitolele 2 si 3 le pot gasi ın Anexa A si, respectiv, Anexa B. Capitolul 2 anecesitat ıncorporarea ın text a unor figuri care au fost desenate manual deautoare si scanate pentru a crea fisiere cu extensia eps de inserat ın text ınlocul cel mai potrivit posibil. Timpul extrem de scurt pentru editarea acestuimaterial nu a permis desenarea tuturor figurilor cu software specific, ceea cejustifica diferenta de stil ın reprezentarea grafica. In prezentarea materialuluiam folosit termenul de ”jucator” (sau pronumele ”el”) pentru a referi oriceparticipant, indiferent de sex.

Acest suport de curs a fost pregatit ın timpul concediului meu de odihnaın Olanda si, datorita faptului ca a fost scris ın limba romana, nu a fost cititde nimeni altcineva, asa ca toate greselile ramase ın text sunt desigur alemele.

As vrea sa multumesc celor care au contribuit ıntr-un fel sau altul lapregatirea acestui suport de curs.

Apreciez mult ajutorul acordat de Annemiek Dankers si Ruud Hendrickxpentru scanarea figurilor si crearea fisierelor eps la Universitatea din Tilburg(Olanda). Un rol important pentru pregatirea acestui suport de curs l-a avutStef Tijs care mi-a pus la dispozitie biblioteca sa si a fost o gazda ideala, desi

6

de la bun ınceput a considerat ca e imposibil ca cineva sa scrie un curs deteoria jocurilor pentru studenti ıntr-un interval asa de scurt. Multumescdin suflet prietenei mele Elena Mocanu din Iasi care a muncit din greu ınweekend-urile lunii august si si-a folosit talentul sa faca din fisierele word,pdf si eps trimise de mine via e-mail prezentul suport de curs. As vrea deasemenea sa multumesc mamei mele, Elena Vatamanu, care a facut fatacaldurii tropicale din iulie-august ın Iasi fara ajutorul meu si a considerat cascrierea acestui curs pentru studenti e activitatea cea mai potrivita pentruconcediul meu de odihna ın strainatate. Multumesc fratelui meu, ValentinVatamanu, pentru ca a oferit suport mamei mele suplinind prezenta meaın Iasi ın aceasta vara fierbinte. Dedic acest suport de curs pentru teoriajocurilor fiicelor mele Oana, Dana si Roxana Branzei pe care le port ın sufletsi gand cu dragoste nemarginita oriunde si oricand.

31 august 2006 Rodica Branzei

Prefata la editia a doua

Prezenta editie pastreaza structura si continutul de baza ale editiei prece-dente dar contine variante ımbunatatite ale figurilor 2.6 (b), 2.10 (b), 2.11(a), 2.13, 2.14 (a) si (b), 2.15, 2.21 si 2.22; greselile de tiparire existente ıneditia precedenta sunt acum corectate si redactarea textului este pe alocuriımbunatatita.

10 septembrie 2007 Rodica Branzei

7

LISTA FIGURILOR

• Figura 2.1 Jocul ”Avantaj competitiv” p. 17

• Figura 2.2 Exemple de jocuri matriceale p. 18

• Figura 2.3 Jocul canalelor TV p. 19

• Figura 2.4 Exemple de jocuri cu suma variabila p. 19

• Figura 2.5 Echilibre Nash ale jocului ”Parteneriat ın afaceri” p. 22

• Figura 2.6 Diagrame cu sageti p. 23

• Figura 2.7 Un joc de alegere a rutei p. 24

• Figura 2.8 Eliminarea iterativa a strategiilor dominate p. 26

• Figura 2.9 Un joc cu ”imperfect recall” p. 30

• Figura 2.10 Subjocurile unor jocuri ın forma extensiva p. 31

• Figura 2.11 Jocuri ın forma extensiva cu mutari ale sansei p. 33

• Figura 2.12 Echilibru Nash perfect pe subjoc p. 35

• Figura 2.13 Forma extensiva a jocului parteneriatului p. 36

• Figura 2.14 Jocuri de piata ın forma extensiva p. 39

• Figura 2.15 Forma normala corespunzatoare jocurilor de piata p. 39

• Figura 2.16 Forma extensiva a unui joc de tip ”ultimatum” p. 40

• Figura 2.17 Forma normala a unui joc de tip ”ultimatum” p. 41

• Figura 2.18 Forma extensiva a unui joc de piata extins p. 42

• Figura 2.19 Forma normala a unui joc de piata extins p. 43

• Figura 2.20 Forme normale folosite ın inductia ınapoi p. 44

• Figura 2.21 Jocul ”Batalia sexelor” p. 50

• Figura 2.22 Jocul investitiei p. 54

1 INTRODUCERE

Jocurile de societate (table, jocuri de carti, sah), jocurile sportive (fotbal,baschet, tenis) si jocurile de divertisment (incluzand jocurile video) suntpracticate ın lumea ıntreaga. Elementele comune acestor jocuri sunt:

• Jucatorii (participantii la joc): persoane, sansa (norocul), natura, com-putere, echipe, firme, agenti, tari, etc.

• Regulile: specifica posibilitatile de comunicare ıntre jucatori, rezul-tatele acordurilor asupra jucarii jocului, informatia disponibila diferiti-lor jucatori si ceea ce este ”common knowledge”.

• Posibilitatile strategice ale jucatorilor: actiuni, decizii, strategii ce potfi folosite de catre fiecare jucator.

• Rezultatele posibile: plati psihologice (fericire, satisfactie, prestigiu),plati numerice sau de alta natura (utilitati).

• Preferintele jucatorilor asupra rezultatelor posibile.

Teoria jocurilor este stiinta care studiaza jocuri ıntr-un sens mult mai largdecat jocurile mentionate mai sus: un joc este orice situatie strategica guver-nata de reguli, cu un rezultat bine definit, caracterizat prin interdependentastrategica a jucatorilor, care au relatii de preferinta asupra rezultatelor posi-bile. Negocierile economice si politice, afacerile si multe alte domenii fur-nizeaza numeroase exemple de jocuri. Teoria jocurilor este o ramura amatematicii. Ea foloseste rezultate si metode din alte ramuri ale mate-maticii cum sunt: algebra, geometria, analiza matematica, probabilitati sistatistica, matematici discrete, ecuatii, fundamentele matematicii. Teoriajocurilor interactioneaza cu multe alte stiinte si domenii fundamentale alevietii: stiinte economice, management, administrarea afacerilor, drept, psi-hologie sociala, stiinte politice, biologie, sociologie, informatica, cercetari

9

operationale. Interactiunea ıntre teoria jocurilor si informatica se refera laramuri variate ale informaticii, cum sunt: proiectarea si analiza algoritmilor,inteligenta artificiala, logica si decidabilitate, teoria complexitatii, calcul pa-ralel si distribuit, baze de date, retele de calculatoare, internet.

Teoria jocurilor este o teorie matematica care se ocupa cu modelarea sianaliza situatiilor de interactiune ce implica conflict de interese individualesau de grup. Borel (1921), John von Neumann (1928) si John von Neumannsi Oskar Morgenstern (1944) au pus bazele teoriei matematice a jocurilor ca oteorie a modelarii si a solutiilor. Exista multe clasificari ale modelelor teore-tice de joc. Din punctul de vedere al naturii intereselor jucatorilor distingemıntre teoria jocurilor necooperative (cu accent pe interesele individuale) siteoria jocurilor cooperative (cu accent pe interesele de grup). Ambele tipuride modele, jocuri necooperative si cooperative, se bazeaza pe presupuneri va-riate privind: rationalitatea jucatorilor (jucatori perfect rationali sau jucatoricu rationalitate limitata); ceea ce este ”common knowledge” pentru jucatori;informatia (simetrica sau asimetrica) asupra situatiei analizate disponibilajucatorilor.

1.1 Forme de reprezentare a jocurilor

Cele mai utilizate forme pentru a reprezenta jocuri sunt: forma extensiva,forma normala (sau strategica) si forma coalitionala.

Forma extensiva a unui joc este un arbore ale carui noduri reprezintapozitiile posibile ale jocului si ale carui arce (ramuri) reprezinta mutarile posi-bile pentru participantii la joc. Jocul se desfasoara ca o alternare de mutariale participantilor la joc (jucatorii), motiv pentru care un joc ın forma exten-siva este numit un joc dinamic. Fiecare nod neterminal are atasata eticheta(de identificare a) jucatorului care trebuie sa ia o decizie (sa faca o mutare)ın acea pozitie a jocului. Adesea etichetele nodurilor sunt 1, 2, ..., n. Nodurileterminale contin vectorul platilor jucatorilor daca jocul se termina ın aceapozitie. Fiecare arc are atasata eticheta unei actiuni. Reprezentarea ın formaextensiva a unui joc ilustreaza desfasurarea ın timp a jocului. Unele mutaripot fi aleatoare (mutari ale sansei sau naturii); pentru asemenea mutari existadistributii de probabilitate bine-definite care sunt folosite ca etichete pentruarcele ce ies din nodurile apartinand sansei. Nodurile de decizie ale jucatorilor

10

din arborele jocului sunt partitionate ın multimi de informatie. O multime deinformatie pentru un jucator consta din acele pozitii de joc ın care jucatoruls-ar putea afla atunci cand este randul sau sa faca o mutare. In reprezentareaın forma extensiva a jocului, multimile de informatie ale jucatorilor carecontin mai mult decat un nod de decizie sunt marcate grafic, spre exemplucu contur de tipul − − −. Evident, pentru o anumita multime de informatie,numarul deciziilor posibile pentru acel jucator trebuie sa fie acelasi pentrutoate nodurile apartinand acelei multimi. Daca toate multimile de informatiea tuturor jucatorilor constau dintr-un singur nod, aceasta ınseamna ca oricejucator cunoaste perfect situatia ın care se afla atunci cand trebuie sa aleagao actiune, motiv pentru care jocul se numeste joc cu informatie perfecta.Intr-un joc cu informatie perfecta fiecare jucator cunoaste ıntreaga istorie dedesfasurare a jocului pana ın momentul cand trebuie sa faca o mutare. Sahuleste un joc cu informatie perfecta. Daca cel putin un jucator nu cunoastetoata istoria de desfasurare a jocului, atunci jocul este un joc cu informatieimperfecta. Jocurile de carti (bridge, poker) sunt jocuri cu informatie imper-fecta. Presupunerea de rationalitate a participantilor la joc implica luareadeciziilor personale astfel ıncat plata individuala sa fie maximizata sau cos-tul individual sa fie minimizat. Daca jocul nu are mutari ale sansei si platilejucatorilor sunt cunoscute cu certitudine avem un joc dinamic cu informatiecompleta si perfecta. Daca exista mutari ale sansei si platile din nodurile ter-minale ale arborelui sunt cunoscute de toti jucatorii, atunci platile de primitde catre jucatori depind de distributia de probabilitate a oricarei mutarialeatoare. In acest caz se accepta presupunerea ca jucatorii actioneaza astfelıncat sa-si maximizeze plata asteptata (medie). Plata asteptata de un jucatoreste o medie ponderata prin distributia de probabilitate corespunzatoare aplatilor din nodurile terminale. Spre exemplu, ıntr-un joc cu aruncarea uneimonede, daca un jucator obtine plata 2 ın caz de ”pajura” si plata 6 ın cazde ”cap”, plata ”asteptata” de jucator este 1/2 · 2 + 1/2 · 6 = 4. O strategiea unui jucator este un plan complet de actiune de-a lungul arborelui jocului,adica o lista ordonata a mutarilor jucatorului (cate una pentru fiecare dinmultimile sale de informatie) de-a lungul arborelui jocului, de la nodul initialcatre nodurile terminale. Analiza unui joc ın forma extensiva are ca scop de-terminarea strategiilor optimale ale jucatorilor si a platilor corespunzatoare.

11

Conceptul de solutie folosit pentru determinarea strategiilor optimale ıntr-unjoc ın forma extensiva este acela de echilibru Nash perfect pe subjoc (Selten,1975).

Forma normala a unui joc listeaza pentru fiecare jucator strategiile (pure)disponibile si platile de obtinut pentru fiecare combinatie de strategii (pure),cate una pentru fiecare jucator (profil strategic). Se presupune ca jucatoriiısi aleg strategiile simultan si independent, motiv pentru care un joc ın formanormala este numit un joc static. Totusi, jucarea repetata de un numar finitsau infinit de ori a unui joc ın forma normala este un joc dinamic. Analizaunui joc ın forma normala are ca scop determinarea strategiilor optimale alejucatorilor si a platilor corespunzatoare. Conceptul de solutie fundamentalpentru forma normala a unui joc este acela de echilibru Nash (Nash, 1950a).Forma extensiva a unui joc cu informatie completa (si perfecta sau imper-fecta) si fara mutari ale sansei genereaza o forma normala unic definita ajocului, ın care platile jucatorilor sunt cele din nodurile terminale ale arbore-lui jocului. Forma extensiva a unui joc cu informatie completa si mutari alesansei genereaza de asemenea o forma normala unica, dar platile jucatorilorın forma normala a jocului sunt platile asteptate (medii) din jocul ın formaextensiva. Forma normala a unui joc poate genera mai multe jocuri ın formaextensiva. Orice echilibru Nash perfect pe subjoc al jocului ın forma ex-tensiva este un echilibru Nash al jocului corespunzator ın forma normala.In schimb, numai un echilibru Nash ”credibil” al jocului ın forma normalaeste un echilibru Nash perfect pe subjoc pentru o forma extensiva generatade forma normala a jocului. Forma normala si forma extensiva sunt un buncandidat pentru reprezentarea unei situatii cu conflict de interese individualeatunci cand nu sunt permise acorduri preliminare ıntre jucatori, desi comuni-carea ıntre jucatori ınainte de ınceperea jocului nu este ıntotdeauna interzisa.Daca acordurile preliminare (si eventual platile laterale) sunt permise atunciforma coalitionala a jocului este un bun candidat pentru descrierea uneisituatii decizionale interactive ca un joc.

Forma coalitionala a unui joc, cunoscuta si sub numele de forma functieicaracteristice, este o descriere foarte generala a unei situatii, care specificadoar suma (maxima) ce poate fi obtinuta (pe cont propriu) de fiecare grupde jucatori (coalitie), incluzand coalitiile formate dintr-un singur jucator simarea coalitie (grupul format din toti participantii la joc). Analiza formeicoalitionale a unui joc are ca scop determinarea coalitiei care se va forma

12

si a modului ın care valoarea acelei coalitii va fi distribuita ıntre membriisai. Adesea, se presupune ca marea coalitie se formeaza si problema derezolvat este ca jucatorii sa cada de acord asupra modului de alocare a valoriiobtinute de marea coalitie ıntre membrii sai. O regula de alocare corespundeunui anumit concept de solutie din teoria jocurilor cooperative. Exista maimulte concepte de solutie a caror atractivitate este prezentata ın termenide proprietati caracteristice (caracterizare axiomatica). Samburele, valoareaShapley, τ -valoarea si nucleolul sunt concepte de solutie fundamentale pentrujocuri cooperative ın forma coalitionala. Forma coalitionala a unui joc sepoate construi pornind de la forma normala a jocului sau direct, pe bazaanalizei situatiei interactive ın studiu.

1.2 Modelarea situatiilor decizionale interactiveca jocuri

Teoria jocurilor a aparut din necesitatea de a oferi suport pentru optimizarealuarii deciziilor ın situatii conflictuale. Multe situatii practice sau din altestiinte pot fi analizate si solutionate folosind modelele existente de joc siconceptele de solutie disponibile sau introducand noi modele de joc si/saunoi concepte de solutie. Folosirea teoriei jocurilor ın aplicatii presupune douaetape: o etapa de modelare si o etapa de (analiza si) rezolvare a modelului dejoc ales. Solutia obtinuta este oferita ca varianta optimala, din punctul devedere al teoriei jocurilor, pentru rezolvarea problemei studiate.

Modelarea unei situatii cu conflict de interese consta ın construirea unuimodel formal de joc, ın sensul teoriei jocurilor, pornind de la o descriere nefor-mala a situatiei, adesea narativa. Pentru a alege cel mai potrivit model teo-retic de joc, modelatorul va trebui sa analizeze situatia respectiva din punctulde vedere al tipului predominant al conflictului de interese existent (intereseindividuale sau de grup) si al regulilor privind comunicarea si informatiadisponibila diferitelor parti implicate si capacitatea lor de rationare. Deciziamodelatorului priveste de asemenea forma cea mai adecvata de reprezentarea jocului. Modelele necooperative si cooperative de joc sunt complementare,oferind modelatorului o paleta larga de posibilitati. Un criteriu fundamen-tal pentru alegerea tipului modelului de joc, necooperativ sau cooperativ, ılconstituie tipul comunicarii si al acordurilor de comportare strategica per-mise (sau interzise) participantilor la joc. Daca acorduri ferme ale jucatorilor

13

(”binding agreements”) ınainte de ınceperea jocului nu sunt permise, atuncimodelul folosit va apartine ın principiu teoriei necooperative a jocurilor. Inacest caz, modelatorul va trebui sa aleaga ıntre forma extensiva si forma nor-mala (strategica) pentru a descrie formal situatia studiata. Forma extensivaprezinta avantajul unei modelari mai usoare si al unei analize mai simple, darrezolvarea jocurilor mari este de obicei dificila si uneori imposibila. Formanormala are avantajul unei rezolvari mai simple; ea este folosita mult pentrurezolvarea jocurilor de doua persoane. Daca participantii la joc au posibilitatilargi de comunicare (incluzand deseori si posibilitatea efectuarii de plati late-rale), atunci un model din teoria cooperativa a jocurilor va fi preferabil. Maideparte, modelatorul are ınca de decis asupra tipului de model de joc coo-perativ folosit si va alege forma cea mai adecvata de reprezentare a situatieianalizate. Forma coalitionala este folosita adesea.

Incheiem introducerea ın teoria jocurilor cu o motivatie pentru studiulacestei teorii. Cunoasterea modelelor teoriei jocurilor si a conceptelor desolutie specifice diferitelor modele furnizeaza suport pentru ımbunatatirealuarii deciziilor strategice ın viata de zi cu zi, ın profesie si ın afaceri. Des-crierea unui numar relativ mare de situatii conflictuale variate, modelarealor ca jocuri si rezolvarea jocurilor construite (pentru a furniza solutii pentrusituatia conflictuala supusa studiului) creaza abilitati de aplicare a teorieijocurilor ın practica. Cunoasterea teoriei jocurilor poate de asemenea ımbu-natati performanta ın jocuri de societate, jocuri de divertisment si jocuri denoroc, ridicand astfel calitatea vietii ın timpul liber. In plus, teoria jocurilorsi interactiunea sa cu alte discipline, ın particular cu informatica, constitueun domeniu de cercetare activ prin programe de masterat si doctorat la multeuniversitati din lumea ıntreaga, oferind un domeniu interesant pentru conti-nuarea studiilor. Aprecierea teoriei jocurilor pe plan mondial este confirmatade premiile Nobel pentru Economie obtinute pentru contributii ın domeniulteoriei jocurilor: Nash, Harsanyi, Selten (1994), Vickrey (1996), Aumann siSchelling (2005).

14

2 JOCURI NECOOPERATIVE

In teoria jocurilor exista doua modele de baza de jocuri necooperative,jocuri ın forma normala (sau strategica) si jocuri ın forma extensiva. Unjoc ın forma normala este o descriere statica si concisa a unei situatii con-flictuale ın care jucatorii ısi aleg simultan si independent strategiile lor (puresau mixte) si primesc plati determinate de acele strategii. Conceptul desolutie fundamental pentru jocurile ın forma normala (strategica) este acelade echilibru Nash. Jocurile ın forma normala (cu informatie completa) siconceptul de echilibru Nash (ın strategii pure) sunt introduse ın paragraful2.1. Acest paragraf trateaza de asemenea doua clase speciale de jocuri strate-gice, jocurile de tip potential si congestie, care au ıntotdeauna echilibre Nash(ın strategii pure); ele joaca un rol important ın interactiunea dintre teoriajocurilor si informatica. Un joc ın forma extensiva este o descriere dinamicadetaliata a unei situatii conflictuale, specificand cine si cand face o ”mu-tare” (adica ia o decizie sau actiune) ın joc si care sunt optiunile disponibilefiecarui jucator de fiecare data cand are dreptul la o ”mutare”. Concep-tul de solutie fundamental pentru jocuri ın forma extensiva (cu informatiecompleta) este acela de echilibru Nash perfect pe subjoc. Jocurile ın formaextensiva cu informatie completa si conceptul de echilibru Nash perfect pesubjoc sunt introduse ın paragraful 2.2. Paragraful 2.3 trateaza legaturaıntre forma extensiva si forma normala si relatia dintre conceptele corespun-zatoare de echilibru Nash. Extensia mixta a unui joc ın forma normala siconceptul de echilibru Nash ın strategii mixte sunt introduse ın paragraful2.4, care trateaza de asemenea rezolvarea jocurilor matriceale si bimatriceale(ın strategii mixte). Capitolul se ıncheie cu o vedere de ansamblu asuprajocurilor necooperative analizand rolul informatiei ın modelele teoriei ne-cooperative a jocurilor (informatie completa versus informatie incompleta,informatie perfecta versus informatie imperfecta, informatie simetrica versusinformatie asimetrica).

15

2.1 Jocuri ın forma normala si echilibre Nash

Un joc necooperativ ın forma normala (strategica) este un model al uneisituatii ın care sunt implicati n participanti cu interese proprii conflictuale,jucatorii, ale caror actiuni posibile sunt cunoscute de catre toti jucatorii.Fiecare jucator alege planul sau de actiune (o data si pentru totdeauna ınsituatia data) si toate deciziile jucatorilor sunt facute simultan (adica atuncicand un jucator alege planul sau de actiune, el nu este informat asupra planu-lui de actiune a nici unui alt jucator). Jucatorii aleg simultan si independentactiunile lor si apoi primesc plati care depind de combinatia strategiilor alese.Presupunem ca platile sunt deterministe si cunoscute de toti jucatorii. Unjoc necooperativ ın forma normala consta din trei elemente. Intai, o multimeN = {1, 2, ..., n} a jucatorilor. Apoi, fiecare jucator i ∈ N are o multimede actiuni (strategii pure) Xi disponibile pentru el si o functie de plata (sau

utilitate) Ki :∏j∈N

Xj −→ IR, care descrie platile jucatorului i rezultate din

toate alegerile posibile de strategii de catre jucatori (cate una pentru fiecarejucator), adica pentru fiecare profil strategic x = (x1, x2, ..., xn).

Un joc necooperativ ın forma normala (strategica) este un triplet〈N, {Xi}i∈N , {Ki}i∈N〉, unde N este multimea jucatorilor si, pentru fiecarei ∈ N, Xi este multimea actiunilor sau strategiilor pure ale jucatorului i,

iar Ki :∏j∈N

Xj −→ IR, este functia de plata (sau functia de utilitate) a

jucatorului i.

Un element din∏j∈N

Xj este un profil strategic; el se mai numeste rezultat

(posibil) al jocului. Uneori notam un profil strategic (x1, ..., xi, ..., xn) cu

(xi, x−i), unde x−i ∈ X−i =∏

j∈N\{i}Xj.

Un joc 〈N, {Xi}i∈N , {Ki}i∈N〉 e un joc finit daca N este o multime finitasi multimile X1, ..., Xn sunt multimi finite. Un joc finit de doua persoane vafi desemnat ın cele ce urmeaza prin 〈X, Y,K,L〉 . Un asemenea joc este deobicei reprezentat printr-un tablou ale carui linii sunt ınsotite de etichetelestrategiilor jucatorului 1 si ale carui coloane sunt ınsotite de etichetele strate-giilor jucatorului 2, iar la intersectia fiecarei linii cu o coloana se gasesteo pereche de numere, reprezentand plata jucatorului 1 urmata de platajucatorului 2 pentru combinatia de strategii (pure) corespunzatoare liniei

16

si coloanei respective. Daca ıntr-un joc finit cu doi jucatori etichetam strate-giile fiecarui jucator astfel ıncat X = {1, .., m} si Y = {1, .., n}, atunci joculeste descris printr-o (bi)matrice (K(i, j), L(i, j))i=1,...,m;j=1,...,n, unde K(i, j)si L(i, j) reprezinta, respectiv, plata obtinuta de jucatorul 1 si de jucatorul2 ın situatia ın care jucatorul 1 alege strategia i si jucatorul 2 alege strategiaj. Un joc strategic finit de doua persoane se numeste un joc bimatriceal.Etichete explicite pot fi atasate liniilor si coloanelor bimatricii ın cazul unuijoc bimatriceal. Exemplul 2.1 modeleaza o situatie de interactiune strategicalegata de avantaj competitiv ca un joc bimatriceal, reprezentat ın Figura 2.1.

Exemplul 2.1. (Avantaj competitiv) Doua companii cu acelasi tip de acti-vitate trebuie sa decida simultan si independent daca sa introduca o tehnolo-gie noua (strategia I) sau nu (strategia N). Daca ambele companii introductehnologia noua sau ambele decid sa nu o introduca, profitul curent al fiecareicompanii nu este afectat. Daca ınsa o companie decide sa introduca nouatehnologie, iar cealalta companie nu o introduce, atunci profitul companieicare adopta noua tehnologie va creste cu a unitati valorice (spre exemplumiliarde de lei), ın timp ce profitul curent al celeilalte companii va ınregistrao scadere de a unitati valorice.

I NI 0, 0 a,−aN −a, a 0, 0

Figure 2.1: Jocul ”Avantaj competitiv”

Cand cel putin unul dintre jucatori are infinit de multe strategii posibile, joculnu este finit. Exemplul 2.2 modeleaza o situatie strategica de parteneriat ınafaceri ca un joc infinit de doua persoane.

Exemplul 2.2. (Parteneriat ın afaceri) Doi prieteni doresc sa-si deschidaımpreuna o afacere si trebuie sa decida simultan si independent asupra nivelu-lui de efort investit ın aceasta afacere. Presupunem ca nivelul de efort poatefi ın intervalul [0, 4], iar profitul obtinut de fiecare dintre ei depinde de nivelulde efort investit de ambii prin functiile de plata K : [0, 4]×[0, 4] −→ IR siL : [0, 4]×[0, 4] −→ IR, definite prin:

K(x, y) = 2(x + y + cxy)− x2, L(x, y) = 2(x + y + cxy)− y2,

17

unde c ∈ (0, 1

4

)este o constanta care masoara complementaritatea muncii

celor doi parteneri de afaceri. Un echilibru Nash corespunzand maximizariifunctiilor de plata individuale este x∗ = y∗ = 1/(1 − c). Acesta se obtinerezolvand ın raport cu x si y sistemul format din ecuatiile ∂K(x, y)/∂x = 0,∂L(x, y)/∂y = 0. Totusi, daca ambii jucatori urmaresc maximizarea functieide plata totale, K + L, echilibrul Nash este x = y = 2/(1− 2c) < 1/(1− c).Astfel, ın cazul ın care cei doi parteneri de afaceri au un tel comun, un nivelmai mic de efort e necesar din partea fiecaruia. Echilibrul Nash (x∗, y∗) esteilustrat ın Figura 2.5.

Un joc finit 〈N, {Xi}i∈N , {Ki}i∈N〉 este un joc cu suma nula daca∑i∈N

Ki=0.

Un joc finit de doua persoane cu suma nula satisface L = −K si, de aceea,poate fi reprezentat printr-un tablou sau o matrice, [K(i, j)]i=1,...,m;j=1,...,n,continand doar platile pentru jucatorul 1 (primite de la jucatorul 2). Unastfel de joc se numeste joc matriceal. Un joc cu suma nula pentru douapersoane este de asemenea cunoscut sub numele de joc strict competitiv,ıntrucat cooperarea dintre jucatori este exclusa. Jocul din Figura 2.1 este unjoc pur competitiv; ın Figura 2.2 (a) gasiti descrierea sa (mai simpla) ca unjoc matriceal. Sahul este un joc finit de doua persoane cu suma nula: candjucatorul 1 castiga, el obtine plata 1 iar jucatorul 2 obtine plata −1; candjucatorul 2 castiga, acesta obtine plata 1, iar jucatorul 1 obtine plata −1; ıncaz de remiza ambii jucatori obtin plata 0.

0 a−a 0

2 2 1 40 2 5 34 2 3 2

6 2 14 3 50 1 6

(a) (b) (c)

Figure 2.2: Exemple de jocuri matriceale

Un joc strategic 〈N, {Xi}i∈N , {Ki}i∈N〉 este un joc cu suma constanta daca∑i∈N

Ki = C, unde C este o constanta. Orice joc cu suma constanta poate fi

transformat ıntr-un joc cu suma nula, asa cum ilustram ın Exemplul 2.3 siFigura 2.3.

18

Exemplul 2.3. (Jocul canalelor TV) Un canal de televiziune specializat ıntransmisiuni sportive si un canal de televiziune specializat ın telenovele sperasa-si largeasca audienta la telespectori daca ambele vor transmite atat sportcat si telenovele. Sondajele efectuate permit evaluarea ın procente a audienteicelor doua canale ın randurile telespectatorilor, conform cu Figura 2.3 (a),ın care situatia descrisa este modelata ca un joc cu suma constanta. Figura2.3 (b) contine jocul cu suma nula echivalent jocului cu suma constanta.

T ST 55%, 45% 52%, 48%S 50%, 50% 45%, 55%

T ST 10%,−10% 4%,−4%S 0%, 0% −10%, 10%

(a) (b)

Figure 2.3: Jocul canalelor TV

Cele mai multe jocuri bimatriceale nu sunt ınsa cu suma nula sau con-stanta; acestea sunt cunoscute sub numele de jocuri cu suma variabila. Figura2.4 contine exemple de jocuri cu suma variabila care vor fi utilizate ulterior.

3, 1 0, 00, 0 1, 3

5, 5 0, 1010, 0 1, 1

2, 2 0, 00, 0 1, 2

(a) (b) (c)

Figure 2.4: Exemple de jocuri cu suma variabila

In cele ce urmeaza, prin jocuri bimatriceale vom referi numai jocurilede doua persoane cu suma variabila. Intrucat ıntr-un astfel de joc ambiijucatori pot castiga sau ambii jucatori pot pierde, ın acelasi timp, depinzandde actiunile luate de cei doi jucatori, un joc bimatriceal 〈X, Y, K, L〉 poate fireprezentat ca o pereche de jocuri matriceale, K si L, ambii jucatori urmarindacelasi scop (maximizarea castigului propriu sau minimizarea costului pro-priu).

Conceptul de solutie de baza pentru jocuri ın forma strategica este celde echilibru Nash (Nash, 1950a). Un echilibru Nash este un profil strategiccare este stabil ın sensul ca nici-un jucator nu-si poate ımbunatati platadeviind unilateral de la acest profil strategic prin alegerea unei alte strategii.

19

Elementele multimilor Xi se mai numesc strategii pure pentru a le distinge destrategii mixte, care sunt distributii de probabilitate pe multimea strategiilorpure ale unui jucator. Acest paragraf se refera ın exclusivitate la echilibreNash ın strategii pure, numite si echilibre Nash pure. Echilibrele Nash ınstrategii mixte, numite si echilibre Nash mixte, sunt definite folosind extensiamixta a unui joc ın forma normala; ele vor fi studiate ın paragraful 2.4.

Profilul strategic x = (x1, ..., xn) este un echilibru Nash (pur) al jocului〈N, {Xi}i∈N , {Ki}i∈N〉 daca pentru toti i ∈ N si toti xi ∈ Xi avem

Ki(xi, x−i) ≤ Ki(xi, x−i).

Exemplul 2.4. Consideram jocul ın forma normala reprezentat ın Figura2.1, unde a > 0. Combinatia de strategii (I, N) nu este un echilibru Nash,deoarece jucatorul 2 ısi poate ımbunatati plata (de la −a la 0) prin deviereunilaterala, alegand strategia I. Combinatia de strategii (I, I) este un echili-bru Nash deoarece prin deviere unilaterala oricare dintre jucatori obtine plata−a care e mai mica decat 0.

Un joc care are cel putin un echilibru Nash se numeste un joc determi-nat. Daca un joc matriceal 〈X,Y,K,−K〉 este un joc determinat atuncispunem ca jocul are ”punct sa”; plata jucatorului 1 ıntr-un echilibru Nashse numeste valoarea jocului si se noteaza cu v (〈X,Y,K,−K〉) , sau v(K). Incazul existentei mai multor echilibre Nash pentru un joc matriceal, fiecareechilibru Nash are aceeasi valoare si echilibrele Nash sunt interschimbabile.

Teorema 2.5. Fie 〈X, Y, K,−K〉 un joc de doua persoane cu suma nula sifie (x1, y1) si (x2, y2) echilibre Nash ale jocului. Atunci:

(i) (Proprietatea de interschimbare) (x1, y2) si (x2, y1) sunt de asemeneaechilibre Nash;

(ii) (Proprietatea platilor egale) K(xi, yj)=K(x1, y1) pentru toti i,j∈{1, 2}.

Intr-un echilibru Nash al unui joc bimatriceal, fiecare jucator ısi maxi-mizeaza utilitatea proprie dat fiind ceea ce face celalalt jucator. O strategiex ∈ X pentru care exista y ∈ Y astfel ca (x, y) este un echilibru Nash senumeste strategie optimala pentru jucatorul 1. Analog se defineste o strate-gie optimala pentru jucatorul 2. O pereche de strategii optimale corespundeıntotdeauna unui echilibru Nash al jocului. Daca un joc are un singur echili-bru Nash, el se numeste un joc strict determinat. Intr-un joc matriceal (strict)determinat, cunoasterea de catre un jucator a strategiei celuilalt jucator nu-l

20

determina pe jucator sa-si schimbe planurile proprii. In cazul multiplicitatiiechilibrelor Nash ale unui joc bimatriceal determinat, platile jucatorilor potfi diferite pentru echilibre Nash distincte. Din acest motiv, un jucator poateprefera un echilibru Nash iar celalalt jucator poate prefera un alt echilibruNash, caz ın care rezultatul jocului nu va fi un echilibru Nash. Chiar si ıncazul unui echilibru Nash unic, acest rezultat al jocului poate fi nesatisfacator.

In orice joc de doua persoane cu suma nula putem determina valoareainferioara si valoarea superioara a jocului definite prin

v(X, Y,K,−K) := supx∈X

infy∈Y

K(x, y);

v(X, Y,K,−K) := infy∈Y

supx∈X

K(x, y).

Are loc relatia v(X,Y,K,−K) ≤ v(X, Y, K,−K) pentru orice joc〈X, Y, K,−K〉.

Valoarea inferioara si superioara pentru un joc de doua persoane cu sumanula pot fi privite ca nivele de securitate ale jucatorilor, ıntrucat reprezintasuma minima pe care jucatorul 1 si-o poate garanta ın jocul respectiv si, res-pectiv, suma maxima pe care jucatorul 2 ar putea-o pierde ın jocul respectiv,indiferent de actiunea aleasa de adversarul sau (sub presupunerea ca acestaeste rational si inteligent). Daca valoarea superioara si valoarea inferioara aunui joc matriceal au aceeasi valoare, atunci jocul are punct sa. Un punctsa are cea mai mica valoare ın linie (astfel ıncat jucatorul 2 nu poate castigaprin schimbarea coloanei) si cea mai mare valoare ın coloana (deci jucatorul1 nu poate castiga prin schimbarea liniei). Daca un joc are punct sa, ambiijucatori ar trebui sa aleaga strategii care duc la acest punct. Jocul dinFigura 2.2. (c) este strict determinat: punctul sa este 3 si echilibrul Nash aljocului este profilul strategic (linia 2, coloana 2). Pentru jocuri determinatede doua persoane, determinarea punctelor de echilibru Nash se poate facepe baza considerarii multifunctiilor ”cel mai bun raspuns” ale jucatorilor.Multifunctia cel mai bun raspuns (ın strategii pure) a unui jucator asociazala fiecare dintre strategiile pure ale celuilalt jucator, multimea strategiilorpure care ar putea fi optimale (cel mai bun raspuns) pentru acel jucator ınacea situatie. Un echilibru Nash pur este un profil strategic care consta dinstrategii pure care sunt cel mai bun raspuns la cel mai bun raspuns. O metodaanalitica pentru determinarea functiilor cel mai bun raspuns pentru jocuriinfinite de doua persoane este prezentata dupa Teorema 2.12. Din punct devedere grafic, echilibrele Nash pure ale unui astfel de joc sunt punctele de

21

intersectie ale graficelor functiilor cel mai bun raspuns. Figura 2.5 ilustreazaaceasta pentru jocul ”Parteneriat ın afaceri” din Exemplul 2.2.

Figure 2.5: Echilibre Nash ale jocului ”Parteneriat ın afaceri”

O diagrama cu sageti poate fi folositoare pentru determinarea echilibrelorNash (pure) pentru jocuri finite de doua persoane. Pentru fiecare jucator seconsidera pe rand toate strategiile celuilalt jucator. Pentru o strategie fixataa partenerului de joc se traseaza sageti ın sensul strategiilor ce sunt mai avan-tajoase jucatorului respectiv din punctul de vedere al platilor (sau costurilor)generate. Sagetile converg spre un echilibru Nash (vezi Figura 2.6 unde (a) si(b) reprezinta jocuri de tip cost, iar (c) si (d) reprezinta jocuri de tip castig).Daca nu exista sageti care converg, atunci jocul respectiv nu are echilibreNash (pure); el va avea ınsa echilibre Nash ın strategii mixte (vezi para-graful 2.4). Fiecare pereche de sageti convergente indica un echilibru Nash.Jocurile matriceale determinate au deseori echilibre Nash multiple; acesteaau aceeasi valoare. Jocurile cu suma variabila au ın mod obisnuit punctede echilibru Nash multiple; acestea pot avea valori foarte diferite. Figura2.6 ilustreaza existenta sau nu a unui echilibru Nash, respectiv unicitateasau multiplicitatea echilibrelor Nash, marcand cu simbolul ∗ toate echilibreleNash existente.

22

−→↑ 8, 9 8, 7

11, 12 7, 6∗↓

−→(a)

←−↓ −10, 4 −5, 0

2,−10 −5, 5↑

−→(b)

−→↓ 50, 50 80, 100∗

100, 80∗ 60, 60↑

←−(c)

−→↓ 130 180∗

180∗ 160↑

←−(d)

Figure 2.6: Diagrame cu sageti

Exemplul 2.6. (Un joc de alegere a rutei) Doua companii de transporturitrebuie sa aleaga ruta cea mai putin costisitoare luand ın consideratie efectulaglomeratiei pe sectoarele de drum folosite ın comun. Presupunem ca ocompanie trebuie sa faca transporturi de la localitatea A la localitatea C sipoate face aceasta via B sau via D, iar cealalta companie trebuie sa facatransporturi de la localitatea B la localitatea D si poate face aceasta viaA sau via C. Costurile aferente sectoarelor de drum AB, BC, AD si CD,pentru fiecare utilizator, sunt mai mari ın caz de folosinta ın comun; ambelecosturi posibile sunt precizate ın Figura 2.7 (a). Spre exemplu, sectorul dedrum AB implica un cost de 2 unitati valorice daca are un singur utilizator,si un cost de 5 unitati valorice pe utilizator, ın cazul ın care ambele companiifolosesc acest sector de drum. Aceasta situatie de alegere a rutei poate fimodelata ca un joc bimatriceal unde jucatorul 1 are doua strategii, R1 siR2, corespunzand rutelor A−B − C si A−D − C, iar jucatorul 2 are douastrategii, R′

1 si R′2, corespunzand rutelor B−A−D si B−C −D. Costurile

aferente sunt indicate ın Figura 2.7 (b).

Jocul din Exemplul 2.6 este generat de un model de congestie introdusde Rosenthal (1973).

Un model de congestie poate fi descris ca 〈N, M, (Xi)i∈N , (cj)j∈M〉 unde

• N este multimea jucatorilor implicati (calatori, soferi, producatori).

• M este multimea facilitatilor implicate ın folosinta comuna (sectiuni dedrum, utilaje, etc.)

23

• Xi este multimea strategiilor jucatorului i, o submultime nevida alui M .

• cj : {1, 2, ..., n} −→ IR este functia de cost pentru facilitatea j, undecj(k) ınseamna costurile facilitatii j, pentru fiecare utilizator al ei, ıncazul ın care exista exact k utilizatori.

1 2

AB 2 5BC 3 6AD 4 10DC 1 3

(a)

R′1 R′

2

R1 8, 9 8, 7R2 11, 12 7, 6∗

(b)

−→↑ 14 12

17 11∗↓

−→

(c)

Figure 2.7: Un joc de alegere a rutei

Situatiile corespunzatoare unui model de congestie pot fi modelate cajocuri (de tip) congestie. Un joc de tip congestie este un joc ın forma strate-

gica 〈N, {Xi}i∈N , {Ki}i∈N〉, unde pentru fiecare i ∈ N , Ki(x) :∏j∈N

Xj −→ IR

este definita prin Ki(x) = −∑j∈xi

cj(nj(x)), unde nj(x) = |{i ∈ N |j ∈ xi}| este

numarul de utilizatori ai facilitatii j daca jucatorii aleg strategiile conform cuprofilul strategic x. Intr-un joc congestie de tip cost, toti jucatorii urmarescminimizarea costului individual total. Echilibrele Nash ale unui joc con-gestie recomanda jucatorilor evitarea congestiei (aglomeratiei). Jocurile (detip) congestie sunt jocuri strategice determinate si au multe aplicatii ın infor-matica. Ele formeaza o subclasa interesanta a jocurilor potential introdusede catre Monderer si Shapley (1996) pe baza notiunii de functie potential(exact). O functie potential (exact) masoara diferenta platilor fiecarui jucatorın caz de deviere unilaterala. In Figura 2.7 (c) este data o functie potential(exact) pentru jocul de alegere a rutei.

Exemplul 2.7. (Un joc al documentarii) Studentii din doi semiani de studiitrebuie sa se pregateasca pentru un examen folosind un suport de curs tiparitexistent la biblioteca facultatii si un laborator cu calculatoare. Daca toti

24

studentii ınvata la biblioteca, ori toti la laborator, aglomeratia creata dimi-nueaza eficienta documentarii lor. Jocul din Figura 2.6 (c) poate fi consideratca un joc al documentarii.

Fie G = 〈N, {Xi}i∈N , {Ki}i∈N〉 un joc strategic de n persoane si fie

P :∏i∈N

Xi −→ IR o functie cu valori reale definita pe multimea profilurilor

strategice. Functia P este un potential exact pentru G daca pentru orice

i ∈ N , pentru orice x−i ∈ X−i =∏

j∈N\{i}Xj si pentru orice xi, yi ∈ Xi, are loc

Ki(xi, x−i)−Ki(yi, x−i) = P (xi, x−i)− P (yi, x−i).O functie P potential exact pentru G induce un joc potential GP =

〈N, {Xi}i∈N , P, ..., P 〉 . Figura 2.6 (d) contine un joc potential pentru ”Joculdocumentarii” din Figura 2.6 (c).

Teorema 2.8. Fie G = 〈N, {Xi}i∈N , {Ki}i∈N〉 un joc finit de n persoane sifie P un potential exact pentru G. Atunci

(i) Jocurile G si GP au aceeasi multime de echilibre Nash;

(ii) G are cel putin un echilibru Nash.

Propozitia 2.9. (Rosenthal) Fie 〈N, M, (Xi)i∈N , (cj)j∈M〉 un model de con-gestie si fie G jocul de tip congestie corespunzator. Atunci G este un joc

potential exact. O functie potential pentru G este data de P :∏i∈N

Xi −→ IR,

definita pentru orice x = (xi)i∈N prin

P (x) = −∑

j∈ ⋃i∈N

xi

∑

`=1,...,nj(x)

cj(`).

Intrucat multe jocuri strategice finite au echilibre Nash multiple, ın teo-ria jocurilor necooperative au fost introduse variante (rafinari) ale notiuniide echilibru Nash, care impun conditii suplimentare asupra echilibrelor Nash.Notiunea de echilibru Nash nedominat (sau echilibru Nash ın strategii ne-dominate) si cea de echilibru Nash puternic prezinta un interes particular.Spunem ca o strategie xi a jucatorului i domina strategia xi a aceluiasi jucatordaca prima nu este niciodata mai nefavorabila jucatorului i decat cea de-a

25

doua si uneori e mai avantajoasa, adica pentru toate profilurile strategice

x−i ∈ X−i =∏

j∈N\{i}Xj ale celorlalti jucatori are loc

(∗) Ki(xi, x−i) ≥ Ki(xi, x−i)

cu cel putin o inegalitate stricta pentru cel putin un x−i ∈ X−i. O strategiecare nu este dominata de catre nici-o alta strategie se numeste strategie ne-dominata. Un profil strategic x = (xi)i∈N este un echilibru Nash nedominatdaca el este un echilibru Nash ın strategii nedominate, adica este un echili-bru Nash ın care xi este o strategie nedominata pentru fiecare i ∈ N. Unechilibru Nash ın strategii nedominate poate fi gasit prin eliminarea iterativaa strategiilor dominate, asa cum ilustram ın Figura 2.8.

2 2 1 40 2 5 34 2 3 2

−→2 2 10 2 54 2 3

−→ 0 2 54 2 3

−→ 0 24 2

−→ 4 2 −→ 2

Figure 2.8: Eliminarea iterativa a strategiilor dominate

Un caz special apare ın situatia ın care un jucator are o strategie care ıida o plata la fel de buna cu plata pe care o poate obtine utilizand oricare dincelelalte strategii ale sale pentru orice profil strategic al celorlalti jucatori.O strategie xi ∈ Xi se numeste o strategie slab dominanta daca relatia (∗)are loc pentru orice xi ∈ Xi si pentru orice x−i ∈ X−i. Un jucator poateavea mai multe strategii slab dominante. Asemenea strategii ar trebui saofere jucatorului aceeasi plata pentru orice profil strategic fixat al celorlaltijucatori. Daca o strategie slab dominanta xi ∈ Xi este astfel ıncat pentrufiecare xi ∈ Xi exista un profil strategic x−i astfel ıncat (∗) are loc cu ine-galitate stricta, atunci strategia xi ∈ Xi domina toate celelalte strategii alejucatorului si se numeste strategie dominanta. Un jucator poate avea celmult o strategie dominanta.

Exemplul 2.10. In jocul de tip ”ultimatum” descris ın Exemplul 2.18 sireprezentat ın forma normala ın Figura 2.17 (a), jucatorul 2 are o singurastrategie dominanta: (a1, a2, a3). Toate celelate strategii ale jucatorului 2 suntdominate. Spre exemplu, strategia (r1, a2, r3) este dominata de (r1, a2, a3)deoarece aceasta da jucatorului 2 aceeasi plata daca jucatorul 1 foloseste

26

strategia 5-1 sau 4-2, dar daca jucatorul 1 foloseste strategia 3-3, strategia(r1, a2, a3) da jucatorului 2 o plata mai mare decat strategia (r1, a2, r3).

Un echilibru Nash care satisface conditia ca este stabil ımpotriva tuturordeviatiilor de catre coalitii de jucatori se numeste un echilibru Nash puternic.Un echilibru Nash x∗ = (x∗i )i∈N al jocului 〈N, {Xi}i∈N , {Ki}i∈N〉 este unechilibru Nash puternic daca pentru toate coalitiile S ⊂ N nu exista nici-un

xS = (xi)i∈S ∈ XS =∏i∈S

Xi astfel ıncat Ki(xS, x∗(N \ S)) ≥ Ki(x∗) pentru

toti i ∈ N , cu inegalitate stricta pentru cel putin un jucator i ∈ S.

Exemplul 2.11. Pentru jocul din Exemplul 2.19, dintre cele trei echili-bre Nash marcate cu ∗ ın Figura 2.19 (b), doua sunt echilibre Nash pu-ternice: (A1, (I, L2, A3)) si (A1, (I, A2, A3)). Echilibrul Nash (L1, (I, L2, L3))nu este puternic deoarece coalitia {1, 2} poate creste plata jucatorului 1 dela 2 la 3, mentinand plata 2 pentru jucatorul 2, prin folosirea strategieixS = (A1, (I, A2, L3)).

Exista totusi multe jocuri strategice finite care nu au nici-un echilibruNash (ın strategii pure). Intr-o asemenea situatie (si de asemenea cand joculare echilibre Nash ın strategii pure), se poate considera extensia mixta a jocu-lui. Aceasta este construita pe baza randomizarii pe multimea strategiilorpure, asa-numitele strategii mixte. Extensia mixta a unui joc necooperativın forma normala si determinarea echilibrelor Nash ın strategii mixte pentrujocuri matriceale si bimatriceale sunt tratate ın paragraful 2.4.

Consideram acum jocuri de doua persoane cu (infinit de) multe strategiisi tratam determinarea echilibrelor lor Nash. Fie x1 o strategie a jucatorului1, x2 o strategie a jucatorului 2, K1 : X1×X2 −→ IR, functia de plata ajucatorului 1, si K2 : X1×X2 −→ IR, functia de plata a jucatorului 2. Dacax1 si x2 pot lua, spre exemplu, 100 de valori diferite, utilizarea unei bimatricede dimensiune 100×100 devine cel putin anevoioasa. Daca x1 si x2 iau valoriıntr-un interval, spre exemplu [0,1], situatia conflictuala este imposibil safie reprezentata printr-o (bi)matrice. Intr-un asemenea caz, daca functiilede plata ale jucatorilor sunt diferentiabile, pentru determinarea echilibrelorNash se poate folosi analiza matematica.

Teorema 2.12. Fie 〈N, {Xi}i∈N , {Ki}i∈N〉 un joc strategic cu N multimefinita. Daca pentru fiecare i ∈ N multimea strategiilor Xi este un intervalmarginit si functia de plata Ki este de clasa C2 si strict concava ın xi, atunciexista un echilibru Nash x∗ al jocului.

27

In cele ce urmeaza, prezentam o metoda analitica pentru determinareaechilibrelor Nash a unui joc infinit de doua persoane. Notam cu f1 : X2 −→ X1

functia cel mai bun raspuns a jucatorului 1, unde f1(x2) este cel mai bunraspuns a jucatorului 1 la x2, unde x2 este o strategie arbitrara fixata ajucatorului 2. Aceasta functie se obtine din ∂K1(x1, x2)/∂x1 = 0 si furnizeazavaloarea lui x1 care maximizeaza K1(x1, x2) pentru orice x2 fixat. Notam cuf2 : X1 −→ X2 functia cel mai bun raspuns a jucatorului 2, unde f2(x1) estecel mai bun raspuns a jucatorului 2 la x1, unde x1 este o strategie arbitrarafixata a jucatorului 1. Aceasta functie se obtine din ∂K2(x1, x2)/∂x2 = 0 sifurnizeaza valoarea lui x2 care maximizeaza K2(x1, x2) pentru orice x1 fixat.Functia f definita prin f = (f1, f2) se numeste functia cel mai bun raspuns ajocului. Aceasta functie este continua si asociaza fiecarei perechi de strategii(x1, x2) plata (f1(x2), f2(x1)). Un echilibru Nash al jocului, x∗ = (x∗1, x

∗2), sa-

tisface simultan x∗1 = f1(x∗2) si x∗2 = f2(x

∗1). Din punct de vedere grafic, echili-

brele Nash ale jocului se afla la intersectia functiilor ”cel mai bun raspuns”a celor doi jucatori.

Exemplul 2.13. (Jocul publicitatii) Doua firme concurente pe piata debunuri de consum trebuie sa decida simultan si independent asupra nivelu-lui optim al cheltuielilor lor cu publicitatea (ın vederea maximizarii profi-tului individual). Presupunem ca ambele firme au un plafon bugetar pen-tru publicitate de 1000 e si ca profitul lor individual depinde de cheltu-ielile cu publicitatea x1 si x2 prin functiile de plata K1 : X1×X2 −→ IR siK2 : X1×X2 −→ IR, definite prin: K1(x1, x2) = 1000x1−x2

1−x22, K2(x1, x2) =

1000x2− x1x2− x22. Aceasta situatie de decizie interactiva poate fi modelata

ca un joc infinit de doua persoane cu suma nula 〈[0, 1000], [0, 1000], K1, K2〉.Deciziile optime privind cheltuielile cu publicitatea sunt determinate princalcularea echilibrelor Nash ale jocului. Acestea se obtin rezolvand sistemulliniar 1000−2x1 = 0, 1000−x1−2x2 = 0. Echilibrul Nash al jocului conside-rat este x∗ = (500, 250), generand profitul K1(500, 250) = 187.500 e pentrujucatorul 1 si K2(500, 250) = 62.500 e pentru jucatorul 2.

Conceptul de echilibru Nash este fundamental pentru rezolvarea jocurilornecooperative ın forma strategica. Incheiem acest paragraf ıncercand safurnizam un raspuns la ıntrebarea: Este un echilibru Nash o solutie a jocului?O conditie suficienta este asigurata de strategii nedominate ın profilul strate-gic corespunzand unui echilibru Nash. Presupunem ca (s, t) este un echilibruNash si ca o alta strategie s∗ domina s pentru jucatorul 1 si o strategie t∗

domina t pentru jucatorul 2. Atunci (s, t) nu este o solutie a jocului.

28

2.2 Jocuri ın forma extensiva si echilibre Nash perfectepe subjoc

Forma extensiva a unui joc este o pereche 〈N, T 〉 , unde N = {1, 2, ..., n}este multimea (finita a) jucatorilor si T este arborele jocului, oferind posibi-litatea unei descrieri dinamice detaliate a unei situatii de interactiune strate-gica. Un arbore este un graf orientat cu un nod special, numit radacina,o multime de noduri terminale si una de noduri neterminale si un drumunic de la radacina la fiecare din nodurile grafului. In arborele unui joc (ınforma extensiva) orice drum pornind de la radacina la un nod terminal in-dica un mod ın care ”istoria” jocului poate evolua. Nodurile neterminale alearborelui jocului (incluzand radacina), numite noduri de decizie, corespundpersoanelor ce iau decizii (jucatorii). Nodurile terminale indica rezultatele(platile) posibile ale jucatorilor daca jocul se sfarseste ın acel nod termi-nal. Arcele corespund ”mutarilor” (actiunilor, strategiilor, deciziilor) juca-torilor care muta consecutiv (secvential ın timp). Reprezentarea corecta aunei situatii conflictuale ca un joc ın forma extensiva implica ıncorporareacorecta a tuturor regulilor jocului. Aceasta implica necesitatea identificariipentru fiecare jucator a asa-numitelor multimi de informatie. O multime deinformatie a unui jucator contine toate nodurile de decizie ce apartin aceluijucator cand acelui jucator ıi vine randul la mutare. Multimile de informatiecare contin cel putin doua noduri de decizie se marcheaza grafic ın arborelejocului, de obicei folosind un contur de forma − − −. Daca o multimede informatie a unui jucator consta dintr-un singur nod de decizie, atunciacel jucator stie precis care e pozitia sa ın arborele jocului, adica jucatorulcunoaste toata istoria desfasurarii jocului pana ın acel moment. Daca toatemultimile de informatie ale tuturor jucatorilor constau dintr-un singur nod,jocul este un joc (dinamic) cu informatie perfecta. Jocul de sah este unjoc cu informatie perfecta. De obicei, multimile de informatie cu un singurnod de decizie nu se marcheaza distinct ın reprezentarea arbore a jocului.Daca o multime de informatie a unui jucator contine mai mult decat unnod de decizie, aceasta ınseamna ca ın momentul ın care jucatorul trebuiesa ia o decizie, el stie doar ca se poate afla ın oricare din nodurile multimiisale de informatie; ın acest caz, alegerea strategiei sale se face ın conditiide informatie imperfecta. Un joc ın care cel putin un jucator are cel putino multime de informatie ce contine cel putin doua noduri de decizie esteun joc (dinamic) cu informatie imperfecta. Jocul de bridge este un joc cuinformatie imperfecta. Arborele unui joc ın forma extensiva este un arboreetichetat care satisface urmatoarele reguli:

29

1. Orice nod este un succesor al nodului initial (radacina).2. Orice nod cu exceptia nodului initial are exact un predecesor imediat.

Nodul initial nu are predecesori.3. Ramuri (arce) multiple ce corespund unui acelasi nod au etichete (de

actiuni) diferite.4. Fiecare multime de informatie contine noduri de decizie ale unui singur

jucator.5. Toate nodurile ıntr-o anumita multime de informatie trebuie sa aiba

acelasi numar de succesori imediati si aceeasi multime de etichete pen-tru ramurile corespunzatoare.

In paragraful urmator, trei variante ale unei situatii de piata sunt modelateca jocuri necooperative folosind forma extensiva a unui joc. In forma exten-siva din Figura 2.14 (a), fiecare jucator are o singura multime de informatiecontinand un singur nod. In forma extensiva din Figura 2.14 (b), multimeade informatie a jucatorului 1 contine doua noduri de decizie si multimea deinformatie a jucatorului 2 contine un singur nod de decizie. In forma ex-tensiva din Figura 2.18 (a), jucatorul 1 are o singura multime de informatieconstand dintr-un singur nod de decizie, iar jucatorul 2 are trei multimi deinformatie cu cate un singur nod de decizie. Paragraful urmator continede asemenea un joc de tip ”ultimatum” descris verbal ın Exemplul 2.18 simodelat ca un joc ın forma extensiva ın Figura 2.16 (a).

Figure 2.9: Un joc cu ”imperfect recall”

30

In modelarea unei situatii ca un joc ın forma extensiva, se presupune deobicei ”perfect recall”, adica capacitatea perfecta a fiecarui jucator de a-siaminti mutarile sale anterioare. Jocurile din exemplele precedente sunt jocuricu ”perfect recall”.Teoria jocurilor studiaza de asemenea jocuri cu ”imperfectrecall”. Un asemenea joc este ilustrat ın Figura 2.9. Jocurile cu imperfectrecall au aplicatii in informatica.

(a)

(b)

Figure 2.10: Subjocurile unor jocuri ın forma extensiva

31

Dat un joc ın forma extensiva, un nod x al arborelui se spune ca initiazaun subjoc daca nici x si nici unul dintre succesorii lui x nu sunt ıntr-o multimede informatie care contine si noduri care nu sunt succesori ai lui x. Un subjoceste un arbore definit de x si succesorii sai. Intr-un joc cu informatie perfectaorice nod initiaza un subjoc. In Figura 2.10 evidentiem toate subjocurile unuijoc cu informatie perfecta si ale unui joc cu informatie imperfecta.

Exista numeroase situatii practice ın care sansa joaca un rol. Spre exem-plu, ın fotbal sansa decide care echipa ıncepe jocul. Sansa poate intervenila ınceperea jocului sau/si la anumite momente ın cursul desfasurarii jocu-lui. In astfel de situatii, sansa este considerata ea ınsasi ca un jucator, cazın care spunem ca avem un joc cu mutari ale sansei. In forma extensiva aunui asemenea joc, nodurile apartinand sansei sunt etichetate corespunzator(de obicei cu C (”chance”) sau cu 0) iar arcele ce ies din asemenea noduriindica mutarile sansei prin distributii de probabilitate ale evenimentelor posi-bile. Figura 2.11 contine doua forme extensive ale unor jocuri cu mutari alesansei: Figura 2.11 (a) contine forma extensiva a unui joc cu informatie per-fecta, iar Figura 2.11 (b) contine forma extensiva a unui joc cu informatieimperfecta.

Conceptul de solutie specific jocurilor ın forma extensiva este acela deechilibru Nash perfect pe subjoc. Un echilibru Nash perfect pe subjoc esteun profil strategic secvential rational, ın sensul ca ıncorporeaza rationalitateasecventiala a jucatorilor prin evaluarea individuala a subjocurilor. Rationa-litatea secventiala implica faptul ca o strategie optimala pentru un jucatorar trebui sa maximizeze plata sa conditionat de oricare din multimile sale deinformatie. Presupunerea obisnuita pentru jocuri ın forma extensiva este carationalitatea secventiala este ”common knowledge”. Ideea care sta la bazadeterminarii unui echilibru Nash perfect pe subjoc este ca fiecare jucator,ınainte de a-si alege o strategie (adica un plan complet de actiune de-a lungularborelui jocului), ıncearca sa anticipeze alegerile de alternative ale celorlaltijucatori ın urma fiecarei decizii posibile pentru el. Procedand astfel, unjucator ıncearca sa determine (ghiceasca) care nod final va fi atins ca urmarea selectarii de catre el a oricareia dintre alternativele disponibile. Apoi,jucatorul foloseste aceasta informatie pentru a lua decizia optima. Astfel,fiecare jucator va studia reprezentarea jocului si va considera ce vor faceceilalti jucatori (rationali si inteligenti) ın viitor ca raspuns la mutarea sa ıntr-o multime de informatie particulara. Folosirea acestei abordari pentru joculın forma extensiva din Figura 2.16 (a) conduce la determinarea echilibruluiNash perfect pe subjoc reprezentat prin sageti ın Figura 2.16 (b).

32

(a)

(b)

Figure 2.11: Jocuri ın forma extensiva cu mutari ale sansei

Metoda de baza pentru determinarea echilibrelor Nash perfecte pe subjoceste inductia ınapoi (”backward induction”). Inductia ınapoi este un procesde analizare a jocului de la nodurile terminale ale arborelui jocului catreradacina sa, prin identificarea tuturor subjocurilor jocului si determinareasolutiilor optimale ale jucatorilor la nivel de subjoc. Determinarea solutiiloroptimale ın cadrul fiecarui subjoc (si a jocului initial) se realizeaza astfel: pen-tru fiecare dintre multimile de informatie ale jucatorilor, date fiind nodurileterminale ce pot fi atinse, se renunta la actiunile dominate ale jucatoruluirespectiv. O strategie a unui jucator ıntr-un (sub)joc ın forma extensiva esteun plan complet de actiune al jucatorului de-a lungul arborelui (sub)jocului.Strategiile posibile ale unui jucator trebuie sa aiba cate o singura compo-nenta pentru fiecare din multimile de informatie ale jucatorului respectiv ınarborele jocului, considerand o ordine fixata de parcurgere a arborelui jocului(de obicei, pe nivele ale arborelui de la radacina spre nodurile terminale, si ıncadrul fiecarui nivel de la stanga la dreapta). Fiecare componenta a strate-giei unui jucator poate primi ca valoare oricare dintre etichetele actiunilorposibile pentru jucatorul respectiv din multimea de informatie corespunza-toare acelei componente. Spre exemplu, strategiile jucatorului 2 sunt I si R ın

33

jocul ın forma extensiva din Figura 2.14 (a). In jocul ın forma extensiva dinFigura 2.18 (a) strategiile jucatorului 2 sunt 3-uple ın care prima componentacorespunde primei multimi de informatie a acestui jucator (radacina arbore-lui), a doua componenta corespunde multimii de informatie a jucatorului 2situata la stanga pe nivelul 2 al arborelui, iar a treia componenta corespun-de multimii de informatie a jucatorului 2 situata la dreapta pe nivelul 2 alarborelui. Prima componenta poate lua valori ın multimea {I, R}, a douacomponenta poate lua valori ın multimea {L2, A2}, iar a treia componentapoate lua valori ın multimea {L3, A3}. Jucatorul 2 are, prin urmare, 8 strate-gii posibile ın jocul din Figura 2.18 (a): (I, L2, L3), (I, L2, A3), (I, A2, L3),(I, A2, A3), (R, L2, L3), (R, L2, A3), (R, A2, L3) si (R, A2, A3).

Un profil strategic este un echilibru Nash perfect pe subjoc daca el specificaun echilibru Nash ın orice subjoc al jocului original; un asemenea profil strate-gic este rational secvential. Daca nu exista egalitate de plati, adica doua saumai multe noduri terminale ce conduc la aceeasi plata pentru vreunul dintrejucatori, atunci inductia ınapoi identifica un singur echilibru Nash perfectpe subjoc. In cele ce urmeaza, exemplificam determinarea echilibrulor Nashperfecte pe subjoc prin metoda inductiei ınapoi pentru jocurile din Figura2.10.

Exemplul 2.14. Analizam jocul din Figura 2.10 (a) folosind metoda inductieiınapoi. Ultimele decizii care trebuie facute sunt acelea ın care jucatorul 2trebuie sa decida daca sa lupte sau sa se acomodeze, dupa ce a observat de-cizia luata de jucatorul 1. In subjocul 1, jucatorul 2 va prefera actiunea L2

care-i asigura plata 2 (fiindca 2 > 1), iar ın subjocul 2, jucatorul 2 va preferaactiunea A3 care-i asigura plata 4 (fiindca 4 > 3). Acum, analizam subjocul3 care ıncepe cu decizia jucatorului 1 (L1 sau A1) ın situatia ın care jucatorul2 a selectat actiunea I. Daca jucatorul 1 ar alege L1, atunci am vazut cajucatorul 2 alege L2, implicand plata 2 pentru jucatorul 1; daca jucatorul1 ar alege A1, am vazut ca jucatorul 2 alege A3, implicand plata 5 pentrujucatorul 1. Actiunea optimala pentru jucatorul 1 ın subjocul 3 este asadarA1 (fiindca 5 > 2). Acum analizam jocul complet pentru a stabili care eactiunea optimala a jucatorului 2 la ınceputul jocului. Daca jucatorul 2 aralege R, atunci el ar obtine plata 0; daca el ar alege I, am vazut din analizaanterioara a subjocului 3 ca jucatorul 1 alege A1, urmata de actiunea A3 ajucatorului 2, implicand plata 4 pentru jucatorul 2 (care este mai mare decat0). Echilibrul perfect pe subjoc al acestui joc, (A1, L2, A3), este reprezentatprin sageti ın Figura 2.18 (b).

34

Exemplul 2.15. Analizam jocul din Figura 2.10 (b) prin metoda inductieiınapoi, ıncepand cu subjocul care ıncepe ın situatia ın care jucatorul 1 a alesanterior actiunea U . Fiindca jucatorul 2 nu stie daca jucatorul 1 alege A sauB, el va prefera (pentru multimea de informatie ın care se afla) actiunea Xcare-i asigura o plata mai buna (1 > 0) sau cel putin la fel de buna (4 = 4) castrategia Y . Jucatorul 1 va prefera actiunea A care-i asigura plata 3 (fiindca3 > 1). Acum ramane de analizat jocul complet. Daca jucatorul 1 ar alegeD, el ar primi plata 2; daca, ın schimb, el ar alege U , tocmai am vazut caulterior el poate alege A, urmat de alegerea X de catre jucatorul 2, rezultandplata 3 pentru jucatorul 1, care e mai mare decat 2. Prin urmare, ın radacinaarborelui jocului jucatorul 1 va alege U . Echilibrul Nash perfect pe subjocal jocului analizat, (UA,X), este reprezentat prin sageti ın Figura 2.12.

Figure 2.12: Echilibru Nash perfect pe subjoc

Determinarea prin metoda inductiei ınapoi a echilibrelor Nash perfecte pesubjoc pentru jocurile (ın forma extensiva) finite cu informatie perfecta sauimperfecta se poate face, de asemenea, folosind forma normala (corespunza-toare formei extensive) pentru fiecare subjoc al jocului si pentru jocul initial.Un echilibru Nash al jocului strategic este un echilibru perfect pe subjoc aljocului ın forma extensiva daca restrictia sa la fiecare subjoc este un echilibruNash al acelui subjoc. Aceasta metoda este ilustrata ın Exemplul 2.20.

In cele ce urmeaza tratam reprezentarea ın forma extensiva a jocurilor(cu sau fara mutari ale sansei) ın care jucatorii au (infinit de) multe strategii.

35

Simbolul grafic arc de cerc este folosit pentru a reprezenta o multime infinitade strategii pure. Pentru exemplificare folosim forma extensiva a joculuiparteneriatului din Exemplul 2.2, reprezentata ın Figura 2.13.

Figure 2.13: Forma extensiva a jocului parteneriatului

In aplicarea metodei inductiei ınapoi pentru determinarea echilibrelorNash perfecte pe subjoc pentru jocuri infinite, se recomanda pornirea cuacele subjocuri (care sunt spre sfarsitul jocului original) pentru care existasperanta sa aiba un singur echilibru Nash. Apoi, se foloseste inductia ınapoiıncorporand aceste rezultate de echilibru ın subjocuri mai ample. Desigur,determinarea echilibrelor Nash perfecte pe subjoc se poate face folosindmetoda analitica bazata pe functiile cel mai bun raspuns ale jucatorilor (vezide asemenea paragraful 2.4). Exemplificam aceasta pentru un joc de piatacu infinit de multe strategii.

Exemplul 2.16. Consideram o piata cu doua firme concurente, firma 1 sifirma 2, care trebuie sa-si aleaga simultan si independent nivelul (optim) alproductiei, q1 si, respectiv, q2, dupa ce firma 1 a selectat nivelul (optim al)publicitatii. Presupunem ca pretul pietei este p = a − q1 − q2, unde a estenivelul publicitatii ales de firma 1 (si observat de firma 2). Presupunem deasemenea ca cele doua firme produc la cost zero si costul publicitatii firmei 1este 2a3/81. Profitul firmei 1 este de forma (a−q1−q2)q1−2a3/81, iar profitulfirmei 2 este (a− q1 − q2)q2. Observam ca BR1(q2) = (a− q2)/2, BR2(q1) =(a − q1)/2. Echilibrul Nash al jocului corespunde la q∗1(a) = q∗2(a) = a/3,implicand p∗(a) = a/3. Profitul generat pentru firma 1 va fi functia z1 definitaprin z1(a) = a2 − 2a3/81. Maximixarea profitului firmei 1 determina niveluloptim a∗ = 3 al publicitatii. Nivelul optim al productiei ambelor firme este,prin urmare, q∗1 = q∗2 = 1.

36

2.3 Forma extensiva si forma normala

Situatii practice pot fi uneori studiate folosind instrumentele teoriei jocurilor.In orice aplicatie a teoriei jocurilor trebuie sa transpunem descrierea nefor-mala (adesea narativa) a problemei ıntr-un model teoretic din teoria jocuriloralegand forma cea mai potrivita pentru a reprezenta jocul si apoi sa-l re-zolvam. Situatiile practice ın care conflictul existent este ın principal gene-rat de interese individuale, iar acordurile ferme (de comportare strategica)ale jucatorilor nu sunt permise (desi comunicarea ıntre jucatori ınainte deınceperea jocului nu este ıntotdeauna interzisa) pot fi adesea modelate cuusurinta folosind un model din teoria necooperativa a jocurilor. O decizieimportanta care trebuie facuta este aceea a selectarii formei celei mai potri-vite de reprezentare a jocului. Forma extensiva este o descriere dinamica sidetaliata a jocului. Ea prezinta avantajul unei analize naturale a situatieimodelate folosind arborele jocului. Forma normala este o descriere statica siconcisa. Ea se bazeaza pe presupunerea ca jucatorii iau decizii simultan siindependent si prezinta un avantaj din punctul de vedere al rezolvarii jocu-lui. Adesea, descrierea neformala a unei situatii conflictuale este mai usortradusa ın forma extensiva a unui joc. Pentru a folosi avantajele formei nor-male ın rezolvarea jocului, forma extensiva obtinuta poate fi apoi translatataın forma normala corespunzatoare, pe baza determinarii strategiilor juca-torilor ın arborele jocului. Oricarui joc ın forma extensiva ıi corespunde oforma normala unica. Totusi, forme extensive diferite pot genera acelasi jocın forma normala. Ilustram relatia dintre forma extensiva si forma normalaprin urmatorul exemplu care modeleaza, ın doua variante privind regulilejocului, comportarea pe piata de jocuri video a doua firme de software.

Exemplul 2.17. Consideram urmatoarea situatie decizionala interactiva pepiata de jocuri video. Presupunem ca pe piata se afla o firma specializata ınjocuri video, jucatorul 1, care realizeaza un profit curent de 5 unitati valo-rice (spre exemplu miliarde de lei). O alta firma de software, firma 2, carerealizeaza un profit curent de o unitate valorica din alte tipuri de activitati,intentioneaza sa intre pe piata de jocuri video. Ea trebuie sa decida daca intrasau nu pe piata stiind ca firma 1 va reactiona, ori ostil (ıncercand sa distrugafirma 2) ori acceptand situatia de concurenta creata prin intrarea firmei 2.Situatia descrisa poate fi modelata ca un joc necooperativ de doua persoane,unde firma 1 are doua alternative (ın caz de intrare pe piata a firmei 2):A – corespunzand acomodarii sale cu prezenta pe piata a firmei 2 – si L –

37

corespunzand luptei cu firma 2, spre exemplu printr-o campanie publicitaracostisitoare –, iar firma 2 are doua strategii: I – corespunzand deciziei dea intra pe piata – si R – corespunzand deciziei de renuntare la intentia deintrare pe piata. In ceea ce priveste platile jucatorilor, ın cazul ın care firma 2decide sa nu intre pe piata, ambele firme realizeaza profitul lor curent. Dacafirma 2 decide sa intre pe piata si firma 1 se acomodeaza situatiei, profitulfirmei 2 va creste, spre exemplu la 2 unitati valorice, ın timp ce profitulfirmei 1 va scadea, spre exemplu la 2 unitati valorice. Daca ınsa firma 2 intrape piata si firma 1 lupta pentru ınlaturarea firmei 2, piata de jocuri videova avea de suferit asigurand ambelor firme profit zero. Modelarea acesteisituatii ca un joc ın forma extensiva necesita informatii suplimentare privinddesfasurarea temporala a jocului si regulile privind informatia disponibila ju-catorilor. Presupunem ca firma 2 trebuie sa decida ıntai daca intra sau nupe piata si consideram urmatoarele doua variante privind informatia de caredispune firma 1 atunci cand decide tipul sau de comportare fata de firma 2pe piata de jocuri video:

(a) Firma 1 observa intrarea pe piata a firmei 2 si apoi decide comportareasa. Aceasta varianta este modelata ca un joc necooperativ cu informatie(completa si) perfecta, al carui arbore este descris ın Figura 2.14 (a);

(b) Firma 1 trebuie sa decida comportarea sa pe piata video (ın caz deintrare a firmei 2) fara a sti decizia luata de firma 2. Aceasta variantaeste modelata ca un joc necooperativ cu informatie (completa dar)imperfecta, al carui arbore este descris ın Figura 2.14 (b).

Ambelor forme extensive privind jocul firmelor pe piata de jocuri videole corespunde un acelasi joc ın forma normala, reprezentat ın Figura 2.15.

Scopul acestui paragraf este sa studieze legatura ıntre forma extensiva siforma normala a unui joc necooperativ si ıntre conceptele de solutie speci-fice fiecarei forme. Modul ın care forma extensiva a unui joc genereaza oforma normala unica este ilustrat cu ajutorul a doua situatii de interactiunestrategica prezentate ın Exemplul 2.18 si Exemplul 2.19.

38

(a)

(b)

Figure 2.14: Jocuri de piata ın forma extensiva

I R

L 0, 0 5, 1A 2, 2 5, 1

Figure 2.15: Forma normala corespunzatoare jocurilor de piata

Exemplul 2.18. (Joc de tip ”ultimatum”) Doi jucatori pot primi o suma de6 unitati valorice daca ei cad de acord asupra modului de ımpartire (ın unitativalorice ıntregi) a acestei sume. In vederea atingerii unui acord, jucatoriiurmeaza o procedura stricta: unul dintre jucatori, jucatorul 1, propune oschema de ımpartire a celor 6 unitati valorice iar celalalt jucator, jucatorul2, reactioneaza la propunerea facuta acceptand-o sau refuzand-o. Alterna-tivele rezonabile (si realizabile) pentru jucatorul 1 sunt schemele de divizare

39

5-1, 4-2 si 3-3. Daca jucatorul 2 accepta propunerea facuta de jucatorul 1,cele 6 unitati valorice sunt ımpartite conform propunerii respective, dar dacajucatorul 2 refuza propunerea facuta de jucatorul 1, oferta este anulata (adicaambii jucatori primesc 0 unitati valorice). Situatia descrisa poate fi mode-lata usor ca un joc ın forma extensiva cu informatie (completa si) perfecta,reprezentat ın Figura 2.16 (a), unde alternativele disponibile jucatorului 2 –a(ccepta) si r(espinge) – sunt indexate pentru a face clar la care propunerea jucatorului 1 se refera. Echilibrul perfect pe subjoc al jocului dinamicdin Figura 2.16 (a) este reprezentat ın Figura 2.16 (b) cu ajutorul sagetilor.Este natural (sub presupunerea de rationalitate perfecta) ca jucatorul 2 sa ac-cepte oricare dintre cele trei propuneri ale jucatorului 1 fiindca ın caz contraracest jucator va primi 0 unitati valorice ın loc de 1, 2 sau 3 unitati valorice.Bazat pe aceasta, jucatorul 1 va alege alternativa cea mai atractiva pentru el(5-1). In termeni de strategii ale jucatorilor (planuri complete de actiune alefiecarui jucator de-a lungul arborelui jocului), echilibrul perfect pe subjoceste profilul strategic (5-1,(a1, a2, a3)).

(a)

(b)

Figure 2.16: Forma extensiva a unui joc de tip ”ultimatum”

40

Formei extensive din Figura 2.16 (a) ıi corespunde o forma normala unicareprezentata ın Figura 2.17 (a) ca un joc bimatriceal ale carui linii corespundla strategiile pure ale jucatorului 1, ın ordinea 5-1, 4-2, 3-3, si ale caruicoloane corespund la cele 8 strategii ale jucatorului 2, ın ordinea: (a1, a2, a3),(a1, a2, r3), (a1, r2, a3), (a1, r2, r3), (r1, a2, a3), (r1, a2, r3), (r1, r2, a3) si(r1, r2, r3). Acest joc ın forma normala are 7 echilibre Nash care sunt marcatecu ∗ ın Figura 2.17 (b). Dintre aceste echilibre Nash numai echilibrul Nash(5-1, (a1, a2, a3)), adica (linia 1, coloana 1) a bimatricei, este ”credibil” fiindunicul echilibru Nash ın strategii nedominate al jocului. Acest echilibru Nashcoincide cu echilibrul perfect pe subjoc din Figura 2.16 (b) pentru jocul ınforma extensiva care a generat aceasta forma normala.

5, 1 5, 1 5, 1 5, 1 0, 0 0, 0 0, 0 0, 04, 2 4, 2 0, 0 0, 0 4, 2 4, 2 0, 0 0, 03, 3 0, 0 3, 3 0, 0 3, 3 0, 0 3, 3 0, 0

(a)

5, 1∗ 5, 1∗ 5, 1∗ 5, 1∗ 0, 0 0, 0 0, 0 0, 04, 2 4, 2 0, 0 0, 0 4, 2∗ 4, 2∗ 0, 0 0, 03, 3 0, 0 3, 3 0, 0 3, 3 0, 0 3, 3∗ 0, 0

(b)

Figure 2.17: Forma normala a unui joc de tip ”ultimatum”

Exemplul 2.19. (Un joc de piata extins) Consideram o versiune mai amplaa unui joc de piata de tipul celui descris ın Exemplul 2.17. Presupunem, casi ın prima versiune a Exemplului 2.17, ca ıntai firma 2 decide daca intrape piata de jocuri video (strategia I) sau renunta (strategia R), dupa carefirma 1, observand alternativa aleasa de firma 2, decide daca va lupta cufirma 2 (spre exemplu printr-o campanie publicitara costisitoare) ın scopuldistrugerii acesteia sau se va acomoda intrarii pe piata a firmei 2. Firma2, observand alternativa de comportare adoptata de firma 1 ca raspuns laintrarea sa pe piata, va trebui sa decida modul sau de comportare strategicaın continuare: ori sa intre ın lupta cu firma 1 ca sa-si consolideze pozitia pepiata, ori, pur si simplu, sa se acomodeze situatiei existente.

41

O situatie de tipul celei descrise ın Exemplul 2.19 este modelata ca unjoc ın forma extensiva ın Figura 2.18 (a). Alternativele L (lupta) si A (seacomodeaza) sunt indexate pentru a face clar jucatorul la care se refera si,pentru jucatorul 2, situatia particulara ın desfasurarea jocului. Un echilibruperfect pe subjoc pentru acest joc este reprezentat ın Figura 2.18 (b) cu aju-torul sagetilor. El poate fi determinat cu usurinta folosind metoda inductieiınapoi. Figura 2.10 (a) marcheaza subjocurile jocului initial, folosite ın cadrulinductiei ınapoi.

(a)

(b)

Figure 2.18: Forma extensiva u unui joc de piata extins

Formei extensive din Figura 2.18 (a) ıi corespunde o forma normala unicareprezentata ın Figura 2.19 (a) ca un joc bimatriceal. Jucatorul 1 are doua

42

strategii pure: L1 – sa lupte ımpotriva firmei 2 – si A1 – sa se acomodezeintrarii pe piata a firmei 2, corespunzand, ın aceasta ordine, liniilor bimatricii.Jucatorul 2 are 8 strategii pure, ce corespund coloanelor bimatricei ın or-dinea: (I, L2, L3), (I, L2, A3), (I, A2, L3), (I, A2, A3), (R,L2, L3), (R,L2, A3),(R, A2, L3), (R,A2, A3). Acest joc ın forma normala are 3 echilibre Nashmarcate cu ∗ ın Figura 2.19 (b). Dintre acestea numai profilul strategic(A1, (I, L2, A3)), adica (linia 2, coloana 2) a bimatricei, este un echilibruNash ”credibil” fiind unicul echilibru Nash ın strategii nedominate. Acestechilibru Nash coincide cu echilibrul perfect pe subjoc din Figura 2.18 (b)pentru jocul ın forma extensiva care a generat aceasta forma normala.

2, 2 2, 2 4, 1 4, 1 9, 0 9, 0 9, 0 9, 02, 3 5, 4 2, 3 5, 4 9, 0 9, 0 9, 0 9, 0

(a)

2, 2∗ 2, 2 4, 1 4, 1 9, 0 9, 0 9, 0 9, 02, 3 5, 4∗ 2, 3 5, 4∗ 9, 0 9, 0 9, 0 9, 0

(b)

Figure 2.19: Forma normala a unui joc de piata extins

Incheiem acest paragraf cu un exemplu de utilizare a formei normaleın cadrul inductiei ınapoi pentru determinarea echilibrului Nash perfect pesubjoc.

Exemplul 2.20. Consideram jocul ın forma extensiva din Figura 2.10 (b) siFigura 2.12. Forma sa normala si cea a subjocului sau sunt reprezentate ınFigura 2.20. Echilibrul Nash al subjocului este profilul strategic (A, X). Joculcomplet are trei echilibre Nash: (UA,X), (DA, Y ) si (DB, Y ). Considerandrestrictia acestor echilibre Nash la subjoc obtinem (A,X), (A, Y ) si (B, Y ).Concludem ca numai echilibrul Nash (UA,X) este perfect pe subjoc. Acestechilibru perfect pe subjoc este de asemenea obtinul folosind forma extensiva(vezi Figura 2.12).

43

X Y

UA 3, 4 1, 4UB 2, 1 2, 0DA 2, 6 2, 6DB 2, 6 2, 6

(a)

X Y

A 3, 4 1, 4B 2, 1 2, 0

(b)

Figure 2.20: Forme normale folosite ın inductia ınapoi

2.4 Extensia mixta si echilibre Nash ın strategii mixte

In paragraful 2.1 am introdus forma normala pentru jocuri necooperative de npersoane (n ≥ 2) si notiunea de echilibru Nash ın strategii pure. Problemelefundamentale abordate au fost existenta si calcularea echilibrelor Nash purepentru jocuri matriceale si bimatriceale. Am vazut ca nu toate jocurile ma-triceale si bimatriceale au echilibre Nash pure. Clase de jocuri necooperativecare au echilibre Nash pure, cum sunt jocurile de tip potential si congestie, aufost introduse si unele exemple rezolvate. Identificarea jocurilor matricealecare au echilibre Nash pure s-a bazat ın principal pe cautarea punctelor sa (ınstrategii pure) folosind matricea initiala a jocului sau cea obtinuta prin eli-minarea iterativa a liniilor si coloanelor dominate. Determinarea echilibrelorNash pure pentru jocuri (bi)matriceale s-a facut folosind diagrame cu sageti,metoda eliminarii iterative a liniilor si coloanelor dominate, si functiile celmai bun raspuns (ın strategii pure) ale fiecarui jucator la toate strategiilepure ale celuilalt jucator. Totusi multe jocuri matriceale obtinute prin mo-delarea de situatii practice nu au punct sa ın strategii pure, si cele mai multejocuri bimatriceale nu au echilibre Nash ın strategii pure. Pentru asemeneajocuri e dificil sa se recomande jucatorilor strategii optimale (din punctulde vedere al teoriei jocurilor) de folosit ın situatia de joc analizata. Esteınsa ıntotdeauna posibil, ıntr-un joc finit, sa se recomande fiecarui jucatoro (schema rationala de) randomizare pe multimea strategiilor sale (pure),adica o strategie mixta optimala.

O strategie mixta pentru jucatorul i ın jocul 〈N, {Xi}i∈N , {Ki}i∈N〉 este

o distributie de probabilitate σi = (σ1i , ...., σ

|Xi|i ) pe multimea Xi a strategi-

ilor sale pure, adica un vector cu componente nenegative a caror suma esteegala cu 1. O strategie pura poate fi considerata ca un caz degenerat de

44

strategie mixta care atribuie probabilitatea 1 acelei strategii pure si proba-bilitatea 0 tuturor celelalte strategii pure ale jucatorului respectiv. Notam

cu Σi multimea strategiilor mixte σi ale jucatorului i. Atunci Σ =∏i∈N

Σi de-

semneaza multimea (convexa a) tuturor combinatiilor de strategii mixte alejucatorilor. Daca σ = (σ1, ..., σn) ∈ Σ, atunci Ki(σ) este plata asteptata dejucatorul i cand jucatorii aleg profilul strategic σ. Extensia mixta a jocului〈N, {Xi}i∈N , {Ki}i∈N〉 este jocul 〈N, {Σi}i∈N , {Ki}i∈N〉 care foloseste strate-giile mixte si platile asteptate ale jucatorilor. Un echilibru Nash ın strategiimixte, numit si echilibru Nash mixt, este o combinatie σ∗ = (σ∗1, ..., σ

∗n) de

strategii mixte astfel ıncat strategia σ∗i a fiecarui jucator i maximizeaza plataasteptata de acest jucator daca strategiile celorlalti jucatori (notate cu σ−i)sunt mentinute fixe, adica

Ki(σ∗) = max

σi

K(σi, σ∗−i) pentru toti i ∈ N.

Existenta echilibrelor Nash ın strategii mixte pentru jocuri finite a fostdemonstrata de Nash (1950a) folosind teorema de punct fix a lui Brouwer.

Teorema 2.21. (Nash) Orice joc strategic finit are cel putin un echilibruNash ın strategii mixte.

In cele ce urmeaza ne concentram atentia asupra calcularii echilibrelorNash (ın strategii mixte) ale jocurilor matriceale si bimatriceale. Fie A =(a(i, j))i=1,...,m;j=1,...,n un joc matriceal (de tip m×n). Multimea strategiilormixte pentru jucatorul 1 este

∆m =

{p ∈ IRm | p ≥ 0,

m∑i=1

pi = 1

},

iar multimea strategiilor mixte ale jucatorului 2 este

∆n :=

{q ∈ IRn | q ≥ 0,

n∑j=1

qj = 1

}.

Extensia mixta a lui A este jocul infinit

〈∆m, ∆n, K, L〉 cu K(p, q) :=m∑

i=1

n∑j=1

piaijqj = pT Aq; L(p, q) := −K(p, q).

45

Lema 2.22. Valoarea inferioara si valoarea superioara pentru jocul A satis-fac relatiile:

(i) v(A) = supp∈∆m

minj∈{1,...,n}

pT Aej;

(ii) v(A) = infq∈∆n

maxi∈{1,...,m}

eTi Aq, unde ej este vectorul j din baza standard

ın IRn.

Teorema 2.23. (Minmax, John von Neumann) Pentru fiecare joc matricealv(A) = v(A).

Strategiile mixte optimale ale jucatorilor si valoarea unui joc matriceal potfi determinate ıntotdeauna prin rezolvarea unei perechi de programe liniare.Aceasta metoda generala de rezolvare a jocurilor matriceale nu va fi tratataın acest curs. In cele ce urmeaza prezentam metode pentru a rezolva jocurimatriceale mici, adica jocuri de tip 2× 2, 2× n si m× 2, si jocuri simetrice.Multe jocuri matriceale obtinute prin modelarea unei situatii pur competitivesunt ori de tip 2×2, 2×n, m× 2, ori pot fi reduse la un astfel de joc pe bazaeliminarii iterative a liniilor si coloanelor dominate. Strategiile dominatesunt determinate prin relatia de dominare introdusa ın paragraful 2.1 si/sauprin relatia de dominare stochastica, pe care o introducem aici. Spunemca o strategie pura a unui jucator este dominata stochastic daca exista ocombinatie liniara a altor strategii pure ale acelui jucator care o domina.Rezolvarea jocului initial poate fi astfel redusa uneori la rezolvarea unui jocmatriceal de tipul 2 × 2, 2 × n sau m × 2. Strategiile optimale ale joculuimic, completate cu componente egale cu zero pentru liniile si/sau coloaneleignorate (pe baza relatiei de dominare (stochastica)), sunt strategii optimaleale jocului initial.

Rezolvarea jocurilor matriceale de tip 2×2. Fie A un joc matriceal detip 2×2. Pentru a determina strategiile optimale ale celor doi jucatori, cautamıntai un punct sa (ın strategii pure) verificand daca valoarea inferioara ajocului coincide cu valoarea superioara a jocului, adica daca exista un elemental matricei care este cel mai mic ın linia sa si cel mai mare ın coloana sa. Dacaexista un punct sa, atunci el determina strategiile optimale (linia si coloanacorespunzatoare), care sunt deci strategii pure. Daca nu exista punct sa (ınstrategii pure), aceasta ınseamna ca strategiile optimale (daca exista) trebuiesa fie strategii mixte, ın care fiecare jucator foloseste ambele strategii pure

46

cu probabilitati (strict) pozitive. Pentru a le determina formam matriceaadjuncta A∗ (interschimband elementele de pe diagonala principala si luandopusul celorlalte doua elemente). Vectorii JA∗ si A∗JT , unde J = (1, 1),corespund atunci sumarii liniilor si coloanelor, iar strategiile optimale vorfi proportionale cu JA∗ si A∗JT ; constanta multiplicativa este aleasa astfelıncat suma componentelor strategiilor optimale sa fie egala cu 1. Valoareajocului se determina folosind formula v=(a11a22−a21a12)/(a11+a22−a21−a12).

Rezolvarea jocurilor matriceale de tip 2×n si m×2. In orice joc detipul 2× n sau m× 2 exista ıntotdeauna ori un punct sa (ın strategii pure)ori o submatrice de tipul 2× 2 care da solutia jocului. O procedura generalapentru a rezolva un joc matriceal de tip 2 × n consta din urmatorii patrupasi:

1. Cauta un punct sa.

2. Daca nu exista puncte sa, vezi daca exista coloane dominate (stochas-tic) si sterge-le.

3. Din coloanele ramase ia toate combinatiile de cate doua coloane sirezolva toate jocurile de tip 2× 2 obtinute.

4. Ia jocul care are cea mai mica valoare. Strategiile optimale pentruacest joc sunt strategii optimale ale jocului initial, completand cu 0probabilitatile coloanelor nefolosite ın acest joc de tip 2× 2.

Pentru jocuri matriceale de tip m×2 exista o procedura similara, constanddin urmatorii patru pasi:

1. Cauta un punct sa.

2. Daca nu exista puncte sa , vezi daca exista linii dominate (stochastic)si sterge-le.

3. Din liniile ramase ia toate combinatiile de cate doua linii si rezolvatoate jocurile de tip 2× 2 obtinute.

4. Ia jocul care are cea mai mare valoare. Strategiile optimale pentruacest joc sunt strategii optimale ale jocului initial, completand cu 0probabilitatile liniilor nefolosite de acest joc de tip 2× 2.

Asa cum am mentionat deja, este uneori posibil ca jocuri matriceale detip m× n, cu m,n ≥ 3, sa fie reduse la jocuri de tip 2× 2, 2× n sau m× 2,prin eliminarea iterativa a liniilor si coloanelor dominate (stochastic). Uncaz special este cand matricea jocului initial este simetrica si exista simetriecompleta ıntre strategiile de acelasi tip, ceea ce permite reducerea jocului

47

initial astfel ıncat (cel putin) unul dintre jucatori sa aiba doar doua strategiipure. Pentru rezolvarea jocurilor de tip 2×2, 2×n si m×2 sunt de asemeneadisponibile metode grafice.

Rezolvarea jocurilor matriceale simetrice. Un joc matriceal simetriceste descris printr-o matrice patratica A = (aij)i,j=1,...,n stramb-simetrica,adica o matrice ale carei elemente satisfac egalitatea aij = −aji, pentru

toti i, j = 1, ..., n. Intr-un joc matriceal simetric ambii jucatori au aceleasistrategii (mixte) optimale si valoarea jocului este egala cu zero. Rezolvareajocurilor simetrice se bazeaza pe ideea ca daca r este o strategie optimala ın

jocul A, atuncin∑

i=1

riaij ≥ 0 pentru toti j si unele inegalitati sunt egalitati

(altfel v > 0). Strategia optimala r este o necunoscuta cu r1+r2+ ...+rn = 1.Vom determina componentele lui r folosind, ımpreuna cu ecuatia precedenta,n−1 ecuatii obtinute alegand n−1 inegalitati si considerandu-le ca egalitatisi rezolvand sistemul liniar de n ecuatii cu n necunoscute obtinut. Dacari ≥ 0 pentru toti i si inecuatia a n-a e verificata, am obtinut o strategieoptimala.

Jocurile bimatriceale fara echilibre Nash ın strategii pure (si de asemeneacele cu echilibre Nash ın strategii pure) pot fi studiate folosind extensia mixtaa jocului bimatriceal. Extensia mixta a unui joc bimatriceal (A,B) de tipm × n este data prin (∆m, ∆n, K, L), unde K(p, q) = pT Aq si L(p, q) =pT Bq, pentru toti p ∈ ∆m si toti q ∈ ∆n. Teorema 2.21 asigura existentaechilibrelor Nash ın strategii mixte pentru orice joc bimatriceal finit (A,B),adica existenta echilibrelor Nash pentru extensia mixta a acestui joc. Notamcu NE(A,B) multimea echilibrelor Nash pentru extensia mixta a lui (A,B).Fie p ∈ ∆m si q ∈ ∆n. Suportul strategiei mixte p a jucatorului 1 este C(p) :={i ∈ {1, ...,m} | pi > 0}. Multimea celor mai bune raspunsuri ın strategiipure ale jucatorului 1 la strategia mixta q este PB1(q) := {i ∈ {1, ..., m} |eT

i Aq = maxr∈{1,...,m}

eTr Aq}, iar multimea celor mai bune raspunsuri ın strategii

mixte ale jucatorului 1 la q este B1(q) := {p ∈ ∆m | pT Aq = maxr∈{1,...,m}

eTr Aq}.

Analog se definesc C(q), PB2(p) si B2(p).

Teorema 2.24. Fie (A,B) un joc bimatriceal de tip m × n, p ∈ ∆m siq ∈ ∆n. Profilul strategic (p∗, q∗) este un echilibru Nash al extensiei mixte alui (A,B) daca si numai daca C(p∗) ⊆ PB1(q

∗) si C(q∗) ⊆ PB2(p∗).

48

Strategiile mixte optimale ale jucatorilor si platile jucatorilor corespunza-toare acestor strategii pot fi ıntotdeauna determinate folosind legatura dintreteoria complementaritatii liniare si jocuri bimatriceale. Acesta metoda ge-nerala de rezolvare a jocurilor bimatriceale nu va fi prezentata aici. In celece urmeaza prezentam o metoda algebrica pentru determinarea echilibrelorNash ın strategii mixte ale jocurilor bimatriceale de tip 2×2 si o metodagrafica pentru rezolvarea jocurilor de doua persoane cu suma variabila.

Rezolvarea jocurilor bimatriceale de tip 2×2. Un echilibru Nash pen-tru un joc bimatriceal (K(i, j)i=1,2; j=1,2, L(i, j)i=1,2; j=1,2) poate fi determinatfolosind urmatoarea procedura:

1. Se formeaza jocurile matriceale K(i, j)i=1,2; j=1,2 si L(i, j)i=1,2; j=1,2, se-parand platile celor doi jucatori.

2. Se determina strategia mixta optimala p∗ a jucatorului 1 ın jocul ma-triceal L si strategia mixta optimala q∗ a jucatorului 2 ın jocul K,folosind metoda prezentata pentru jocuri matriceale de tip 2 × 2. Pe-rechea (p∗, q∗) este o strategie mixta optimala a jocului bimatriceal detip 2× 2.

Aceasta metoda este aplicabila de asemenea ın jocuri mai largi ce pot fireduse la tipul 2×2 prin eliminarea iterativa a liniilor si coloanelor dominate(stochastic).

Rezolvarea jocurilor de doua persoane cu suma variabila. Fie G =〈X, Y, K, L〉 un joc de doua persoane cu suma variabila. Fie B1 : Y→X,B2 : X → Y multifunctiile cel mai bun raspuns pentru jucatorul 1 si, res-pectiv, jucatorul 2 ın jocul G. Fie G∗

1 := {(x, y) ∈ X × Y | x ∈ B1(y)}si G2 := {(x, y) ∈ X × Y | y ∈ B2(x)}. Observam ca G2 este graficulmultifunctiei B2, iar G∗

1 este imaginea graficului G1 ⊂ Y × X a lui B1 subaplicatia Y ×X → X × Y cu (y, x) → (x, y) pentru toti (y, x) ∈ Y ×X. De-terminarea echilibrelor Nash ın strategii mixte ale jocului se poate face prinreprezentarea grafica, ın acelasi sistem de coordonate, a (multi)functiilor ”celmai bun raspuns” ale jucatorilor. Aceasta metoda grafica se bazeaza pe fap-tul ca (x∗, y∗) ∈ NE(G) ←→ x∗ ∈ B1(y

∗), y∗ ∈ B2(x∗) ←→ (x∗, y∗) ∈ G∗

1,(x∗, y∗) ∈ G2 ←→ (x∗, y∗) ∈ G∗

1 ∩G2. Deci, (x∗, y∗) ∈ NE(G) ←→ (x∗, y∗) ∈G∗

1 ∩ G2. Exemplificam aceasta metoda grafica folosind un joc denumit im-propriu ”Batalia sexelor”.

Exemplul 2.25. (Batalia sexelor) Un cuplu trebuie sa decida daca vor mergeımpreuna la un meci de box sau la un spectacol de opera. Sotul prefera meciul

49

de box, ın timp ce sotia prefera spectacolul de opera. Modelarea unei situatiide acest tip ca un joc necooperativ conduce la forma normala din Figura2.21 (b). Notam cu (x, 1− x) strategia mixta a jucatorului 1 si cu (y, 1− y)strategia mixta a jucatorului 2. Functiile de plata ale jucatorilor sunt:

K1(x, y) = 3xy + (1− x)(1− y) = (4y − 1)x− y + 1,K2(x, y) = xy + 3(1− x)(1− y) = (4x− 3)y − 3x + 3.

Graficele corespunzatoare multifunctiilor cel mai bun raspuns, G∗1 si G2, unde

G∗1 = {(x, y) | K1(x, y) este maxim ın raport cu x pentru y fixat},

G2 = {(x, y) | K2(x, y) este maxim ın raport cu y pentru x fixat},sunt reprezentate ın Figura 2.21(a) cu linie plina si, respectiv, cu linie − − −.Echilibrele Nash ale jocului, (0,0), (3/4, 1/4) si (1,1), sunt de asemenea vi-zualizate ın Figura 2.21(a) ca puncte de intersectie ale celor doua grafice.

Meci Opera

Meci 3, 1 0, 0Opera 0, 0 1, 3

(b)

Figure 2.21: Jocul ”Batalia sexelor”

50

2.5 Informatie si jocuri necooperative

Teoria jocurilor necooperative ıncearca sa prezica rezultatul ın situatii de de-cizie interactiva, adica ın situatii ın care rezultatul este determinat de catreactiunile tuturor jucatorilor si nici-un jucator nu are control complet asuprasituatiei. Ea foloseste presupunerea ca jucatorii se comporta rational, adicaurmeaza scopuri exogene bine-definite si rationeaza strategic, adica iau ınconsideratie atat cunoasterea lor cat si posibilitatile de comportare rationalaale celorlalti jucatori. Informatia disponibila jucatorilor ıntr-un joc necoope-rativ face o mare diferenta privind ceea ce jucatorii pot sa faca sau ar trebuisa faca. In paragrafele precedente am studiat jocuri necooperative ın formastrategica (normala) si ın forma extensiva ın care platile corespunzatoare ju-catorilor sunt deterministe si ”common knowledge”. Forma extensiva a unuijoc are un caracter dinamic ıntrucat ilustreaza desfasurarea secventiala ıntimp a jocului. Forma normala (strategica) analizeaza o situatie conflictualafolosind o descriere concisa, considerand o singura jucare a jocului si pre-supunand ca jucatorii ısi aleg alternativa strategica simultan si independent.Jocurile ın forma normala studiate ın paragrafele 2.1 si 2.4 sunt de aceeanumite jocuri statice sau jocuri de tip ”one-shot”, ın comparatie cu jocurileın forma extensiva, care sunt numite jocuri dinamice. Jucarea repetata aunui joc static (”one-shot”) de un numar finit sau infinit de ori are ınsa uncaracter dinamic si face obiectul de studiu al teoriei jocurilor prin modelespecifice. Mai departe, am vazut ca ıntr-un joc ın forma extensiva jucatoriipot avea informatie perfecta si/sau imperfecta. Un jucator are informatieperfecta cand el stie exact tot ce s-a ıntamplat pana atunci, de fiecare datacand o decizie trebuie facuta. Un joc are informatie perfecta daca fiecarejucator ın acel joc are informatie perfecta. Daca exista jucatori care nu auinformatie perfecta, atunci jocul este un joc cu informatie imperfecta.

O situatie ın care un jucator stie ceva ce un alt jucator nu stie, se numesteasimetrie de informatie. Asimetriile de informatie se ıntalnesc frecvent ınsituatiile practice. Informatia imperfecta si asimetriile informationale auimplicatii pentru comportarea strategica a jucatorilor si platile asteptatede jucatori. Din punctul de vedere al caracterului simetric sau asimetrical informatiei de care dispun jucatorii, teoria necooperativa a jocurilor dis-tinge ıntre doua tipuri de modele: jocuri cu informatie completa si jocuri cuinformatie incompleta. Jocurile cu informatie completa nu afiseaza asimetriiinformationale, cu exceptia posibila a informatiei asimetrice privind actiunilejucatorilor. Informatia privata privind elemente intangibile ın situatii strate-

51

gice poate fi modelata prin ıncorporarea unor evenimente aleatoare (numiteadeseori mutari ale naturii) ın specificarea unui joc cu informatie incom-pleta. Expresia informatie incompleta se refera la jocuri care au mutari alesansei (naturii) care genereaza informatie asimetrica pentru jucatori. Mo-delele studiate ın paragrafele 2.1-2.4 sunt jocuri cu informatie completa.Am studiat asadar urmatoarele tipuri de jocuri necooperative: jocuri staticecu informatie completa; jocuri dinamice cu informatie completa si perfecta;jocuri dinamice cu informatie completa dar imperfecta. In toate aceste mo-dele de jocuri necooperative se presupune ca jucatorii au capacitati idealede rationare si comportare strategica si ca platile posibil de obtinut de catrejucatori sunt deterministe si common knowledge, fiind ori indicate explicit ındescrierea jocului, ori platile asteptate de jucatori (cand sansa joaca un rol)care pot fi calculate de toti jucatorii pe baza descrierii jocului. Selectareadeciziilor optimale de catre jucatori se bazeaza pe principiul ca a castiga maimulti bani (sau a pierde mai putini bani) este ıntotdeauna mai bine. In cazulunui joc de tip cost , selectarea strategiei optimale se bazeaza pe principiulca a plati un cost mai mic e mai bine decat a plati un cost mai mare.

Reamintim ca jocurile statice cu informatie completa sunt modele deforma 〈N, {Xi}i∈N , {Ki}i∈N〉 . Predictii privind comportarea optimala a ju-catorilor se pot obtine folosind notiunea de echilibru Nash ın strategii pure(echilibru Nash pur) sau ın strategii mixte (echilibru Nash mixt). Tehnicifolositoare pentru rezolvarea jocurilor statice cu informatie completa sunt:eliminarea iterativa a strategiilor (strict) dominate (stochastic), utilizareafunctiilor celui mai bun raspuns (ın strategii pure sau mixte), teoria pro-gramarii liniare si cea a complementaritatii liniare, metode pentru tipuriparticulare de jocuri (de tip 2×2, 2×n, m×2 si simetrice).

Modelul de joc static cu informatie incompleta, numit joc strategic detip Bayes (”static Bayesian game”), este o extensie a modelului de joc staticcu informatie completa. Un joc static Bayesian este un model de forma〈N, {Ai}i∈N , {Ti}i∈N , {pi}i∈N , {ui}i∈N〉, ın care N este multimea jucatorilorsi pentru fiecare i ∈ N :

• Ai este multimea actiunilor posibile ale jucatorului i.

• Ti este multimea tipurilor posibile pentru jucatorul i.

• pi este distributia de probabilitate existenta pe multimea Ti a tipurilorjucatorului i.

• ui este functia de utilitate a jucatorului i (analoaga functiei de plataKi).

52

Conceptul de solutie specific este acela de echilibru Nash de tip Bayes(”Bayesian Nash equilibrium”), o extensie a notiunii de echilibru Nash.

Reamintim ca jocurile dinamice cu informatie completa (si perfecta sauimperfecta) sunt modele de forma 〈N, T 〉, unde T este arborele jocului.Recunoastem daca un joc ın forma extensiva este cu informatie perfectasau imperfecta privind la multimile de informatie ale jucatorilor (delimitategrafic prin − − −). Intrucat arborele jocului ın forma extensiva continetoata informatia necesara pentru determinarea strategiilor tuturor jucato-rilor, modelul de joc dinamic cu informatie completa poate fi consideratca o extensie a modelului de joc static cu informatie completa, de forma〈N, T, {Xi}i∈N〉, unde Xi este multimea strategiilor jucatorului i (planuricomplete de actiune ale jucatorului i de-a lungul arborelui T al jocului).Predictii privind comportarea optimala a jucatorilor pot fi obtinute folosindconceptul de echilibru Nash perfect pe subjoc, care selecteaza dintre echili-brele Nash ale jocului (ın forma normala) corespunzator doar pe cele caresunt ”credibile”. Am vazut ca echilibrele Nash perfecte pe subjoc pot fi de-terminate folosind metoda inductiei ınapoi pe baza formei extensive a joculuisau pe baza formelor normale ale jocului initial si ale tuturor subjocurilorsale.

Modelul de joc dinamic (ın forma extensiva) cu informatie incompletaeste o extensie a modelului de joc ın forma extensiva cu informatie com-pleta care se bazeaza pe considerarea multimilor de informatie ale jucatorilorıncorporand elemente de tip ”belief” (”information set(s) with players’ be-lief”). Figura 2.22 ilustreaza deosebirea dintre forma extensiva a unui joccu informatie completa (Figura 2.22(a)) si a unuia cu informatie incompleta(Figura 2.22(b)) ce modeleaza o aceeasi situatie strategica, descrisa ın Exem-plul 2.26, pentru doua ipostaze diferite.

Exemplul 2.26. (Jocul investitiei) Doi prieteni trebuie sa decida daca sainvesteasca sau nu efort ın repararea unui motociclete stricate ce apartineunuia dintre ei, dat fiind ca dupa aceea ar putea-o folosi ın comun. Unulpoate repara partea mecanica a motocicletei, iar celalalt partea ei electrica.Presupunem ca motocicleta e proprietatea jucatorului 1. Astfel, pe langaactiunile posibile I (investeste) si N (nu investeste), valabile ambilor jucatori,jucatorul 1 are posibilitatea sa decida daca, dupa repararea motocicletei, o vafolosi singur sau ın comun. Strategiile corespunzand acestor decizii le notamcu E (pentru cazul cand jucatorul 1 e egoist) si A (pentru cazul cand el ealtruist).

53

Evident, ambii jucatori stiu ca jucatorul 1 poate fi egoist sau altruist.Plati posibile pentru acest joc cu informatie completa sunt date ın Figura2.22 (a).

(a)

(b)

Figure 2.22: Jocul investitiei

54

Situatia analizata poate fi descrisa mai precis luand ın consideratie faptulca majoritatea indivizilor sunt, ın mod obisnuit, ınclinati sa puna intere-sele individuale mai presus de cele colective (induse de cooperare) si caree tipul fiecarui individ particular depinde de fapt de natura, fiecare individcunoscandu-si propriul tip. Ca urmare, o modelare mai realista a situatiei caun joc se face considerand natura ca un jucator cu doua strategii: O (pentrutip obisnuit) cu probabilitate mai mare, spre exemplu 3/4, si C (pentru tipcooperant) cu probabilitate mai mica, spre exemplu 1/4. Jocul obtinut esteunul cu informatie incompleta, fiindca natura genereaza informatie asimetri-ca pentru jucatori. Jocul dinamic cu informatie incompleta corespunzatorjocului dinamic cu informatie completa din Figura 2.22 (a) este reprezentatın Figura 2.22 (b).

Un joc ın forma extensiva cu informatie incompleta este un tiplet de

forma⟨N, T , {Xi}i∈N

⟩, unde N este multimea jucatorilor, T este ansamblul

multimilor de informatie (continand informatia de tip ”belief”) ale jucatori-lor, si pentru fiecare i ∈ N, Xi este multimea strategiilor jucatorului i.

Conceptul de solutie specific jocurilor dinamice cu informatie incompletaeste acela de echilibru perfect de tip Bayes (”perfect Bayesian equilibrium”).Acesta este o extensie a conceptului de perfect echilibru pe subjoc. Unechilibru perfect de tip Bayes poate fi de asemenea considerat ca o extensiea notiunii de echilibru Nash de tip Bayes.

Adesea, participantii ıntr-o situatie de interactiune strategica trebuie safaca decizii ın conditii de incertitudine. Ei pot fi:

• Incerti cu privire la parametrii obiectiv ai mediului (”environment”) ıncare actioneaza.

• Imperfect informati asupra evenimentelor ce pot aparea ın joc.

• Incerti cu privire la actiunile (posibil nedeterministe ale) altor jucatori.

• Incerti cu privire la modul de rationare a celorlalti jucatori.

Principiile de rationalitate si cunoasterea de catre jucatori a posibilitatilorde rationare ale jucatorilor joaca un rol fundamental ın teoria necooperativaa jocurilor. In teoria jocurilor necooperative se presupune curent ca regulilejocului sunt cunoscute perfect de catre toti jucatorii si ca abilitatea jucato-rilor de a analiza jocul este ideala. Este common knowledge ca toti jucatoriisunt rationali si ınteleg perfect jocul care este jucat, adica fiecare jucator

55

cunoaste jocul, fiecare jucator stie ca fiecare jucator cunoaste jocul, s.a.m.d.Optimalitatea comportarii jucatorilor se bazeaza pe cunoasterea pe care oau jucatorii. Nu numai cunoasterea de catre un jucator a unui parametruexogen, ci si cunoasterea sa despre cunoasterea celorlalti jucatori joaca unrol. In modelele de joc studiate se presupune ca posibilitatile de rationare alejucatorilor sunt nelimitate, ceea ce asigura ınvatarea instantanee a joculuisi selectarea ın timp real a strategiei optimale. In cele mai multe situatiipractice o asemenea presupunere nu este realista. Jocurile cu rationalitatelimitata (”bounded rationality”) fac de asemenea obiectul de studiu al teorieijocurilor.

56

3 JOCURI COOPERATIVE

Acest capitol este dedicat modelelor din teoria cooperativa a jocurilor. For-mele de reprezentare a jocurilor folosite ın aceste modele sunt forma strate-gica si forma coalitionala, iar notiunea de coalitie (grup de jucatori) joacaun rol central. Un joc ın forma strategica sau ın forma coalitionala estecooperativ daca jucatorii pot face acorduri ferme (”binding agreements”)privind alegerea strategiilor sau distributia platilor, chiar daca aceste acor-duri nu sunt specificate de regulile jocului sau implicate de acestea. Unacord (sau contract) este ferm daca nerespectarea lui conduce la penalizarimonetare, fapt care ıi ımpiedica pe jucatori sa nu-l respecte. In paragra-ful 3.1 introducem jocuri cooperative ın forma strategica si aratam ca oricejoc necooperativ ın forma normala (strategica) poate fi jucat ”cooperativ”daca acordurile ferme ıntre jucatori sunt permise. Intr-un joc cooperativ ınforma strategica jucatorii ısi coreleaza strategiile pure sau folosesc strategiicorelate. Paragrafele 3.2 - 3.5 sunt dedicate jocurilor cooperative ın formacoalitionala cu plati laterale, numite si jocuri ın forma functiei caracteris-tice. Acest model teoretic de joc cooperativ a fost introdus de catre Johnvon Neumann si Oskar Morgenstern (1944) pornind de la forma strategica ajocurilor cu utilitati transferabile (adica utilitati care sunt liniare ın bani).Valoarea fiecarei coalitii S ⊆ N , unde N={1, 2, ..., n} este multimea finitasi nevida a jucatorilor, ıntr-un joc strategic cu utilitati transferabile este va-loarea sa maxima ın jocul de doua persoane cu suma nula unde adversarullui S este N \ S (ansamblul jucatorilor care nu sunt membri ai coalitiei S) sistrategii corelate sunt folosite de ambii jucatori, S si N \ S. In paragrafele3.2-3.5 consideram functia caracteristica (coalitionala) a unui joc cooperativca o notiune primara, ıntrucat ın multe situatii de interactiune strategicaunde cooperarea ıntre jucatori este posibila si benefica (adica conduce lasporirea castigurilor sau diminuarea costurilor) functia caracteristica poatefi construita direct, din descrierea neformala a situatiei, fara nici o referire laun joc strategic. Paragraful 3.2 introduce notiuni de baza ın teoria jocurilor

57

cooperative ın forma functiei caracteristice, incluzand notiunea de sambure(Gillies, 1953), care joaca ın cadrul acestei teorii un rol similar cu cel alnotiunii de echilibru Nash ın teoria jocurilor necooperative. Paragrafele 3.3-3.5 sunt dedicate conceptelor de solutie de tip ”single-valued” cu rol predo-minant ın teoria jocurilor cooperative, si anume: valoarea Shapley (Shapley,1953), σ-valoarea si τ -valoarea (Tijs, 1981), nucleolul (Schmeidler, 1969) siAL-valoarea (Tijs, 2005). In paragraful 3.6 analizam rolul comunicarii ıntrejucatori si al informatiei disponibile jucatorilor ın cadrul teoriei jocurilorcooperative ın forma functiei caracteristice. Sunt mentionate unele clasede jocuri cooperative cu restrictii de comunicare ıntre jucatori si jocuri cuasimetrii informationale. Incheiem capitolul cu o privire globala asupra mo-delelor teoriei jocurilor cooperative ın forma coalitionala.

3.1 Jocuri cooperative ın forma strategica

In capitolul 2 am studiat si rezolvat jocuri necooperative, ın care comuni-carea ıntre jucatori ınainte de ınceperea jocului (”pre-play communication”),acordurile ferme (contractele) si platile laterale sunt interzise prin regulilejocului. Chiar daca comunicarea ıntre jucatori ınainte de ınceperea joculuinu e interzisa, ea nu poate conduce la acorduri ferme ıntre jucatori privindalegerea strategiilor sau distribuirea platilor. Rezolvarea jocurilor necoo-perative s-a facut folosind notiunea de echilibru Nash si variante ale sale.Totusi, asa cum am vazut ın paragraful 2.1, un profil strategic corespunzatorunui echilibru Nash pur ın jucarea necooperativa a unui joc ar putea sa nuofere cea mai avantajoasa alternativa de plata tuturor jucatorilor, chiar siın situatia ın care jocul are un echilibru Nash unic. Jucarea cooperativa aunui joc ın forma strategica, ın situatia cand acordurile ferme ıntre jucatorisunt permise (explicit sau implicit) poate ınlatura acest inconvenient. Jocul”Dilema prizonierilor”, reprezentat ın Figura 2.4 (b), este un exemplu clasicpentru evidentierea diferentelor dintre jucarea necooperativa si cooperativaa unui joc. In jocul ”Dilema prizonierilor”, doi suspecti de crima ınchisipentru un conflict minor si pusi ın celule separate sunt interogati (sepa-rat) facandu-li-se promisiunea de gratiere ın caz de recunoastere a crimei sidenuntare a complicelui. Platile din jocul bimatriceal din Figura 2.4 (b) suntanii de ınchisoare ce ıi asteapta pe cei doi detinuti pentru diferitele situatii decomportare strategica, fiecare dintre ei putand folosi una din doua strategii:R – recunoaste crima facuta – si N – nu o recunoaste. Jucarea necooperativaa acestui joc conduce la echilibrul Nash (unic), (linia 1, coloana 1) ın Figura

58

2.4 (b), care asigura jucatorilor plati egale cu cate 5 ani de ınchisoare. Totusi,ambii jucatori ar putea obtine ”plati” mai bune, anume cate un singur an deınchisoare, daca ar alege (de comun acord) profilul strategic (linia 2, coloana2) din Figura 2.4 (b), prin corelarea strategiilor lor pure. Consideram acumjocul de tip ”ultimatum” din Exemplul 2.18. In jucarea necooperativa a aces-tui joc, jucatorul 2 este de fapt fortat sa accepte oricare dintre propunerilejucatorului 1 fiindca altfel nu primeste nimic. Jucarea cooperativa a aces-tui joc va conduce, prin acordul jucatorilor asupra diviziunii celor 6 unitativalorice, la schema de divizare 3-3, care este echitabila (”fair”) pentru ambiijucatori.

In jucarea cooperativa a unui joc (de tip castig) ın forma strategica secauta o solutie optimala, adica un profil strategic care asigura o plata to-tala maxima, si o distributie echitabila pentru toti jucatorii a acestei platimaxime. O asemenea distributie ar trebui sa ia ın consideratie pozitiile denegociere ale jucatorilor (care sunt diferite de abilitatile lor de negociere)si/sau posibilitatea efectuarii de plati laterale ıntre jucatori. Intr-un joc bi-matriceal (A,B) (de tip castig), o solutie optimala si o distributie echitabilaa platii totale maxime ar putea fi calculate de catre un arbitru impartial sionest, urmand urmatoarea procedura:

1. Se determina valoarea ν a jocului A− B; aceasta reprezinta avantajulrelativ pe care jucatorul 1 ıl are asupra jucatorului 2.

2. Se determina plata totala maxima posibil de obtinut, notata cu P , cavaloarea maxima a elementelor matricei A + B.

3. Daca e posibil, se ımparte plata totala maxima P astfel ıncat jucatorul1 primeste ν unitati valorice mai mult decat jucatorul 2 (adica sepastreaza avantajul relativ ν al jucatorului 1). Daca profilul strate-gic care corespunde platii totale maxime P da prea mult unui jucator,atunci (pentru a pastra cooperarea si plata P ) acel jucator ar trebui safaca o plata laterala (oferind celuilalt jucator parte din plata sa) astfelıncat sa se obtina o ımpartire a platii P care pastreaza avantajul relatival jucatorului 1.

Exemplul 3.1. Ilustram aplicarea procedurii descrise mai sus consideranddoua jocuri bimatriceale: jocul (A1, B1) cu ν1=3 si P1=5 care corespundeunui profil strategic care asigura jucatorului 1 plata 4 si jucatorului 2 plata

59

1, si jocul (A2, B2) cu ν2=1 si P2=5 care corespunde unui profil strategic careda jucatorului 1 plata 1 si jucatorului 2 plata 4. Observam ca pentru jocul(A1, B1) distributia (4,1) corespunzatoare profilului strategic optimal esterezonabila pentru ambii jucatori fiindca ea ıncorporeaza avantajul relatival jucatorului 1 fata de jucatorul 2. In cazul jocului (A2, B2), jucatorul2 trebuie sa faca o plata laterala de 2 unitati valorice catre jucatorul 1,pentru a respecta avantajul relativ al jucatorului 1 fata de el. Astfel, jucareacooperativa a jocului bimatriceal (A2, B2) conduce ın final la plata 3 pentrujucatorul 1 si plata 2 pentru jucatorul 2.

Evident, procedura descrisa mai sus poate fi aplicata de asemenea unui jocbimatriceal de tip cost cu modificarea pasului 2 al procedurii, unde, ın acestcaz, elementul minim al matricii A + B va fi selectat. Pentru jocul ”Dilemaprizonierilor”, ν=0, P=2 si distributia platilor pentru profilul strategic careasigura plata totala 2 este (1,1). Aceasta distributie e echitabila pentru ambiijucatori. Evident, ın jocul ”Dilema prizonierilor” jucatorii nu pot face platilaterale.

In cele ce urmeaza, introducem notiunea de joc cooperativ ın forma strate-gica si atasam fiecarui joc necooperativ ın forma normala (strategica) joculcooperativ ın forma strategica corespunzator.

Un joc cooperativ ın forma strategica este un triplet

〈N, (Σ(S))∅6=S⊆N , {ui}i∈N〉 ,unde: N este multimea finita si nevida a jucatorilor; pentru fiecare submul-time nevida S de jucatori, Σ(S) este multimea nevida a strategiilor lui S,cu proprietatea Σ(S ∪ T )⊇Σ(S)×Σ(T ) pentru toti S, T astfel ıncat ∅ 6= S,T⊆N, S∩T = ∅; pentru fiecare i ∈ N, ui : Σ(N) −→ IR este functia de plataa jucatorului i.

Orice joc necooperativ finit ın forma normala (strategica),

〈N, {Xi}i∈N , {Ki}i∈N〉 ,genereaza un joc cooperativ ın forma strategica prin considerarea strategiilorcorelate. Fie S o submultime nevida de jucatori (coalitie). O strategie core-

lata pentru S este o distributie de probabilitate pe XS=∏i∈S

Xi. Notam cu

Σ(S) multimea tuturor strategiilor corelate pentru S si cu σS o strategie core-lata arbitrara ın Σ(S). Presupunem ca acordurile ferme ıntre jucatori sunt

60

permise si orice strategie corelata σS pentru S 6= ∅ cu |S|=2 este sprijinitaprintr-un acord ferm ıntre membrii lui S. Pentru fiecare i ∈ N , consideramfunctia de plata ui : Σ(N) −→ IR, definita prin

ui(σN)=∑

x∈XN

σN(x)Ki(x) pentru toti σN ∈ Σ(N) si toti i ∈ N.

Astfel, situatii de interactiune strategica ın care jucatorilor li se interziceaıncheierea acordurilor ferme, modelate ın capitolul 2 ca jocuri necooperative,pot fi modelate ca jocuri cooperative ın forma strategica daca restrictiileinitiale privind comunicarea si cooperarea ıntre jucatori sunt ridicate. Uncaz particular de joc cooperativ ın forma strategica, obtinut pornind de laun joc necooperativ ın forma strategica prin admiterea acordurilor fermeıntre jucatori, este cel ın care pentru fiecare coalitie nevida S consideramΣ(S)=XS, ceea ce corespunde corelarii strategiilor pure ale jucatorilor. Ju-carea cooperativa a jocului ”Dilema prizonierilor” corespunde astfel unui joccooperativ ın forma strategica ın care profilurile strategice pure sunt aleseprin acordul jucatorilor.

3.2 Jocuri cooperative ın forma functiei caracteristicesi samburele

Situatii practice ın care partile implicate pot sa-si sporeasca castigurile sausa-si reduca costurile prin cooperare pot fi modelate adesea folosind jocuricooperative ın forma functiei caracteristice (cu plati laterale) de tip castigsau de tip cost.

Un joc cooperativ de tip castig este o pereche 〈N, v〉, unde N este multimeafinita si nevida a jucatorilor, adesea de forma N={1, 2, ..., n}, iar v : 2N −→ IReste functia caracteristica (coalitionala), cu v(∅)=0, unde pentru fiecare coali-tie (grup de jucatori) S ∈ 2N \{∅}, v(S) reprezinta castigul pe care S ıl poateobtine prin cooperarea membrilor sai (fara ajutorul nici-unui alt jucator dinafara lui S).

Exemplul 3.2. Trei prieteni, etichetati ın continuare cu 1, 2, 3, posesoride materii prime de tip A si B ın cantitatile A1 = 0, A2 = 1, A3 = 5,B1 = 3, B2 = 1, B3 = 9, planuiesc sa deschida ımpreuna o ıntreprinderemica pentru a fabrica un produs care necesita pe unitate o unitate din ma-teria prima A si doua unitati din materia prima B si se poate vinde cu 50

61

lei pe unitate. Cooperarea micilor ıntreprinzatori poate genera castiguri, darei vor intra ın aceasta afacere numai daca vor cadea de acord asupra modu-lui de distribuire a castigului total. Teoria cooperativa a jocurilor poate fifolositoare. Situatia descrisa poate fi modelata ca un joc a carui functie ca-racteristica este v(∅) = v({1}) = v({2}) = 0, v({3}) = 200, v({1, 2}) = 50,v({1, 3}) = v({2, 3}) = 250, v({1, 2, 3}) = 300. Un concept de solutie din teo-ria cooperativa a jocurilor poate fi apoi folosit pentru a propune o distributiea celor 300 unitati valorice ıntre cei trei ıntreprinzatori (vezi Exemplul 3.19).

Un joc cooperativ de tip cost este o pereche 〈N, c〉, unde N este multimeafinita si nevida a jucatorilor si c : 2N −→ IR este functia coalitionala (carac-teristica) cu c(∅)=0, unde pentru fiecare coalitie S ∈ 2N\{∅}, c(S) reprezintacostul pe care S trebuie sa-l plateasca daca membrii ei coopereaza. Exem-plul 3.3 modeleaza ca un joc cooperativ de tip cost o situatie privind insta-larea unor sisteme de alarma ın apartamente. Orice joc cooperativ de tipcost genereaza un joc cooperativ de tip castig, unde pentru fiecare coalitieS ∈ 2N\{∅}, castigul v(S) obtinut prin cooperare reprezinta economiile rea-lizate de S prin reducerea costurilor ca urmare a cooperarii membrilor sai siv(∅)=0, adica :

(3.1) v(S) :=∑i∈S

c({i})− c(S), pentru toti S ∈ 2N .

Exemplul 3.3. Trei familii care locuiesc ın acelasi bloc de locuinte vor sa-siinstaleze sisteme de alarma cu aceeasi firma. Firma le face o oferta cu cos-turi pentru contracte individuale, costuri pentru contracte pentru cate douafamilii si costul pentru un contract colectiv. Cele trei familii trebuie sa decidadaca coopereaza sau nu ın vederea reducerii costurilor si, ın situatia ın caredecid sa coopereze, trebuie sa cada de acord asupra ımpartirii costului total.Teoria cooperativa a jocurilor poate fi utila pentru rezolvarea acestei proble-me prin modelarea situatiei ca un joc cooperativ de tip cost si folosirea unuiconcept de solutie considerat rezonabil de catre toate cele trei familii. Pentrusituatia descrisa, N={1, 2, 3}, iar oferta firmei genereaza functia coalitiona-la c, cu c({1})=100, c({2})=90, c({3})=80, c({1, 2})=130, c({1, 3})=110,c({2, 3})=110 si c({1, 2, 3})=140. Evident, c(∅)=0. Economiile realizate decele trei familii prin cooperarea lor sunt descrise prin jocul de tip castig cores-punzator (obtinut folosind formula (3.1)): v(∅)=v({1})=v({2})=v({3})=0,v({1, 2})=60, v({1, 3})=70, v({2, 3})=60 si v({1, 2, 3})=130.

62

Intr-un joc cooperativ de tip castig jucatorii urmaresc maximizarea cas-tigurilor, iar ıntr-un joc de tip cost ei urmaresc minimizarea costurilor (sau,echivalent, maximizarea economiilor ın jocul de tip castig asociat jocului detip cost). In cele de urmeaza, prin 〈N, v〉 vom subıntelege un joc de tip castigsi prin 〈N, c〉 vom subıntelege un joc de tip cost.

O reprezentare geometrica a jocurilor cooperative ın forma functiei carac-teristice identifica un joc 〈N, v〉 sau 〈N, c〉 cu |N |=n, cu un vector (punct)ın IR2n−1, ale carui componente sunt valorile functiei caracteristice pentruo ordine fixata a celor 2n − 1 coalitii nevide de jucatori. In mod normal,un joc este identificat cu functia sa caracteristica (coalitionala). MultimeaGN a functiilor coalitionale v cu multimea jucatorilor N formeaza, ın raportcu adunarea si ınmultirea cu un scalar a functiilor coalitionale, un spatiuliniar (2n − 1)–dimensional. O baza interesanta a acestui spatiu liniar estemultimea jocurilor unanime uT , T ∈ 2N \ {∅}, care sunt definite prin

(3.2) uT (S)=

{1 daca T⊆S,

0 altfel.

Interpretarea unui joc unanim uT este ca un castig (sau o economie la costuri)de o unitate valorica poate fi obtinut daca si numai daca toti jucatorii dincoalitia T sunt implicati ın cooperare. Orice joc v ∈ GN poate fi exprimatca o combinatie liniara de jocuri unanime de forma

(3.3) v=∑

T∈2N\{∅}cT uT , cu cT =

∑S:S⊆T

(−1)|T |−|S|v(S).

Exemplul 3.4. Jocul v din Exemplul 3.3 se poate scrie sub formav = 60u{1,2} + 70u{1,3} + 60u2,3 − 60u{1,2,3}.

Jocurile unanime sunt un caz special de jocuri simple. Un joc v ∈ GN

se numeste simplu daca v(S) ∈ {0, 1} pentru toti S ∈ 2N \ {∅}, v(∅)=0 siv(N)=1.

Exemplul 3.5. Consideram urmatoarele situatii de votare: votare prinmajoritate simpla (jumatate plus 1) si votare cu majoritate minima fixata siun grup cu putere veto. Primul tip de votare este folosit frecvent, inclusivpentru trecerea legilor ın parlament. Presupunand ca parlamentul consta din100 membri, pentru a trece o lege prin parlament sunt necesare cel putin 51de voturi ın favoarea legii supuse votului. Aceasta situatie poate fi modelata

63

prin jocul simplu v definit pentru fiecare S ∈ 2N \ {∅} prin v(S)=1 daca|S| ≥ 51 si v(S)=0, altfel. Al doilea de tip de votare e folosit ın ConsiliulNatiunilor Unite care e format din 15 membri dintre care 5 membri, etichetatiaici cu 1, 2, 3, 4, 5, au putere veto si unde pentru a vota o lege sunt necesarecel putin 9 voturi pro incluzand voturile pro ale tuturor membrilor cu putereveto. Aceasta situatie poate fi modelata prin jocul simplu v definit pentrufiecare S ∈ 2N \ {∅} prin v(S)=1 daca |S| ≥ 9 si {1, 2, 3, 4, 5}⊆S si v(S)=0,altfel.

Un joc v ∈ GN este 0-normalizat daca v({i})=0 pentru toti i ∈ N. Un jocv ∈ GN este (0,1)-normalizat daca v({i})=0 pentru fiecare i ∈ N si v(N)=1.Un joc v ∈ GN se numeste monoton daca v(S) ≤ v(T ) pentru toti S, T ∈ 2N

cu S⊆T. Un joc v ∈ GN se numeste nenegativ daca pentru orice S ∈ 2N

avem v(S) ≥ 0. Un joc v ∈ GN se numeste aditiv daca v(S ∪T )=v(S)+ v(T )pentru toti S, T ∈ 2N cu S ∩ T = ∅. Un joc aditiv este determinat de catre

vectorul a=(v({1}), .., v({n})) ∈ IRn ıntrucat v(S)=∑i∈S

ai pentru toti S ∈ 2N .

Jocurile aditive formeaza un subspatiu liniar n-dimensional al spatiului liniarGN . Un joc v ∈ GN se numeste neesential daca el este un joc aditiv. Un

joc v ∈ GN se numeste N -esential daca v(N) >∑i∈N

v({i}). Cele mai multe

jocuri cooperative de tip castig care apar prin modelarea situatiilor reale suntjocuri superaditive. Un joc v ∈ GN se numeste superaditiv daca v(S ∪ T ) ≥v(S) + v(T ) pentru toti S, T ∈ 2N cu S ∩ T = ∅. Cele mai multe jocuricooperative de tip cost care apar prin modelarea situatiilor reale sunt jocurisubaditive. Un joc v ∈ GN se numeste subaditiv daca v(S∪T ) ≤ v(S)+v(T )pentru toti S, T ∈ 2N cu S ∩ T = ∅. Un joc v ∈ GN se numeste convex (Sha-pley, 1971) daca v(S ∪ T ) + v(S ∩ T ) ≥ v(S) + v(T ) pentru toti S, T ∈ 2N .Evident, orice joc convex este un joc superaditiv. Un joc care se exprimaca o combinatie liniara cu coeficienti pozitivi de jocuri unanime, conform cuformula (3.3), este un joc convex. O coalitie S ∈ 2N \ {∅} se zice ca areputere veto daca v(T )=0 pentru toti T astfel ca S 6⊆ T. Un joc se numestejoc veto daca exista o coalitie S ∈ 2N \ {∅} cu putere veto. Jocul de votarecorespunzand Consiliului Natiunilor Unite, din Exemplul 3.5, este un joc veto(coalitia {1, 2, 3, 4, 5} are putere veto).

In jocul v ∈ GN , pentru fiecare S ∈ 2N si pentru fiecare i ∈ S, contributiamarginala a lui i la S este Mi(S, v) := v(S)−v(S\{i}). In particular, pen-tru fiecare i ∈ N , contributia marginala a lui i la N este Mi(N, v) :=

64

v(N)−v(N\{i}). Un joc v ∈ GN se numeste un joc big boss cu n ca bigboss (Muto et al., 1988) daca: (i) v este un joc veto unde coalitia {n} areputere veto; (ii) v este un joc monoton; (iii) v are proprietatea uniunii, adica

v(N)− v(S) ≥∑

i∈N\SMi(N, v) pentru fiecare S cu n ∈ S.

Jocurile convexe si jocurile big boss sunt cazuri speciale de jocuri balansate.Definitia jocurilor balansate se bazeaza pe notiunea de aplicatie balansata(echilibrata). O aplicatie λ : 2N\{∅} −→ IR+ se numeste aplicatie balansata

(echilibrata) daca∑

S∈2N\{∅}λ(S)eS=eN , unde eS este vectorul caracteristic al

lui S, cu (eS)i=1 daca i ∈ S si (eS)i=0 altfel. Un joc v ∈ GN se numestebalansat (echilibrat) daca pentru orice aplicatie balansata λ : 2N\{∅} −→ IR+

avem∑

S∈2N\{∅}λ(S)v(S) ≤ v(N). Importanta acestei notiuni urmeaza din Teo-

rema 3.8 care a fost demonstrata independent de Bondareva (1963) si Sha-pley (1967). O colectie B de coalitii S ∈ 2N \ {∅} este o colectie balansata(echilibrata) daca exista o aplicatie balansata λ astfel ıncat B={S ∈ 2N\{∅} |λ(S) > 0}. O colectie balansata se numeste colectie balansata minimala dacanu contine o alta colectie balansata. O colectie B={S1, S2, ..., Sk} de coalitiinevide este balansata (echilibrata) daca exista αS1 , ..., αSk

∈ IR, αSj> 0,

j=1, ..., k, astfel ıncat pentru toti i ∈ N,∑

j|i∈Sj

αSj=1, unde coeficientii αSj

sunt ponderi asociate la fiecare coalitie Sj (aceste ponderi sunt unic deter-minate pentru colectii balansate minimale).

Multimea GN a jocurilor cooperative de n persoane poate fi partitionataın clase echivalenta ın raport cu o relatie de echivalenta strategica, numitaS-echivalenta, doua jocuri v, w ∈ GN ın aceeasi clasa de echivalenta fiind”ın esenta” acelasi joc. Jocul w este strategic echivalent cu jocul v dacaexista k > 0 si un joc aditiv a ∈ GN astfel ca w(S)=kv(S) + a(S), unde

a(S)=∑i∈S

ai pentru toti S ∈ 2N \ {∅}. Putem considera ca w se obtine

din v prin urmatoarele transformari: (i) unitatea valorica este schimbata,unde rata de schimb este k; ın jocul w fiecare jucator primeste ori un bonus(daca ai > 0) ori o penalizare (daca ai < 0) ınainte ca suma k · v(N) safie distribuita ıntre jucatori. Pentru cele mai multe concepte de solutie estesuficient sa ne ocupam de un singur joc ıntr-o anumita clasa de echivalenta

65

strategica. Fiecare joc v ∈ GN este strategic echivalent cu un joc w ∈ GN care

este 0-normalizat, unde w(S)=v(S)−∑i∈S

v({i}) pentru orice S ∈ 2N . Intr-o

clasa de echivalenta se considera adesea jocul (0,1)-normalizat corespunzatoracelei clase. Fiecare joc N -esential v ∈ GN este strategic echivalent cu unjoc w ∈ GN care este (0,1)-normalizat. Se poate verifica usor ca pentru

k=1/(v(N)−∑i∈N

v({i})) si ai=−v({i})/(v(N)−∑i∈N

v({i})), pentru toti i ∈ N,

jocul w definit prin w(S)=k ·v(S)+a(S) pentru toti S ∈ 2N \{∅}, este (0,1)-normalizat.

Spunem ca f : GN −→ IRn satisface proprietatea de invarianta cu privirela echivalenta strategica (S-echivalenta) daca pentru toti v, w ∈ GN , toatejocurile aditive a ∈ GN si toti k > 0, avem

w=k · v + a implica f(k · v + a)=k · f(v) + a.

O sarcina fundamentala a teoriei jocurilor cooperative este sa faca luminaasupra structurii diferitelor clase de jocuri, considerate ca subclase ale spa-tiului liniar GN . Cele mai multe dintre clasele de jocuri cooperative pot fivazute ca niste conuri poliedrale, fiind intersectii finite de semispatii ınchise.Exemple de conuri poliedrale de jocuri cooperative sunt conurile jocurilorsuperaditive, convexe, balansate, big boss.

Problema esentiala ın teoria jocurilor cooperative ın forma functiei ca-racteristice este cum sa se distribuie v(N) ıntre jucatori daca marea coalitieN se formeaza. Aceasta problema este rezolvata folosind concepte de solutiedin teoria cooperativa a jocurilor. Un concept de solutie este o aplicatie careasociaza fiecarui joc dintr-o anumita clasa de jocuri unul sau mai multi vectoride plata x=(x1, ..., xn) ∈ IRn. Conceptele de solutie care asociaza fiecarui jocv ∈ GN un singur vector plata se numesc de tip ”single-valued” sau ”one-point”. In paragrafele 3.3 - 3.5 vom prezenta urmatoarele solutii de acesttip: valoarea Shapley, σ-valoarea, τ -valoarea, nucleolul si AL-valoarea. Elefac selectii din multimi particulare de vectori de plata, si anume: multimeapreimputatiilor, multimea imputatiilor si samburele jocului.

Multimea preimputatiilor unui joc v ∈ GN este

PI(v) :=

{x ∈ IRn |

∑i∈N

xi = v(N)

}.

Multimea PI(v) este un hiperplan ın IRn.

66

Multimea imputatiilor unui joc v ∈ GN este

I(v) =

{x ∈ IRn |

∑i∈N

xi = v(N) si xi ≥ v({i}) pentru toti i ∈ N

}.

Teorema 3.6. Multimea I(v) este nevida daca si numai daca jocul v esteN-esential.

Multimea I(v) este un simplex cu punctele extremef 1(v), ..., fn(v), undepentru fiecare i ∈ N, f i(v)=(f i

1, ..., fij , ..., f

in) cu

f ij=

v({i}) daca i 6= j

v(N)−∑

k∈N\{i}v({k}) daca i=j.

Teorema 3.7 Fie v ∈ GN un joc N-esential. Atunci

(i) I(v) este o multime infinita.

(ii) I(v) este ınfasuratoarea convexa a punctelor f 1(v), ..., fn(v).

Notam cu IN={v ∈ GN | I(v) 6= ∅}. IN este un con ın multimea GN

si CIS : IN −→ IRn este un concept de solutie de tip single-valued definit

pentru fiecare v ∈ IN prin CIS(v) := 1/nn∑

i=1

f i(v). Din punct de vedere

geometric, CIS(v) este baricentrul lui I(v).Conceptul de solutie dominant ın teoria cooperativa a jocurilor este sam-

burele (Gillies, 1953).

Samburele unui joc v ∈ GN este

C(v) := {x ∈ I(v) |∑i∈S

xi ≥ v(S) pentru toti S ∈ 2N \ {∅}}.

Daca ıntr-un joc este propus un element al samburelui, nici-un subgrup dejucatori nu poate obtine mai mult prin separarea sa de restul jucatorilor.

Samburele unui joc c ∈ GN este

C(c) := {x ∈ IRN |∑i∈S

xi ≤ c(S) pentru toti S ∈ 2N \ {∅} si∑i∈N

xi=c(N)}.

67

Samburele unui joc se determina prin rezolvarea unui sistem de inecuatiiliniare. Samburele unui joc poate fi multimea vida, poate consta dintr-unsingur element (spre exemplu, jocul cost din Exemplul 3.3 are sambureleC(c)={(30, 30, 80)}) sau poate contine o infinitate de elemente. Sambureleunui joc cooperativ de n persoane este o multime poliedrala ın IRn.

Teorema 3.8 Fie v ∈ GN . Urmatoarele afirmatii sunt echivalente:

(i) C(v) 6= ∅.(ii) Jocul v este balansat.

Faptul ca samburele C(v) al unui joc v ∈ GN este solutia marginitaa unui sistem de inecuatii liniare ınseamna ca samburele unui joc este unpolitop, adica ınfasuratoarea convexa a unei multimi finite de vectori x ∈ IRn.Samburele unui joc convex si a unui joc big boss sunt politopi speciali cuo structura geometrica frumoasa. Forma samburelui unui joc convex estedescrisa de catre Shapley (1971). Forma samburelui unui joc big boss estedescrisa de Muto, Potters si Tijs (1989). Samburele unui joc big boss cu nca big boss este

C(v)={x ∈ I(v) | 0 ≤ xi ≤ Mi(N, v) pentru fiecare i ∈ N\{n}}.

Samburele C este un concept de solutie care satisface proprietatea de S-echivalenta. Un joc (balansat) v ∈ GN cu C(v)=I(v) se numeste joc (balan-sat) simplex. Un joc v ∈ GN se numeste exact daca pentru fiecare S ∈ 2N\{∅}exista un x ∈ C(v) cu

∑i∈S

xi=v(S). Jocurile convexe sunt jocuri exacte.

Exactificarea unui joc v ∈ GN este jocul vE cu vE(∅)=0, definit pentru fiecare

S ∈ 2N \ {∅} prin vE(S)= min

{∑i∈S

xi | x ∈ C(v)

}.

3.3 Valoarea Shapley si AL-valoarea

Valoarea Shapley (Shapley, 1953) asociaza cu fiecare v ∈ GN o preimputatiepe baza vectorilor contributiilor marginale mσ(v) ai jocului, undeσ = (σ(1), ..., σ(n)) este o ordine (permutare) a jucatorilor. Notam cuΠ(N) multimea tuturor permutarilor σ : N −→ N ale lui N . MultimeaP σ(i) := {r ∈ N | σ−1(r) < σ−1(i)} consta din toti predecesorii lui i cu

68

privire la permutarea σ. Pentru v ∈ GN si σ ∈ Π(N) vectorul contributiilormarginale mσ(v) are coordonate de forma mσ

i (v) := v(P σ(i)∪{i})−v(P σ(i))pentru orice i ∈ N. Valoarea Shapley Φ(v) a unui joc v ∈ GN este mediaaritmetica a vectorilor contributiilor marginale ai jocului, adica

(3.4) Φ(v) := 1/n!∑

σ∈Π(N)

mσ(v).

Exemplul 3.9. Consideram jocul cooperativ cu v({1})=v({2})=v({3})=0,v({1, 2})=4, v({1, 3})=7, v({2, 3})=15, v({1, 2, 3})=20. Vectorii contribu-tiilor marginale sunt m(1,2,3) = (0, 4, 16), m(1,3,2) = (0, 13, 7), m(2,1,3) =(4, 0, 16), m(2,3,1) = (5, 0, 15), m(3,1,2) = (7, 13, 0), m(3,2,1) = (5, 15, 0). Prinformula (3.4) obtinem Φ(v) = 1/3!(21, 45, 54) = (7/2, 15/2, 9).

Valoarea Shapley a unui joc cooperativ v de doua persoane este

Φ(v)=(v({1})+(v(N)−v({1})−v({2}))/2, v({2})+(v(N)−v({1})−v({2}))/2);

aceasta este numita solutia standard a unui joc cooperativ de doua persoane.Valoarea Shapley a unui joc aditiv v este Φ(v)=(v({1}), ..., v({n})). Pen-

tru jocul unanim pe T, uT , valoarea Shapley este Φ(uT ) = 1/|T | eT .Valoarea Shapley satisface urmatoarele proprietati care o fac un con-

cept de solutie interesant pentru teoria cooperativa a jocurilor: eficienta, S-echivalenta, proprietatea jucatorului fictiv, anonimitatea, aditivitatea, sime-tria (tratament egal al jucatorilor simetrici).

Valoarea Shapley este singura solutie care satisface proprietatile : eficienta,anonimitate, proprietatea jucatorului fictiv si aditivitate (caracterizare axio-matica).

Spunem ca f : GN −→ IRn satisface proprietatea:

• eficienta daca∑i∈N

fi(v) = v(N) pentru fiecare v ∈ GN .

• anonimitate daca f(vσ) = σ∗(f(v)) pentru orice σ ∈ Π(N), unde σ∗ :IRn −→ IRn este definita prin (σ∗(x))σ(k) := xk pentru toti x ∈ IRn sik ∈ N, iar vσ este jocul cu vσ(σ(U)) := v(U) pentru toti U ∈ 2N .

• proprietatea jucatorului fictiv daca fi(v) = v({i}) pentru toti v ∈ GN

si pentru toti jucatorii fictivi i, i.e. jucatori i ∈ N astfel ca v(S∪{i}) =v(S) + v({i}) pentru toti S ∈ 2N\{i}.

• aditivitate daca f(v + w) = f(v) + f(w) pentru toti v, w ∈ GN .

69

• simetrie (tratament egal al jucatorilor simetrici) daca fi(v) = fj(v)pentru toti i, j ∈ N astfel ıncat v(S ∪ {i}) = v(S ∪ {j}) pentru totiS ∈ 2N\{i,j}.

• rationalitate individuala daca fi(v) ≥ v({i}) pentru toti v ∈ GN sii ∈ N.

Valoarea Shapley nu satisface ın general proprietatea de rationalitate indi-viduala. Exista multe jocuri cooperative pentru care valoarea Shapley nueste un element al samburelui.

Exemplul 3.10. In jocul v({1})=v({2})=v({3})=0, v({1, 2})=10, v({1, 3})= 8, v({2, 3}) = 6, v({1, 2, 3}) = 12, Φ(v)=(5, 4, 3) /∈ C(v) deoarece inegali-tatea x1 + x2 ≥ v({1, 2}) nu este satisfacuta (5 + 4 < 10).

Pentru jocuri convexe valoarea Shapley este un element al sambureluijocului si ocupa o pozitie centrala ın cadrul acestuia: ea coincide cu ”bari-centrul” samburelui. Folosind proprietatile caracteristice ale valorii Shapleyımpreuna cu formula (3.3) si expresia valorii Shapley a unui joc unanim,obtinem o alta formulare a valorii Shapley, care are mare aplicabilitate prac-tica

(3.5) Φ(v) =∑

T∈2N\{∅}

cT

|T | eT pentru toti v ∈ GN cu v =∑

T∈2N\{∅}cT uT .

Exemplul 3.11. Determinam valoarea Shapley a jocului v din Exemplul3.4. folosind formula (3.5): Φ1(v) = 60 · 1/2 + 70 · 1/2 + 0 − 60 · 1/3 = 45;Φ2(v) = 40, Φ3(v) = 45. Deci Φ(v) = (45, 40, 45).

Alte formulari ale valorii Shapley existente ın literatura teoriei jocurilorcooperative, cum sunt cele bazate pe interpretarea sa probabilista, pe divi-dende si pe extensia multiliniara a unui joc cooperativ, nu sunt prezentateın acest curs.

AL-valoarea (Tijs, 2005) este un concept de solutie definit pe multimeajocurilor balansate (adica jocuri v ∈ GN cu C(v) 6= ∅). Ca si ın definitiavalorii Shapley, se face o medie aritmetica a n! vectori care corespund celorn! permutari posibile ale celor n jucatori ıntr-un joc cooperativ de n per-soane. Dar, spre deosebire de valoarea Shapley, unde acesti vectori sunt vec-torii contributiilor marginale, vectorii utilizati de AL-valoarea jocului suntelementele x ∈ C(v) care sunt optimale din punctul de vedere al ordiniilexicografice.

In IRn ordinea lexicografica ≥L este definita dupa cum urmeaza.Pentru fiecare x, y ∈ IRn:

70

• x >L y daca exista r ∈ {1, .., n} astfel ca xk = yk pentru k < r sixr > yr;

• x ≥L y daca x = y sau x >L y.

Spre exemplu, x = (8, 5, 11, 0) >L (8, 5, 10, 100) = y.Ordinea lexicografica este o relatie de ordine liniara pe IRn. Pentru o

multime compacta C ⊆ IRn exista un maxim lexicografic unic x ∈ C (cuproprietatea x ≥L x pentru toti x ∈ C), notat cu L(C). Daca C este unpolitop, atunci L(C) este un punct extrem al lui C care poate fi determinatrezolvand o problema de optimizare.

Fie v ∈ GN un joc balansat si σ = (σ(1), ..., σ(n)) ∈ Π(N). Maximul lexi-cografic al samburelui C(v) al lui v ın raport cu σ, notat cu Lσ(v), este uniculelement al lui C(v) cu proprietatile: (Lσ(v))σ(1) = max{xσ(1) | x ∈ C(v)},(Lσ(v))σ(2) = max{xσ(2) | x ∈ C(v) cu xσ(1) = (Lσ(v))σ(1)}, ..., (Lσ(v))σ(n) =max{xσ(n) | x ∈ C(v) cu (xσ(1), xσ(2), ..., xσ(n−1))=((Lσ(v))σ(1), (L

σ(v))σ(2), ...,(Lσ(v))σ(n−1))}. Observam ca Lσ(v) este un punct extrem al lui C(v) pentrufiecare σ ∈ Π(N). AL-valoarea AL(v) a lui v este media aritmetica a tuturorLσ(v), adica media lexicografica a jocului (”average lexicographic value”).Pentru orice joc balansat v ∈ GN , AL-valoarea AL(v) a jocului v este

(3.6) AL(v) = 1/n!∑

σ∈Π(N)

Lσ(v).

Exemplul 3.12. Pentru jocul v cu v({1})=v({2})=v({3}) = 0, v({1, 2})=v({1, 3}) = v({2, 3}) = 1, v({1, 2, 3}) = 3 avem L(1,2,3)(v) = (2, 1, 0), L(1,3,2)(v)= (2, 0, 10), ..., L(3,2,1)(v) = (0, 1, 2). Deci, AL(v) = 1/3!(L(1,2,3)(v)+L(1,3,2)(v)+ ... + L(3,2,1)(v)) = (1, 1, 1).

Pentru un joc (balansat) de doua persoane AL-valoarea jocului coincidecu solutia standard a jocului (deci si cu valoarea Shapley a jocului). Pentruorice joc convex v, AL-valoarea si valoarea Shapley coincid, adica AL(v) =Φ(v). Pentru orice joc balansat de trei persoane, pentru orice joc (balansat)simplex si pentru orice joc big boss (cu n ca big boss), AL(v) = Φ(vE), undevE este exactificarea lui v (proprietatea de invarianta cu privire la exactifi-care).

AL-valoarea satisface o gama larga de proprietati: eficienta, rationalitateindividuala, S-echivalenta, simetrie, proprietatea jucatorului fictiv, invariantacu privire la exactificare, aditivitate pe subconurile de jocuri exacte undesamburele este o corespondenta aditiva.

71

3.4 σ-valoarea si τ-valoarea

Ambele valori au fost introduse de Tijs (1981) pentru a furniza un vector pla-ta eficient care este un cel mai bun compromis ıntre doi vectori plata cores-punzand la situatii extreme: situatia ”ideala” (de fapt ”utopica”) si situatia”catastrofala”(cea mai rea posibila). Pentru ambele valori, σ-valoarea si τ -va-loarea, vectorul ideal al platilor este vectorul contributiilor marginale ale ju-catorilor la marea coalitie, adica vectorul M(N, v) = (M1(N, v), ..., Mn(N, v)).Cel mai nefavorabil vector plata pentru σ-valoarea jocului este vectorul i(v) alvalorilor individuale ale jucatorilor, adica i(v) = (v{1}), v({2}), ..., v({n})).Pentru τ -valoarea jocului cel mai nefavorabil vector de plata este asa-numitulvector al dreptului minim, ce va definit ın cele ce urmeaza pe baza vectoru-lui contributiilor marginale ale jucatorilor la marea coalitie. Pentru fiecareS ∈ 2N \{∅} si pentru fiecare i ∈ N, restul R(S, i) disponibil pentru jucatoruli daca coalitia S se formeaza si toti ceilalti jucatori j ∈ S primesc plata ideala,Mj(N, v), este

R(S, i) := v(S)−∑

j∈S\{i}Mj(N, v).

Jucatorul i ar putea pretinde de la marea coalitie N , cel mai mare dintretoate resturile disponibile pentru el ın coalitiile ın care el este un membru,adica dreptul minim al jucatorului i ın jocul v este

mi(v) := maxS:i∈S

R(S, i).

Cel mai nefavorabil vector plata pentru τ -valoarea jocului este asadar vec-torul m(v) ale carui coordonate sunt mi(v) pentru toti i ∈ N.

Un joc v ∈ GN se numeste semibalansat daca

• i(v) ≤ M(N, v) si

•∑i∈N

v({i}) ≤ v(N) ≤∑i∈N

Mi(N, v).

Notam cu SBN multimea jocurilor v ∈ GN care sunt semibalansate. Pentruun joc v ∈ SBN , σ-valoarea σ(v) a jocului este definita prin

(3.7) σ(v) := α i(v) + (1− α)M(N, v),

unde α ∈ [0, 1] este unic determinat prin∑i∈N

σi(v) = v(N).

72

Exemplul 3.13. Consideram o situatie cu un vanzator al unui tablou sidoi cumparatori potentiali, unul oferind 100 e si celalalt 200 e. Modelamaceasta situatie ca un joc de trei persoane, unde jucatorul 1 este vanzatorul,jucatorul 2 este cumpatorul care ofera 100 e si jucatorul 3 este cumparatorulcare ofera 200 e. Functia caracteristica a jocului este v({1}) = 0, v({1, 2}) =100, v({1, 3}) = 200, v({1, 2, 3}) = 200, v(S) = 0 ın rest. Verificam dacajocul este semibalansat si, daca este, calculam σ-valoarea jocului folosindformula (3.7). Vectorul cel mai nefavorabil este i(v) = (0, 0, 0), iar vec-torul ideal este M(N, v) = (200, 0, 100). Jocul este semibalansat deoarece(0, 0, 0) ≤ (200, 0, 100) si 0 ≤ 200 ≤ 300. Prin formula (3.7) obtinem σ(v) =α(0, 0, 0) + (1− α)(200, 0, 100), unde α este determinat din conditia σ1(v) +σ2(v) + σ3(v) = 200. Obtinem α = 1/3, deci σ(v) = (400/3, 0, 200/3).

Din punct de vedere geometric, σ-valoarea σ(v) a unui joc semibalansatv este unicul punct de intersectie al segmentului [i(v),M(v)] cu hiperplanul

E(v) = {x ∈ IRn |∑i∈N

xi = v(N)} al vectorilor de plata eficienti pentru v.

Un joc v ∈ GN se numeste quasi-balansat daca

• m(v) ≤ M(N, v) si

•∑i∈N

mi(v) ≤ v(N) ≤∑i∈N

Mi(N, v).

Notam cu QN multimea jocurilor v ∈ GN care sunt quasi-balansate. Pentruun joc v ∈ QN , τ -valoarea τ(v) a jocului este definita prin

(3.8) τ(v) := αm(v) + (1− α)M(N, v),

unde α ∈ [0, 1] este unic determinat prin∑i∈N

τi(v) = v(N).

Exemplul 3.14. Consideram jocul v din Exemplul 3.13. Verificam dacajocul este quasi-balansat si, daca este, calculam τ -valoarea sa folosind formula(3.8). Calculam vectorul dreptului minim m(v) = (100, 0, 0). Jocul estequasi-balansat deoarece (100, 0, 0) ≤ (200, 0, 100) si 100 ≤ 200 ≤ 300. Prinformula (3.8) obtinem τ(v) ≤ (150, 0, 50) 6= σ(v).

Pentru orice joc convex v, τ(v) = σ(v). Din punct de vedere geometric,τ -valoarea τ(v) a unui joc quasi-balansat v este unicul punct de intersectie alsegmentului [m(v),M(v)] cu hiperplanul E(v) al vectorilor de plata eficientipentru v.

73

Proprietati satisfacute de τ -valoare sunt: eficienta, rationalitatea indivi-duala, S-echivalenta, proprietatea jucatorului fictiv, anonimitatea, proprie-tatea dreptului minim, proprietatea de proportionalitate restrictiva.

O aplicatie f : QN −→ IRn are

• proprietatea dreptului minim daca f(v) = m(v) + f(v −m(v)) pentruorice v ∈ QN .

• proprietatea de proportionalitate restrictiva daca f(v) este un multiplual lui M(v) ın cazul cand m(v) = 0.

τ -valoarea este unica regula de alocare pe QN care satisface proprietatile:eficienta, proportionalitate restrictiva si proprietatea dreptului minim(caracterizare axiomatica (Tijs, 1987)).

In general, τ -valoarea nu este un element al samburelui jocului.Un joc 〈N, c〉 este quasi-balansat daca

•∑i∈N

Mi(N, c) ≤ c(N) ≤∑i∈N

mi(c);

• Mi(N, c) ≤ mi(c) pentru fiecare i ∈ N,

unde, pentru fiecare i ∈ N, Mi(N, c) = c(N)−c(N\{i}), mi(c) = minS:S3i

(c(S)−∑

j∈S\{i}Mj(N, c)); vectorul m(c) este vectorul contributiilor maximale.

Propozitia 3.15. Daca v ∈ GN este un joc balansat, atunci v ∈ SBN siv ∈ QN .

Pentru un joc big boss cu n ca big boss τ -valoarea jocului este

τ(v) =

(1

2M1(N, v),

1

2M2(N, v), ...,

1

2Mn−1(N, v), v(N)− 1

2

n−1∑i=1

Mi(N, v)

)si

τ(v) = AL(v).Pentru un joc big boss convex, τ(v) = Φ(v).Pentru un joc quasi-balansat c, τ -valoarea τ(c) este definita prin

τ(v) = αm(c) + (1− α)M(N, c),

unde α ∈ [0, 1] este unic determinat prin conditia de eficienta.

74

3.5 Nucleolul

Nucleolul a fost introdus de Schmeidler (1969) pe baza ideii de tratare echi-tabila a coalitiilor ın distribuirea valorii marii coalitii ıntre jucatori. Pentrufiecare joc v ∈ GN cu I(v) 6= ∅, orice vector x = (x1, x2, ..., xn) ∈ I(v)reprezinta un mod posibil de distribuire a lui v(N) dar acceptul de cooperareın cadrul marii coalitii depinde de acordul tuturor coalitiilor asupra uneianumite distributii x ∈ I(v), pe baza posibilitatilor v(S) ale coalitiilor S ∈2N\{∅, N}. Evaluarea unei distributii x de catre o coalitie S ∈ 2N\{∅, N}ın jocul v se face ın mod natural calculand diferenta ıntre ceea ce coalitiaS poate obtine pe cont propriu, adica v(S), si ceea ce coalitia S ar primiconform cu distributia x daca ea ar coopera ın cadrul marii coalitii, adica

x(S) =∑i∈S

xi. Diferenta v(S) − x(S) a fost numita de Schmeidler excesul

coalitiei S cu privire la imputatia x ın jocul v, notat cu e(S, x; v). Pentrufiecare joc cooperativ v ∈ GN , fiecare x ∈ I(v) si orice S ∈ 2N\{∅, N},excesul coalitiei S cu privire la x ın jocul v este

(3.9) e(S, x; v) := v(S)− x(S).

Consideram situatia cand o anumita distributie x este propusa jucatorilor.Fiecare coalitie S∈2N\{∅, N} va evalua e(S, x; v). Evident, daca e(S, x; v)>0,coalitia S are o nemultumire directa fata de x si poate sa refuze cooperareaın marea coalitie. Daca e(S, x; v) ≤ 0, coalitia S va compara excesul saucu cel al celorlalte coalitii, pentru a decide daca accepta imputatia x sauo refuza. Notam vectorul exceselor, pentru o ordine fixata a coalitiilor, cue(x; v) ≤ (e(S, x; v))S∈2N\{∅,N} si notam cu θ(x; v) vectorul obtinut din e(x; v)prin rearanjarea componentelor sale e(S, x; v) ın ordine descrescatoare.

Exemplul 3.16. Consideram jocul v({1} = v({2}) = v({3}) = 0, v({1, 2}) =v({1, 3}) = 8, v({2, 3}) = 6, v({1, 2, 3}) = 12. Pentru imputatia x = (5, 3, 4)avem x({1}) = 5, x({2}) = 3, x({3}) = 4, x({1, 2}) = 8, x({1, 3}) = 9,x({2, 3}) = 7. Excesele coalitiilor sunt: e({1}, x; v) = −5, e({2}, x; v) = −3,e({3}, x; v)= − 4, e({1, 2}, x; v)=0, e({1, 3}, x; v)= − 1, e({2, 3}, x; v) = −1.Pentru ordinea coalitiilor {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, vectorul exce-selor este e(x; v) = (−5,−3,−4, 0,−1,−1). Rearanjand componentele luie(x; v) ın ordine descrescatoare obtinem θ(x; v) = (0,−1,−1,−3,−4,−5).

Vectorul θ(x; v) permite evaluarea rapida a efectului global al imputatieix asupra (nemultumirii) ansamblului coalitiilor ın jocul v. Daca jucatorii

75

au de ales o imputatie din doua imputatii propuse, x si y, ei vor preferaacea imputatie care minimizeaza nemultumirea maxima a coalitiilor. Aceastaselectie se poate obtine prin compararea lexicografica a vectorilor θ(x; v) siθ(y; v).

Exemplul 3.17. Consideram jocul v si imputatia x din Exemplul 3.16.Presupunem ca jucatorii au de ales ıntre imputatia x si imputatia y =(6, 4, 2). Un calcul similar ce cel facut pentru θ(x; v) conduce la θ(y; v) =(0, 0,−2,−2,−4,−6). Comparand lexicografic

θ(x; v) = (0,−1,−1,−3,−4,−5) si

θ(y; v) = (0, 0,−2,−2,−4,−6)

obtinem x ≤L y. Prin urmare, imputatia x va fi preferata imputatiei y, fiindcanemultumirea cea mai mare a coalitiilor cu privire la x este mai mica decatnemultumirea cea mai mare a coalitiilor cu privire la y. In termeni de exces,excesul maxim ın raport cu x este mai mic decat excesul maxim ın raportcu y.

Nucleolul asociaza fiecarui joc v ∈ GN , cu I(v) 6= ∅, multimea η(v) aimputatiilor x∗ = (x∗1, x

∗2, ..., x

∗n) astfel ıncat

θ(x∗; v) ≤L θ(x; v) pentru toti x ∈ I(v).

Teorema 3.18. (Schmeidler, 1969) Fie v ∈ GN un joc N-esential (adicacu I(v) 6= ∅). Atunci nucleolul θ(v) al jocului v exista si contine un singurelement.

Adeseori referim imputatia selectata de nucleol ın jocul v ca η(v). Dacasamburele unui joc v este nevid, adica C(v) 6= ∅, atunci nucleolul selecteazaun element al samburelui jocului, adica η(v) ∈ C(v), ıntrucat

C(v) = {x ∈ I(v) | e(S, x; v) ≤ 0 pentru toti S ∈ 2N \ {∅}}.

Faptul ca nucleolul unui joc este ın samburele jocului ori de cate orisamburele jocului este nevid, este adesea folositor pentru calcularea nucleolu-lui: daca samburele unui joc v consta dintr-un singur element, atunci η(v) =C(v); daca samburele jocului este nevid si elementele sale sunt functii de unparametru, atunci componentele imputatiei selectate de nucleol sunt aceleasi

76

functii liniare de acel parametru si valoarea parametrului corespunzatoarenucleolului poate fi determinata printr-o metoda grafica ce va fi descrisa maijos si ilustrata ın Exemplul 3.19. Determinarea nucleolului unui joc se poateface ın general prin rezolvarea unei succesiuni de programe liniare; aceastametoda generala nu va fi prezentata ın acest curs. Relatia dintre nucleolulunui joc si samburele jocului, cand samburele este nevid, este de asemeneautila pentru a raspunde (negativ) la ıntrebarea daca o anumita imputatieeste sau nu cea selectata de nucleol.

Doua proprietati ale nucleolului pot juca un rol ın calcularea nucleoluluisau ın furnizarea raspunsului (negativ sau pozitiv) la problema daca o anu-mita imputatie este sau nu cea selectata de nucleol: proprietatea jucatoruluifictiv si proprietatea jucatorilor simetrici (vezi Exemplul 3.19).

Ori de cate ori componentele unui vector de plata candidat pentru a fiimputatia selectata de nucleol sunt functii liniare de un parametru, deter-minarea nucleolului poate fi facuta printr-o metoda grafica simpla:

• Se determina intervalul pentru valorile parametrului din conditia cavectorul de plata respectiv sa fie o imputatie.

• Se calculeaza excesele tuturor coalitiilor nevide, cu exceptia marii coalitii;acestea sunt functii liniare de parametrul respectiv.

• Se reprezinta grafic aceste functii (excesele tuturor coalitiilor) pentruvalorile parametrului ın intervalul determinat specific problemei.

• Se traseaza graficul maximului acestor functii si se determina valoareaparametrului pentru care aceasta functie ısi atinge minimul.

Exemplul 3.19. Consideram jocul v din Exemplul 3.2. Observam cajucatorii 1 si 2 sunt simetrici, ceea ce implica η1(v) = η2(v). Evident, η3(v) =v(N) − η1(v) − η2(v). Nucleolul jocului este de forma (x, x, 300 − 2x), cu0 ≤ x ≤ 50, ıntrucat acest vector trebuie sa fie o imputatie. Calculam exce-sele tuturor coalitiilor cu privire la imputatia (x, x, 300− 2x). Reprezentamfunctiile de x obtinute ın sistemul de coordonate xOy, pentru x ∈ [0, 50].Trasam conturul functiei care este maximul functiilor exceselor si vedemcare este valoarea lui x pentru care aceasta functie are valoarea minima.Pentru jocul nostru, obtinem x = 100/3. Nucleolul jocului este, prin urmare,η(v) = (100/3, 100/3, 700/3).

Criteriul lui Kohlberg este un instrument cu valabilitate generala utilpentru a raspunde la ıntrebarea daca o anumita imputatie este sau nu nu-cleolul unui joc N -esential. Consideram multimea exceselor coalitiilor S ∈

77

2N\{∅, N, {1}, ..., {n}} cu privire la imputatia x ın ordine descrescatoare:

ε1, ε2, ..., εk(x).

Propozitia 3.20. (Criteriul lui Kolhberg, 1971) Fie v ∈ GN si x ∈ I(v)astfel ca xi 6= v({i}) pentru toti i ∈ N. Imputatia x este nucleolul jocului vdaca si numai daca pentru toti 1 ≤ j ≤ k(x)

j⋃t=1

Bt este o colectie balansata (echilibrata),

unde Bi este multimea de coalitii asociata cu al i-lea exces εi (ın ordineadescrescatoare a acestor excese).

3.6 Comunicare si informatie ın jocuri cooperative

In teoria clasica a jocurilor cooperative ın forma functiei caracteristice sepresupune ca toti jucatorii sunt capabili (si li se permite) sa comunice ıntreei si, prin urmare, toate coalitiile (grupurile de jucatori) se pot forma. Toatefelurile de acorduri, incluzand acordurile ferme, si de asemenea platile la-terale sunt permise. Totusi, ın multe situatii practice, unii dintre jucatorisunt incapabili sa comunice unul cu celalalt si, prin urmare, unele coalitii,incluzand marea coalitie nu pot fi formate. Restrictiile privind comunicareaıntre jucatorii conduc astfel la cooperare restrictiva. Pentru a modela astfelde situatii cu cooperare restrictiva indusa de restrictii de comunicare, a fostintrodus un model specific de jocuri cooperative, asa-numitele jocuri de co-municare (Myerson, 1977, 1980; Owen, 1986). O situatie (cu restrictii de coo-perare datorate posibilitatilor limitate) de comunicare este o situatie ın careposibilitatile economice ale participantilor sunt descrise printr-un joc coope-rativ 〈N, v〉 sau 〈N, c〉 si posibilitatile de comunicare sunt descrise printr-opereche 〈N, A〉, unde N este multimea finita si nevida a jucatorilor si A esteun graf neorientat, numit graful comunicarii. Jocurile de comunicare suntnumite si jocuri cu restrictii de tip graf (”graph-restricted games”). O clasamica de jocuri de comunicare (dar interesanta atat din punct de vedere teo-retic cat si al aplicatiilor practice) este clasa jocurilor numite ”peer groupgames” (Branzei, Fragnelli si Tijs, 2002; Branzei, Solymosi si Tijs, 2005),unde graful comunicarii este un arbore ce corespunde ierarhiei organizationale

78

a jucatorilor. Adeseori comunicarea ıntre participanti are loc prin retele, sis-teme de relatii bilaterale descentralizate. Retelele pot fi integrate ın jocuricoalitionale pentru a forma asa-numitele ”network-restricted games” (Slikkersi van den Nouweland, 2001).

Informatia disponibila jucatorilor ın situatii de interactiune decizionalabazata pe interese de grup joaca, de asemenea, un rol important ın teo-ria jocurilor cooperative. In teoria clasica a jocurilor cooperative ın formafunctiei caracteristice jucatorii au informatie simetrica si platile coalitiilorsunt cunoscute cu certitudine de catre toti jucatorii. Totusi, exista multesituatii practice cu asimetrii informationale si, ın unele situatii, informatiape care o detin unii jucatori reprezinta o resursa cu rol important ın evaluareaposibilitatilor economice ale coalitiilor. Pentru a modela astfel de situatii aufost introduse clase speciale de jocuri cooperative ın forma functiei caracter-istice, cum sunt: ”information market games” (Muto, Potters si Tijs, 1989),”information collecting games” (Branzei, Tijs si Timmer, 2001; Tijs, Timmersi Branzei, 2006), ”information sharing games” (Slikker, Norde si Tijs, 2003).Pentru a modela situatii de interactiune decizionala ın care platile coalitiilorsunt incerte, au fost introduse noi modele teoretice de jocuri cooperative ınforma functiei caracteristice, cum sunt: ”games in stochastic characteristicfunction form” (Charnes si Granot, 1973; Granot, 1977), ”stochastic coope-rative games” (Suijs, 1999; Suijs si Borm, 1999), ”cooperative games withrandom payoffs” (Timmer, Borm si Tijs, 2000). Exista un interes actualcrescand ın teoria jocurilor cooperative cu informatie incompleta motivatatat din punct de vedere teoretic cat si al aplicatiilor practice (Ichiishi siYamazaki, 2006).

Toate modelele de jocuri cooperative ın forma functiei caracteristice stu-diate ın paragrafele 3.2 - 3.5 si discutate mai sus, se bazeaza pe notiuneaclasica de coalitie, aceea de grup de jucatori, unde fiecare jucator poate fisau nu membru al uneia sau mai multor coalitii. Situatii cu posibilitati decooperare mai relaxata au condus la introducerea unor notiuni mai sofisti-cate de coalitie, cum sunt cea de coalitie multi-choice si coalitie fuzzy, simodele corespunzatoare de jocuri cooperative ın forma functiei caracteristice:”multi-choice games” (Hsiao si Raghavan, 1993a, 1993b; van den Nouwelandet al., 1995; Calvo si Santos, 2000) si ”fuzzy games” (Aubin,1974, 1981).

Intr-un joc de tip multi-choice fiecare jucator are un numar finit de nivelede activitate privind cooperarea cu ceilalti jucatori si plata fiecarei coalitiimulti-choice depinde de nivelele de activitate ale (tuturor) jucatorilor ıncadrul acelei coalitii. Jocurile cooperative clasice ar putea fi considerate ca

79

un caz special al jocurilor multi-choice, unde fiecare jucator are exact douanivele de activitate, corespunzand la participare (completa) ıntr-o coalitie sauneparticipare. Intr-un joc fuzzy fiecare jucator are posibilitatea sa cooperezela (infinit de) multe nivele, variind de la necooperare la cooperare totala siplata fiecarei coalitii fuzzy depinde de nivelele de participare ale (tuturor)jucatorilor ın cadrul acelei coalitii. Modele de jocuri cooperative ın formafunctiei caracteristice bazate pe notiunea clasica de coalitie (crisp), coalitiemulti-choice si coalitie fuzzy, sunt prezentate ın monografia avand ca autoripe Branzei, Dimitrov si Tijs (2005).

Toate modelele de jocuri cooperative ın forma functiei coalitionale discu-tate pana acum fac parte din teoria jocurilor cu utilitati transferabile. Elese mai numesc TU-games (Transferable Utility games). Calificativul ”cuutilitati transferabile” este menit sa faca clar faptul ca ın astfel de jocurisunt permise plati laterale ıntre jucatori ın sensul ca valoarea (plata, uti-litatea) marii coalitii poate fi distribuita ıntre jucatori ın (infinit de) multemoduri, iar transformari ale valorilor (platilor, utilitatilor) coalitiilor datorateschimbarii unitatii monetare sau acordarii de bonus sau amenda unor jucatorinu afecteaza ın mod esential modelul de joc. Teoria jocurilor cooperative ınforma coalitionala include, pe langa jocurile de tip TU, jocuri de tip NTU,adica jocuri cu utilitate netransferabila (NTU-games). Un joc de tip NTUeste o pereche 〈N, V 〉, unde N este multimea finita si nevida a jucatorilor siV este o aplicatie care asociaza fiecarei coalitii S ∈ 2N \ {∅} o submultimeV (S)⊆IRS, cu proprietati specifice pe care nu le definim aici, ce poate fi in-terpretata astfel: daca coalitia S se formeaza, atunci pot fi obtinuti vectoriix ∈ V (S), care dau fiecarui jucator i ∈ N plata (utilitatea) xi. Jocurilecooperative cu utilitati netransferabile au fost introduse de Aumann si Peleg(1960). Ele sunt potrivite pentru analiza multor fenomene economice com-petitive si cooperative. Un joc de tip NTU poate fi construit pornind de laun joc cooperativ ın forma strategica sau direct, pe baza descrierii narativea situatiei de interactiune decizionala analizata.

Jocurile de negociere pentru doua persoane (”bargaining games”) pot ficonsiderate un caz particular al jocurilor de tip NTU. Un joc de negocierede doua persoane este o pereche 〈F, d〉, unde F⊆IR2 si d = (d1, d2) ∈ IR2.Elementele lui F , perechi de plati (utilitati), se numesc rezultate admisibile,pe care jucatorii le pot obtine prin cooperare (acord bilateral). In cazul ıncare cooperarea ıntre jucatori nu are loc, jucatorii obtin perechea de plati(d1, d2), motiv pentru care d se numeste rezultatul dezacordului. Modelul dejoc de negociere a fost introdus de Nash (1950b).

80

ANEXA A

Demonstratii privind Capitolul 2

Demonstratia Teoremei 2.5. Observam ca au loc relatiile

K(x1, y1) = maxx∈X

K(x, y1) ≥ K(x2, y1) ≥ miny∈Y

K(x2, y) = K(x2, y2), (A.1)

unde egalitatile au loc ıntrucat (x1, y1) si (x2, y2) sunt echilibre Nash alejocului.

Schimband rolurile lui (x1, y1) si (x2, y2) obtinem, ın mod similar,

K(x2, y2) = maxx∈X

K(x, y2) ≥ K(x1, y2) ≥ miny∈Y

K(x1, y) = K(x1, y1). (A.2)

Din (A.1) si (A.2) rezulta ca K(x1, y1) = K(x2, y2) si toate inegalitatileın (A.1) si (A.2) sunt de fapt egalitati. Aceasta implica

K(x2, y1) = maxx∈X

K(x1, y1); K(x2, y1) = miny∈Y

K(x2, y).

Prin urmare, (x2, y1) este un echilibru Nash si K(x2, y1) = K(x1, y1). In modsimilar, rezulta ca (x1, y2) este un echilibru Nash cu K(x1, y2) = K(x1, y1).

Demonstratia Teoremei 2.8.

(i) urmeaza din definitia unei functii potential exact pentru jocul G.

(ii) urmeaza din (i) pe baza observatiei ca x∗ este un echilibru Nash pentruGP daca

P (x∗) = max

{P (x) | x ∈

n∏i=1

Xi

}.

81

Teorema de punct fix a lui Brouwer. Fie C o multime nevida convexasi compacta a lui IRk si fie f : C −→ C o functie continua. Atunci exista unx∗ ∈ C cu f(x∗) = x∗.

Demonstratia Teoremei 2.21. (Nash) Pentru i ∈ N si xi ∈ Xi consideramUxi

i (σ) = max(0, Ki(xi, σ−i)−Ki(σ)) si f : Σ −→ Σ definita (pe componente)prin

fxii (σ) = (σxi

i + Uxii (σ))/

1 +

∑

x′i∈Xi

Ux′ii (σ)

,

unde σxii desemneaza probabilitatea pe care σi o atribuie lui xi.

Observam ca Σ este o multime nevida convexa si compacta, iar f este ofunctie continua pe Σ. Prin teorema de punct fix a lui Brouwer, exista unpunct fix σ∗. Verificarea faptului ca σ∗ este un echilibru Nash al jocului nueste dificila.

Demonstratia Lemei 2.22. (Tijs) Aratam doar ca

v(A) = maxp∈∆m

minj∈{1,...,n}

pT Aej.

Evident,inf

q∈∆npT Aq ≤ min

j∈{1,...,n}pT Aej. (A.3)

Intrucat pentru fiecare p ∈ ∆m

pT Aq =n∑

j=1

qjpT Aej ≥ min

j∈{1,...,n}pT Aej

n∑j=1

qj = minj∈{1,...,n}

pT Aej,

aveminf

q∈∆npT Aq ≥ min

j∈{1,...,n}pT Aej. (A.4)

Din (A.3) si (A.4) obtinem

infq∈∆n

pT Aq = minj∈{1,...,n}

pT Aej. (A.5)

Consideram f : ∆m −→ IR, definita prin f(p) = minj∈{1,...,n}

pT Aej. Aceasta

functie este continua, iar multimea ∆m este o multime nevida marginita siınchisa. Prin urmare, exista max

p∈∆mf(p). Combinand aceasta cu (A.5) obtinem

v(A) := supp∈∆m

infq∈∆n

pT Aq = supp∈∆m

minj∈{1,...,n}

pT Aej = maxp∈∆m

minj

pT Aej.

82

Demonstratia Teoremei 2.23. (Tijs) Intai observam ca

infz∈Y

K(x, z) ≤ K(x, y) pentru toti x ∈ X si y ∈ Y

implicasupx∈X

infz∈Y

K(x, z) ≤ supx∈X

K(x, y) pentru toti y ∈ Y,

si atuncisupx∈X

infz∈Y

K(x, z) ≤ infy∈Y

supx∈X

K(x, y),

sauv(X,Y,K,−K) ≤ v(X,Y,K,−K), i.e., v(A) ≤ v(A).

Demonstram ca v(A) = v(A) prin inductie matematica dupa marimea s(A)a lui A, unde s(A) := m + n. Evident, s(A) ≥ 0. Definim functia ”gap” a luiA prin g(A) := v(A)− v(A). Am aratat anterior ca g(A) ≥ 0. Aratam acumca g(A) = 0, prin inductie dupa marimea lui A.

• Pentru s(A) = 2, A este de forma [a], deci g(A) = v(A) − v(A) =a− a = 0.

• Presupunem ca g(B) = 0 pentru toti B cu s(B) < r. Luam A ∈ IRm×n

cu m+n = r. Folosind Lema 2.22, putem gasi un p∗ ∈ ∆m si un q∗ ∈ ∆n

astfel ıncat

(p∗)T Aej ≥ v(A) pentru toti j ∈ {1, ..., n}. (A.6)

eTi Aq∗ ≤ v(A) pentru toti i ∈ {1, ..., m}. (A.7)

Consideram 3 cazuri:

1. In (A.6) si (A.7) avem numai egalitati. Atunci (p∗)T Aq∗ = v(A) =v(A), deci g(A) = 0.

2. Exista un k ∈ {1, ..., n} astfel ıncat (p∗)T Aek > v(A), ceea ceimplica n > 1.

3. Exista un ` ∈ {1, ..., m} astfel ıncat eT` Aq∗ < v(A), ceea ce implica

m > 1.

Intrucat cazurile 2 si 3 sunt similare, vom demonstra numai pentrucazul 2 ca g(A) = 0.

83

Fie A−k matricea care se obtine din A prin eliminarea coloanei k. Dinpresupunerea inductiva, g(A−k) = 0. Este usor de aratat ca

v(A−k) ≥ v(A)(si v(A−k) ≥ v(A)

).

In cele ce urmeaza, vom arata, prin metoda reducerii la absurd, ca

v(A−k) = v(A).

Presupunem ca v(A−k) > v(A). Acesta ınseamna ca exista p ∈ ∆m careeste maximin pentru A−k, deci pAej > v(A) pentru toti j ∈ {1, ..., n}\{k}.

Pentru orice ε ∈ (0, 1) avem atunci

(εp + (1− ε)p∗)T Aej > v(A) pentru toti j 6= k.

Pentru ε arbitrar de mic vom avea

(εp + (1− ε)p∗)T Aej > v(A).

Dar atunciv(A) ≥ min

j∈{1,...,n}(εp + (1− ε)p∗)T Aej

> v(A),

ceea ce contrazice presupunerea facuta. Prin urmare v(A−k) = v(A).

Demonstratia Teoremei 2.24.

(p∗, q∗) ∈ NE(A,B) ⇐⇒

(p∗)T Aq∗ = maxp∈∆m

pT Aq∗,

(p∗)T Bq∗ = maxq∈∆n

p∗Bq,⇐⇒

⇐⇒

(p∗)T Aq∗ = maxi{1,...,m}

eTi Aq∗,

(p∗)T Bq∗ = maxj∈{1,...,n}

(p∗)T Bej,⇐⇒

⇐⇒{

C(p∗)⊂PB1(q∗),

C(q∗)⊂PB2(p∗).

84

ANEXA B

Demonstratii privind Capitolul 3

Demonstratia Teoremei 3.6.

(=⇒) Presupunem x ∈ I(v). Atunci v(N) =n∑

i=1

xi ≥n∑

i=1

v({i}), unde egali-

tatea urmeaza din proprietatea de eficienta si inegalitatea urmeaza din pro-prietatea de rationalitate individuala.

(⇐=) Presupunem v(N) ≥n∑

i=1

v({i}). Atunci

(v({1}), ..., v({n− 1}), v(N)−

n−1∑i=1

v({i}))

este o imputatie.

Teorema B.1. (caracterizarea punctelor extreme ale unei multimi poliedrale)Fie A o matrice ın IRn×p, b ∈ IRp si fie P multimea poliedrala a solutiilorsistemului de inegalitati xT A ≥ bT . Pentru x ∈ IRn, fie tight(x) multimeacoloanelor {Aej | xT Aej = bj} ale lui A, unde inegalitatile corespunzatoaresunt egalitati pentru x si unde pentru fiecare j ∈ N, ej este al j-lea vector albazei standard ın IRn. Atunci x este un punct extrem al lui P daca si numaidaca tight(x) este un sistem complet de vectori ın IRn.

Demonstratia Teoremei 3.7.

(i) Intrucat v ∈ GN este un joc N -esential, avem a = v(N)−∑i∈N

xi > 0.

Pentru orice n-uplu b = (b1, ..., bn) de numere nenegative astfel ca∑i∈N

bi = a, vectorul plata x′ = (x′1, ..., x′n) cu x′i = v({i}) + bi pen-

tru toti i ∈ N este o imputatie.

(ii) Aceasta urmeaza din Teorema B.1 observand ca I(v) = {x ∈ IRn |xT A ≥ bT}, unde A este matricea n×(n+2) cu coloanele e1, ..., en, 1n,−1n

85

si b = (v({1}), ..., v({n}), v(N),−v(N)), unde pentru fiecare i ∈ N, ei

este al i-lea vector al bazei standard ın IRn si 1n este vectorul ın IRn cutoate coodonatele egale cu 1.

Teorema B.2. (teorema dualitatii ın programarea liniara) Fie A o matricen× p, b ∈ IRp si c ∈ IRn. Atunci

min{xT c | xT A ≥ bT} = max{bT y | Ay = c, y ≥ 0}daca {x ∈ IRn | xT A ≥ bT} 6= ∅ si {y ∈ IRp | Ay = c, y ≥ 0} 6= ∅.Demonstratia Teoremei 3.8. Intai observam ca C(v) 6= ∅ daca si numaidaca

v(N) = min

{∑i∈N

xi |∑i∈S

xi ≥ v(S) pentru toti S ∈ 2N\{∅}}

. (B.1)

Prin Teorema B.2, egalitatea (B.1) are loc daca si numai daca

v(N) = max

∑

S∈2N\{∅}λ(S)v(S) |

∑

S∈2N\{∅}λ(S)eS = eN , λ ≥ 0

, (B.2)

(luand matricea A cu vectorii caracteristici eS drept coloane). Acum, (B.2)

are loc daca si numai daca∑

S∈2N\{∅}λ(S)v(S) ≤ v(N) are loc, unde λ este o

aplicatie balansata. Prin urmare, (i) si (ii) sunt echivalente.

Demonstratia Propozitiei 3.15. Fie x ∈ C(v). Pentru orice i ∈ N are loc

xi = x(N)− x(N\{i}) = v(N)− x(N\{i}) ≤ v(N)− v(N\{i}) =

= Mi(N, v).(B.3)

Daca i ∈ S, are loc

xi = x(S)− x(S\{i}) ≥ v(S)− x(S\{i}(B.3)

≥ v(S)−∑

j∈S\{i}Mj(N, v)

=⇒ xi ≥ mi(v).

(B.4)

Din (B.3) si (B.4) obtinem

mi(v) ≤ xi ≤ Mi(N, v) pentru toti i ∈ N. (B.5)

Observam ca (B.5) ınseamna m(v) ≤ x ≤ M(N, v) pe coordonate si implica∑i∈N

mi(v) ≤ v(N) ≤∑i∈N

Mi(N, v).

Deci, am aratat ca orice joc balansat este un joc quasi-balansat. Faptulca orice joc balansat este de asemenea un joc semibalansat urmeaza simi-lar din (B.3) si din proprietatea de rationalitate individuala a elementelelorsamburelui jocului.

86

BIBLIOGRAFIE

1. Aubin, J.P. (1974). Coeur et valeur des jeux flous a paiements lateraux.Comptes-Rendus de l’Academie des Sciences Paris 279 A, 891-894.

2. Aubin, J.P. (1981). Cooperative fuzzy games. Mathematics of OperationsResearch 6, 1-13.

3. Aumann, R.J. and B. Peleg (1960). Von Neumann-Morgenstern solutionsto cooperative games without side payments. Bulletin of the American Ma-thematical Society 66, 173-179.

4. Bondareva, O.N. (1963). Some applications of linear programming methodsto the theory of cooperative games (in Russian). Problemi Kibernetiki 10,119-139.

5. Borel, E. (1921). La theorie du jeu et les equations integrales a noyausymetrique. Comptes Rendus de l’Academie des Sciences 173, 1304-1308.

6. Branzei, R., D. Dimitrov and S. Tijs (2005). Models in Cooperative GameTheory: Crisp, Fuzzy and Multi-Choice Games. Springer.

7. Branzei, R., V. Fragnelli and S. Tijs (2002). Tree-connected peer groupsituations and peer group games. Mathematical Methods of OperationsResearch 55, 93-106.

8. Branzei, R., T. Solymosi and S. Tijs (2005). Strongly essential coalitions andthe nucleolus of peer group games. International Journal of Game Theory33, 447-460.

9. Branzei, R., S. Tijs and J. Timmer (2001). Collecting information to improvedecision making. International Game Theory Review 3, 1-12.

10. Calvo, E. and J.C. Santos (2000). A value for multichoice games. Mathe-matical Social Sciences 40, 341-354.

87

11. Charnes, A. and D. Granot (1973). Prior solutions: extensions of convexnucleolus solutions to chance-constrained games. Proceedings of the Com-puter Science and Statistics Seventh Symposium at Iowa State University,323-332.

12. Gardner, R. (1995). Games for Business and Economics. John Wiley &Sons.

13. Gibbons, R. (1992). A primer in Game Theory. Harvester/Wheatsheaf.

14. Gillies, D.B. (1953). Some Theorems on n-person Games. Ph. D. Disserta-tion, Princeton University Press.

15. Granot, D. (1977) Cooperative games in stochastic function form. Manage-ment Science 23, 621-630.

16. Harsanyi, J.C. (1967/68). Games with incomplete information played by’Bayesian’ players, Part I, II, and III. Management Science 14, 159-182,320-334, and 486-502.

17. Hsiao, C.-R. and TES Raghavan (1993a). Monotonicity and dummy freeproperty for multi-choice cooperative games. International Journal of GameTheory 21, 301-312.

18. Hsiao, C.-R. and TES Raghavan (1993b). Shapley value for multi-choicecooperative games (I). Games and Economic Behavior 5, 240-256.

19. Kohlberg, E. (1971). On the nucleolus of a characteristic function game.SIAM Journal on Applied Mathematics 20, 62-66.

20. Ichiishi, T. and A. Yamazaki (2006). Cooperative Extensions of the BayesianGame. Series on Mathematical Economics and Game Theory, Vol. 3.

21. Monderer, D. and L. Shapley (1996). Potential games. Games and EconomicBehavior 14, 124-143.

22. Morris, P. (1994). Introduction to Game Theory. Springer-Verlag.

23. Muto, S., M. Nakayama, J. Potters and S. Tijs (1988). On big boss games.Economic Studies Quarterly 39, 303-321.

24. Muto, S., J. Potters and S. Tijs (1989). Information market games. Inter-national Journal of Game Theory 18, 209-226.

25. Myerson, R. (1977). Graphs and cooperation in games. Mathematics ofOperations Research 2, 225-229.

88

26. Myerson, R. (1980). Conference structures and fair allocation rules. Inter-national Journal of Game Theory 9, 169-182.

27. Nash, J. (1950a). Equilibrium points in n-person games. Proceedings of theNational Academy of Sciences 36, 48-49.

28. Nash, J. (1950b). The bargaining problem. Econometrica 18, 155-162.

29. Nash, J.F. (1951). Non-cooperative games. Annals of Mathematics 54, 286-295.

30. van den Nouweland, A., S. Tijs, J. Potters and J. Zarzuelo (1995). Cores andrelated solution concepts for multi-choice games. Mathematical Methods ofOperations Research 41, 289-311.

31. von Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. Mathema-tische Annalen 100, 295-320.

32. von Neumann, J. and O. Morgenstern (1944). Theory of Games and Eco-nomic Behavior. Princeton University Press.

33. Osborne, M. and A. Rubinstein (1994). A Course in Game Theory. MITPress.

34. Owen, G. (1986). Values of graph-restricted games. SIAM Journal on Al-gebraic and Discrete Mathematics 7, 210-220.

35. Owen, G. (1999). Discrete Mathematics and Game Theory. Theory andDecision Library: Series C, Kluwer Academic Publishers.

36. Peleg, B. and P. Sudholter (2004). Introduction to the Theory of Coope-rative Games. Theory and Decision Library: Series C, Kluwer AcademicPublishers.

37. Rafels, C. (Coordinacio) (1999). Jocs cooperatius i aplicacions economiques.Col-leccio UB.

38. Rosenthal, R.W. (1973). A class of games possessing pure-strategy NashEquilibria. International Journal of Game Theory 2, 65-67.

39. Schmeidler, D. (1969). The nucleolus on a characteristic function game.SIAM Journal on Applied Mathematics 17, 1163-1170.

40. Selten, R. (1975). Reexamination of the perfectness concept for equilibriumpoints in extensive games. International Journal of Game Theory 4, 25-55.

89

41. Shapley, L.(1953). A value for n-person games. In: Tucker, A. and H. Kuhn(Eds.), Contributions to the Theory of Games II, pp. 307-317.

42. Shapley, L. (1971). Cores of convex games. International Journal of GameTheory 1, 11-26.

43. Slikker, M., H. Norde and S. Tijs (2003). Information sharing games. Inter-national Game Theory Review 5, 1-12.

44. Slikker, M. and A. van den Nouweland (2001). Social and Economic Net-works in Cooperative Game Theory. Theory and Decision Library: SeriesC, Kluwer Academic Publishers.

45. Suijs, J. (1999). Cooperative Decision-Making under Risk. Boston: Kluwer.

46. Suijs, J. and . Borm (1999). Stochastic cooperative games: superadditivity,convexity and certain equivalents. Games and Economic Behavior 27, 331-345.

47. Tijs, S.H. (1981). Bounds for the core of a game and the τ -value. In:Moeschlin, O. and D. Pallaschke (Eds.), Game Theory and MathematicalEconomics, Amsterdam: North Holland, pp.123-132.

48. Tijs, S.H. (1987). An axiomatization of the τ -value. Mathematical SocialSciences 13, 177-181.

49. Tijs, S. (2003). Introduction to Game Theory. Hindustan Book Agency.

50. Tijs, S. (2005). The first steps with Alexia, the lexicographic order. CentERDP 2005-123, Tilburg University, Tilburg, The Netherlands.

51. Tijs, S., J. Timmer and R. Branzei (2006). Compensations in informationcollecting situations: A cooperative approach. Journal of Public EconomicTheory 8, 181-191.

52. Timmer, J., P. Borm and S. Tijs (2000). Convexity in stochastic cooperativesituations. International Game Theory Review 7, 25-42.

53. Watson, J. (2002). An Introduction to Game Theory. W.W. Norton &Company.

90