teoria jocurilor de doua persoane

7/30/2019 teoria jocurilor de doua persoane

1/35

Aplicatii ale teoremelor de punct fix n

teoria jocurilor

Radoi Mihaela Luciana

2010


2/35

Cuprins

1 Introducere 2

2 Despre jocuri 10

3 Conceptul general de joc de Doua Persoane 16

3.1 Demonstratia teoremei Brouwer . . . . . . . . . . . . . . . . . . . . . . . . 203.2 Teorema de echilibru Nash . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.3 Jocuri de doua persoane de suma zero

si Teorema Minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.4 Jocuri de productie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.5 Multiplicatori Lagrange, subgradienti si MIN-MAX . . . . . . . . . . . . . 27

3.6 Puncte sa si solutii miez . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.7 Dinamica preturilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

1


3/35

Capitolul 1

Introducere

Capitolul 1 Introducere

In acest capitol voi prezenta teoreme de punct fix pentru aplicat ii continue de

valori proprii n statii Banach finit si infinit dimensionale.

Definitia 1.1. Doua spatii topologice X si Y se numesc homeomorfe daca exista

o functie bijectiva f : X Y astfel ncat f si f1 sunt continue. Aplicatia f se

numeste homeomorfism.

Definitia 1.2. Un spatiu topologic X are proprietatea de punct fix daca fiecare

functie continua f : X X admite un punct fix.

Teorema 1.1. Daca X are proprietatea de punct fix si X este homeomorf cu Y,

atunci si Y va avea proprietatea de punct fix.

Demonstratie. Fie h : X Y un homeomorfism si sa presupunem ca g : Y Y

este o functie continua . Vom arata ca g are un funct fix n Y. Observam ca:

h1 g h : X X

este o aplicatie continua. Intrucat X are proprietatea de punct fix, exista un x0 X

astfel ncat

h1 g h(x0) = x0.

Rezunta ca g(y0) = y0, unde y0 = h(x0).

Definitia 1.3. O submultime A a spatiului topologic X este o retracta a lui X, daca

exista o aplicatie continua r : X A, cu r(a) = a, pentru orice a A. Aplicatia r

se numete retratie .

Teorema 1.2. Daca X are proprietatea de punct fix si A este o retractie a lui X,

atunci A are proprietatea de punct fix.

Demonstratie. Fie f : A A o aplicatie continua si r : X A o retratie. Vom

arata ca f are un punct fix n A. Observam mai ntai ca :

f r : X A X.

2


4/35

Cum X are proprietatea de punct fix, exista x0 X cu f r(x0) = x0. In orice

caz, f((x0)) A are loc si pentru x0 A. Dar cum x0 A si r : X Aeste o

retractie, obtinem r(x0) = x0. Rezulta ca f(x0) = x0, x0 A. In R, se observa ca

f : [1, 1] [1, 1] admite un punct fix cat timp functia g : x x f(x) satisface

g(1) 0 g(1) si atinge valoarea 0. Ca rezultat, [-1,1] va avea proprietatea depunct fix.

Teorema 1.3. Bila nchis a Bn n Rn are proprietatea de punct fix.

Vom considera ca spatiul Rn este nzestrat cu produsul scalar

< x, y >= ni=1xiyi,

si norma

x =< x, x >1/2 .

De asemenea, Bn si Sn1 := {x Rn : x = 1}.

Definitia 1.4. Fie A Rn.O aplicatie continua f : A Rn se zice de clasa C1,

daca are o extindere continua ntr-o vecinatate deschisa a lui A, peste care este

continuu-diferent iabila.

Teorema 1.4. Fie A o submultime compacta a lui Rn si f : A Rn de clasa C1

a lui A. Atunci exista o constanta L 0 (constanta Lipschitz), cu

f(x) f(y) Lx y, x, y A.

Teorema 1.5. Fie A un domeniu nchis si marginit n Rn si F : ArightarrowRn

de clasa C1 n A. Atunci exista un interval (, ), pentru anumiti > 0, pentru

care functiile

: t V ol(ft(A))

sunt polinomiale de grad cel mult n; n acest caz, ft : A Rn este exprimat astfel:

ft(x) := x + tF(x),

iar Vol se refera la masura Lebesque n-dimensionala n Rn.

Definitia 1.5. Fie A Rn. O aplicatie (vectoriala) f : A Rn se numeste

neneglijabila daca

f(x) = 0, x A

si normata daca

f(x) = 1, x A.

Domeniul functiei f : Sn1 Rn se numeste tangent la Sn1 daca

< x, f(x) >= 0, x Sn1.

3


5/35

Teorema 1.6. Consideram ca F : Sn1 Rn este o aplicatie vectoriala normata

de clasa C1, tangenta la Sn1. Atunci pentru orice t > 0, suficient de mic,

ft(Sn1) = (1 + t2)1/2Sn1;

unde ft : x x + tF(x).

Demonstratie. Fie F(x) := xF(x/x)), x Rn\{0} si

A := {x Rn : 1/2 x 3/2}.

Tinand cont ca |t| < min{1/3, 1/L}, L fiind constanta Lipsxhitz al lui F pe A.

Fixam z Sn1 si definim G : A Rn astfel

G(x) := z tF(x).

Intrucat F(y) = 1, y Sn1 si |t| < 1/3, vom obtine de fapt G : A A. In

plus, este usor de probat (utilizand constanta Lipscitz L al lui F pe A si |t|L < 1

) ca G : A A este o contractie . Teorema 1.1 garanteaza ca G are un punct fix,

de exemplu x A si

x + tF(x) = z.

Din 1 =< x + tF(x), x + tF(x) >, F(u) = 1, u Sn1 si < v, F(v) >= 0, v

Sn1, obtinem imediat

x = (1 + t2)1/2.

Ca rezultat:y = (1 + t2)1/2, x Sn1

si de aici:

y + tF(y) = (1 + t2)1/2z.

Am aratat ca pentru |t| < min{1/3, 1/L} si pentru orice z Sn1, exista y Sn1

astfel:

ft(y) = (1 + t2)1/2z.

Drept consecinta

ft(Sn1) (1 + t2)1/2Sn1.

Pentru a arata incluziunea inversa, fixam w (1+t2)1/2Sn1 si |t| < min{1/3, 1/L}.

Atunci exista z Sn1 cu w = (1 + t2)1/2z. Pentru z Sn1 ,exista u Sn1 cu

ft(u) = (1 + t2)1/2z.

Deci ft(u) = w si

(1 + t2)1/2Sn1 ft(Sn1).

Teorema 1.7. Fiek {1, 2,...}. Atunci nu exista nicio aplicatie vectoriala normata

de clasa C1 tangenta la S2k.

4


6/35

Demonstratie. Vom presupune ca exista un astfel de vector F. Fie 0 < a < 1 < b

care extind F la F definit pe domeniul

A := {x R : a x b}.

Este usor de observat ca, asa cum F este tangent la S2k, F este tangent la orice

sfera concentrica cu S2k care contine pe A. Fie ft(x) := x + tF(x) si vom obtine

imediat

ft(A) = (1 + t2)(1/2)A,

pentru t > 0, suficient de mic. Deci

V ol(ft(A)) = (1 + t2)2k+1/2V ol(A).

Expresia (1 + t2)2k1/2 nu coincide cu niciun polinom ntr-o vecinatate a lui zero,

ceea ce contrazice concluzia teoremei 1.5.Teorema 1.8. Fie k {1, 2, ..} fixat. Atunci nu exista spatii vectoriale continue,

neneglijabile, tamgente la S2k.

Teorema 1.9. Orice submultime C, nevida, nchisa si convex a a luiRn este retracta

n Rn.

Demonstratie. Pentru orice x Rn, stim ca exista un unic y = PC(x) C astfel

x y = inf{x u : u C},

