TGH13 - Teorie her I

TGH13 - Teorie her I. Jan Bˇrezina Technical University of Liberec

19. kvˇetna 2015

Hra s bank´eˇrem

M´ate pr´avo sehr´at s bank´eˇrem hru: 1. h´az´ı se korunou dokud nepadne hlava 2. pokud hlava padne v hodu N , ban´eˇr vyplat´ı 2N Kolik m˚ uˇzete poˇzedovat za odstoupen´ı od hry?

ˇreˇsen´ı

Pˇrimˇeˇren´a n´ahrada je stˇredn´ı hodnota vyplacen´e ˇc´astky tj. 1 1 1 1 + 2 + . . . 2N N + · · · = ∞ 2 4 2

Vˇezˇnovo dilema

Vˇezˇnovo dilema - vlastnosti

• Pˇredpoklad, ˇ ze nedojde k dalˇs´ı ”hˇre”, napˇr. odplata. • Optim´ aln´ı pro oba je spolupr´ace (remain silent). • Nicm´ enˇe pokud kaˇzd´y hled´a jen svoje optimum, skonˇc´ı to pro oba

nejhorˇs´ım zp˚ usobem. • Model pro nˇ ekter´e re´aln´e situace (napˇr. reklama, doping)

V´ybˇerov´e ˇr´ızen´ı

• tˇri firmy: A-comp, B-comp, C-comp • 3/4 zak´ azky z´ısk´a druh´a nejlevnˇejˇs´ı nab´ıdka, prvn´ı nab´ıdka z´ısk´a 1/4

zak´azky • v pˇr´ıpadˇ e shody cen se zak´azka d´ale dˇel´ı • strategie A-comp (kolik bude jej´ı cena): 20, 40 • strategie B-comp: 20, 30, 40 • strategie C-comp: 10, 50

hra - v´ybˇerov´e ˇr´ızen´ı nab´ıdky (A,B,C) 20, 20, 10 20, 20, 50 20, 30, 10 20, 30, 50 20, 40, 10 20 ,40, 50 40, 20, 10 40, 20, 50 40, 30, 10 40, 30, 50 40, 40, 10 40 ,40, 50

zisky (A,B,C) 7.5, 7.5, 2.5 10, 10, 0 15, 0, 2.5 5, 22.5, 0 15, 0, 2.5 5, 30, 0 0, 15, 2.5 30, 5, 0 0, 22.5, 2.5 30, 7.5, 0 15, 15, 2.5 20, 20, 0

Hra v norm´aln´ım tvaru Hra v norm´aln´ım tvaru je trojce mnoˇzin H = (U, S, F ) • mnoˇ zina u ´ˇcastn´ık˚ u - hr´aˇc˚ u U = {1, . . . , N } • mnoˇ zina prostor˚ u strategi´ı pro u ´ˇcastn´ıky S = {X1 , . . . , X2 } • mnoˇ zina v´yplatn´ıch funkc´ı hr´aˇc˚ u F = {F1 , . . . , F2 },

Fi : X1 × X2 × . . . XN → R F lze ch´apat jako vektorovou funkci, kter´a kaˇzd´emu vektoru strategi´ı pˇriˇrazuje vektor v´yher Pr˚ ubˇeh hry: 1. kaˇzd´y hr´aˇc i ∈ U vybere svou strategii xi ∈ Xi 2. vznikne vektor strategi´ı (x1 , x2 , . . . , xN ) 3. Kaˇzd´emu hr´aˇci i ∈ U se vyplat´ı “v´yhra” podle v´yplatn´ı funkce Fi (x1 , x2 , x3 )

Souˇcet v´yher

Dˇelen´ı her podle souˇctu v´yher vˇsech u ´ˇcastn´ık˚ u: 1. konflikt (hra) s nekonstantn´ım souˇctem = souˇcet v´yher z´avis´ı na volbˇe strategi´ı (pˇr: vˇezˇ novo dilema) 2. konflikt (hra) s konstantn´ım souˇctem = souˇcet v´yher nez´avis´ı na volbˇe strategi´ı (pˇr: v´ybˇerov´e ˇr´ızen´ı) 3. konflikt (hra) s nulov´ym souˇctem = souˇcet v´yher je nulov´y (pˇr: kamen-n˚ uˇzky-pap´ır, poker, obchodn´ı hry) Kooperativn´ı hry jsou pops´any prvn´ım typem.

