Gra w postaci normalnej

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Gra w postaci normalnej - typ gry w której gracze jednocześnie i niezależne od siebie decydują o swoich strategiach nie znając decyzji przeciwników. Do opisania takiej gry potrzebna jest znajomość możliwych akcji graczy (zwanych także zagraniami, strategiami czystymi), oraz wysokości wypłat przy zastosowaniu przez graczy danych akcji.

Oznaczenia:

 N = \{1, 2, ..., n\} \; - zbiór graczy,

 A_i \; - zbiór możliwych zagrań gracza i-tego, i \in N ,

 A = \prod\limits_{i=1}^n A_i	,

 u_i : A \rightarrow \mathbb{R} - funkcja wypłat i-tego gracza.

Elementy zbioru A to tzw. profile strategii czystych. Mamy a = (a_1, ..., a_n) \in A, gdzie a_i \; oznacza pewną strategię czystą i-tego gracza. Gdy dla każdego i \in N ,|A_i| < \infty, to mówimy że gra jest skończona.

Definicja[edytuj | edytuj kod]

Grą w postaci normalnej nazywamy trójkę <N, A, (u_i)_{i \in N} >.

Zauważmy, że przy tej definicji nie podajemy ile możliwych zagrań ma każdy z graczy. Może to być nieskończenie (nawet nieprzeliczalnie) wiele akcji.

Strategia mieszana[edytuj | edytuj kod]

Strategią mieszaną i-tego gracza nazywamy dowolny rozkład prawdopodobieństwa na zbiorze  A_i.

Oznaczmy przez x_i(a_j) prawdopodobieństwo zagrania przez i-tego gracza strategii czystej a_j.

Przypadek gry skończonej[edytuj | edytuj kod]

Gdy gra jest skończona to strategia mieszana tworzy wektor w  \mathbb{R}^{|A_i|} . Kolejne współrzędne tego wektora to prawdopodobieństwa wyboru kolejnych zagrań. Strategia czysta to szczególny przypadek strategii mieszanej. Załóżmy, że zbiór A_i jest ponumerowany od 1 do k. Wtedy j-ta strategia czysta (j-te zagrane) to wersor  1_j^i = (0, ..., 0, 1, 0, ..., 0) (1 na j-tym miejscu). W dalszej części artykułu będziemy stosować to oznaczene. Jest to rozkład na A_i, który z prawdopodobieństwem 1 przypisuje j-te zagranie.

Zauważmy, że w grach skończonych każdą strategię mieszaną, można przedstawić w postaci kombinacji wypukłej strategii czystych. Weźmy dowolnego gracza i, zbiór jego strategii czystych (zagrań) A_i = \{ 1_1^i, ..., 1_k^i \} oraz pewną strategię mieszaną tego gracza: x_i. Wtedy x_i = \sum_{j=1}^k x_{i}(1_j^i)1_j^i.

Profil gry[edytuj | edytuj kod]

Jeśli przez x_i oznaczymy strategię mieszaną i-tego gracza, to analogicznie jak dla strategii czystych określiliśmy profil strategii czystych, określamy profil gry jako x = (x_1, ..., x_n) \in \prod\limits_{i=1}^n 	 \mathbb{R}^{|A_i|} .

Dla ustalonego profilu przypisujemy  x(a) - prawdopodobieństwo zagrania przez graczy strategii czystej a = (a_1, ..., a_n). Wybory graczy są niezależne zatem  x(a) = x_1(a_1) \cdots x_n(a_n) \;. A więc gracz i-ty otrzyma wypłatę  u_i(a) z prawdopodobieństwem  x(a) . Zatem wypłata i-tego gracza jest zmienną losową która przyjmuje wartość  u_i(a) z prawdopodobieństwem  x(a) .

Wypłata przy danym profilu gry[edytuj | edytuj kod]

Wypłatą przy danym profilu gry gracza i-tego nazywamy wartość oczekiwaną wyżej określonej zmiennej losowej. Poniżej znajdują się pewne tożsamości związane z tą wartością oczekiwaną. Oznaczmy: (a_i, a_{-i}) = (a_1, ..., a_i, ..., a_n), A_{-i} = \prod\limits_{j \not = i} A_j  oraz x_{-i}(a_{-i}) = \prod\limits_{j \not =i}x_j(a_j) .

Wypłata jest linowa względem składowych dowolnego profilu:

u_i(x) = u_i(x_1, ..., \sum_{k=1}^{|A_j|} x_{j}(1_k^j)1_k^j, ..., x_m) = \sum_{a \in A} u_i(a)x(a) =

\sum_{a_j \in A_j} \sum_{a_{-j} \in A_{-j}}  u_i(a_j, a_{-j})x(a_j, a_{-j}) =  \sum_{a_j \in A_j} x_j(a_j) \sum_{a_{-j} \in A_{-j}}  u_i(a_j, a_{-j})x_{-j}(a_{-j})  = \sum_{a_j \in A_j} x_j(a_j) u_i(x_1, ..., a_j, ..., x_n) = \sum_{k=1}^{|A_j|} x_j(1_k^j) u_i(x_1, ..., 1_k^j, ..., x_n), dla j \in N.

Gry symetryczne[edytuj | edytuj kod]

Grę nazywamy symetryczną jeśli dla dowolnych  i, j \in N i dowolnego profilu strategii czystch  a = (a_1, ..., a_n) \; zachodzi:

u_i(a_1, ..., a_i, ..., a_j, ..., a_n) = u_j(a_1, ..., a_j, ..., a_i, ..., a_n) \;.

Warunek ten można łatwo zinterpretować. Mianowicie wypłata gracza i-tego przy danym profilu ma być równa wypłacie gracza j-tego gdy obaj zamienią się swoimi strategiami czystymi.

Gry skończone[edytuj | edytuj kod]

Gdy gra jest dwuosobowa, możemy funkcję wypłat przedstawić w postaci macierzy wypłat.

Gry symetryczne[edytuj | edytuj kod]

W przypadku gry dwuosobowej warunek symetryczności gry oznacza, że macierz wypłat dla każdego z graczy jest równa transponowanej macierzy wypłat przeciwnika. Rzeczywiście:

 w_{i,j}^1 = u_1(1_i,1_j) = u_2(1_j,1_i) = w_{j,i}^2