unde PC este aplicatia care asociaza fiecarui x H cel mai apropiat punct din C.

Cum PC este neextensibil, atunci n particular, este o retractie a lui Rn n C.

Teorema 1.10. Orice submultime C nevida, nchis a si convex a a lui Rn are pro-

prietatea de punct fix.

Demonstratie. Observam ca C este submultimea unei bile B din Rn. Cum Bn si

B sunt homeomorfe, teoremele 1.1 si 1.3 garanteaza faptul ca B are proprietatea

de punct fix. Mai mult, C este retractia lui B, deci C are proprietatea de punct

fix.

Observatia 1.1. Intrucat orice spatiu liniar, normat, finit dimensionat X este

izomorf cu Rn, cu n = dimX, obtinem: orice submultime nevida, marginita, nchisa,

convexa a unui spatiu liniar, normat, finit dimensional are proprietatea de punct fix.

Vom extinde teorema anterioara la un spatiu infinit dimensional, ca n urmatorul

exemplu:

Exemplu 1.1. Fie

l2 := {x = (x1, x2,...) : x2 =

i=1 |xi|2 < }

5


7/35

si

B := {x l2 : x 1}.

Definim f : B B B astfel:

f(x) := (1 x2, x1, x2,...).Este usor de probat ca f este continua, dar nu admite puncte fixe.

Definitia 1.6. Fie X si Y spatii liniare normate. O aplicatie F : X Y se numeste

compacta daca F(X) este inclusa ntr-o submultime compacta a lui Y. O aplicatie

F : X Y se numeste finit dimensionala, daca F(X) este inclusa ntr-un subspatiu

liniar, finit dimensional al lui Y .

In continuare vom extinde teorema de punct fix a lui Brouwer la aplicat ii com-

pacte pe spatii liniare normate. Aceasta generalizare i se datoreaza lui Shauder.

Ideea de baza este aceea de a aproxima aplicatii compacte cu aplicatii de rang finitdimensional.

Fie A = {a1,..,an} o submultime finita a unui spatiu liniar normat E = (E, )

si pentru > 0 fixat fie

A := ni=1B(ai, ), B(ai, ) := {x E : x ai < }.

Pentru fiecare i = 1,..,n fie i : A R aplicatia data de:

i(x) := max{0, x ai}.

Fie co(A) cea mai mica multime convexa care contine A. Proiectie Shauder esteaplicatia P : Aepsilon co(A) data astfel

P(x) :=

ni=1 i(x)ain

i=1 i, x A.

Se observa ca P(x) este bine definit daca x A, atunci x B(ai, ) pentru anumiti

i {1, 2,...} sin

i=1 i(x) = 0. De asemenea, P(x) co(A) daca fiecare P(x) este

o combinatie convexa a punctelor a1, a2,..,an.

Teorema 1.11. Fie C o submultime convexa de spatii liniare normate si A =

{a1,...,an} C. Daca P reprezinta Proiectia Shauder, atunci(i) P este o aplicatie continua si compact a de la A la co(A) si

(ii) x P(x) < , x A.

Demonstratie.

(i) Continuitatea lui P este imediata. Pentru a arata compacticitatea, fie

{P(xm)}m=1 o secventa oarecare din P(A). Fie (x) :=n

i=1 i(x) si atunci

P(xm) :=n

i=1i(xi)

(x)ai.

6


8/35

Se observa ca pentru fiecare m {1, 2, ..}, are loc

(i(xm)

(xm),..,

n(xm)

(xm)) [0, 1]n,

asadar compacticitatea n-cubului implica compacticitatea aplicatiei P.Se observa ca pentru fiecare x A,

x P(x) =1

(x)(x)x

ni=1

i(x)ai

(

1)((x))

ni=1

ix ai 0, exista o multime finita

A = {a1,...,an} n F(E) si o aplicatie continua si finit a F : E C cu urmatoarele

proprietati:

(i) F(x) F(x) < , x E, (ii) F(x) co(A) C.

Demonstratie. F(E) este inclusa ntr-o submultime compacta K a lui C, deci cum

K este marginita, exista o multime {a1,..,an} F(E), F(E) A. Fie P : A

co(A) proiectia Shauder si aplicat ia F : E C definita astfel

F(x) := P(F(x)), x E.

Teorema anterioara garanteaza rezultatul.

Inainte de a proba teorema de punct fix a lui Shauder, vom introduce not iunea

de punct fix. Fie D o submultime a unui spatiu liniar normat E si F : D E

o aplicatie. Se dau > 0,un punct d D : d f(d) < se numeste punct fix

pentru F.

Teorema 1.13. Fie D o subtime nchis a a unui spatiu liniar normat si F : D Eo aplicatie compacta si continua.Atunci F are un punct fix daca si numai daca F

are un punct fix.

Demonstratie. Vom considera ca F admite un punct fix pentru fiecare > 0.

Pentru fiecare n {1, 2,...} consideram dn un 1/npunct fix pentru F:

dn F(dn) 0. Fixam > 0. Teorema 1.12 garanteaza

existenta unei aplicatii continue, finite F : C C :

F(x) F(x) < , pentru x C.

si F co(A) C, pentru anumite multimi finite A C.

Cum co(A) este nchisa si marginita, putem aplica teorema de punct fix a lui

Brower pentru a deduce existenta lui x co(A) cu x = F(x). De asemenea,

x F(x) = f(x) F(x) < .

In anul 1980, Monch a generalizat aceasta teorema si pentru a o completa vom

prezenta rezultatul sau n continuare.

Teorema 1.15. Fie o multime deschisa, convexa ntr-un spatiu Banach E, cu

x0 . Consideram ca exista o aplicatie continua F : cu urmatoareaproprietate:

C numarabila si C co(x0 F(C)) implica C este relativ compact.

Atunci F are un punct fix n .

Demonstratie. Fie D0 := {x0} si Dn := co({x0} F(Dn1)) pentru n=1,2,...

Teorema 1.12 (Teorema lui Mazur) mpreuna cu faptul ca imaginea contunua

a unei multimi compacte este compacta probeaza ca Dn este relativ compacta.Mai

mult:

D0 D1 ... Dn1 Dn ... .

In plus, fiecare Dn este separabil, adica exista o secventa de numarabili {Cn}, cu

Cn = Dn, pentru n = 0, 1, 2, .. Fie

D := n=0Dn, C := n=0Cn.

Este usor de verificat cum Cn este crescator, ca

D = n=0Dn = n=0co({x0} F(Dn1)) = co({x0} F(D))

8


10/35

si (observam n=0Dn n=0Dn

n=0Dn):

n=0Dn = n=0Dn;

n=0Dn =n=0Cn =

n=0 Cn = C.

Rezulta ca :

C C = D = co({x0}F(D)) = co({x0}F(D)) = co({x0}F(C)) = co({x0}F(C)).

Observatia 1.2. Continuitatea lui F implica

F(D) {x0} F(D) {x0} f(D) {x0} co(F(D) {x0})

si de aici

co(F(D) {x0}) = co(F(D) {x0}).

Cum C este numarabil, rezulta C este compact. Deci D este compact. De asemenea,observam ca D = co({x0} F(D)) si atunci F(D) D. Se aplica teorema de punct

fix a lui Shauder pentru a arata ca F are un punct fix n D.

In continuare suntem pregatiti pentru a demonstra teorema de punct fix a

lui Monch.

Teorema 1.16. Fie C o submultime nchis a si convex a a unui spatiu Banach E,

cu x0 C. Vom considera ca exista o aplicatie continua F : C C cu urmatoarea

proprietate:

D C numarabila si D co({x0} F(D)) implica D relativ compact.

Atunci F are un punct fix n C.

Demonstratie. Rationamentul va fi acelasi ca n teorema precedenta.Am putea

spune ca aceasta este o a doua demonstratie. Conform teoremei 1.8, exista o aplicatie

