Zagadnienia

3.1 Definicje
3.2 Własności RN

3. Równowaga Nasha

3.1. Definicje

Równowaga Nasha (RN) jest centralnym pojęciem teorii gier strategicznych.

Definicja (ważna) 3.1

Profil (strategii mieszanych) gry strategicznej σ* jest równowagą Nasha wtedy i tylko wtedy jeżeli

ui⁢σi*,σ-i*≥ui⁢σi,σ-i*⁢⁢∀i=1,…⁢n,⁢∀σi∈Σi

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.

3.2. Własności RN

Definicja 3.2

Nośnik strategii mieszanej σi=σi⁢1,…,σi⁢mi jest to zbiór s⁢u⁢p⁢p⁢σi⊂Ai akcji (strategii czystych gracza i) taki że akcja o numerze k z Ai należy do s⁢u⁢p⁢p⁢σi⁢⇔σi⁢k>0.

INaczej mówiąc nosnik strategii σi jest to zbiór strategii czystych które sa grane z dodatnimi prawdopodobieństwami w danej strategii mieszanej σi.

Jeżeli używamy dla strategii mieszanej notacji xi, to jej nośnik oznaczmy s⁢u⁢p⁢p⁢xi. 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).

Twierdzenie 3.1 (O wypłatach strategii czystych w RN)

Niech

x=x1,…⁢xn,⁢xi=∑k=1mieik⁢xi⁢k,⁢i=1,…⁢n

- profil strategii mieszanych GS. Ustalmy gracza i. Niech eik1,eik2 - dwie różne strategie w s⁢u⁢p⁢p⁢xi czyli p1:=xi⁢k1>0,⁢p2:=xi⁢k2>0. Wtedy

x⁢⁢j⁢e⁢s⁢t⁢⁢R⁢N⇒∀i∈N⁢⁢⁢ui⁢eik1,x-i=ui⁢eik2,x-i

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

Uwaga 3.1

ui⁢eik1,x-i oznacza ui(x1,x2,…,eik1,…,,xn).

ad absurdum. Niech x=x1,…,xn - RN, oraz

ui⁢eik1,x-i>ui⁢eik2,x-i

(3.2)

Definiujemy profil

x~=x1,…,xi-1,x~i,xi+1,…,xN

taki że

x~i=∑k=1mieiki⁢x~i⁢k,

gdzie

x~i⁢k1=p1+p2,

x~i⁢k2=0,

x~i⁢j=xi⁢j⁢⁢⁢d⁢l⁢a⁢⁢⁢j≠k1,j≠k2.

Pokażemy że

ui⁢x~i,x-i>ui⁢xi,x-i

(3.3)

czyli sprzeczność z definicją RN. Lewa strona tej nierówności ma postać:

	L=ui⁢∑k=1mieik⁢x~i⁢k,x-i=	p1+p2⁢ui⁢eik1,x-i		(3.4)
		+0⋅ui⁢eik2,x-i+ui⁢∑k≠k1,k≠k2eik⁢xi⁢k,x-i.		(3.5)

Prawa strona nierówności

	P=ui⁢∑k=1mieik⁢xi⁢k,x-i=	p1⁢ui⁢eik1,x-i+p2⁢ui⁢eik2,x-i		(3.6)
		+ui⁢∑k≠k1,k≠k2eik⁢xi⁢k,x-i,		(3.7)

a zatem z (3.2) otrzymujemy L>P, czyli (3.3), i.e. sprzeczność z definicją RN.

∎

Wniosek 3.1

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

Stwierdzenie 3.1 (O wypłatach w RN)

Niech

x*=x1*,…⁢xN*,⁢xi*=∑k=1mieik⁢xi⁢k*,⁢i∈N

- profil strategii mieszanych GS w RN. Wypłata każdego gracza i∈N z profilu x* jest równa jego wypłacie z profilu w którym gra (dowolną) strategię czystą z s⁢u⁢p⁢p⁢xi* a wszyscy inni nie zmieniają swych strategii. Formalnie:

ui⁢xi*,x-i*=ui⁢eik,x-i*⁢⁢∀eik∈s⁢u⁢p⁢p⁢xi*

