Echilibru Nash

Echilibrul Nash este un termen central al teoriei matematice a jocurilor. Prin jocuri este descrisă o stare a echilibrului strategic, plecând de la care un jucător nu are nici un avantaj, schimbând de unul singur strategia. Definiția si demonstrarea existenței echilibrului Nash au fost făcute in anul 1950 în disertația publicată de matematicianul John Forbes Nash Jr.

Strategii pure

Printr-un echilibru Nash într-o strategie pură întelegem un profil strategic $\sigma ^{*}=(\sigma _{1}^{*},...,\sigma _{n}^{*})\in \Sigma$, la care strategia fiecărui jucător $i$ este răspunsul cel mai bun la strategiile alese de ceilalți jucători.

Cu condiția că toți ceilalți jucători rămân strict fideli strategiei alese, pentru jucătorul $i$ nu există $\sigma _{i}\neq \sigma _{i}^{*}$, astfel încât jucătorului i să i se promită o recompensă mai mare: $u_{i}(\sigma _{1}^{*},\ldots ,\sigma _{i}^{*},\ldots ,\sigma _{n}^{*})\geq u_{i}(\sigma _{1}^{*},\ldots ,\sigma _{i},\ldots ,\sigma _{n}^{*})\ \forall \sigma _{i}\in \Sigma _{i}$.

Se mai spune că recompensa jucătorului nu se poate îmbunătăți, atunci când o singură parte deviază.

Strategii mixte

În anumite cazuri se permite jucătorilor să nu rămână fideli unei anumite strategii, ci unei distribuții probabilistice cu care σi se extrage aleator din $\Sigma _{i}$. Este $\Sigma _{i}$ finit sau cel puțin se poate număra, atunci distribuția probabilistică poate fi descrisă printr-un vector, unde $s_{i,j}$ este probabilitatea ca strategia $\sigma _{i,j}\in \Sigma _{i}$să fie aleasă.

Dacă strategia mixtă$s=(s_{1}^{*},...,s_{n}^{*})$ este un echilibru Nash, atunci e valabil: $u_{i}(s_{1}^{*},\ldots ,s_{i}^{*},\ldots ,s_{n}^{*})\geq u_{i}(s_{1}^{*},\ldots ,s_{i},\ldots ,s_{n}^{*})\ \forall s_{i}\in S_{i}$.

Existența echilibrului Nash

Se poate arăta, că în anumite condiții există cel puțin un echilibru Nash:

1. Funcțiile $H_{i}(\sigma _{1},\ldots ,\sigma _{n})$ sunt continue.
2. Cantitățile strategiilor $\Sigma _{1},\ldots ,\Sigma _{n}$ sunt convexe și compacte.

Adesea jocurile sunt astfel construite, încât $\Sigma _{i}$ este mărginit,însă cantitățile mărginite pot totuși să nu fie convexe. În plus, cantitatea strategiilor mixte $S_{i}$ asupra $\Sigma _{i}$ este compactă și convexă. În timp ce existența unui echilibru Nash în strategiile pure nu poate fi garantat, într-un joc general există cel puțin un echilibru Nash în strategiile mixte.

Un algoritm simplu de identificare a echilibrelor Nash

Dacă există un joc în formă strategică, echilibrele Nash în strategiile pure sunt exprimate prin următorul algoritm:

1. Se optimizează alegerea jucătorului i=1,...,n pentru orice strategii fixe ale tuturor celorlalți jucători: se marchează recompensele pe care jucătorul $i$ le poate atinge în aceste condiții. Aceasta se repetă pentru toate combinațiile de strategii posibile ale altor jucători.
2. Se implementează 1. pentru toți jucătorii.

Atunci, echilibre Nash sunt exact combinațiile de strategii, pentru care toate recompensele sunt marcate.

Acest procedeu este potrivit doar pentru un număr redus de jucători și de strategii.

Exemplu

Fie următorul joc, dat în formă normală:

		Jucătorul 2
		stânga	mijloc	dreapta
Jucătorul 1	sus	4 , 2	1 , 1	2 , 0
	mijloc	2, 3	1 , 1	1, 4
	dedesubt	3, 0	0, 2	1, 3

Atunci, algoritmul funcționează după cum urmează:

• i = 1:
  • se dă: jucătorul 2 joacă dreapta: Pentru jucătorul 1 sus este optim – 2 este marcat
  • se dă: jucătorul 2 joacă mijloc: sus și mijloc este optim – cei doi 1 sunt marcați
  • se dă: jucătorul 2 joacă stânga: sus este optim – 4 este marcat
• i = 2:
  • se dă: jucătorul 1 joacă sus: Pentru jucătorul 2 stânga este optim – 2 este marcat
  • se dă: jucătorul 1 joacă mijloc: dreapta este optim – 4 este marcat
  • se dă: jucătorul 1 joacă dedesubt: dreapta este optim – 3 este marcat

Un echilibru Nash clar este deci strategia care conduce la recompensa 4, 2.

În cazul în care trebuie verificat dacă un tuple de strategii mixte este echilibru Nash, algoritmul de mai sus funcționează (trebuie variate, la pasul 1, doar strategiile pure ale celorlalți jucători, deoarece distribuțiile probabilistice arbitrare asupra acestora nu pot să conducă la recompense mai mari).

Prin această metodă se pot identifica și strategiile strict dominante: acele strategii pentru care nu au fost marcată vreo recompensă.

Vezi și

• Jocul lașului
• Dilema prizonierului
• Bătălia sexelor
• Problema lui Nash

Bibliografie

• Fudenberg, Drew and Jean Tirole (1991) Game Theory MIT Press.
• Mehlmann, A. The Game's Afoot! Game Theory in Myth and Paradox, American Mathematical Society (2000).
• Morgenstern, Oskar and John von Neumann (1947) The Theory of Games and Economic Behavior Princeton University Press
• Nash, John (1950) "Equilibrium points in n-person games" Proceedings of the National Academy of the USA 36(1):48-49.