continua F : E C cu F(x) = F(x), x C. Fie D E numarabila si

D co({x0} F(D)).

Cum F(D) C rezulta ca D C si F(D) = F(D). Exista x Ecu F(x) = x.

Daca F

(x) C x C, adica x = F

(x) = F(x).

Observatia 1.3. Teorema precedenta foloseste bine-cunoscuta teorema de punct

fix a lui Sadavskii (teorema 1.5)

9


11/35

Capitolul 2

Despre jocuri

Teoria jocurilor reprezinta o apropiere formala de studiul jocurilor.Putem con-

sidera un joc drept un conflict din care fac parte anumite numere sau indivizi (numitijucatori) si care ncearca sa-si maximizeze utilitatea. Uneori, jucatorilor le este per-

mis sa colaboreze, n acest caz putem vorbi de jocuri de echipa, opusul acestui tip

de joc este jocul individual, n care jucatorilor le este interzisa colaborarea. Teoria

jocurilor are aplicatii n domenii ca economia, biologia, psihologia, dar si n domeniul

razboaielor. Realitatea din jur este de obicei atat de complexa, ncat vom analiza

modele simplificate (un astfel de model simplificat este jocul de Poker, cu doua carti:

As si Doi).

De una singura, aceasta teorie este destul de abstracta, de aceea se va apela

adesea la cunostiint e de Analiza functionala si Topologie. Pentru nceput, vomdescrie doua jocuri care ne vor ajua la o mai buna ntelegere a notiunilor care vor

urma.

Exemplu 2.1. Jocul de Poker simplificat

In acest joc exista doar doua carti, un As si un Doi si doar doi jucatori:

Jucatorul 1 si Jucatorul 2.La nceput, fiecare dintre cei doi jucatori pune cate un

euro drept pot Cele doua carti stau cu fata n jos si niciunul dintre cei doi jucatori

nu stiu care dintre ele este As-ul sau Doi-ul.Apoi al doilea jucator alege o carte si

se uita la ea.Daca aceasta carte este As-ul, el va spune As. Daca este Doi-ul, el

poate spune Doi si va pierde jocul, iar primul jucator va primi cei 2 euro, saupoate ncerca sa blufeze, va spune As si va mai adauga un euro la pot. In acest

caz, primul jucator va avea doua optiuni: fie l crede pe al doilea jucator, caz n

care al doilea jucator va castiga jocul si pe cei 3 euro, fie mai adauga 1 euro la pot

si al doilea jucator va trebui sa i arate cartea sa. Daca aceasta carte este As ul,

atunci al doilea jucator va castiga cei 4 euro si jocul, alfel castigatorul va fi primul

jucator.In ambele cazuri, jocul se va finaliza.

Exemplu 2.2. NIM(2,2) In acest joc exista doua gramezi de chibriuri si doi

jucatori.Jucatori trag alternativ cate un chibrit din una dintre cele doua gramezi.

10


12/35

Incepe primul jucator. Jocul se va termina cand nu vor mai fi chibrituri. Jucatorul

care pierde este cel care extrage ultimul chibrit.

Fiecare dintre jocurile de mai sus au urmatoarea strucura:

1.Exista un numar de jucatori implicati n joc.

2.Exista o regula dupa care jucatorii pot sa-si aleaga strategia (mutarile).

3.Rezultatul jocului este determinat de strategiile alese de fiecare dintre jucatori

si de regula jocului.

Cele doua jocuri prezentate anterior difera totusi prin cateva aspecte: n cel

de-al doilea joc, cei doi jucatori cunosc n orice moment actiunile oponentului.Acest

lucru nu se ntampla si n primul joc, unde al doilea jucator poate trisa. Ne referim

aici la jocuri perfect transparente sau jocuri netransparente. De asemenea, n primul

joc exista un element de schimb, care lipseste n cel de-al doilea joc. Asemeneainformatii pot fi considerate individual ca structuri aditionale. De obicei un joc poate

fi reprezentat arborescent, nodurile fiind stadiile (nivelurile) jocului, iar muchiile

sunt mutarile. Pentru exemplul NIM(2,2) jocul va avea urmatorul arbore:

Figura 2.1: Numarul de pe fiecare muchie indica care dintre jucatori face mutarea, nu-merele de sub diagrama l indica pe castigator.

Exemplu 2.3.

Arborele poate fi util la ntelegerea structurii jocului, desi pentru scopul pur

matematic, adesea poate fi considerat anevoios de lucrat cu acest arbore. Vom

proceda la dezlegarea structurii de joc ntr-o forma mai ampla . Mai ntai vom

considera strategii individuale pe care jucatorii din NIM(2,2) le pot alege:

Strategiile pentru primul jucator sunt notate cu si1 pentri i {1, 2, 3} si cele

pentru cel de-al doilea jucator cu sj2, j {1, 2, 3, 4, 5, 6, }. Daca jucatorii se decid

11


13/35

12


14/35

pentru una dintre posibilitatiile lor, rezultatul jocului este deja cunoscut. Vom nota

rezultatul jocului cu 1, daca primul jucator pierde si -1, daca va castiga. Atunci

jocul va deveni echivalentul urmatorului joc, a carei forma matriceala este :

L := 1 1 1 1 1 11 1 1 1 1 1

1 1 1 1 1 1

Valoarea L(i,j) de pe pozitia (i,j) a acestei matrice este rezultatul jocului NIM(2,2)

daca primul jucator aplica a i-a strategie si al doilea jucator alege strategia a j-a.

Observam ca jucatorul al doilea are strategia s32, care i asigura victoria jocului.

De asemenea, n mod analog vom discuta jocul de Poker simplificat dupa acelasi

rac tionament.Tabelul de mai jos ne arata strategiile posibile pentru jucatori:

Intrucat exista cate un element de schimb (As si Doi, fiecare avand probabil-

itatea 1/2), pierderile corespunzatoare perechilor de strategii nu se pot determina.In corespondenta cu cartea de care Jucatorul 2 o va extrage, vom avea urmatoarele

cazur de esec:

LDoi :=

1 11 2

si LAs :=

1 12 2

Putem considera Natura fiind un al treilea jucator si pierderile vor fi reprezen-

tate ntr-un tablou 3-dimensional, dar de obicei un singur jucator va hotar sa faca

o mutare n schimbul pierderilor anticipate n matrice. Cum fiecare dintre cele doua

evenimente As si Doi au loc cu probabilitatea 1/2, vom obtine pentru pierderile

anticipate:

L :=1

2LDoi +

1

2LAs =

0 1

1/2 0

.

Cele doua exemple au proprietatea ca daca unul dintre jucatori pierde, celalalt

castiga.

Exemplu 2.4. Batalia sexelor Un cuplu casatorit ncearca sa hotarasca unde

va iesi ntr-o seara. Ea si-ar dori sa mearga la teatru, lui i-ar placea sa vada un

meci de fotbal.Cei doi sunt proaspat casatoriti de cateva saptamani si ar dori sa-si

petreaca timpul mpreuna si se vor simti bine numai daca si partenerul i va nsoti n

13


15/35

activitatea desfasuta. Sa spunem ca prima strategie pentru fiecare ar fi sa merga la

teatru si cea de-a doua meciul de fotbal. Atunci piederile individuale pentru fiecare

dintre cei doi sunt ilustrate n forma matriceala:

L := (1, 4) (0, 0)(0, 0) (4, 1) In fiecare dintre optiuni, primul numar indica pierderea barbatului, iar celalalt

pierderea femeii .

Poate fi considerat neobisnuit sa vorbim mai degraba despre perdanti decat

despre catigatori.Explicatia ar fi aceea ca n analiza convexa se prefera mai degraba

determinarea minimului decat a maximului (din motive formale), iar de vreme ce

