Date post: | 14-Apr-2018 |
Category: |
Documents |
Upload: | mihaela-radoi |
View: | 245 times |
Download: | 1 times |
of 35
7/30/2019 teoria jocurilor de doua persoane
1/35
Aplicatii ale teoremelor de punct fix n
teoria jocurilor
Radoi Mihaela Luciana
2010
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
13/35
12
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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
7/30/2019 teoria jocurilor de doua persoane
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.