Normální forma hry - Normal-form game

v herní teorie, normální forma je popis a hra. Na rozdíl od rozsáhlá forma, reprezentace v normálním tvaru nejsou grafické per se, ale spíše představují hru formou a matice. Tento přístup může být při identifikaci mnohem užitečnější přísně dominují strategie a Nashovy rovnováhy, některé informace jsou ztraceny ve srovnání s reprezentacemi v extenzivním formátu. Normální podoba hry zahrnuje vše vnímatelné a myslitelné strategií a jejich odpovídající výplaty pro každého hráče.

Ve statických hrách kompletní, perfektní informace, reprezentace hry v normální formě je specifikací strategických prostorů hráčů a výplatních funkcí. Strategický prostor pro hráče je soubor všech strategií, které má tento hráč k dispozici, zatímco strategie je úplným akčním plánem pro každou fázi hry, bez ohledu na to, zda tato fáze ve hře skutečně vznikne. Funkce výplaty pro hráče je mapování z křížového produktu strategických prostorů hráčů na sadu výplat daného hráče (obvykle sada reálných čísel, kde číslo představuje kardinál nebo pořadová užitečnost —Často kardinál v reprezentaci normální formy) hráče, tj. Funkce výplaty hráče bere jako svůj vstup strategický profil (to je specifikace strategií pro každého hráče) a poskytuje reprezentaci výplaty jako jeho výstupu.

Příklad

Poskytovaná matice je normální formou reprezentace hry, ve které se hráči pohybují současně (nebo alespoň nesledují pohyb druhého hráče před provedením vlastního) a dostávají výplaty, jak je uvedeno pro kombinace odehraných akcí. Například pokud hráč 1 hraje nahoře a hráč 2 hraje vlevo, hráč 1 dostává 4 a hráč 2 přijímá 3. V každé buňce představuje první číslo výplatu hráči v řadě (v tomto případě hráč 1) a druhé číslo představuje výplatu hráči ve sloupci (v tomto případě hráči 2).

Další zastoupení

Částečná topologie her pro dva hráče a dvou strategií, včetně her jako Vězňovo dilema, Lov jelenů, a Kuře

Často, symetrické hry (kde výplaty nezávisí na tom, který hráč si vybere každou akci) jsou reprezentovány pouze jednou výplatou. Toto je výplata pro hráče v řadě. Například výplatní matice vpravo a vlevo dole představují stejnou hru.

Topologický prostor her se souvisejícími výplatními maticemi lze také mapovat, přičemž sousední hry mají nejpodobnější matice. To ukazuje, jak přírůstkové motivační změny mohou změnit hru.

Použití normální formy

Dominované strategie

Matice výplat usnadňuje eliminaci dominují strategie, a obvykle se používá k ilustraci tohoto konceptu. Například v vězňovo dilema, můžeme vidět, že každý vězeň může buď „spolupracovat“, nebo „defektovat“. Pokud přesně jeden z vězňů poruší, snadno vystoupí a druhý vězeň je na dlouhou dobu uzamčen. Pokud se však oba porouchají, budou oba zavřeni na kratší dobu. To lze určit Spolupracovat striktně dominuje Přeběhnout. Jeden musí porovnat první čísla v každém sloupci, v tomto případě 0> −1 a −2> −5. To ukazuje, že bez ohledu na to, co si hráč ve sloupci vybere, si hráč s řadou vybere lépe Přeběhnout. Podobně se porovnává druhá výplata v každém řádku; opět 0> −1 a −2> −5. To ukazuje, že bez ohledu na to, co řádek dělá, sloupec dělá lépe výběrem Přeběhnout. To ukazuje jedinečnost Nashova rovnováha této hry je (Přeběhnout, Přeběhnout).

Postupné hry v normální formě

Rozsáhlá i normální forma ilustrace postupné hry s nedokonalou subgame a dokonalou Nashovou rovnováhou označenou červenou, respektive modrou.