vrem sa maximizam castigurile, va trebui sa minimizam pierderile.

Teoria jocurilor independente a ajuns sa ocupe pe parcursul ultimelor decenii

un loc central n economie. Aceasta uneste diferite domenii si leaga mai multebranse. In acest tip de jocuri este importanta regula care decide cine ce va face,

cand va actiona si informatiile de baza.

Teoria jocurilor de colaborare s-a dezvoltat cam n aceeasi perioada de timp, dar

ntr-o masuta mai mica si cu noi aplicatii. Acest lucru poate reflecta nemultumire

fata de supraabundenta conceptelor de solutie- sau aplicandu-se doar funtia carac-

teristica.Se poate observa ca aceasta functie subsumeaza- si adesea acopera actiunile,

optiunile si informatiile de baza; toate fiind necesare pentru o ntelegere adecvata

a situtiei de fata.Indreptandu-ne ntreaga atentie spre mpartirea platilor (a cos-

turilor), funtia mentionata presupune ca fiecare data de intrare relevanta sa fie dejaprocesata.

Asemenea predilectii de a lucra numai cu informatii reduse, esentiale pot gen-

era urmatoarele riscuri: unul dintre acestea este tendinta de a trece cu vederea,

asa numita diavolul se ascunde n detalii, altele pot aparea ignorand anumite

trasaturi, importante pentru formarea unor coalitii viabile.De asemenea, timpul de-

ciziilor jucatorilor si asocierea defectuoasa a informatiilor pot fi adesea neluate n

calcul.

Toate aceste riscuri actioneaza, ntr-o mare masura la asa-numita productie (sau

piat a) a jocurilor si sunt cel mai bine atenuate atunci cand datele jocului ramanaproximativ constante.Jocurile mentionate sunt ntalnite adesea si sunt considerate

foarte importante.Fiecare instanta implica partile vizate la o mpartire echitabila

a eficientei costului de productie.Fiind data multime finita de jucatori I, coalic tia

S I presupune asumarea unui cost-independent CS R {+}, care rezulta

din planificarea explicita si din optimizare.Vom considera ca acest cost areforma

generala

CS := inf{fS(x) + hS(gS(x))}.

In relatia de mai sus, functia fS parcurge o multime prestabilita XS din R

{};operatorul gS proiecteaza aceeasi multimeXS ntr-un spatiu vectorial real

E;

14


16/35

hS : E R{} reprezinta o sortare a functiei de penalitate.In continuare urmeaza

cateva exemple:

In calitate de consumator-client, un profil al costului c = (ci) CI se numeste

miez (core), scris c core, daca ncorporeaza:

acoperirea costului total:

iI ci CI si

stabilitatea coalitiei:

iS CS pentru fiecare submultime nevida S I.

Mai clar, acest concept de solutie ne da sensul corect cand miezul (core) nu este

nici gol, nici prea mare sau nici sensibil la informatii. Fiind data functia caracter-

istica definita de relatia de mai sus, vom urmari trei obiective: mai ntai, stabilirea

dualitatii fara sa invocam programarea ntregilor, n al doilea rand, sa aratam ex-

plicit solutiile miezului, generat de asa zisul pret din umbra si n al treilea rand sa

aflam cate astfel de entitati pot fi atinse.

Exista urmatoarele motivatii:nevoia recurenta de a junge dincolo de instanteleconvexe si multimi de productie. Ceea ce va rezulta n continuare va fi codul de

resurse, vazut ca o caracteristica particulara si construit ca vectori n E- fiind perfect

divizibil si transferabil. Deficitul de resurse i obliga pe cei obisnuit i sa fie dispusi sa

plateasca pentru apropiere. Aparitia preturilor de umbra endogene echilibreaza

intrinsec piata de schimb.

15


17/35

Capitolul 3

Conceptul general de joc de DouaPersoane

Definitia 3.1. Jocul de doua persoane G2 n forma normala consta n urmatoarele

informatii:

1. Spatiile topologice S1 si S2 numite si strategiile jucatorilor 1, respectiv 2.

2. Subspatiul topologic U S1 S2 al perechilor de strategii admise.

3. Operatorul dublei-pierderi

L : U R2

(s1, s2) (L1(s1, s2), L2(s1, s2)).

Li(s1, s2) reprezinta pierderea jucatorului i daca au loc strategiile i si j.

Pentru jocurile prezentate n capitolul anterior, spatiile Si sunt de dimensiune

finita (cu topologia discreta) si a fost ales chiar S1 S2. Pentru NIM(2,2 ) si jocul

de Poker simplificat vom avea L2 = L1. Principala problema din Teoria Jocurilor

este aceea de a dezvolta conceptul de solutie si mai apoi de a gasi solutia jocului.

Conceptul de solutie ne ajuta la caracterizarea acelor strategii care sunt optime n

anumite directii.

Definitia 3.2. Fiind dat jocul de doua persoane G2, vom defini unicul minim:

= (1, 2),

unde 1 = inf(s1,s2)UL1(s1, s2) si 2 = inf(s1,s2)/inU L2(s1, s2).G2 este marginita

inferior, daca 1 si 2 sunt finite.

Unicul minim reprezinta pierderile minime pentru ambii jucatori, daca acestia

nu-si planifica strategiile deloc. Pentru NIM(2,2) unicul minim este = (1, 1),

pentru jocul de Poker simplificat = (0, 1), iar pentru Batalia sexelor =

(4, 4). In acest caz, exista

(s1, s2) Ua.i.L(s1, s2) = .

16


18/35

Atunci o buna optiune pentru ambii jucatori ar fi sa aleaga stratrgiile s1 si s2 care

garanteaza pierderea minima. In majoritatea jocurilor, asemenea strategii nu exista.

De exemplu, pentru jocul NIM(2,2) nu exista nicio pereche de strategii pentru care

s-ar putea obtine dupla-pierdere (-1,-1).

Dat fiind jocul G2, vom considera U = S1 S2. Definim funtiile L1 : S1 R

si L2 : S2 R dupa cum urmeaza:

L1 = sups2S2

L1(s1, s2)

L2 = sups1S1

L2(s1, s2).

L1 reprezinta cea mai mare pierdere pe care o poate avea jucatorul 1 cand acesta

alege strategia s1 si prin analogie L2 reprezinta cea mai grea pierdere a jucatorului

2, avand strategia s2. Cum pentru ambii jucatori exista un risc ridicat, urmatoareaanaliza este potrivita: Jucatorul 1 trebuie sa aiba o strategie care minimizeaza L1,

adica va minimiza pierderea maxima si analog Jucatorul 2 va folosi o strategie care

minimizeaza L2.

Exemplu 3.1. Se cere calculul functiei Li pentru jocurile prezentate n capi-

tolul anterior.

Definitia 3.3. O strategie si care satisface

L1(s1) = v

1 := inf

s1S1L1 = inf

s1S1sups2S2

L1(s1, s2)

se numeste strategie conservativa pentru Jucatorul 1 si prin analogie s2 pentru

Jucatorul 2, daca

L2(s2) = v

2 := inf

s2S2L2 = inf

s2S2sups1S1

L2(s1, s2).

Perechea v = (v1, v2) se numeste valoarea conservativa a jocului. Un

calcul simplu va arata ca pentru Batalia sexelor vom avea L1 0 L2. Vom

obtine ca v1 = 0 = v2 si orice strategie din joc este o strategie conservativa. Asadar,

considerand ca barbatul va alege sa vada un meci de fotbal, deci strategia aleasa vafi s1 = s

21 si femeia va opta pentru teatru, ceea ce nseamna strategia s

2 = s

12, atunci

ambele strategii sunt conservative, dar ambii parteneri pot alege mai bine:

L1(s1, s

2) = 0 1 = L1(s

11, s

2)

L2(s1, s

2) = 0 1 = L2(s

1, s

22).