(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 i gra w RN pewną strategią xi*=∑k∈s⁢u⁢p⁢p⁢xi*xi⁢k*⁢eik.

Korzystając z liniowości ui otrzymujemy

ui⁢xi*,x-i*=∑k∈s⁢u⁢p⁢p⁢xi*xi⁢k*⁢ui⁢eik,x-i*=

(z Twierdzenia 3.1), oznaczając s–numer dowolnej ustalonej strategii z s⁢u⁢p⁢p⁢xi*:

=∑k∈s⁢u⁢p⁢p⁢xi*xi⁢k*ui(eis,x-i*)=ui(eis,x-i*)∑k∈s⁢u⁢p⁢p⁢xi*xi⁢k*=

=(∑k∈s⁢u⁢p⁢p⁢xi*xi⁢k*=1)ui(eis,x-i*).

∎

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

ui⁢s′,x-i*>ui⁢s′′,x-i*⁢⁢⁢d⁢l⁢a⁢⁢⁢s′∉s⁢u⁢p⁢p⁢xi*,s′′∈s⁢u⁢p⁢p⁢xi*.

Z Wniosku (3.1), w RN dla s′′∈s⁢u⁢p⁢p⁢xi*

ui⁢s′′,x-i*=ui⁢xi*,x-i*≡ui⁢x*,

a zatem otrzymujemy ui⁢s′,x-i*>ui⁢xi*,x-i*, sprzeczność z definicją RN.

⇐:

Ustalmy gracza i. Niech xi* będzie jego strategią mieszaną spełniającą warunki 1. i 2. Należy wykazać że

ui⁢xi,x-i*≤ui⁢xi*,x-i*⁢⁢⁢∀xi∈Σi.

Oznaczmy, pomijając dla uproszczenia notacji w obu symbolach indeks i: ⁢S:=s⁢u⁢p⁢p⁢xi*, ⁢ak≡eik - k-ta strategia czysta gracza i. Rozkładając ui⁢xi,x-i* względem nośnika strategii xi* i jego dopełnienia otrzymujemy, korzystając z liniowości ui:

ui⁢xi,x-i*=∑ak∈Sxi⁢k⁢ui⁢ak,x-i*+∑ak∉Sxi⁢k⁢ui⁢ak,x-i*,

gdzie zastosowaliśmy zapis xi=∑kak⁢xi⁢k.

Pierwsza suma po prawej stronie ma (z warunku 1.) postać:

∑ak∈Sxi⁢k⁢ui⁢as,x-i*=ui⁢as,x-i*⁢∑ak∈Sxi⁢k,

gdzie as jest jedną ze strategii czystych z nośnika S. Druga suma spełnia (z warunku 2.) nierówność:

∑ak∉Sxi⁢k⁢ui⁢ak,x-i*≤∑ak∉Sxi⁢k⁢ui⁢as,x-i*=ui⁢as,x-i*⁢∑ak∉Sxi⁢k

gdzie as jest ustaloną strategią czystą z nośnika S. Zatem, ponieważ Ai=S∪S¯,

ui⁢xi,x-i*≤ui⁢as,x-i*⁢∑ak∈Aixi⁢k,

Zauważmy że dla obu profili xi oraz xi* (każdy profil należy do sympleksu jednostkowego Δi)

∑ak∈Aixi⁢k=∑ak∈Aixi⁢k*=1,

a więc

ui⁢xi,x-i*≤ui⁢as,x-i*⁢∑ak∈Aixi⁢k*=∑ak∈Sui⁢as,x-i*⁢xi⁢k*+∑ak∉Sui⁢as,x-i*⁢xi⁢k*.

Wykorzystując warunek 1. (do zamiany as na ak), reprezentację xi*=∑ak∈Aiak⁢xi⁢k* i liniowość funkcji wypłat względem odpowiednich argunentów, przepisujemy wyrażenie po ostatnim znaku równości w postaci

∑ak∈Sui⁢ak,x-i*⁢xi⁢k*+∑ak∉Sui⁢as,x-i*⁢xi⁢k*=∑ak∈Aiui⁢ak,x-i*⁢xi⁢k*=ui⁢xi*,x-i*,

gdzie ostatnia równość wynika z liniowości wypłat. Otrzymaliśmy więc

ui⁢xi,x-i*≤ui⁢xi*,x-i*.

Powyższe rozumowanie przeprowadzamy ∀i∈N.

∎

Pokażemy przykład zastosowania Twierdzenia LABEL:waz1.

Przykład 3.1

	L	C	R
T	a,2	3,3	1,1
M	0,0	0,0	2,b
B	c,4	5,1	0, 7

a,b,c∈ℜ. Nastepująca para (profil) strategii mieszanych jest RN:

x*=x1*,x2*=3/4,0,1/4,0,1/3,2/3

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 i=1:

Wypłata z T:0⋅a+1/3⋅3+2/3⋅1=5/3

Wypłata z M:0⋅b+1/3⋅0+2/3⋅2=4/3

Wypłata z B:0⋅c+1/3⋅5+2/3⋅0=5/3

Wypłaty ze strategii czystych z s⁢u⁢p⁢p⁢x1=T,B są jednakowe, wypłata z M jest niższa. Dla gracza i=2 analogiczny rachunek pokazuje że wypłaty ze wszystkich strategii czystych: u2(x1*,⋅) są równe 5/2, np:

u2⁢x1*,L=2⋅3/4+0⋅0+4⋅1/4=5/2.

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

u1⁢M,x2*=u1⁢0,1,0,0,1/3,2/3=6/3>5/3.

A oto jeszcze jedna charakterystyka RN dająca w szczególności warunek dostateczny istnienia RN.

Stwierdzenie 3.2

Profil x* jest RN ⇔

∀i∈N,∀eik∈Ai⁢⁢⁢ui⁢eik,x-i*≤ui⁢xi*,x-i*

⇒: Z definicji RN.

⇐: Ustalmy i. Niech xi=∑k=1mixi⁢k⁢eik - dowolna strategia mieszana gracza i. Obliczamy: z liniowości

	ui⁢xi,x-i*=	∑k=1mixi⁢k⁢ui⁢eik,x-i≤∑k=1mixi⁢k⁢ui⁢xi,x-i*		(3.9)
		=ui(xi,x-i)∑k=1mixi⁢k=ui(xi,x-i).		(3.10)

∎

Istotną rolę w teorii gier strategicznych odgrywa ścisła RN.

Definicja 3.3

Profil x*=x1*,…,xi* jest ścisłą RN (SRN) ⇔∀i⁢⁢⁢∀xi≠xi*

ui⁢xi,x-i*<ui⁢xi*,x-i*

Uwaga 3.2

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 ∀i∈N funkcja wypłat ui jest różnowartościowa.

Zachodzi:

Stwierdzenie 3.3

SRN jest RN w strategiach czystych

Wsk. W przeciwnym razie w RN nośnik strategii xi pewnego gracza i nie jest singletonem. Z Twierdzenia 3.1 wynika istnienie co najmniej dwóch różnych najlepszych odpowiedzi na xi.

∎

Uwaga 3.3

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

D,A jest (jedyną) RN, ale nie jest SRN.

Przykład 3.2

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.

Definicja 3.4

Profil σ*=σj*j∈N w GS w której wszyscy gracze mają ten sam zbiór akcji ( czyli Aj=A,⁢∀j∈N) jest symetryczną RN jeśli jest RN oraz σi*=σj*⁢⁢⁢∀i,j∈A.

Uwaga 3.4

”Większość” gier skończonych ma nieparzystą liczbę RN. Przykładem sa gry 2–osobowe dla których ∀i∈N funkcja ui:A→ℜ 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 1/2,0,1/2.

Innym ”kontrprzykładem” jest gra ”Słaby Dylemat Więźnia”, która jest modyfikacją DW z wypłatą P=S:

	C	D
C	R,R	S,T
D	T,S	S,S

dla T>R>S. 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.

Definicja 3.5

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

Przykład 3.3

	L	S	R
U	4,3	5,1	6,2
M	2,1	8,4	3,6
D	3,0	9,6	2,8

U,L jest RN ale nie jest PO. D,S jest PO, ale nie jest RN.

Przykład 3.4

Gra koordynacyjna

	A	B
A	2,2	-10-5,0
B	-10-5,0	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.

Przykład 3.5

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

Ćwiczenie 3.1

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ą σ1,σ2, to dla σ2=β,1-β mamy, z twierdzenia podstawowego u1⁢C,σ2=u1⁢D,σ2, czyli R⁢β+S⁢1-β=T⁢β+P⁢1-β, czyli S-P⁢1-β=T-R⁢β, 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.

Ćwiczenie 3.2

Pokaż że w grze w Kota i Myszkę uM⁢1/2,1/2,1/2,1/2≥uM⁢x,1-x,1/2,1/2⁢⁢⁢∀x∈0,1, oraz uM⁢1/2,1/2,1/2,1/2≥uM⁢1/2,1/2,y,1-y⁢⁢⁢∀y∈0,1, a zatem para strategii 1/2,1/2,1/2,1/2 jest RN (w istocie zachodzą równości).

Ćwiczenie 3.3

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.

Ćwiczenie 3.4

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.

Ćwiczenie 3.5

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

Ćwiczenie 3.6

GS jest o sumie zerowej jeżeli ∀a1,…,an∈A⁢⁢∑i=1nui⁢a1,…,an=0. 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.

Wstęp do Teorii Gier