Echilibru Nash

În teoria jocurilor, echilibrul Nash este definit ca un profil de strategii (una pentru fiecare jucător) în raport cu care niciun jucător nu are interes să fie singurul care să se schimbe.

«Un joc poate fi descris în termeni de strategii, pe care jucătorii trebuie să le urmeze în mișcările lor: echilibrul este acolo, atunci când nimeni nu își poate îmbunătăți comportamentul unilateral. Pentru a ne schimba, trebuie să acționăm împreună. ^[1] "

( John Nash )

Nașterea teoremei lui Nash

Prima formulare a acestei teoreme, referitoare la cea mai faimoasă noțiune de echilibru din teoria jocurilor în ceea ce privește „ jocurile necooperante ”, apare într-un articol foarte scurt publicat în 1950 unde John Nash , pe atunci doctorand la Princeton , își explică ideea să fuzioneze intim două concepte aparent foarte îndepărtate ^[2] : cel al unui punct fix într-o transformare a coordonatelor și cel al celei mai raționale strategii pe care un jucător o poate adopta, atunci când concurează cu un adversar care este și rațional, extinzând teoria jocuri pentru un număr arbitrar de participanți sau agenți. Nash demonstrează că, în anumite condiții, există întotdeauna o situație de echilibru, care se obține atunci când fiecare individ care participă la un anumit joc își alege mișcarea strategică pentru a-și maximiza recompensa , sub conjectura că comportamentul rivalilor nu va varia. datorită alegerii sale (înseamnă că, chiar și cunoscând mișcarea adversarului, jucătorul nu ar mai face o mutare în afară de cea pe care a decis-o).

Rezultatul Nash poate fi văzut ca o extensie relevantă în ceea ce privește cazul „ jocurilor cu sumă zero ” studiat anterior de John von Neumann . Ideea de echilibru reprezintă, de asemenea, o variație conceptuală semnificativă față de abordarea lui von Neumann, care a folosit ideea de minimax .

Echilibrul Nash

Acum să vedem mai detaliat ce se înțelege exact prin echilibrul Nash . În acest scop, poate fi util să clarificăm câteva aspecte matematice simple ale teoriei jocurilor și să definim câteva concepte de bază.

Un joc se caracterizează prin:

Un set de jucători , sau agenți , în număr de N, pe care îl vom nota cu i = 1, ..., N;
Pentru fiecare agent, un transportator

S_{i}=\left(s_{i,1},s_{i,2},...,s_{i,j},...,s_{i,M_{i}}\right)

{\ displaystyle S_ {i} = \ left (s_ {i, 1}, s_ {i, 2}, ..., s_ {i, j}, ..., s_ {i, M_ {i}} \ dreapta)}

S_ {i} = \ left (s _ {{i, 1}}, s _ {{i, 2}}, ..., s _ {{i, j}}, ..., s _ {{ i, M_ {i}}} \ dreapta)

a strategiilor pe care jucătorul i le are la dispoziție, adică setul de acțiuni pe care le poate efectua; din motive de scurtă durată, vom indica mai jos cu $s_{i}$ ${\ displaystyle s_ {i}}$ $da$ strategia aleasă de jucătorul i ;

Pentru fiecare agent, o funcție

U_{i}\left(s_{1},s_{2},...,s_{i},...,s_{N}\right)

{\ displaystyle U_ {i} \ left (s_ {1}, s_ {2}, ..., s_ {i}, ..., s_ {N} \ right)}

{\ displaystyle U_ {i} \ left (s_ {1}, s_ {2}, ..., s_ {i}, ..., s_ {N} \ right)}

care asociază player - i câștig ( de asemenea , numit pay-off) care rezultă din fiecare combinație de strategii (câștigul unui jucător , în general , nu depinde numai de strategia sa , ci și pe strategiile alese de adversari).

Un echilibru Nash pentru un anumit joc este o combinație de strategii (pe care le vom nota cu supercriptul e )

s_{1}^{e},s_{2}^{e},...,s_{N}^{e}

{\ displaystyle s_ {1} ^ {e}, s_ {2} ^ {e}, ..., s_ {N} ^ {e}}

s_ {1} ^ {e}, s_ {2} ^ {e}, ..., s_ {N} ^ {e}

astfel încât

U_{i}\left(s_{1}^{e},s_{2}^{e},...,s_{i}^{e},...,s_{N}^{e}\right)\geq U_{i}\left(s_{1}^{e},s_{2}^{e},...,s_{i},...,s_{N}^{e}\right)

{\ displaystyle U_ {i} \ left (s_ {1} ^ {e}, s_ {2} ^ {e}, ..., s_ {i} ^ {e}, ..., s_ {N} ^ {e} \ right) \ geq U_ {i} \ left (s_ {1} ^ {e}, s_ {2} ^ {e}, ..., s_ {i}, ..., s_ {N} ^ {e} \ dreapta)}

U_ {i} \ left (s_ {1} ^ {e}, s_ {2} ^ {e}, ..., s_ {i} ^ {e}, ..., s_ {N} ^ {e} \ dreapta) \ geq U_ {i} \ left (s_ {1} ^ {e}, s_ {2} ^ {e}, ..., s_ {i}, ..., s_ {N} ^ {e } \ dreapta)

pentru fiecare i și pentru fiecare strategie $s_{i}$ ${\ displaystyle s_ {i}}$ $da$ ales de către jucătorul j- - lea.