Vom afirma ca perechea de strategii aleasa nu este individual stabila.

17


19/35

Definitia 3.4. Un dublet s1, s2 se numeste un echilibru independent sau pe scurt

NCE daca:

L1()s1, s

2) L1(s1, s

2), s1 S1

L2()s1, s

2) L2(s

1, s2), s2 S2.

Cu alte cuvinte, acest lucru se traduce prin:

L1(s1, s

2) = min

s1S1L1(s1, s

2)

L2(s1, s

2) = min

s2S2L1(s

1, s2)

Asadar, un echilibru independent este stabil n sensul de mai sus daca jucatorii

folosesc un astfel de dublet, deci niciunul nu are vreo motivatie sa degenereze de la

strategia sa. Pentru Batlia sexelor, avem echilibrele independente s11, s12 si s

12, s

22.

Daca multimile de strategii sunt finite si L este scris ca o matrice n fuctie de

dubla pierdere, atunci un echilibru independent este dubletul (s1, s2), astfel ncat

L1(s1, s

2) reprezinta minimul de pe coloana lui (ne referim doar la valorile lui L1),

iar L2(s1, s

2) reprezinta minimul de pe limia sa (ne referim doar la valorile lui L2

).Cu ajutorul acestui criteriu, putem proba usor ca n jocul de Poker Simplificat nu

exista niciun echilibru independent. Acest lucru ne conduce ntr-un punct crucial n

teoria moderna a jocurilor, la extinderea multimilor de strategii numita si strategie

mixta.

Definitia 3.5. Fie X o multime arbitrara si RX spatiu vectorial ale valorilor reale

ale funtiilor pe X, mpreuna cu topologia de convergenta. Pentru orice x X

definim corespondenta masurii Direc x ca fiind

x : RX R

f f(x).

Orice combinatie liniara (finita) m =n

i=1 ixi , care duce pe f RX n

m(f) =n

i=1if(xi)

se numeste masura discreta. Afirmam ca m este pozitiv daca 0, i. Pe m

l numim masura de probabilitate discreta, daca m este pozitiv sin

i=1 i = 1.

Vom nota multimea masurilor de probabilitate discreta cu M(X). Acest spatiu este

nzestrat cu topologia slaba.

Putem proba usor ca multimea M(X) este convexa. Mai mult, facem o fixare

canonica:

: X M(X)

x x.

18


20/35

In continuare vom considera ca avem un joc de doua persoane G2 dat prin

multimea de strategii S1, S2 si operatorul dublei pierderi L = (L1, L2). Vom defini

un nou joc G2 dupa cum urmeaza : multimea de strategii va fi

Si := M(Si), i = 1, 2

si operatorul dublei-pierderi L = (L1, L2) cu

Li : S1 S2 R

(ni=1

1i si1,

mj=1

mj sj2

) ni=1

mj=1

112jLi(s

i1, s

j2).

Definitia 3.6. Multimile M(Si) se numesc strategii mixte ale lui G si jocul G2 se

numeste extindere a lui G2 prin strategii mixte. Strategiile continute n imaginea

fixarii canonice:

: S1 S2 M(S1) M(S2)

(s1, s2) (s1 , s2)

se numesc strategii pure.

Exemplu 3.2. Sa se arate ca o extindere a jocului de Poker Simplificat are un

echilibru independent.

Cum se ntampla adesea, asemenea jocuri nu se joaca doar o data, ci se repeta

de mai multe ori.Daca primul jucator are doua strategii pure si jocul de repeta sa

spunem, de o suta de ori, atunci acest jucator poate realiza 0.3s11

+ 0.7s21

jucand

strategia s11 de 30 de ori si s21 de 70 de ori. Alta interpretare ar fi ca de fiecare

data cand va avea o strategie mixta de tipul 1s11 + 2s21 va realiza un experimentaleatoriu care are doua rezultate posibile, unul de probabilitate 1 si celalalt de

probabilitate 2. Atunci se va hotar n favoarea uneia dintre cele doua strategii pure

s11, respectiv s21corespunzand rezultatului experimentului. Daca exista mai multe

strategii pure, atunci strategiile mixte vor avea urmatarea interpretare geometrica:

sa spunem ca S1 are n+1 elemente. Atunci S1 este homeomorf cu n-simplexul

nchis n := {(0,..,n) Rn+1i 0,n

i=0 = 1} prin aplicatia (0,..,n) ni=1

ni=1si . Aceasta relatie aduce geometria n jocul studiat.

Se poate ntampla de asemenea ca un joc sa aiba mai multe echilibre indepen-

dente.In acest caz, unul dintre jucatori va avea de ales unul dintre echilibre, dupao anumita regula de decizie. Acest lucru ne duce la conceptul de solutie stricta a

jocului G2.

In demonstrarea teoremei e punct fix Brouwer nu este atat de important cate

simplificari complet caracterizate sunt, ci daca exista cel putin una. Aceasta afirmatie

sta la baza urmatorului corolar.

Corolarul 3.1. Fie T = x0..xn o subdiviziune simplificata si caracterizat a propriu.

Atunci exista cel putin un simplex complet caracterizat n subdiviziunea simplificata.

Demonstratie. Zero nu este un numar impar.

19


21/35

3.1 Demonstratia teoremei Brouwer

Mai ntai vom proba o versiune simplificata a teoremei lui Brouwer de punct fix .

Propozitia 3.2. Fie f : n n continua. atunci f are un punct fix.

Demonstratie. Fie > 0. Cum n este compact, putem gasi o subdiviziune

simplificata cu o retea mai mica decat 2. Fie V multimea varfurilor acestei subdi-

viziuni. Vom considera un varf arbitrar v din subdiviziune si v xi0 ..xik . Fie vi si

fi componentele lui v, respectiv f. atunci:

{i0,..,ik}

{i|fi(v) vi} = ,

cat timp fi(v) > vi, pentru fiecare i {i0,..,ik}, va implica:

1 =

ni=0

fi(v)

kj=0

fik(v) >

ki=0

vi = 1.

Vom defini eticheta functiei:

: V {0,..n}

alegand pentru fiecare varfv xi0..xik un element (v) {i0, . . ,ik}

{i|fi(v) vi}.

Atunci este funtie proprie. Rezulta din corolarul anterior ca exista un simplex

caracterizat complet n subdiviziunea simplificata. Inseamna ca exista un simplex

x0 ,..,xn astfel ncat pentru orice i {0, 1,..,n}, exista j astfel ncat

fi(xj

) xj

,j.

xj,i reprezinta a i-a componenta lui xj. Vom face pe sa tinda la zero. Atunci,

vom obtine o secventa de simplecsi complet caracterizati x0 , . . ,xn . Cum reteaua

subdiviziunilor tinde la zero si n plus n este compact, putem o subsecventa care

converge la un punct din n. Vom nota acest punct cu x. Acest punct reprezinta

limita tuturor secventelor xj pentru 0. Folosind inegalitatea de mai sus si

continuitatea lui f vom obtine:

fi(x) xi, i {0,..,n}.

Vom considera ca pentru un i {0,..,n} vom avea fi(x) < xi. Atunci

1 =ni=0

fi(x) y. Cum 0 X,rezulta ca exista > 0 astfel ncat Dm := {z R

m : z } X. Atunci nvelisul

convex co(x, Dm ) contine o vecinatate a lui y. Cum X este convex si nchis, vom

avea co(x, Dm ) X si deci y X, ceea ce este o contradictie a lui y X. Vom

considera functia urmatoare:

f : X Sm1 := {z Rm : z = 1}

x x

x.

Cum X contine o bila deschisa n jurul originii, rezulta ca aplicatia f este bine

definita, 0 X si mai mult, f este surjectiva. Este evidenta continuitatea lui

