WYK. 5 Temat : Teoria gier

Podejmowanie decyzji może odbywać się w następujących rodzajów warunków:

Uzasadnienie

Niech: D- działanie, W-wynik lub D- decyzja, W- skutek, wynik.

Wtedy:

D_i -> W_i lub P{D_i -> W_i} =1.

Gdzie p_ij = P {D_i ->W_ij} nie istnieją lub nie ma sensu.

D_i ->W(D_i).

Wnioski:

Konflikt lub nieokreśloność występuje wtedy, gdy wynik tej decyzji jest funkcją tej decyzji D_i.

W warunkach konfliktu skutek jest antagonistyczną odpowiedzią na decyzje D_i.

W warunkach nieokreśloności skutek jest nie koniecznie antagonistyczną odpowiedzią na decyzje Di.

Jedną z efektywnych metodologii analizy problemów decyzyjnych w warunkach konfliktu lub nieokreśloności jest Teoria gry

Teoria Gier jest matematyczną teoria modeli podejmowania decyzji w warunkach konfliktu lub nieokreśloności.

Teoria gier jest to nauka o zachowaniu w warunkach konfliktu lub nieokreśloności.

Geneza Teorii gier:

Nagroda nobla w dziedzinie ekonomi 1994r. - J. Hasanyi, J. Nash, R. Selten

Ogólna charakterystyka zadań i modeli teorii gier

- charakterystykę uczestników gry, czyli graczy

- wyszczególnienie możliwości postępowania graczy

- opis informacji dostępnej graczom

- określenie celów do których dążą gracze

3) Decyzje graczy w problemach teorii gier nazywamy strategiami

Podstawowa klasyfikacja gier

Teoria Gier Macierzowych

Def. 1

Dana jest dwuosobowa gra macierzowa o sumie 0 ( pomiędzy graczami G1 i G2) jeżeli zadana jest następująca macierz:

A=[a1j]mxn =

Macierz gry/wypłat jeżeli:

Elementy aij macierzy wypłat A interpretuje się jako wielkości wygranej gracza G1 u gracza G2 lub odwrotnie w przypadku gdy:

- Gracz G1 wykona ruch odpowiadający i-temu wierszowi macierzy A

- Gracz G2wykona ruch odpowiadający j-tej kolumnie macierzy A

Strategie uczestników gry

Definicja 2

Strategią mieszana Gracza G1 nazywamy wektor: X = [x1,x2, … , xm] którego składowe xi są częstościami(prawdopodobieństwami) z jakimi gracz G1 wybiera ruch odpowiadający i-temu wierszowi.

Definicja 3

Strategią mieszana Gracza G2 nazywamy wektor: Y = [y1,y2, … , yn] którego składowe yj są częstościami(prawdopodobieństwami) z jakimi gracz G2 wybiera ruch odpowiadający j-tej kolumnie.

Wniosek. Dla dowolnej strategii obydwu graczy zachodzą następujące równości:

Uwaga Powyższe wzory wynikają bezpośrednio z powyższych definicji 2 i 3

Związku z powyższymi def. I oznaczeniami w teorii gier określa się następującą tzw. Tablicę dwuosobowej gry macierzowej

Def. 4

Strategiami czystymi graczy G1 i G2 nazywamy odpowiednie wektory jednostkowe i oznaczone symbolami:

Wnioski:

Sformułowanie zadania optymalizującego W Teorii Gier

Podstawowe zagadnienie teorii gier polega na wyznaczaniu takiej strategii gracza G1, która zapewnia mu maksymalną wygraną, przy założeniu, że gracz G2 będzie stosował taką strategię, która zapewnia temu graczowi minimalną przegraną.

Metody Rozwiązywania gry macierzowej

Funkcja wypłaty gry macierzowej

Def. 5

Funkcja Wypłaty gry o macierzy wypłaty A nazywamy wartość oczekiwaną wygranej gracza G1 w przypadku, gdy stosuje on strategię X, a gracz G2 stosuje strategię Y, czyli

Ea(X,Y)= XAYt = E_A(X,Y) = XAY^T =
a_ij * x_iY_j

Definicja 6

Rozwiązania zagadnień teorii gier

Rozwiązaniem dwuosobowej gry macierzowej o sumie zero nazywamy taką parę strategii X i Y oraz liczbę v, Że spełnione będą następujące warunki:

1)
E_A(
,Y_j) ≥ V

2)
E_A(X_i,
)
V