Sensul acestei ultime inegalități este foarte simplu: dacă un joc admite cel puțin un echilibru Nash, fiecare agent are la dispoziție cel puțin o strategie $s_{i}^{e}$ ${\ displaystyle s_ {i} ^ {e}}$ $s_ {i} ^ {e}$ de la care nu are niciun interes să plece dacă toți ceilalți jucători și-au jucat strategia $s_{j}^{e}$ ${\ displaystyle s_ {j} ^ {e}}$ $s_ {j} ^ {e}$ . De fapt, după cum se poate deduce direct din inegalitate, dacă jucătorul i joacă orice altă strategie la dispoziția sa decât $s_{i}^{e}$ ${\ displaystyle s_ {i} ^ {e}}$ $s_ {i} ^ {e}$ , în timp ce toți ceilalți au jucat propria strategie $s_{j}^{e}$ ${\ displaystyle s_ {j} ^ {e}}$ $s_ {j} ^ {e}$ , nu poate decât să-și înrăutățească câștigurile sau, cel mult, să-l lase neschimbat. Prin urmare, se poate deduce că, dacă jucătorii ating un echilibru Nash, nimeni nu își poate îmbunătăți rezultatul schimbându-și doar strategia și, prin urmare, este legat de alegerile altora. Deoarece acest lucru se aplică tuturor jucătorilor, este evident că, dacă există un echilibru Nash și este unic, acesta reprezintă soluția jocului, deoarece niciunul dintre jucători nu are interes să schimbe strategia.

Cea mai importantă contribuție adusă de John Nash la teoria jocurilor este demonstrarea matematică a existenței acestui echilibru. În special, el a arătat că fiecare joc finit are cel puțin un echilibru Nash, posibil în strategii mixte. Prin joc finit se înțelege un joc cu orice număr finit de jucători și strategii, iar prin strategie mixtă pentru un anumit jucător se înțelege o distribuție de probabilitate a strategiilor disponibile acelui jucător.

Teorema

Este $G=(S_{i},U_{i})$ ${\ displaystyle G = (S_ {i}, U_ {i})}$ ${\ displaystyle G = (S_ {i}, U_ {i})}$ un anunț de joc necooperant $Nu.$ ${\ displaystyle N}$ $Nu.$ jucători. Să presupunem că urmează:

$S_{i}\in \mathbb {R} ^{n_{i}}$ ${\ displaystyle S_ {i} \ in \ mathbb {R} ^ {n_ {i}}}$ ${\ displaystyle S_ {i} \ in \ mathbb {R} ^ {n_ {i}}}$ sunt subseturi convexe , compacte și ne-goale ale $\mathbb {R} ^{n_{i}}$ ${\ displaystyle \ mathbb {R} ^ {n_ {i}}}$ ${\ displaystyle \ mathbb {R} ^ {n_ {i}}}$ , pentru fiecare $i=1,\dots ,N$ ${\ displaystyle i = 1, \ dots, N}$ ${\ displaystyle i = 1, \ dots, N}$ ;
$U_{i}:S:=S_{1}\times \dots \times S_{N}\rightarrow \mathbb {R}$ ${\ displaystyle U_ {i}: S: = S_ {1} \ times \ dots \ times S_ {N} \ rightarrow \ mathbb {R}}$ ${\ displaystyle U_ {i}: S: = S_ {1} \ times \ dots \ times S_ {N} \ rightarrow \ mathbb {R}}$ sunt funcții continue, pentru fiecare $i=1,\dots ,N$ ${\ displaystyle i = 1, \ dots, N}$ ${\ displaystyle i = 1, \ dots, N}$ ;
$U_{i}:S_{i}\rightarrow \mathbb {R}$ ${\ displaystyle U_ {i}: S_ {i} \ rightarrow \ mathbb {R}}$ ${\ displaystyle U_ {i}: S_ {i} \ rightarrow \ mathbb {R}}$ , astfel încât $s_{i}\mapsto U_{i}(s_{i},S_{-i})$ ${\ displaystyle s_ {i} \ mapsto U_ {i} (s_ {i}, S _ {- i})}$ ${\ displaystyle s_ {i} \ mapsto U_ {i} (s_ {i}, S _ {- i})}$ , unde este $S_{-i}$ ${\ displaystyle S _ {- i}}$ ${\ displaystyle S _ {- i}}$ indică șirul de lungime $N-1$ ${\ displaystyle N-1}$ $N-1$ unde a fost ștearsă componenta $the$ ${\ displaystyle i}$ $the$ -thth, să fie aproape concav, pentru fiecare $i=1,\dots ,N$ ${\ displaystyle i = 1, \ dots, N}$ ${\ displaystyle i = 1, \ dots, N}$ . Cu alte cuvinte, funcția de utilitate, limitată la o strategie, odată ce celelalte sunt fixate, este aproape concavă.

Apoi, jocul admite cel puțin un echilibru Nash.

Demonstrație

