Równowaga Nasha (RN) jest centralnym pojęciem teorii gier strategicznych.
Profil (strategii mieszanych) gry strategicznej jest równowagą Nasha wtedy i tylko wtedy jeżeli
![]() |
Słownie: żaden z graczy nie może podwyższyć swojej wypłaty przez jednostronną (to znaczy bez zmiany strategii wszystkich innych graczy) zmianę swojej strategii.
W dalszym ciągu udowodnimy ważne twierdzenia charakteryzujące RN.
Nośnik strategii mieszanej jest to zbiór
akcji (strategii czystych gracza
) taki że akcja o numerze
z
należy do
.
INaczej mówiąc nosnik strategii jest to zbiór strategii czystych które sa grane z dodatnimi
prawdopodobieństwami w danej strategii mieszanej
.
Jeżeli używamy dla strategii mieszanej notacji , to jej nośnik oznaczmy
. Nośnik strategii
czystej jest singletonem. Można wprowadzić dodatkowe charakterystyki strategii: strategie istotnie mieszane
(te które nie są czyste) i całkowicie mieszane (te których nośniki pokrywają się ze odpowiednim zbiorem
strategii czystych).
Niech
![]() |
- profil strategii mieszanych GS. Ustalmy gracza . Niech
- dwie różne strategie w
czyli
. Wtedy
![]() |
(3.1) |
Tak więc w RN każdy gracz ma jednakowe wypłaty ze wszystkich strategii czystych z nośnika swojej strategii mieszanej którą gra w RN.
oznacza
.
ad absurdum. Niech - RN, oraz
![]() |
(3.2) |
Definiujemy profil
![]() |
taki że
![]() |
gdzie
![]() |
![]() |
![]() |
Pokażemy że
![]() |
(3.3) |
czyli sprzeczność z definicją RN. Lewa strona tej nierówności ma postać:
![]() |
![]() |
(3.4) | ||
![]() |
(3.5) |
Prawa strona nierówności
![]() |
![]() |
(3.6) | ||
![]() |
(3.7) |
a zatem z (3.2) otrzymujemy , czyli (3.3), i.e. sprzeczność z definicją RN.
Wypłata każdego gracza w RN jest równa jego wypłacie z profilu w którym gracz ten gra dowolną strategią czystą z nośnika swojej strategii w RN, a pozostali gracze grają swoimi strategiami z RN. Mowi o tym
Niech
![]() |
- profil strategii mieszanych GS w RN. Wypłata każdego gracza z profilu
jest równa jego
wypłacie z profilu w którym gra (dowolną) strategię czystą z
a wszyscy inni nie zmieniają
swych strategii. Formalnie:
![]() |
(3.8) |
Mówimy, że w RN wypłata gracza jest równa wypłacie z dowolnej granej przez niego w RN strategii czystej.
Gracz gra w RN pewną strategią
Korzystając z liniowości otrzymujemy
![]() |
(z Twierdzenia 3.1), oznaczając –numer dowolnej ustalonej strategii z
:
![]() |
![]() |
Poniżej udowodnimy twierdzenie które pozwala znaleźć RN jeśli jest spełniony warunek dostateczny, oraz daje charakterystykę RN jako warunek konieczny.
:
Warunek 1. jest identyczny z Twierdzeniem 3.1.
Warunek 2.: ad absurdum: w przeciwnym razie mielibyśmy
![]() |
Z Wniosku (3.1), w RN dla
![]() |
a zatem otrzymujemy , sprzeczność z definicją RN.
:
Ustalmy gracza . Niech
będzie jego strategią mieszaną spełniającą warunki 1. i 2. Należy wykazać że
![]() |
Oznaczmy, pomijając dla uproszczenia notacji w obu symbolach indeks :
,
- k-ta strategia czysta gracza
. Rozkładając
względem nośnika strategii
i jego dopełnienia otrzymujemy, korzystając z liniowości
:
![]() |
gdzie zastosowaliśmy zapis
Pierwsza suma po prawej stronie ma (z warunku 1.) postać:
![]() |
gdzie jest jedną ze strategii czystych z nośnika
. Druga suma spełnia (z warunku 2.) nierówność:
![]() |
gdzie jest ustaloną strategią czystą z nośnika
. Zatem, ponieważ
,
![]() |
Zauważmy że dla obu profili oraz
(każdy profil należy do sympleksu jednostkowego
)
![]() |
a więc
![]() |
Wykorzystując warunek 1. (do zamiany na
),
reprezentację
i liniowość funkcji wypłat
względem odpowiednich argunentów, przepisujemy wyrażenie po ostatnim znaku równości w postaci
![]() |
gdzie ostatnia równość wynika z liniowości wypłat. Otrzymaliśmy więc
![]() |
Powyższe rozumowanie przeprowadzamy .
Pokażemy przykład zastosowania Twierdzenia LABEL:waz1.
L | C | R | |
---|---|---|---|
T |
![]() |
3,3 | 1,1 |
M | 0,0 | 0,0 | 2,![]() |
B |
![]() |
5,1 | 0, 7 |
. Nastepująca para (profil) strategii mieszanych jest RN:
![]() |
Porównamy wypłaty ze strategii czystych i zastosujemy Twierdzenie LABEL:waz1.
Obliczamy wypłaty ze strategii czystych gdy profil przeciwnika jest z RN. Dla gracza :
Wypłata z
Wypłata z
Wypłata z
Wypłaty ze strategii czystych z są jednakowe, wypłata z
jest niższa.
Dla gracza
analogiczny rachunek pokazuje że wypłaty ze wszystkich strategii czystych:
są równe
, np:
![]() |
Warunki dostateczne na RN (dla drugiego gracza jest potrzebny tylko warunek 1) są więc spełnione.
∎Uwaga: Jeśli w drugim wierszu zamienimy 2 na 3 to powyższy profil nie będzie RN bo
A oto jeszcze jedna charakterystyka RN dająca w szczególności warunek dostateczny istnienia RN.
Profil jest RN
![]() |
: Z definicji RN.
: Ustalmy
. Niech
- dowolna strategia mieszana gracza
. Obliczamy: z liniowości
![]() |
![]() |
(3.9) | ||
![]() |
(3.10) |
Istotną rolę w teorii gier strategicznych odgrywa ścisła RN.
Profil jest ścisłą RN (SRN)
![]() |
RN jest SRN gdy strategia każdego gracza w RN jest JEDYNĄ najlepszą odpowiedzią na strategie wszystkich innych graczy w RN (definicja najlepszej odpowiedzi będzie podana w następnym rozdziale).
Mówimy że skończona GS jest generyczna jeśli funkcja wypłat
jest różnowartościowa.
Zachodzi:
SRN jest RN w strategiach czystych
Wsk. W przeciwnym razie w RN nośnik strategii pewnego gracza
nie jest singletonem.
Z Twierdzenia 3.1 wynika istnienie co najmniej dwóch różnych najlepszych odpowiedzi na
.
SRN nie musi istnieć. Przykład: Gra Orzeł-Reszka.
RN w strategiach czystych nie musi być SRN. Przykład: W grze
A | B | |
---|---|---|
A | 1,1 | 0,0 |
B | 0,0 | 0,0 |
(A,A) jest SRN, (B,B) nie.
Nawet gdy GS ma dokładnie jedną RN, to ta RN nie musi być SRN. Przykład: w grze
A | B | C | |
---|---|---|---|
D | 1,1 | 1,0 | 0,1 |
E | 1,0 | 0,1 | 1,0 |
jest (jedyną) RN, ale nie jest SRN.
W Słabym Dylemacie Więźnia nie ma SRN. To że mieszane strategie nie są SRN wynika ze Stwierdzeniaq 3.3. Bezpośredni rachunek pokazuje że żadna z 3 czystych Rn nie jest SRN.
Profil w GS w której wszyscy gracze mają ten sam zbiór akcji (
czyli
) jest symetryczną RN jeśli jest RN oraz
”Większość” gier skończonych ma nieparzystą liczbę RN.
Przykładem sa gry 2–osobowe dla których funkcja
jest różnowartościowa (gry generyczne).
Oto ”kontrprzykład”: GS z czterema RN ([33]):
A | B | C | |
---|---|---|---|
D | 0,0 | -1,-1 | -1,-1 |
E | -1,-1 | -1,-1 | -1,-1 |
E | -1,-1 | -1,-1 | 0,0 |
(poza trzema czystymi RN jest ”częściowo mieszana” RN .
Innym ”kontrprzykładem” jest gra ”Słaby Dylemat Więźnia”, która jest modyfikacją DW z wypłatą :
C | D | |
---|---|---|
C | R,R | S,T |
D | T,S | S,S |
dla . Wypłata każdego gracza nie jest funkcją różnowartośiowa.
Gra ma continuum RN (w tym 3 RN w strategiach czystych), patrz Cwiczenie 4.1.
W ekonomicznych zastosowaniach teorii gier istotną rolę odgrywa pojęcie Pareto-optymalności.
Profil gry strategicznej jest Pareto-optymalny (PO) jeżeli nie istnieje profil dający conajmniej jednemu graczowi wyższą, a wszystkim innym conajmniej taką samą wypłatę.
Profil gry jest Pareto-nieoptymalny jeżeli istnieje inny, lepszy dla conajmniej jednego gracza i nie gorszy dla żadnego (czyli gdy nie jest PO).
L | S | R | |
---|---|---|---|
U | 4,3 | 5,1 | 6,2 |
M | 2,1 | 8,4 | 3,6 |
D | 3,0 | 9,6 | 2,8 |
jest RN ale nie jest PO.
jest PO, ale nie jest RN.
Gra koordynacyjna
A | B | |
---|---|---|
A | 2,2 |
![]() |
B |
![]() |
1,1 |
ma 2 RN w strategiach czystych. RN (A,A) jest PO, ale, zakładając wypłaty np. w PLN, nie jest to ”przekonywujący” wybór w praktycznej realizacji.
W 2-osobowym DW profil (C,C) jest PO gdyż gdy jeden z graczy sobie podwyższy wypłatę to wypłata drugiego się obniży. (C,C) jest PO, ale nie jest RN. Profil (D,D) jest RN ale nie jest PO.
W ”Dylemacie Wspólnych Zasobów” (Tragedy of Commons) tzw. minimalna efektywna kooperacja (czyli profil w którym jest dokładnie tylu kooperantów ile wynosi ”próg” - minimalna liczba kooperantów przy której pula jest rozdzielana między wszystkich graczy) jest jedynym profilem PO.
Dla gier o sumie stałej (patrz część 5) każdy profil jest PO (bo nie istnieje profil dający conajmniej jednemu graczowi wyższą, a wszystkim innym conajmniej taką samą wypłatę).
Pokazać że DW nie ma innych równowag poza (D,D).
W strategiach czystych nie ma innych RN poza (D,D).
Gdyby miał równowagę ściśle mieszaną , to dla
mamy, z twierdzenia podstawowego
,
czyli
, czyli
, sprzeczność dla DW. Dla profili w których jeden gracz gra strategią ściśle mieszaną a drugi czystą z twierdzenia–warunku koniecznego na wypłaty z obu strategii czystych pierwszego gracza byłyby jednakowe, co nie jest możliwe dla DW.
Pokaż że w grze w Kota i Myszkę
oraz
a zatem para strategii
jest RN (w istocie zachodzą równości).
Ogólniejsza postać gry ”W Kota i Myszkę”
L | P | |
---|---|---|
L | 0,K | M,0 |
P | M,0 | 0,K |
Obliczyć średnie wypłaty przy stosowaniu strategii mieszanych i znależć RN.
W grze
L | S | R | |
---|---|---|---|
U | 0,1 | 0,1 | 2,4 |
M | 5,1 | 2,2 | 1,0 |
D | 4,3 | 1,4 | 1,0 |
znależć RN i profile PO w strategiach czystych.
Odp.: (U,R): RN, PO. (M,S):RN ale nie PO. (D,L):PO ale nie RN.
Znaleźć RN w grze
L | S | R | |
---|---|---|---|
U | 1,3 | 1,3 | 1,3 |
M | 0,0 | 2,2 | 2,2 |
D | 0,0 | 0,0 | 3,1 |
GS jest o sumie zerowej jeżeli .
Wykaż że dla GS o sumie zerowej każdy profil jest PO.
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
Projekt współfinansowany przez Unię Europejską w ramach
Europejskiego Funduszu Społecznego.
Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.