f si se observa ca este si injectiva (altfel doua elemente din X vor avea aceeasi

raza din origine). Cum X este compact si Sm1 este Hausdorff, rezulta ca f este

homeomorfism.Asadar aplicatia inversa

f1 : Sm1 X

este de asemenea contunua.Vom considera o aplicatie definita pe ntreg spatiul X

k : D

m

X

21


23/35

x

x f1(x/x), daca x = 0;

0, daca x = 0.

Cum X este compact, exista M R astfel ncat x M, x X. Atunci

f1

(x/x) M, x X si deci

k(x) x M.

De aici rezulta ca aplicatia k este continua n 0. Continuitatea n celelalte puncte este

evidenta, deci k este o aplicatie continua. Consideram ca x, y X si k(x) = k(y).

Atunci

x f1(x/x) = y f1(y/y).

Intrucat f1(x/x) = 1 = f1(y/y), va trebui sa avem x = y. Dar

atunci ecuatia de mai sus este echivalenta cu

f1(x/x) = f1(y/y)

si din injectivitatea lui f1 va rezulta ca xx =yy , ceea ce implica x=y. Aceast

lucru probeaza injectivitatea lui k. De asemenea, k este surjectiv: fie x X. Atunci,

la fel ca n prima parte a demonstratiei, x poate fi scris ca x = t x, cu x X si

t (0, 1), f(x) = xx

, ceea ce este echivalent cu x = f1( xx

). Atunci

x = t x = t f1(t xx

t xx)

= t xx

f1(t x

xt x

x

)

= k(t x

x ) Dm

Repetand rationamentul anterior, ntrucat Dm este compact si X este Hausdorff,

vom obtine k este homeomorfism. Fara a se pierde generalitatea, putem considera

ca 0 X (prin translatie- translatiile sunt homeomorfisme), dar nu mai putem

considera ca 0 X. Se poate gasi numarul maxim de vectori liniari independenti

v1, . . ,vn X. Atunci X span(v1, . . ,vn). Este evident, conform algebrei liniare, sa

aratam ca exista p aplicatie liniara

: Rm Rn,

care duce pe span(v1,..,vn) izomorf la Rn (si complementii sai ortogonali la zero).

Aceasta aplicatie duce pe X homeomorf la (X) Rn, iar cum aplicatiile liniare

conserva convexitatea, (X) este de asemenea convex. Putem aplica rezultatul

anterior lui (X) si obtinem

X (X) n X n.

22


24/35

Corolarul 3.5. Fie X Rmconvex si compact. Atunci X n, pentru anumiti

0 n m.

Demonstratie. Cum pentru fiecare n, n este convex si compact, folosind propozitia

precedenta probam ca

n

Dn

(ne referim la dimensiune).Tot din propozitia an-terioara stim ca exista n astfel ncat X Dn. Atunci X Dn n.

Abia acum putem proba foma generala a teoremei Brouwer de punct fix:

Teorema 3.6. Fie X Rmconvex si compact si f : X Xcontinua; atunci f are

un punct fix.

Demonstratie. Din corolarul anterior: X n. Deci totul rezulta direct din

corolarul anterior.

3.2 Teorema de echilibru Nash

Teorema 3.7. FieG2 un joc cu multimile finite de strategiiS1 siS2 siU = S1S2.

Atunci exista cel putin un echilibru independent pentru extinderea jocului G2.

Demonstratie. Fie L operatorul dublei-pierdei al lui G2 si L operatorul extin-

derii.In plus, fie S1 = {si1 : i {1, . . ,n}}, S2 = {sj2 : j {1,..,m}} si l1 = L1, l2 =

L2. Este evident ca S1 S2 n1 m1 este convex si compact. Fie s1 S1 si

s2 S2 definite astfel

s1 =

ni=1

11 si1

s2 =m

j=1

2j sj2

.

Pentru 1 i n si 1 j m, definim aplicatiile ci, dj : S1 S2 R astfel :

ci(s1, s2) = max(0, l1(si1, s2) l1(s1, s2))

dj(s1, s2) = max(0, l2(s1, sj2) l2(s1, s2)).

Mai mult, vom defini aplicatia f : S1 S2 S1 S2:

(s1, s2) (ni=1

1i + ci(s1, s2)

1 +n

i=1 ci(s1, s2) si1,m

j=1

2j + dj(s1, s2)

1 +n

j=1 dj(s1, s2) sj

2

)

:= 1i := 2j

Este evident can

i=1 i1 =

mj=1

j2 si deci membrul drept al expresiei este un

element din S1 S2. Aplicatia f este continua si conform aplicatiei teoremei de

punct fix a lui Brouwer, trebuie sa existe un dublet (sji , sj2) astfel ncat

(

s

i

1,

s

j

2) = f(

s

i

1,

s

j

2).

23


25/35

Scriinds1 =

ni=1

1i si1 si

s2 =

nj=1

2j sj

2

, observam ca ecuatia de mai sus este

echivalenta cu urmatoarea multime de ecuatii:

1i =1i + c1(s1, s2)

1 + ni=1 ci(s1, s2) , 2j =

2j + dj(s1, s2)

1 + mj=1 dj(s1, s2) , 1 i n, 1 j m.Vom considera acum ca pentru fiecare 1 i n, avem l1(si1,

s2) > l1(

s1,

s2).

Folosind extinderea operatorului dublei pierderi si apoi biliniaritatea pentru l1 si l2,

avem:

l1(s1,

s2) =

ni=1

1i l1(si1,

s2) >

ni=1

1i l1(s1,

s2) = l1(

s1,

s2)

ceea ce reprezinta o contradictie. Trebuie sa existe i {1,..,n} astfel ncat l1(si1,s2) 0 arbitrar, rezulta ca CI

SwsCS. Rezultatul Bondavera-Shapley Shapley

va certifica faptul ca miezul este nevid.

Propozitia 3.9 indica perspective pentru gasirea de miezuri nevide, dar ofera o mai

mica satisfactie vis-a-vis de gasirea solutiilor implicite. Se cere prea multa convexitate

n multimea activitatiilor Xi si functiile de cost Fi. Agregarea de resurse este prea liniara

. Datele originate nu sunt introduse exact.Toate aceste dezavantaje motiveaza o analiza

mai atenta a marii aliante S = I.

3.5 Multiplicatori Lagrange, subgradienti si MIN-MAX

In aceasta sectiune vom avea de-a face cu material auxiliar si destul de util. Vom

considera problema si costul urmator:

Ci := inf{fI(x) + hI(gI(x))}

din marea alianta.Pentru o notatie mai usoara vom utiliza P, C, f, g, h, X, n locul

PI, CI, fI, gI, hI,XI. O analiza mai atenta rezolva asa-numita functie de perturbatie:

(x,e,y) X E Y f(x) + h(g(x) + e) < y, e > (3.1)

In acest caz, Y este ales convenabil, convex, ca o multime nevida de functionale liniare

y : E R. Alte caracteristici ale functionalelor y (n afara de liniaritate), vor fi invocate

numai n caz de necesitate.Uzual prin expresia < y, e > ntelegem y(e). Obiectivul relatiei

3.1 este de a exprima perturbarea e disponibila la primul produs < y , e >.Atunci 3.1

dimplifica si transforma problema 3.5 ntr-o piata competitiva unde fiecare dotare e E

este evaluata ca un pret unitar constant y. Pentru a prezenta acesta situatie, vom asocia

conjugata Fenchel lui h :

h(y) := sup{< y, e > h(e) : e E}

. Daca h(e) reprezinta constul cu care o intreprindere produce bunuri e la veniturile , atunci h(e) corespunde profitului. In jargonul economic, firma cea mai apropiata

27


29/35

este cea care stabiletepreturile la produsele pietei. Evident, h : Y R {} este

convex si funtia dubla-conjugata:

h(e) := sup{< y, e > h(y) : y Y}