În primul rând, să luăm în considerare cea mai bună funcție de redare a jucătorului $the$ ${\ displaystyle i}$ $the$ -alea $B_{i}:S_{-i}\rightarrow {\mathcal {P}}(S_{i})$ ${\ displaystyle B_ {i}: S _ {- i} \ rightarrow {\ mathcal {P}} (S_ {i})}$ ${\ displaystyle B_ {i}: S _ {- i} \ rightarrow {\ mathcal {P}} (S_ {i})}$ , definit ca $B_{i}(s_{-i})=\{{\bar {s_{i}}}\in S_{i}:U_{i}(s_{-i},{\bar {s_{i}}})\geq U_{i}(s_{-i},s_{i}),\forall s_{i}\in S_{i}\}$ ${\ displaystyle B_ {i} (s _ {- i}) = \ {{\ bar {s_ {i}}} \ în S_ {i}: U_ {i} (s _ {- i}, {\ bar {s_ {i}}}) \ geq U_ {i} (s _ {- i}, s_ {i}), \ forall s_ {i} \ în S_ {i} \}}$ ${\ displaystyle B_ {i} (s _ {- i}) = \ {{\ bar {s_ {i}}} \ în S_ {i}: U_ {i} (s _ {- i}, {\ bar {s_ {i}}}) \ geq U_ {i} (s _ {- i}, s_ {i}), \ forall s_ {i} \ în S_ {i} \}}$ . Rețineți că $B_{i}(s_{-i})={\biggl \{}{\bar {s_{i}}}\in S_{i}:U_{i}(s_{-i},{\bar {s_{i}}})\geq \max _{s_{i}\in S_{i}}\{U_{i}(s_{-i},s_{i})\}{\biggl \}}$ ${\ displaystyle B_ {i} (s _ {- i}) = {\ biggl \ {} {\ bar {s_ {i}}} \ în S_ {i}: U_ {i} (s _ {- i} , {\ bar {s_ {i}}}) \ geq \ max _ {s_ {i} \ în S_ {i}} \ {U_ {i} (s _ {- i}, s_ {i}) \} {\ biggl \}}}$ ${\ displaystyle B_ {i} (s _ {- i}) = {\ biggl \ {} {\ bar {s_ {i}}} \ în S_ {i}: U_ {i} (s _ {- i} , {\ bar {s_ {i}}}) \ geq \ max _ {s_ {i} \ în S_ {i}} \ {U_ {i} (s _ {- i}, s_ {i}) \} {\ biggl \}}}$ . Având în vedere cea mai bună caracteristică de răspuns din joc $B:S\rightarrow {\mathcal {P}}(S_{1})\times \dots \times {\mathcal {P}}(S_{N})\subseteq {\mathcal {P}}(S)$ ${\ displaystyle B: S \ rightarrow {\ mathcal {P}} (S_ {1}) \ times \ dots \ times {\ mathcal {P}} (S_ {N}) \ subseteq {\ mathcal {P}} ( S)}$ ${\ displaystyle B: S \ rightarrow {\ mathcal {P}} (S_ {1}) \ times \ dots \ times {\ mathcal {P}} (S_ {N}) \ subseteq {\ mathcal {P}} ( S)}$ , definit ca $B(s)=(B_{1}(s_{-1},\dots ,B_{N}(s_{-N}))$ ${\ displaystyle B (s) = (B_ {1} (s _ {- 1}, \ dots, B_ {N} (s _ {- N}))}$ ${\ displaystyle B (s) = (B_ {1} (s _ {- 1}, \ dots, B_ {N} (s _ {- N}))}$ , avem asta $s^{e}$ ${\ displaystyle s ^ {e}}$ ${\ displaystyle s ^ {e}}$ este un echilibru Nash dacă și numai dacă $s^{e}$ ${\ displaystyle s ^ {e}}$ ${\ displaystyle s ^ {e}}$ este un punct fix al celei mai bune funcții de răspuns a jocului, adică $s^{e}\in B(s^{e})$ ${\ displaystyle s ^ {e} \ în B (s ^ {e})}$ ${\ displaystyle s ^ {e} \ în B (s ^ {e})}$ .

Deci, dacă verificăm că cea mai bună funcție de răspuns a jocului, $B.$ ${\ displaystyle B}$ $B.$ , satisface ipotezele teoremei lui Kakutani , vom avea teza.

În mod trivial avem asta $S=S_{1}\times \dots \times S_{N}$ ${\ displaystyle S = S_ {1} \ times \ dots \ times S_ {N}}$ ${\ displaystyle S = S_ {1} \ times \ dots \ times S_ {N}}$ este non-gol, convex și compact, ca produs cartezian al subseturilor ne-goale, convexe și compacte ale $\mathbb {R} ^{n}$ ${\ displaystyle \ mathbb {R} ^ {n}}$ $\ mathbb {R} ^ {n}$ .
Fiind $S_{i}$ ${\ displaystyle S_ {i}}$ $Da}$ ed. compactă $U_{i}$ ${\ displaystyle U_ {i}}$ $U_ {i}$ continua, pentru fiecare $i=1,\dots ,N$ ${\ displaystyle i = 1, \ dots, N}$ ${\ displaystyle i = 1, \ dots, N}$ , atunci există cel puțin un maxim în $S_{i}$ ${\ displaystyle S_ {i}}$ $Da}$ , Si deasemenea, $B(s_{1},\dots s_{N})\neq \emptyset$ ${\ displaystyle B (s_ {1}, \ dots s_ {N}) \ neq \ emptyset}$ ${\ displaystyle B (s_ {1}, \ dots s_ {N}) \ neq \ emptyset}$ .
$B_{i}(s_{-i})\subseteq S_{i}$ ${\ displaystyle B_ {i} (s _ {- i}) \ subseteq S_ {i}}$ ${\ displaystyle B_ {i} (s _ {- i}) \ subseteq S_ {i}}$ este compact, pentru fiecare $i=1,\dots ,N$ ${\ displaystyle i = 1, \ dots, N}$ ${\ displaystyle i = 1, \ dots, N}$ . De fapt, fiind subseturi închise ale unui compact, acestea sunt compacte. Să luăm în considerare o succesiune $\{s_{i}^{n}\}_{n\in \mathbb {N} }$ ${\ displaystyle \ {s_ {i} ^ {n} \} _ {n \ in \ mathbb {N}}}$ ${\ displaystyle \ {s_ {i} ^ {n} \} _ {n \ in \ mathbb {N}}}$ , în $B_{i}(s_{-i})$ ${\ displaystyle B_ {i} (s _ {- i})}$ ${\ displaystyle B_ {i} (s _ {- i})}$ , convergând către $s_{i}$ ${\ displaystyle s_ {i}}$ ${\ displaystyle s_ {i}}$ , asa de $s_{i}\in B_{i}(s_{-i})$ ${\ displaystyle s_ {i} \ în B_ {i} (s _ {- i})}$ ${\ displaystyle s_ {i} \ în B_ {i} (s _ {- i})}$ . Prin definiție, avem asta ${\ displaystyle s_ {i} ^ {n} \ în B_ {i} (s _ {- i}) \ if U_ {i} (s_ {i} ^ {n}, s _ {- i}) \ geq U_ {i} ({\ bar {s_ {i}}}, s _ {- i}), \ forall {\ bar {s_ {i}}} \ în S_ {i}.}$ De la faptul că funcțiile utilitare sunt continue și secvența converge la $s_{i}$ ${\ displaystyle s_ {i}}$ ${\ displaystyle s_ {i}}$ , asa de ${\ displaystyle U_ {i} (s_ {i} ^ {n}, s _ {- i}) \ rightarrow U_ {i} (s_ {i}, s _ {- i}), \ {\ text {per }} \ n \ rightarrow + \ infty.}$ Prin urmare, prin teorema permanenței semnului , rezultă că ${\ displaystyle U_ {i} (s_ {i}, s _ {- i}) \ geq U_ {i} ({\ bar {s_ {i}}}, s _ {- i}), \ forall {\ bara {s_ {i}}} \ în S_ {i}.}$ Aceasta înseamnă că $s_{i}\in B_{i}(s_{-i})$ ${\ displaystyle s_ {i} \ în B_ {i} (s _ {- i})}$ ${\ displaystyle s_ {i} \ în B_ {i} (s _ {- i})}$ .
$B_{i}(s_{-i})\subseteq S_{i}$ ${\ displaystyle B_ {i} (s _ {- i}) \ subseteq S_ {i}}$ ${\ displaystyle B_ {i} (s _ {- i}) \ subseteq S_ {i}}$ este convex, pentru fiecare $i=1,\dots ,N$ ${\ displaystyle i = 1, \ dots, N}$ ${\ displaystyle i = 1, \ dots, N}$ . De fapt, să luăm în considerare întregul ${\ displaystyle C ({\ bar {s_ {i}}}): = \ {s_ {i} \ în S_ {i}: U_ {i} (s_ {i}, s _ {- i}) \ geq U_ {i} ({\ bar {s_ {i}}}, s _ {- i}) \}, \ forall {\ bar {s_ {i}}} \ în S_ {i}.}$ Din faptul că funcțiile utilitare sunt aproape concav, adică subgraful lor intersectat cu hiperplane generează mulțimi convexe, rezultă că mulțimea $C({\bar {s_{i}}})$ ${\ displaystyle C ({\ bar {s_ {i}}})}$ ${\ displaystyle C ({\ bar {s_ {i}}})}$ este convex, $\forall {\bar {s_{i}}}\in S_{i}$ ${\ displaystyle \ forall {\ bar {s_ {i}}} \ în S_ {i}}$ ${\ displaystyle \ forall {\ bar {s_ {i}}} \ în S_ {i}}$ . Observăm că $B_{i}(s_{-i})=\bigcap _{i=1}^{N}C({\bar {s_{i}}})$ ${\ displaystyle B_ {i} (s _ {- i}) = \ bigcap _ {i = 1} ^ {N} C ({\ bar {s_ {i}}})}$ ${\ displaystyle B_ {i} (s _ {- i}) = \ bigcap _ {i = 1} ^ {N} C ({\ bar {s_ {i}}})}$ , $\forall {\bar {s_{i}}}\in S_{i}$ ${\ displaystyle \ forall {\ bar {s_ {i}}} \ în S_ {i}}$ ${\ displaystyle \ forall {\ bar {s_ {i}}} \ în S_ {i}}$ . Fiind $C({\bar {s_{i}}})$ ${\ displaystyle C ({\ bar {s_ {i}}})}$ ${\ displaystyle C ({\ bar {s_ {i}}})}$ este convex, $\forall {\bar {s_{i}}}\in S_{i}$ ${\ displaystyle \ forall {\ bar {s_ {i}}} \ în S_ {i}}$ ${\ displaystyle \ forall {\ bar {s_ {i}}} \ în S_ {i}}$ , atunci intersecția lor este încă un set convex, prin urmare $B_{i}(s_{-i})$ ${\ displaystyle B_ {i} (s _ {- i})}$ ${\ displaystyle B_ {i} (s _ {- i})}$ este convex.
Cea mai bună funcție de răspuns a jucătorului $the$ ${\ displaystyle i}$ $the$ -th a închis graficul. Să luăm în considerare secvențele $\{s_{i}^{n}\}_{n\in \mathbb {N} },\{s_{-i}^{n}\}_{n\in \mathbb {N} }$ ${\ displaystyle \ {s_ {i} ^ {n} \} _ {n \ in \ mathbb {N}}, \ {s _ {- i} ^ {n} \} _ {n \ in \ mathbb {N }}}$ ${\ displaystyle \ {s_ {i} ^ {n} \} _ {n \ in \ mathbb {N}}, \ {s _ {- i} ^ {n} \} _ {n \ in \ mathbb {N }}}$ , în $B_{i}(s_{-i})$ ${\ displaystyle B_ {i} (s _ {- i})}$ ${\ displaystyle B_ {i} (s _ {- i})}$ , convergând respectiv către $s_{i}^{0},s_{-i}^{0}$ ${\ displaystyle s_ {i} ^ {0}, s _ {- i} ^ {0}}$ ${\ displaystyle s_ {i} ^ {0}, s _ {- i} ^ {0}}$ , dacă, în plus, $s_{-i}^{n}\in B_{-i,n}$ ${\ displaystyle s _ {- i} ^ {n} \ în B _ {- i, n}}$ ${\ displaystyle s _ {- i} ^ {n} \ în B _ {- i, n}}$ , asa de $s_{-i}^{0}\in B_{-i,0}$ ${\ displaystyle s _ {- i} ^ {0} \ în B _ {- i, 0}}$ ${\ displaystyle s _ {- i} ^ {0} \ în B _ {- i, 0}}$ , care este cea mai bună funcție de răspuns a jucătorului $the$ ${\ displaystyle i}$ $the$ -th a închis graficul. Este absurd să presupunem că $s_{-i}^{0}\not \in B_{-i,0}$ ${\ displaystyle s _ {- i} ^ {0} \ not \ în B _ {- i, 0}}$ ${\ displaystyle s _ {- i} ^ {0} \ not \ în B _ {- i, 0}}$ . Apoi va exista un anumit ${\bar {s}}_{-i}$ ${\ displaystyle {\ bar {s}} _ {- i}}$ ${\ displaystyle {\ bar {s}} _ {- i}}$ astfel încât $U_{i}(s_{i}^{0},s_{-i}^{0})<U_{i}(s_{i}^{0},{\bar {s}}_{-i})$ ${\ displaystyle U_ {i} (s_ {i} ^ {0}, s _ {- i} ^ {0}) <U_ {i} (s_ {i} ^ {0}, {\ bar {s}} _ {-the})}$ ${\ displaystyle U_ {i} (s_ {i} ^ {0}, s _ {- i} ^ {0}) <U_ {i} (s_ {i} ^ {0}, {\ bar {s}} _ {-the})}$ . Este $\epsilon :=U_{i}(s_{i}^{0},{\bar {s}}_{-i})-U_{i}(s_{i}^{0},s_{-i}^{0})>0$ ${\ displaystyle \ epsilon: = U_ {i} (s_ {i} ^ {0}, {\ bar {s}} _ {- i}) - U_ {i} (s_ {i} ^ {0}, s_ {-i} ^ {0})> 0}$ ${\ displaystyle \ epsilon: = U_ {i} (s_ {i} ^ {0}, {\ bar {s}} _ {- i}) - U_ {i} (s_ {i} ^ {0}, s_ {-i} ^ {0})> 0}$ . În mod echivalent avem asta ${\ displaystyle \ epsilon = {\ big (} U_ {i} (s_ {i} ^ {0}, {\ bar {s}} _ {- i}) - U_ {i} (s_ {i} ^ { n}, {\ bar {s}} _ {- i}) {\ big)} + {\ big (} U_ {i} (s_ {i} ^ {n}, {\ bar {s}} _ { -i}) - U_ {i} (s_ {i} ^ {n}, {\ bar {s}} _ {- i} ^ {n}) {\ big)} + {\ big (} U_ {i } (s_ {i} ^ {n}, {\ bar {s}} _ {- i} ^ {n}) - U_ {i} (s_ {i} ^ {0}, {\ bar {s}} _ {- i} ^ {0}) {\ big)}.}$ Din faptul că secvențele sunt convergente și funcțiile de utilitate sunt continue și, în plus, $s_{-i}^{n}\in B_{-i,n}$ ${\ displaystyle s _ {- i} ^ {n} \ în B _ {- i, n}}$ ${\ displaystyle s _ {- i} ^ {n} \ în B _ {- i, n}}$ , rezultă că ${\ displaystyle U_ {i} (s_ {i} ^ {n}, {\ bar {s}} _ {- i}) \ rightarrow U_ {i} (s_ {i} ^ {0}, {\ bar { s}} _ {- i}), \ U_ {i} (s_ {i} ^ {n}, {\ bar {s}} _ {- i} ^ {n}) \ rightarrow U_ {i} (s_ {i} ^ {0}, {\ bar {s}} _ {- i} ^ {0}), \ {\ text {ed}} \ U_ {i} (s_ {i} ^ {n}, s_ {-i} ^ {n}) \ geq U_ {i} (s_ {i} ^ {n}, {\ bar {s}} _ {- i}).}$ Pentru $n\rightarrow +\infty$ ${\ displaystyle n \ rightarrow + \ infty}$ ${\ displaystyle n \ rightarrow + \ infty}$ , avem asta $\epsilon \leq {\frac {1}{3}}\epsilon +0+{\frac {1}{3}}\epsilon ={\frac {2}{3}}\epsilon$ ${\ displaystyle \ epsilon \ leq {\ frac {1} {3}} \ epsilon +0 + {\ frac {1} {3}} \ epsilon = {\ frac {2} {3}} \ epsilon}$ ${\ displaystyle \ epsilon \ leq {\ frac {1} {3}} \ epsilon +0 + {\ frac {1} {3}} \ epsilon = {\ frac {2} {3}} \ epsilon}$ . Absurd.

Echilibrul Nash și optimul Pareto

În concluzie, este potrivit să facem o scurtă reflecție asupra semnificației profunde a conceptului de echilibru Nash . De fapt, am văzut cum reprezintă o situație în care niciun agent rațional nu are interes să schimbe strategia și cum este rezultatul alegerii, de către toți jucătorii, a strategiei lor dominante: echilibrul Nash reprezintă deci situația în pe care grupul îl găsește dacă fiecare membru al grupului face ceea ce este mai bine pentru el , adică își propune să își maximizeze propriul profit, indiferent de alegerile oponenților. Cu toate acestea, echilibrul Nash nu este neapărat cea mai bună soluție pentru toată lumea . De fapt, dacă este adevărat că într-un echilibru Nash singurul jucător nu își poate crește câștigurile modificându-și doar strategia, nu este deloc sigur că un grup de jucători, sau cel puțin toți, nu își pot crește câștigurile prin mișcare departe.în comun prin echilibru. De fapt, se știe că echilibrul Nash poate să nu fie un optim Pareto (sau Pareto optim ) și, prin urmare, pot exista și alte combinații de strategii care să ducă la îmbunătățirea câștigului unora fără a reduce câștigul nimănui, sau chiar, așa cum se întâmplă în cazul dilemei prizonierului , de a crește veniturile tuturor. În mod similar, cel mai bun rezultat pentru toată lumea poate să nu fie un echilibru. Prin urmare, presupunem că într-un joc există un echilibru Nash și există, de asemenea, o combinație optimă de strategii, pe care le vom indica cu vârful o , astfel încât

U_{i}\left(s_{1}^{o},s_{2}^{o},...,s_{i}^{o},...,s_{N}^{o}\right)>U_{i}\left(s_{1}^{e},s_{2}^{e},...,s_{i}^{e},...,s_{N}^{e}\right)

{\ displaystyle U_ {i} \ left (s_ {1} ^ {o}, s_ {2} ^ {o}, ..., s_ {i} ^ {o}, ..., s_ {N} ^ {o} \ dreapta)> U_ {i} \ left (s_ {1} ^ {e}, s_ {2} ^ {e}, ..., s_ {i} ^ {e}, ..., s_ {N} ^ {e} \ dreapta)}

U_ {i} \ left (s_ {1} ^ {o}, s_ {2} ^ {o}, ..., s_ {i} ^ {o}, ..., s_ {N} ^ {o} \ right)> U_ {i} \ left (s_ {1} ^ {e}, s_ {2} ^ {e}, ..., s_ {i} ^ {e}, ..., s_ {N} ^ {e} \ dreapta)

pentru fiecare i , dar că această combinație nu este un echilibru, așa cum se întâmplă în dilema prizonierului sau, cu alte cuvinte, că $s_{i}^{o}$ ${\ displaystyle s_ {i} ^ {o}}$ $s_ {i} ^ {o}$ nu este o strategie dominantă. În acest caz, fiecare agent individual va avea cel puțin o strategie disponibilă $s_{i}^{e}$ ${\ displaystyle s_ {i} ^ {e}}$ $s_ {i} ^ {e}$ diferit de $s_{i}^{o}$ ${\ displaystyle s_ {i} ^ {o}}$ $s_ {i} ^ {o}$ ceea ce îi permite să își îmbunătățească și mai mult profitul, modificându-și singura strategia, adică există câte una pentru fiecare agent $s_{i}^{e}$ ${\ displaystyle s_ {i} ^ {e}}$ $s_ {i} ^ {e}$ astfel încât

U_{i}\left(s_{1}^{o},s_{2}^{o},...,s_{i}^{e},...,s_{N}^{o}\right)>U_{i}\left(s_{1}^{o},s_{2}^{o},...,s_{i}^{o},...,s_{N}^{o}\right)

{\ displaystyle U_ {i} \ left (s_ {1} ^ {o}, s_ {2} ^ {o}, ..., s_ {i} ^ {e}, ..., s_ {N} ^ {o} \ dreapta)> U_ {i} \ left (s_ {1} ^ {o}, s_ {2} ^ {o}, ..., s_ {i} ^ {o}, ..., s_ {N} ^ {o} \ dreapta)}

U_ {i} \ left (s_ {1} ^ {o}, s_ {2} ^ {o}, ..., s_ {i} ^ {e}, ..., s_ {N} ^ {o} \ right)> U_ {i} \ left (s_ {1} ^ {o}, s_ {2} ^ {o}, ..., s_ {i} ^ {o}, ..., s_ {N} ^ {o} \ dreapta)

.

În consecință, pentru axioma raționalității, el va fi condus să prefere o altă strategie decât $s_{i}^{o}$ ${\ displaystyle s_ {i} ^ {o}}$ $s_ {i} ^ {o}$ . Mai mult, creșterea câștigului în raport cu echilibrul Nash rezultată din alegerea strategiei $s_{i}^{o}$ ${\ displaystyle s_ {i} ^ {o}}$ $s_ {i} ^ {o}$ , depinde, ca întotdeauna, de faptul că toată lumea a ales această strategie, deoarece, în general, câștigul lui i depinde de alegerile tuturor jucătorilor; a nu fi $s_{i}^{o}$ ${\ displaystyle s_ {i} ^ {o}}$ $s_ {i} ^ {o}$ o strategie dominantă, este posibil ca chiar și unul dintre agenți să nu joace $s_{i}^{o}$ ${\ displaystyle s_ {i} ^ {o}}$ $s_ {i} ^ {o}$ , ceilalți suferă o reducere a câștigurilor lor comparativ cu ceea ce ar fi obținut jucând o strategie optimă. În concluzie, fiecare jucător va găsi în continuare preferabil să nu riște și să joace propria strategie dominantă, iar soluția jocului va rămâne în continuare echilibrul Nash, chiar dacă nu garantează câștigul maxim posibil.

Cu toate acestea, nu ar trebui să ne gândim că nu este posibil să se ajungă la o situație în care toată lumea obține cel mai bun rezultat posibil, dacă nu este un echilibru (în unele cazuri $s_{i}^{o}$ ${\ displaystyle s_ {i} ^ {o}}$ $s_ {i} ^ {o}$ coincide cu $s_{i}^{e}$ ${\ displaystyle s_ {i} ^ {e}}$ $s_ {i} ^ {e}$ și, prin urmare, problema nu apare): acest lucru este posibil, dar cu condiția stabilirii unei cooperări între jucători, adică toată lumea acționează nu cu scopul de a obține cel mai bun rezultat pentru ei înșiși, ci de a obține cel mai bun rezultat pentru grupul și, prin urmare, indirect, obținând un rezultat mai bun și pentru el (acest concept este, de asemenea, bine exemplificat în dilema prizonierului ). Cu toate acestea, întrucât raționalitatea colectivă contrastează adesea cu raționalitatea individuală, în majoritatea cazurilor este necesară o convenție obligatorie între jucători (și, prin urmare, o instituție care monitorizează acest acord) și o sancțiune împotriva celor care nu o respectă, reducând astfel profitul. individual dacă se îndepărtează de combinația de strategii care garantează tuturor cel mai bun rezultat, astfel încât nimănui să nu i se pară de preferat să îl defecte.

Exemplu: „dilema prizonierului”

Același subiect în detaliu: Dilema prizonierului .

Dilema prizonierului oferă un punct de plecare valid pentru a compara cele două concepte de echilibru Nash și Pareto optim și pentru a înțelege aplicarea lor în economie . Luând în considerare ceea ce este ilustrat în definiția matematică a echilibrului Nash, vedem aplicarea lor în cazul dilemei prizonierului . Posibilele alegeri pentru doi prizonieri în celule diferite care nu comunică sunt să vorbească (acuzându-l pe celălalt) sau să nu vorbească.

Dacă ambii nu vorbește, vor avea o pedeapsă ușoară (1 an);
Dacă vorbește ambii, acuzându-se reciproc, vor avea o pedeapsă grea (6 ani);
Dacă fac alegeri diferite, vorbitorul va avea libertate (0 ani), iar celălalt va avea o pedeapsă ceva mai grea (7 ani) decât dacă amândoi ar mărturisi.

Dacă amândoi cunosc aceste reguli și nu sunt de acord, alegerea care corespunde echilibrului Nash este să vorbească, pentru ambele. Din acest exemplu vedem că teoria în cazuri reale nu este întotdeauna cea mai bună soluție (sau uneori nu este suficient de realistă).

Ambii jucători au la dispoziție aceleași strategii (două) și aceleași recompense (2x2) care sunt (vom indica din motive de scurtă durată mărturisiți cu c și nu mărturisiți cu n și anii de închisoare cu un semn minus din moment ce ele reprezintă pierderi și, prin urmare, câștiguri negative):

Strategii: $S_{i}=\left(c,n\right)$ ${\ displaystyle S_ {i} = \ left (c, n \ right)}$ $S_ {i} = \ left (c, n \ right)$
Achita:

u_{i}\left(c,c\right)=-6

{\ displaystyle u_ {i} \ left (c, c \ right) = - 6}

u_ {i} \ left (c, c \ right) = - 6

u_{i}\left(c,n\right)=0

{\ displaystyle u_ {i} \ left (c, n \ right) = 0}

u_ {i} \ left (c, n \ right) = 0

u_{i}\left(n,c\right)=-7

{\ displaystyle u_ {i} \ left (n, c \ right) = - 7}

u_ {i} \ left (n, c \ right) = - 7

u_{i}\left(n,n\right)=-1

{\ displaystyle u_ {i} \ left (n, n \ right) = - 1}

u_ {i} \ left (n, n \ right) = - 1

Se deduce imediat că, pentru ambele, strategia dominantă este mărturisită , de fapt

u_{i}\left(c,c\right)\geq u_{i}\left(n,c\right)

{\ displaystyle u_ {i} \ left (c, c \ right) \ geq u_ {i} \ left (n, c \ right)}

u_ {i} \ left (c, c \ right) \ geq u_ {i} \ left (n, c \ right)

Și

u_{i}\left(c,n\right)\geq u_{i}\left(n,n\right)

{\ displaystyle u_ {i} \ left (c, n \ right) \ geq u_ {i} \ left (n, n \ right)}

u_ {i} \ left (c, n \ right) \ geq u_ {i} \ left (n, n \ right)

deci, indiferent de alegerea oponentului, alegerea mărturisirii garantează întotdeauna un câștig mai mare decât alegerea non-mărturisirii . Este imediat să recunoaștem cum mărturisește combinația de strategii dominante - mărturisește că satisface inegalitatea care definește echilibrul Nash, de fapt pentru ambii jucători

u_{i}\left(c,c\right)\geq u_{i}\left(n,c\right)

{\ displaystyle u_ {i} \ left (c, c \ right) \ geq u_ {i} \ left (n, c \ right)}

u_ {i} \ left (c, c \ right) \ geq u_ {i} \ left (n, c \ right)

(pentru al doilea jucător inegalitatea este satisfăcută prin inversarea ordinii strategiilor). Practic, presupunând că al doilea jucător mărturisește, primul trebuie să aleagă și el mărturisește și nu își poate crește profitul schimbându-și doar strategia: plățile sale în cazul în care nu mărturisește - mărturisirea este mai mică decât ceea ce ar obține jucând echilibrul . mărturisire - mărturisirea este, de asemenea, singurul echilibru al jocului, de fapt, nicio altă combinație de strategii nu satisface inegalitatea.

Soluția jocului este, prin urmare, că amândoi mărturisesc, fiecare primind 6 ani de închisoare.

Cu toate acestea, cel mai interesant aspect al dilemei prizonierului este următorul: toate combinațiile de strategii, cu excepția echilibrului Nash, sunt Pareto excelente . De fapt, luând oricare dintre aceste combinații, nu este posibil să se găsească alta care să implice pentru cel puțin unul dintre cei doi jucători o reducere a anilor de închisoare fără a crește cei ai celuilalt. Cu toate acestea, acest concept nu se aplică echilibrului mărturisește - mărturisește : combinația nu mărturisește - nu mărturisește duce la o reducere a anilor de închisoare pentru ambii jucători (câte un an în loc de 6) și din moment ce

u_{i}\left(n,n\right)>u_{i}\left(c,c\right)

{\ displaystyle u_ {i} \ left (n, n \ right)> u_ {i} \ left (c, c \ right)}

u_ {i} \ left (n, n \ right)> u_ {i} \ left (c, c \ right)

pentru toate i , ( c , c ) nu este o soluție Pareto-optimă.

Optimitatea Pareto este un concept foarte important în economie: un mare Pareto este definit ca o situație în care, indiferent de alocarea specifică a resurselor, nu este posibil să se găsească altul care să ducă la creșterea bogăției unora fără a scădea bogăția la alții. Motivul pentru importanța optimului lui Pareto este intuitiv: dacă există o soluție care implică o creștere a veniturilor cuiva fără ca nimeni să sufere pierderi, înseamnă că există resurse care nu au fost alocate sau care au fost alocate greșit; prin urmare, este mai bine să schimbați alocarea. În cazul excelentului Pareto, de fapt, îmbogățirea ulterioară a cuiva trece în mod necesar prin sărăcirea altcuiva. Dilema prizonierului evidențiază un concept cheie al economiei: optimul lui Pareto este rațional din punct de vedere colectiv, dar deloc rațional din punct de vedere individual ; în esență, dacă N agenții unui joc (și, prin urmare, prin extensie, ai unei piețe) acționează în funcție de raționalitatea individuală, adică cu singurul scop de a-și maximiza profitul personal, nu ating neapărat un optim Pareto. În unele cazuri ajung și în altele nu; în acest din urmă caz acțiunile lor implică o dispersie sau o alocare greșită a resurselor.

Comparația dintre echilibrul Nash și optimul Pareto face să ne îndoim de generalitatea a ceea ce susține Adam Smith . De fapt, el credea că dacă fiecare membru al unui grup își urmărește propriul interes personal și există condiții de concurență perfectă, echilibrul rezultat este unul în care fiecare acțiune individuală crește bogăția generală a grupului. Pe scurt, un Pareto excelent. Astăzi, totuși, știm că, dacă fiecare membru al grupului face ceea ce este mai bun pentru el însuși, rezultatul este, în general, un echilibru Nash, dar nu neapărat un optim Pareto : este deci posibil ca, dacă fiecare agent să facă doar sinele -interes, duce la o alocare ineficientă a resurselor. În cazul dilemei prizonierului, acest lucru este evident: valoarea minimă posibilă a anilor de închisoare este 0 pentru individ și 2 pentru grup, dar dacă ambii își aleg strategia dominantă, primesc câte 6.

Echilibrul duopolului Cournot și al economiei

Această noțiune de echilibru constituie o generalizare a echilibrului de duopol pe care Antoine Augustine Cournot , matematician și economist, l-a descris încă din 1838 .

Notă

^ John Nash geniu și nebunie . Interviu de Piergiorgio Odifreddi, Repubblica. Exprimat. Cultură. 11 martie 2008
^ Rețineți că această conexiune era oricum prezentă aici oricum: John von Neumann: Über ein ökonomisches Gleichungssystem und eine Verallgemeinerung der Brouwerschen Fixpunktsatzes , Ergebnisse eines Math. Kolloquiums (editor: Karl Menger ), 8 , 73-83, 1937. Traducere în limba engleză: Un model de echilibru economic general , Review of Economic Studies, 13 , 1-9, 1945-1946.

Bibliografie

Nash, John F. Jr. [1950]: Equilibrium Points in n-Person Games , Proc. Nat. Acad. Sci. SUA, 36, 48-49.
Nash, John F. Jr. [1951]: Jocuri necooperative , Ann. de Math., 54, 286-295.

Elemente conexe

linkuri externe

Nash, Berge, Kakutani demonstrație a teoremei existenței echilibrului Nash și preliminarii (fișier pdf, 18 pagini)

Controllo di autorità	GND ( DE ) 4171190-7

Portale Matematica : accedi alle voci di Wikipedia che trattano di matematica

[1] John Nash geniu și nebunie . Interviu de Piergiorgio Odifreddi, Repubblica. Exprimat. Cultură. 11 martie 2008

[2] Rețineți că această conexiune era oricum prezentă aici oricum: John von Neumann: Über ein ökonomisches Gleichungssystem und eine Verallgemeinerung der Brouwerschen Fixpunktsatzes , Ergebnisse eines Math. Kolloquiums (editor: Karl Menger ), 8 , 73-83, 1937. Traducere în limba engleză: Un model de echilibru economic general , Review of Economic Studies, 13 , 1-9, 1945-1946.

[1]

[2]

V ·D · M Teoria jocului
Definiții	În formă normală joc · joc în formă extinsă · Joc cooperativ · Set de informații · Preferință · Recompensă · Credință · Cel mai bun răspuns · Joc corect
Soluții de echilibru	Nash Equilibrium · Bayesian Equilibrium · Balance perfect Bayesian (EBP) · Great Pareto
Strategii	Strategiile dominante · strategie pură · strategie mixtă · strategie de declanșare · Complotarea tacită · inducție înapoi · Dinte pentru dinte
Cursuri de joc	Full-Informații de joc · statice joc · dinamic sau joc secventiala · joc repetată · Signaling joc · joc cu sumă zero
Giochi	Dilemma del prigioniero · Dilemma del viaggiatore · Gioco del pollo · Dilemma del volontario · Battaglia dei sessi · Caccia al cervo · Matching pennies · Gioco dell'ultimatum · Morra cinese · Oligopolio di Cournot · Duopolio di Stackelberg · Modello di Bertrand · Gioco del centipede
Teoremi	Teorema minimax · Teorema dell'impossibilità di Arrow