k´amen - n˚ uˇzky - pap´ır

Vlastnosti: poˇcet hr´aˇc˚ u N = 2, hra s nulov´ym souˇctem, koneˇcn´y poˇcet strategi´ı |X1 | = |X2 | = 3 X Y K N P

K 0:0 -1:1 1:-1

N 1:-1 0:0 -1:1

P -1:1 1:-1 0:0

ˇ Sachy ˇreˇc´ı teorie her

• koneˇ cn´e mnoˇzstv´ı moˇzn´ych stav˚ u (postaven´ı) (zanedb´ame historii) • u ´pln´y pˇredpis jak v kaˇzd´em postaven´ı t´ahnout = strategie • partie - kaˇ zd´y hr´aˇc zvol´ı svou strategii a partie prob´ıh´a

“automaticky” vyhled´an´ım tahu pro aktu´aln´ı postaven´ı • Teoreticky lze sestavit tabulku v´ ysledk˚ u pro kaˇzdou dvojici strategi´ı. • hra s nulov´ ym souˇctem (asi)

Toto dohromady d´av´a u ´pln´y popis hry ˇsachy i bez zn´amosti pravidel, tabulka v´ysledk˚ u obsahuje vˇsechny moˇzn´e partie.

Pozn´amky

Pˇr´ıklady: k´amen-n˚ uˇzky-pap´ır, intervalov´a hra Vˇsichni u ´ˇcastn´ıci znaj´ı moˇzn´e strategie a v´ypletn´ı funkce vˇsech. (jinak hra s nedokonalou informac´ı) Frustruj´ıc´ı je pouze v to, ˇze kaˇzd´y vol´ı pouze svoji sloˇzku souboru strategi´ı. Pokud jsou prostory strategi´ı stejn´e a v´yplatn´ı funkce naz´avis´ı na permutaci hr´aˇc˚ u, jedn´a se o symetrickou hru.

Klasifikace konflikt˚ u

1. podle poˇctu u ´ˇcastn´ık˚ u - 2, 3, . . . 2. pro v´ıce u ´ˇcastn´ık˚ u - moˇznost tvorby koalic ano/ne 3. podle “inteligence” u ´ˇcastn´ık˚ u - m´ıra neurˇcitosti 4. podle souˇctu v´yher 5. symetrick´e/nesymetrick´e

Neurˇcitost

inteligentn´ı u ´ˇcastn´ık - vyb´ır´a strategii podle v´yhry neinteligentn´ı u ´ˇcastn´ık - vyb´ır´a strategii n´ahodnˇe s dan´ym rozdˇelen´ım pravdˇepodobnosti (rozhodov´an´ı pˇri riziku), nebo vyb´ır´a podle pˇredem nezn´am´eho rozdˇelen´ı (rozhodov´an´ı pˇri neurˇcitosti) p - inteligentn´ı u ´ˇcastn´ık - pro p = 0 je inteligentn´ı, pro p = 1 neinteligentn´ı, jinak pˇri rozhodov´an´ı dˇel´a n´ahodn´y pokus a s pravdˇepodobnost´ı p se bude rozhodovat jako inteligentn´ı, s pst. (1 − p) jako neinteligentn´ı Posledn´ı typ je model pro popis situac´ı, kdy u ´ˇcastn´ık dˇel´a chyby nebo jedn´a pod ˇcasov´ym tlakem.

Maticov´e hry

Pˇredpoklady: N = 2, hra s nulov´ym souˇctem, koneˇcn´y poˇcet strategi´ı Hr´aˇci X a Y , jejich prostory strategi´ı X = {1, . . . m}, Y = {1, . . . n}. V´yplatn´ı funkce ZY = −ZX staˇc´ı ps´at pouze jednu. ⇒ z´apis do matice. Pˇr´ıklad: k´amen - n˚ uˇzky - pap´ır podruh´e K N P Kaˇzd´e matici pˇr´ısluˇs´ı nˇejak´a hra.

