1 Hry v normální formě Hra v normální formě je trojice G = (N, (Xi)ie^, (««)) sestávající z • množiny hráčů N = {1,2,... ,n},n > 2, • neprázdných množin strategií Xi, • výherních funkcí u,i : YííeN ~~^ Prvky množiny n^jv-^ nazýváme situace. Každá situace je tedy určena volbou jedné strategie každým z hráčů. Předpokládáme, že hráči vybírají strategie současně či bez znalosti volby ostatních hráčů. Dále předpokládáme úplnou informaci o hře, tj. všem hráčům jsou známy všechny výherní funkce Ui. Cílem každého hráče i je maximalizovat itj. Neprázdnou podmnožinu S C N nazýváme koalice. Konvence: Je-li x = (x1}..., xn) situace, n— 1-tici (x1}..., xi+1,..., xn) vzniklou vynecháním i-té složky označíme jako rr_j. Dvojicí (xí,x_í) rozumíme situaci, kde do x_i vložíme x,i na i-tou pozici. Jedná se tedy o situaci vzniklou z x nahrazením Označme dále xs = l[xl, ies případně X_j = Xn-^j. Strategie x E Xi dominuje strategii x G XÍ7 pokud (Vy G X-j) Ui(x,y) > u,t(x,y) a alespoň pro jedno y je nerovnost ostrá. U striktního dominování jsou všechny nerovnosti ostré. Hra s konstantním součtem: (3c G R)(Wx G XN,j G N) ^u^x) = c. ieN Hra s nulovým součtem je hra s konstantním součtem, kde c = 0. 1 Konvence: Ve hře dvou hráčů xÍ7 x2, uÍ7 u2 zapisujeme jako x,y,u,v. Nechť n = 2. Symetrická hra: X = Y a (Var,y G X)u(x,y) = v(y,x). (Výměna rolí dává stejnou hru.) Antagonistická hra: (Vx,x e X,y,y eY)(u(x,y) v(x,y)). (Co je lepší pro jednoho, je horší pro druhého.) Bimaticová hra: X, Y jsou konečné. Maticová hra: Bimaticová s nulovým součtem. Situace x dominuje (podle Pareta) situaci x, pokud (Vi G N)uí(x) > Uí(xí) a alespoň pro jedno i je nerovnost ostrá. (Žádný z hráčů si nepohorší a aspoň jeden si polepší.) Situace x se nazývá Nashova rovnováha, pokud (Vi G N,ži G Xí)uí(xí,X-í) < Ui(x). (Žádný hráč si změnou své strategie nepolepší.) Strategií Xi si hráč i zaručuje výhru míyex-iU(x,y). Dolní hodnotou rozumíme číslo sup^g^ iníyex_i u(x,y) (supremum hodnot, které si hráč zaručuje svými strategiemi). Horní hodnotou nazýváme číslo iníyex_i sup^g^ u(x, y). Nejlepší protihra pro y G X_j je strategie x G XÍ7 v níž nabývá u(x,y) svého maxima. 2 1.1 Pravděpodobnostní rozšíření Uvažujme Xi jako Hamelovy báze vektorových prostorů a nechť X* zde označují konvexní obaly Xi. Tzn. každý prvek Xi G X* lze jednoznačně psát jako pro Xíj G Xi, a,ij > 0, aiľ + ... + a,^. = 1. Položme pak Ui iX) ^ ^ ■ ■ ■ (%njnu(xljij ■ ■ ■ i xnjn)- l