Tyto matice představují pouze hry, ve kterých jsou tahy současně (nebo obecněji informacemi) nedokonalý ). Výše uvedená matice nepředstavuje hru, ve které se pohybuje hráč 1, pozorovaný hráčem 2, a poté hráč 2, protože v tomto případě neurčuje každou ze strategií hráče 2. Abychom to reprezentovali sekvenční hra musíme specifikovat všechny akce hráče 2, a to i v případě nepředvídaných událostí, které během hry nikdy nemohou nastat. V této hře má hráč 2 akce, stejně jako dříve, Vlevo, odjet a Že jo. Na rozdíl od dříve, než má čtyři strategie, závislé na akcích hráče 1. Tyto strategie jsou:

1. Vlevo, pokud hráč 1 hraje nahoře a doleva jinak
2. Vlevo, pokud hráč 1 hraje nahoře a vpravo jinak
3. Vpravo, pokud hráč 1 hraje jinak a vlevo
4. Správně, pokud hráč 1 hraje jinak a jinak vpravo

Na pravé straně je normální forma této hry.

Obecná formulace

Aby byla hra v normální podobě, jsou k dispozici následující údaje:

• Existuje konečná množina P hráčů, které označíme jako {1, 2, ..., m}
• Každý hráč k v P má konečný počet čisté strategie

${ displaystyle S_ {k} = {1,2, ldots, n_ {k} }.}$

A čistý strategický profil je sdružení strategií hráčům, to je m-n-tice

${ displaystyle { vec {s}} = (s_ {1}, s_ {2}, ldots, s_ {m})}$

takhle

${ displaystyle s_ {1} v S_ {1}, s_ {2} v S_ {2}, ldots, s_ {m} v S_ {m}}$

A funkce výplaty je funkce

${ displaystyle F_ {i}: S_ {1} krát S_ {2} krát ldots krát S_ {m} rightarrow mathbb {R}.}$

jehož zamýšlenou interpretací je cena udělená jedinému hráči na konci hry. Proto, aby byla hra zcela specifikována, musí být pro každého hráče v sadě hráčů specifikována funkce výplaty P= {1, 2, ..., m}.

Definice: A hra v normální formě je struktura

${ displaystyle G = langle P, mathbf {S}, mathbf {F} rangle}$

kde:

${ displaystyle P = {1,2, ldots, m }}$

je sada hráčů,

${ displaystyle mathbf {S} = {S_ {1}, S_ {2}, ldots, S_ {m} }}$

je m-tuple čistých strategických sad, jedna pro každého hráče, a

${ displaystyle mathbf {F} = {F_ {1}, F_ {2}, ldots, F_ {m} }}$

je m-tuple výplatních funkcí.

Reference

• Fudenberg, D.; Tirole, J. (1991). Herní teorie. MIT Stiskněte. ISBN  0-262-06141-4.
• Leyton-Brown, Kevin; Shoham, Yoav (2008). Základy teorie her: Stručný multidisciplinární úvod. San Rafael, CA: Morgan & Claypool Publishers. ISBN  978-1-59829-593-1.. 88stránkový matematický úvod; zdarma online na mnoha univerzitách.
• Luce, R. D.; Raiffa, H. (1989). Hry a rozhodnutí. Dover Publications. ISBN  0-486-65943-7.
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Multiagentní systémy: Algoritmické, herně teoretické a logické základy. New York: Cambridge University Press. ISBN  978-0-521-89943-7.. Komplexní reference z výpočetní perspektivy; viz kapitola 3. Stahovatelné zdarma online.
• Weibull, J. (1996). Evoluční teorie her. MIT Stiskněte. ISBN  0-262-23181-6.
• J. von Neumann a O. Morgenstern, Teorie her a ekonomické chování, John Wiley Science Editions, 1964. Který byl původně publikován v roce 1944 společností Princeton University Press.