K 0 -1 1

N 1 0 -1

P -1 1 0

Optim´aln´ı strategie

Optim´aln´ı strategie jsou takov´e, ˇze pokud libovoln´y z hr´aˇc˚ u zvol´ı jinou sn´ıˇz´ı si v´yhru. Pˇresnˇe: Pokud Z1 je v´yplatn´ı funkce hr´aˇce 1. Pak strategie x ˜, y˜ jsou optim´aln´ı pokud Z1 (x, y˜) ≤ Z1 (˜ x, y˜) ≤ Z1 (˜ x, y) pro vˇsechna x ∈ X, y ∈ Y Optim´aln´ı strategie se t´eˇz naz´avaj´ı Nashovy rovnov´aˇzn´e strategie nebo Nashovo ekvilibrium. lev´a nerovnost - nejvˇetˇs´ı prvek ve slupci prav´a nerovnost - nejmenˇs´ı prvek v ˇr´adku

Pˇr´ıklad:

Hr´aˇc X vyb´ır´a maximum ve sloupci (maximalizuje sv˚ uj zisk svoj´ı volbou strategie). Hr´aˇc Y vyb´ır´a minimum v ˇr´adku (minimalizuje soupeˇr˚ uv zisk svoj´ı volbou strategie). X Y 1 2 3

1 4 42 -12

2 4 10 56

3 3 2 2

4 5 -1 2

Takto definovan´e Nashovo ekvilibrium existuje jen pokud m´a matice sedlov´y prvek.

Dalˇs´ı pˇr´ıkady

k´amen - n˚ uˇzky - pap´ır - nem´a sedlov´y bod = Nashovo ekvilibrium K N P

K 0 -1 1

N 1 0 -1

P -1 1 0

Sm´ıˇsen´e strategie C´ıl: Popsat optim´aln´ı strategie i pro maticov´e hry bez sedlov´eho bodu. (napˇr. KNP) • Za sm´ıˇsenou strategii x ˆ oznaˇc´ıme n´ahodnou veliˇcinu s hodnotami v

mnoˇzinˇe strategi´ı X. • Kaˇ zd´a takov´a n´ahodn´a veliˇcina je urˇcena ˆi P pravdˇepodobnostmi x

jednotliv´ych strategi´ı xi ∈ X. Pˇriˇcemˇz

x ˆi = 1.

• Sm´ıˇsen´ a strategie je tedy pops´ana vektorem pravdˇepodobnost´ı.

ˆ je mnoˇzina vˇsech tˇechto n´ahodn´ych • Prostor sm´ıˇsen´ ych strategi´ı X veliˇcin resp. rozdˇelen´ı pravdˇepodobnosti. V´yplatn´ı funkce pro sm´ıˇsen´e strategie x ˆ = (ˆ x1 , . . . , x ˆ n )T , yˆ = (ˆ y1 , . . . , yˆn )T je stˇredn´ı hodnota: Z1 (ˆ x, yˆ) = x ˆT Aˆ y=

n X m X

x ˆi Ai,j yˆj

i=1 j=1

kde A je matice p˚ uvodn´ı hry. Nov´a hra se sm´ıˇsen´ymi strategiemi se naz´yv´a sm´ıˇsen´e rozˇs´ıˇren´ı maticov´e hry.

Z´akladn´ı vˇeta o maticov´ych hr´ach

Pro kaˇzd´e sm´ıˇsen´e rozˇs´ıˇren´ı uˇz Nashovo ekvilibrium existuje:

Theorem ˆ y˜ ∈ Yˆ takov´e, ˇze Pro kaˇzdou matici A existuj´ı vektory x ˜ ∈ X, xT A˜ y≤x ˜T A˜ y≤x ˜T Ay

ˆ y ∈ Yˆ . pro vˇsechna x ∈ X,