satisface h h. Astfel, 3.1 garanteaza Lagrangianul

L(x, y) := inf{f(x) + h(g(x) + e) < y, e >: e E}

= f(x)+ < y, g(x) > h(y),

definit pe X Y. In continuare l vom numi pe y Y multiplicatorul Lagrange daca el

apartine multimii

M := {y Y : infx

L(x, y) C := inf(P)}.

Observam ca M este convex, dar poate fi vid. Referindu-ne strict la problema 3.5

exista functia marginala (valoare optima)e E V(e) := inf{f(x) + h(g(x) + e) : x X}.

De prim interes ar fi proprietatile diferentiale ale lui V() n punctul diferential e = 0.

Functionala y Y se numeste subgradient al lui V : E R{} la 0, scris y V(0),

daca

v(e) V(0)+ < y, e >, e.

V se numeste subdiferentiala la 0 daca V(0) este nevid. Urmatoare doua propozitii,

sunt cel putin partial, cunoscute. Vor include si demonstrat ii pentre completari.

Propozitia 3.10. (Subgradient=Multiplicator Lagrange) Sa consideram caC = inf(P) =V(0) este finit. Atunci

V(0) = M

Demonstratie. Fie e := g(x) + e. Vom obtine:

e V(0)

f(x) + h(e) = f(x) + h(g(x) + e) V(e) V(0)+ < y,e >

(x, e) X E

f(x)+ < y, g(x) > +h(e) < y, e > V(0), (x, e) X E

f(x)+ < y, g(x) > h(y) V(0), x X

infx

L(x, y) inf(P) y M.

Propozitia 3.11. (Stabilitate-tare,min-max,dubla-conjugata si valoarea atins a.) Valoarea

functiei V este subdiferentiala la 0 si problema 3.5 este tare-stabila daca infP este finit

si egal cu valoarea sa

infx

L(x, y) = infx

supy

L(x, y), pentruoricemultiplicatorLagrangey.

In acest caz V

(0) = V(0). Mai mult, daca problema 3.5 este tare stabila atunci:

28


30/35

pentru fiecare solutie optima x a problemei 3.5 si multiplicator Lagrange y, avem ca

y h(g(x)) si

f(x)+ < y, g(x) >= min{f(x)+ < y, g(x) >: x X} (3.2)

pentru fiecare pereche (x, y) X Y care satisface 3.2 cu y h(g(x)), puncul x

rezolva optim problema 3.5.

Demonstratie. Din propozitia anterioara V(0) = M = y Y astfel ncat

infx L(x, y) V(0). In acest sir, pentru orice y V(0) = M avem

supy

infx

L(x, y) infx

L(x, y) inf(P).

Mai mult, inegalitatea

f(x) + h(g(x)) f(x)+ < y, g(x) > h(y)

este valida pentru toate perechile (x, y) XY. Ca o consecinta inf(P) infx supy L(x, y).

Astfel inegalitatea infxL(x, y) inf(P) este constransa astfel:

supy

infx

L(x, y) infx

L(x, y) inf(P) infx

supy

L(x, y).

Egalitatiile au loc n 3.5 deoarece supy infx L(x, y) infx supy L(x, y).

Din V(y) = infx L(x, y) rezulta ca V = supy infx L(x, y). Daca 3.5 este tare

stabila, atunci- conform argumentului precedent- ultima parte este egala cu inf(P) =

V(0).

Fiind dar orice minimizant x al lui 3.5, alegem arbitrar un y M = V(0).

Rezulta ca pentru fiecare x X are loc

f(x) + h(g(x)) = inf(P) L(x, y) = f(x)+ < y, g(x) > h(y).

Vom face substitutia x = x n memebrul drept pentru a obtine h(g(x)) < y, g(x) >

h(y), cand

h(g(x)) + h(y) =< y, g(x) > . (3.3)

Aceasta impica, n primul rand, ca y h(g(x)) si n al doilea rand ca y h(g(x))( 3.3),

ceea ce implica

f(x) + h(g(x)) = minx {

f(x)+ < y, g(x) >

h(y)}

= minx

L(x, y).

Conform acestei relatii si din 3.5, reiese ca x minimizeaza 3.5 si ca y M.

Mai tarziu, folosind doar cunostiintele de algebra, ordonarea numericasi multipli-

catorii Lagrange-sau echivalent subgradientii- a fost demonstrata eficace dualitatea La-

grangianului. Mai ramane de probat n continuare ca astfel de indicatori exista neconditionat

n circumstante obisnuite.In acest scop, vom reaminti ca un punct c dintr-o submultime C

a unui spatiu vectorial real se numeste de absortie, daca pentru orice directie d nenula, n

