Echilibru Nash

În teoria jocurilor se definește echilibrul lui Nash, un profil de strategie (unul pentru fiecare jucător) în raport cu care interesul niciunui jucător să nu 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 lui Nash poate fi văzut ca o măsură semnificativă în comparație cu cazul „ jocului cu sumă zero ” studiat anterior de John von Neumann . Ideea echilibrului este, de asemenea, o schimbare conceptuală semnificativă de la abordarea lui von Neumann, care a recurs la ideea de minimax .

Echilibrul Nash

Să vedem mai detaliat ce este exact un echilibru 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, la numărul de N, notat 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)

strategii pe care jucătorul i-th le are la dispoziție, 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 către jucător;

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 se asociază jucătorului câștigul ( de asemenea , numit pay-off) de la fiecare combinație de strategii (câștig de un jucător , în general , aceasta depinde nu numai de strategia sa , ci și pe strategiile alese de adversarii lor).

Un echilibru Nash pentru un anumit joc este o combinație de strategii (notate cu supercriptul )

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 toți i și pentru fiecare strategie $s_{i}$ ${\ displaystyle s_ {i}}$ $da$ ales de i-lea player.

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 inegalitatea, în cazul în care jucătorul joacă orice strategie diferită la dispoziția sa de $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 pare că, dacă jucătorii ating un echilibru Nash, nimeni nu își poate îmbunătăți rezultatele schimbându-și doar propria strategie și, prin urmare, este legat de alegerile altora. Deoarece acest lucru se aplică tuturor jucătorilor, este clar că, dacă există un echilibru Nash și este unic, este soluția jocului, deoarece niciunul dintre jucători nu are interes în strategia de schimbare.

Cea mai importantă contribuție a lui John Nash la teoria jocurilor este demonstrarea existenței acestui echilibru matematic. În special, el a arătat că fiecare joc finit are cel puțin un echilibru Nash, posibil în strategii mixte. A termina jocul înseamnă un joc cu orice număr, dar jucători și strategii terminate, iar strategia mixtă pentru un anumit jucător este definită ca o distribuție a probabilității pe strategiile disponibile jucătorului de mai sus.

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 $\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.$ Satisfac 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.}$ Deci, pentru 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. Am văzut de fapt că reprezintă o situație în care niciun agent rațional nu are interes în strategia de schimbare și cum este fructul alegerii, de către toți jucătorii, a strategiei sale dominante: „echilibrul Nash este astfel situația în care grupul vine în vizită, fiecare membru al grupului face ceea ce este mai bun pentru ei înșiși, care își propune să își maximizeze propriul profit, indiferent de alegerile oponenților. Cu toate acestea, se spune că echilibrul Nash este 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. Se știe că echilibrul Nash nu poate fi un Pareto excelent (sau optimitatea Pareto ), și atunci pot exista și alte combinații de strategii care conduc 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 , pentru a crește câștigul tuturor. În mod similar, cel mai bun rezultat pentru toată lumea poate să nu fie un echilibru. Să presupunem că, într-un joc, există un echilibru Nash și că există, de asemenea, o combinație de strategii optime, care vor fi notate prin supercript sau, 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 astfel de 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 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 dacă unul dintre agenți alege 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 astfel problema nu apare): acest lucru este posibil cu condiția ca pentru stabilirea cooperării între jucători, adică toți acționează nu cu scopul de a obține cel mai bun rezultat pentru el însuși, ci de a obține cel mai bun rezultat pentru grup , și astfel, indirect, obținând un rezultat mai bun și în sine (deși acest concept este 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 bun punct de plecare pentru a compara cele două concepte de echilibru dintre Nash și Pareto optim și pentru a înțelege aplicarea sa în economie . Luând în considerare ceea ce se arată în definiția matematicii de echilibru 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 vorbesc, 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ă ar mărturisi amândoi.

Dacă știți amândoi aceste reguli și nu luați acorduri, alegerea care corespunde echilibrului lui Nash este de a vorbi cu amândoi. 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

Rezultă imediat că, pentru amândoi, strategia dominantă este mărturisește, 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, alege mărturisește garantează întotdeauna un câștig mai mare în comparație cu a nu alege mărturisește. Este imediat recunoscut pe măsură ce combinația de strategii dominante mărturisește - 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ărturisește - recunoaște că este și 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, aspectul mai interesant decât dilema prizonierului este după cum urmează: toate combinațiile de strategii, 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. Acest concept nu se aplică soldului mărturisește - recunoaște el: 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 în continuare a cuiva trece în mod necesar prin sărăcirea altcuiva. Dilema prizonierului evidențiază un concept cheie al economiei: optimul Pareto este rațional din punct de vedere colectiv, dar deloc 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 ajung neapărat la 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 lui Nash și optimitatea lui Pareto se îndoiește de generalitatea afirmațiilor făcute de 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 duopolului de echilibru pe care Antoine Augustine Cournot , matematician și economist, l-a descris deja în 1838 .

Notă

^ Geniul și nebunia lui John Nash . Interviu de Piergiorgio Odifreddi, Repubblica. Exprimat. Cultură. 11 martie 2008
^ Rețineți că această conexiune era totuși deja prezentă aici: John von Neumann: Über ein ökonomisches Gleichungssystem und eine der Verallgemeinerung 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ția teoremei existenței echilibrului lui Nash și preliminară (fișier pdf, 18 pagini.)

Controllo di autorità	GND ( DE ) 4171190-7

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

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

[2] Rețineți că această conexiune era totuși deja prezentă aici: John von Neumann: Über ein ökonomisches Gleichungssystem und eine der Verallgemeinerung 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	Formularul normal de redare · Formă de redare · cooperativ · set Informații · Preferința · payoff · Credința · Cel mai bun răspuns · Fair - play
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