Echilibru Nash

De la Wikipedia, enciclopedia liberă

Echilibrul Nash este un termen central al teoriei matematice a jocului. 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.

Cuprins

1 Strategii pure
2 Strategii mixte
3 Existenţa echilibrului Nash
4 Un algoritm simplu de identificare a echilibrelor Nash
5 Exemplu
6 A se vedea şi
7 Bibliografie

[modifică] 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 înbunătăţi, atunci când o singură parte deviază.

[modifică] 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 $Σ i$ . Este $Σ 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$ .

[modifică] Existenţa echilibrului Nash

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

Funcţiile $H_i(\sigma_1,\ldots,\sigma_n)$ sunt continue.
Cantităţile strategiilor $\Sigma_1,\ldots,\Sigma_n$ sunt convexe şi compacte.

Adesea jocurile sunt astfel construite, încât $Σ i$ este mărginit,însă cantităţile mărginite pot totuşi să nu fie convexe. În plus, cantitatea strategiilor mixte $S i$ asupra $Σ 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.

[modifică] 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:

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.
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.

[modifică] 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ă.

[modifică] A se vedea şi

[modifică] 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.

Adus de la "http://ro.wikipedia.org../../../e/c/h/Echilibru_Nash_a230.html"

Categorie: Teoria jocurilor