acest spatiu exista un real r > 0 astfel ncat c+]0, r[d C. De asemenea, vom reaminti ca

convC reprezinta marginea convergenta a lui C, iar epiV := {(e, r) E R : V(e) r}

reprezinta un diminutiv pentru epigraful lui V.

29


31/35

Propozitia 3.12. (Suportul liniar al lui V la 0). Vom considera ca 0 este punct de

absortie n dom V. De asemenea, consideram ca conv(epi V) contine un punct de absortie,

dar ca(0, V(0)) nu este acesta. Atunci, dacaY contine toate aplicatiile liniare y : E R,

subdiferentiala V este nevida.

Demonstratie. Din teorema de separare Hahn-Banach, exista un hiperplan care sustine

C := conv(epiV) n punctul (0, V(0)). Acest hiperplan este definit ca o funct ionala liniara

(e, r) = 0 prin

< e, e > +rr rV(0), (e, r) C. (3.4)

In plan, (e, r) C, r > r (e, r) C. Prin urmare, r 0. Daca r = 0, atunci, ntrucat

0 este punct de absorbtie n dom V, reiese ca < e, e > 0 pentru fiecare e E, de unde

e = 0 si se obtine contradictia (e, r) = 0. Asadar, mpartind prin 3.4, cu r > 0, vom

defini y := e/r si r = V(e) pentru a obtine

V(e) V(0)+ < y, e >, e E

.Asadar y V(0).

Propozitia 3.13. (Suportul liniar si continuu al lui V la 0). FieE un spatiu vectorial

real, topologic, local convex, separabil. Vom nota cu V cele mai mari funtii convexe

V.Vom considera ca V este finita, marginita de o vecinatate a lui 0 si V(0) = V(0).

Atunci, pentru Y fiind multimea tuturor functionalelor liniare si continue y : E R,

subdiferentiala V(0) este nevida.

Ultimele doua rezultate evidentiaza modul lui (0, V(0)) de a nu fi un punct interior

lui conv(epi V). In paticular, lucrurile se simplifica daca avem epi V- sau echivalent V

nsusi convex.

3.6 Puncte sa si solutii miez

Vom reconsidera jocul de productie avand costul de alianta CS definit n 3.3. De acum

nainte vom considera o forma slaba a subsdivitatii CI

iICi < +. Obiectivul este

acela de a gasi costul explicit alocarii c = (ci) miezului. Pentru acest scop, amintim

exemplul 3.3, unde vom redenumi

LS(x, y) = fS(x)+ < y, gS(x) > h

S

(y)

si vom introduce urmatoarea stare

Ipoteze ale estimarilor aditive: Vom considera n continuare XS :=

iSXi

E si hi : R {+} astfel ncat pentru fiecare S I si y Y,

infx

LS(x, y) inf{iS

[fi(xi)+ < y, gi(xi) > hi (y)] : xi Xi}. (3.5)

In plus, pentru alianta S = I, va avea loc:

infx

LI(x, y) supy

inf{

iI[fi(xi)+ < y, gi(xi) > h

i (y)] : xi Xi}

30


32/35

Propozitia 3.14. Afirmatia din Ipoteza estimarilor aditive are loc pentru fiecare S

I, x XS, y Y

fs+ < y, gS(x) >iS

{fi(xi)+ < y, gi(xi) >}, (3.6)

si pentru fiecare e EhS(e) inf{

iS

hi(ei) :iS

ei = e}, (3.7)

egalitatea avand loc cand S = I.

Demonstratie. 3.7 implica hS(y)

iShi (y).

Exemplu 3.4. (Penalizarea omogen-pozitiva)Fie h : E R{+} omogen-pozitiva.De

exemplu, h poate fi functia suport pentru anumite submultimi nevide ale pre-dualului lui

E. Atunci h restrans la Y este un indicator extins Y la anumite multimi convexe Y Y.

Adica h

(y) = 0, daca y Y, , altfel.Vom considera ca h

= h

S pentru toti S I.Atunci 3.6 implica 3.5.

Exemplu 3.5. (Restrictia conului). O instanta particulara este atunci cand h, descris

n exemplul anterior, este egal cu indicatorul extins K al unui con convex K E.

Atunci h = K, unde K = {y :< y, K > 0} este conul dual negativ. In exemplul

3.3 consideram fiecare Ki acelasicon convex K E si fixam hS := h pentru fiecare

S I.Atunci ipoteza este satisfacuta si coalitia S va avea costul

CS := inf{

iSfi(xi) :

iSgi(xi) K, xi Xi}.

Observam ca atat costurile cat si restrictiile sunt adunate.Nicio multime de activitati nu

poate fi transferata de la un agent la altul.

Exemplu 3.6. (Inf-convolutia penalizarilor). Daca

hS(e) := inf{iS

hi(xi) :iS

xi = e},

vom obtine hS(y) =

iShi (y).

Teorema 3.15. (Neviditatea miezului si alocarile explicite)

Vom presupune VI (0) = VI(0).Atunci, in conditiile ipotezei, miezul este nevid.

Daca n plus VI() este subdiferentiala la 0-atunci, daca 3.5 este tare stabila - atunci

fiecare multiplicator Lagrange y al problemei 3.5 genereaza o alocare de cost

ci = ci(y) := inf{fi(xi)+ < y, gi(xi) > hi (y) : xi Xi} (3.8)

31


33/35

Demonstratie. Conform presupunerii din ipoteza rezulta ca pentr orice pret y Y si

pentru fiecare alianta S:

iS

ci(y) infx LS(x, y) supy infx LS(x, y) infx supy LS(x, y)

= infx

{fs(x) + h(gS(x))} inf

x{fs(x) + hS(gS(x))} = CS.

Asadar nicio alianta nu poate bloca o schema de plata dupa o sortare i ci(y). In plus,

daca y este un multiplicator Lagrange, atunciiI

ci(y) = infx

LI(x, y) CI.

In lipsa unei stabilitati tari, cand pur si simplu VI (0) = VI(0), alegem pentru fiecare

n ntreg un pret yn Y astfel ncat numerele cni = ci(yn), i I, satisfaciI

cni = infx

LI(x, yn) CI 1/n.

iSc

ni CS, pentru fiecare S I. In particular, c

ni Ci < +. Din c

ni CI

1/n

j=i Cj rezulta ca secventa (cn) este marginita.Evident, orice punct de acumulare

c apartine miezului.

Exemplu 3.7. (Programarea liniara n cooperare). O variana partivulara si importanta

a exemplelor 3.9 si 3.1 este Xi := Rni+ cu costul liniar k

Ti xi, ki R

ni si constangerile liniare

gi(xi) := Aixi ei, ei Rm, Ai fiind o matrice m ni. Fixam Ki := {0} pentru fiecare i,pentru alianta S, costul dat de programarea liniara standard

toremovenumbering(beforeeachequation)CS := inf{iS

kTi :iS

Aixi

=iS

ei,cuxi 0i

Vom considera 3.5 o problema de baza si duala sa

sup{yTiI

ei : ATi y ki, i}, (3.9)

ambele realizabile. Atunci inf(3.9) este atins si pentru orice solutie optima y a lui 3.9,

schema de plati ci := yTei duce la ci miezului. Deci, referindu-ne la ei ca la tinta de

productie a fabricii sau a diviziunii i, aceste target-uri sunt evaluate la un pret comun y,

generat natural.

Exemplu 3.8. (Inf-convolut ia continua) Fiecare multiplicator Lagrange y aplicat n ex-

emplul 3.3 genereaza un cost alocat (ci) miezului :

ci :=< y, ei > fi (y).

32


34/35

3.7 Dinamica preturilor

Vom presupune de acum ca exista cel putin un multiplicator Lagrange.Acesta va

fi, de exemplu, M = 0. Apoi, pentru a simplifica scrierea, vom considera un spatiu E

si dualul sau topologic Y, Euclidian real, de dimensiune finita.Vom nota prin D(y) :=infxXI LI(x, y) asa-numitul obiectiv-dual.Foarte important de precizat este ca functia

u Y D(y) R {} astfel definita este concava superior semi-continua.Iar

M, multimea solutiilor optime ale problemei duale

sup{D(y) : y Y},

este o multime nchisa nevida. Drept consecinta, fiecare y Y are o unica proiectie

ortogonala (cea mai buna aproximare) y = PMy n M.Fie T := domM si sa consideram

Y nchis. Vom nota cu T y := clR+{Y y} conul tangent al lui Y n punctul y Y si cu

Ny := {y

:< y

, T y > 0} duala negativa asociata sau conul normal.

Propozitia 3.16. Pentru fiecare punst initial y(0) Y la care D este superdiferentiabil,

doua incluziuni diferentiabile

admit aceeasi traiectorie unica,absolut continua, ifinit extensibila 0 t y(t) Y.In

plus y(t) PMy(t) 0.

Demonstratie. Fie (y) := min{y y : y M} reprezentand distanta Euclidiana

de la y la multimea M a solutiilor duale optime. Sistemul y D(y) N y are o unica

solutie, infinit extensibila y() de-a lungul careiad

dt(y(t))2/2 =< y PMy, y >< y PMy,D(y) Ny > (3.10)

< y PMy,D(y) > D(y) D(PMy). (3.11)

Concavitatea justifica ultima inegalitate. Deoarece D(y)D(PMy) 0, rezulta ca y(t)

PMy 0. Sistemul y PTyD(y) are de asemenea o solutie infinit extensibila conform

teoremei lui Nagumo (1991). Intrucat PTyD(y) D(y) Ny, aceasta solutie este de

asemenea unica.

Propozitia 3.17. Sa consideram ca D este superdiferentiabila la Y cuD(y)2

k(1 +y PMy2), pentru anumite constante k > 0. Vom alege marimea pasilor sk > 0 astfel

nc at

sk = + si

d2k < . Atunci, pentru orice punct initial y0 Y, secventa {yk}

generata iterativ de incluziunea

yk+1 PY[yk + skD(y)] (3.12)

este marginita si fiecare punct de acumulare y trebuie sa fie multiplicator Lagrange.

33


35/35

Demonstratie. Acest rezultat este bine-cunoscut, dar demonstratia sa este data pentru

a-l completa.Fie yk := PMyk si k = yk yk2 . Atunci 3.12 implica

k+1 = yk+1 yk+12 PY[yk + skD(yk)] PYyk

2

yk + skD(yk) yk2

yk yk2 + skD(yk)

2 + 2sk < yk yk, D(yk) >

k(1 + k) + k k

cu k := s2k, k := s

2k si k := 2sk < yk yk, D(yk) > .Demonstratia propozitiei

anterioara duce la

y PMy > 0 sup < y PMu,D(y) >< 0.

Deci k 0. Intrucat k < + si k < +. Daca lim k > 0, proprietatea sk = + va implica contradictia k = +. Atunci k 0 si demonstratia estecompleta.

teoria jocurilor de doua persoane

Documents

Transcript of teoria jocurilor de doua persoane