Istotę, sens i uzasadnienie POWYŻSZEJ definicji 6 oraz wzorów 4 i 5 zawierają następujące def 7 i 8.

Def. 7

Strategiami optymalnymi graczy G1 i G2 nazywamy odpowiednio wektory X^ i Y^ spełniające warunki 4 i 5

Def 8

Optymalna wartością dwuosobowej gry macierzowej o sumie zero nazywamy liczbę v spełniającą warunki 4 i 5

Twierdzenie o istnieniu rozwiązania dwuosobowej gry macierzowej o sumie zero

Dowolna dwuosobowa gra macierzowa o sumie zero ma rozwiązanie optymalne w postaci:

{X^,Y^,v} lub {X^a,Y^a,va}

Warunki istnienia rozwiązań gier macierzowych w strategiach czystych

Punkty siodłowe gier macierzowych

Stosując wyłącznie strategie czyste gracz G1 może zapewnić sobie wygraną nie mniejszą niż nastep[ująca wielkośc:

= apq wzór 6

Analogicznie stosując wyłącznie strategie czyste gracz G2 może zapewnić sobie wygraną nie większą niż następującą wielkość:

= ars wzór 7

Definicja

Jeżeli dla macierzy wypłat A gry macierzowej zachodzi równość apq=ars top punkt v=apq=ars nazywamy wówczas punktem siodłowym rozpatrywanej gry macierzowej.

Twierdzenie o punkcie siodłowym

Jeżeli w macierzy wypłat A pewnej gry macierzowej o sumie zero istnieje punkt siodłowy, czyli zachodzi równość:

Apq=ars gdzie apq i ars są określone wzorami 6 i 7 to rozwiązaniem gry macierzowej o macierzy wpłat A jest

R1) czysta strategia X^=Xp=Xr gracza G1

R2)

Twierdzenie o Istnieniu rozwiązania gier macierzowych w strategiach czystyuch

Twierdzenie o Istnieniu rozwiązania gier macierzowych w strategiach czystyuch

Gry o macierzy wypłat A ma rozwiązanie w strategiach czystych wtedy i tylko wtedy, gdy istnieje punkt siodłowy.

Ponadto współrzędne punktu siodłowego generują jednoznacznie numery czystyuch strategii optymalnych obydwóch graczy G1 i G2 oraz optymalną wartośc gry o macierzy wypłat A.

Rozwiązaniem gry macierzowej o macierzy wypłat A jest wtedy następująca trójka:

{Xp,Yq, apq} = {Xr,Ys,ars}

Wnioski

Skonstruować własny przykład macierzy 3x3 a) istnieje punkt siodłowy b) nie istnieje punkt siodłowy

Wyznaczanie optymalnych strategii w strategiach mieszanych( bez punktu siodłowego)

Przewaga w grach macierzowych

Wiersze i kolumny przeważające w macierzach gier

Def.

Wiersz w macierzy wypłat A przeważa jeżeli wszystkie jego elementy są mniejsze od odpowiednich elementów pewnego innego wiersza macierzy wypłat A.

Def.

Kolumna w macierzy wypłat A przeważa jeżeli wszystkie jego elementy są większe od odpowiednich elementów pewnej innej kolumny macierzy wypłat A.

Wnioski

Przekształcenie gier macierzowych

do równoważnych zadań optymalizacji liniowej

Pokazane zostanie obecnie jak problem wyznaczania optymalnego zadania strategii mieszanych sprowadzić do odpowiednich zadań optymalizacji liniowych…

Bezpośrednia konstrukcja równoważnych ZOL

ETAP 1 (A)

Problem Gracza G1 polega na wyznaczaniu maksymalnej liczby lambda i wektora X=[x1,x2, .. ,xm] o nieujemnych składowych sumujących się do jedności takich, że spełniony będzie następujący układ nierówności liniowych. (wzór 4 i def. 6)

(dla j=1,2, .. , n)

Rozwiązaniem powyższego problemu jest równoważne z problemem rozwiązania następującego ZOL:

Wzór P

ETAP 2 (B)

Problem Gracza G2 polega na wyznaczaniu minimalnej liczby ni i wektora Y=[y1,y2, .. ,yn] o nieujemnych składowych sumujących się do jedności takich, że spełniony będzie następujący układ nierówności liniowych. (wzór 5 i def 6)

(dla i=1,2, .. , n)

Rozwiązaniem powyższego problemu jest równoważne z problemem rozwiązania następującego ZOL:

Wzór R

Wnioski

Uniwersalny schemat rozwiązywania gier macierzowych o sumie zero