Dominantní strategie

Dominantní strategie je strategie používaná v teorii her, případně ve vícekriteriálním rozhodování. Nazývá se též zjednodušeně dominování. Je to jev, který umožňuje zjednodušit proces hledání optimální strategie hry. Zjednodušení se provede tak, že se z rozhodovací matice předem vyloučí takové strategie, které jsou vždy horší než jiná strategie, a to v případě zvolení jakékoli strategie protihráče. Sníží se tak rozměr matice a je pak snazší nalézt optimální strategii.

Hledání optimální strategie

Pro pochopení pojmu dominantní strategie vysvětleme nejprve, o co se jedná při hledání optimální strategie v teorii her. Mějme situaci, kde vystupuje jeden nebo více hráčů, a tuto situaci nazvěme rozhodovací situací (v terminologii teorie her se jedná o hru v normálním tvaru). +more V rozhodovací situaci hráč vybírá rozhodnutí (v terminologii teorie her se jedná o strategii) z dané množiny přípustných rozhodnutí a počítá při tom s určitým důsledkem (v terminologii teorie her se jedná o výhru). Hráč se snaží, aby důsledek jeho rozhodnutí (tedy výhra jím zvolené strategie) byl co nejpříznivější. To je základní předpoklad v teorii her - hráči jsou racionální a maximalizují hodnotu své výplatní funkce. Další předpoklad teorie her je, že hráči mají dokonalé informace, takže znají všechny přípustné strategie protihráče i jejich výplatní funkce.

Dělení rozhodovacích situací se dvěma účastníky

Hra může být buď konfliktní, nebo nekonfliktní. Pokud výhra je závislá nejen na zvolené strategii prvního hráče ale i na strategii protihráče, jedná se o konfliktní hru, jinak jde o hru nekonfliktní. +more Konfliktní hry se dále rozdělují na antagonistické (hra s konstantním součtem) a neantagonistické (hra s nekonstantním součtem), přičemž v antagonistickém konfliktu první hráč získává právě to, co protihráč ztrácí. Jejich zájmy jsou čistě protikladné. Naproti tomu v neantagonistických konfliktech není zájem jednoho hráče v přímém protikladu se zájmem protihráče. Oba hráči sice sledují své vlastní zájmy, ale některé strategie mohou být výhodné pro oba dva. Zde je potom nutné odlišit hry, kde je možné s protihráčem před volbou strategie uzavírat závazné smlouvy - kooperovat, a v jakých případech to možné není - např. protože by se dodržení smlouvy nedalo vynutit.

V nekonfliktní hře je situace s hledáním optimální strategie nejjednodušší. Poněvadž výhra je závislá pouze na strategii jednoho hráče, spočívá výběr optimální strategie v nalezení takové strategie, při které je pro hráče zajištěna maximální výhra. +more V antagonistických konfliktech je situace složitější, optimální strategii určujeme pomocí výplatní matice. V matici hledáme tzv. sedlový bod, tedy prvek, který je současně nejmenší na řádku a největší ve sloupci (za předpokladu, že uvažujeme nejběžnější podobu hry, kdy první hráč má své výhry v řádcích a snaží se je maximalizovat, zatímco strategie druhého hráče jsou určené sloupci a v nich se snaží výhry prvního hráče minimalizovat). Nalezený sedlový bod je potom cenou hry a řádek, ve kterém se nachází je optimální strategií prvního hráče a sloupec určuje optimální strategii druhého hráče.

Obr.1: Matice s vyznačeným sedlovým bodem a optimálními strategiemi

Na obrázku je sedlový bod vyznačen v červeném čtverečku a optimální strategie obou hráčů vyznačeny šipkou. Takto nalezené optimální strategie představují tzv. +more Nashovu rovnováhu v ryzích strategiích. Žádný hráč, který se odchýlí od takovýchto optimálních strategií, si nemůže polepšit. Pro výplatní funkce hráčů totiž platí následující nerovnice:.

f_1 (x,y^O ) \leq f_1 (x^O,y^O )

f_2 (x^O,y) \leq f_2 (x^O,y^O )

kde, f_1 je výplatní funkce prvního hráče a f_2 je výplatní funkce druhého hráče, x je libovolná strategie prvního hráče, x^O je optimální strategie prvního hráče, y je libovolná strategie druhého hráče a y^O je optimální strategie druhého hráče.

Samozřejmě může nastat také situace, kdy v matici nalezneme více sedlových bodů nebo naopak žádný sedlový bod. V případě více sedlových bodů existuje i více alternativních optimálních strategií. +more V případě, že není nalezen žádný sedlový prvek, neexistuje Nashova rovnováha v ryzích strategiích a musíme použít smíšeného rozšíření maticové hry.

Dominantní strategie v antagonistickém konfliktu

V každém případě však ještě před zahájením hledání sedlového bodu si můžeme matici zjednodušit pomocí dominování. Připomeňme, že první hráč se snaží maximalizovat svou výhru a v antagonistickém konfliktu pak tyto výhry prvního hráče jsou ztrátami pro jeho protihráče, které se on snaží zase minimalizovat. +more Strategie prvního hráče jsou v řádcích a strategie druhého hráče ve sloupcích. První hráč jistě nebude volit takový řádek, kde jsou všechny hodnoty menší než odpovídající hodnoty v jiném řádku. Analogicky bude postupovat i druhý hráč, pokud v matici bude existovat sloupec, kde budou všechny hodnoty vyšší než odpovídající hodnoty v jiném sloupci, tento sloupec nebude hráč nikdy volit.

Aplikace dominantní strategie

Zabývejme se nejdříve strategiemi prvního hráče. Strategie, která vede k menším výhrám při jakékoli strategii protihráče, se nazývá dominovaná strategie, je to ten řádek, kde jsou odpovídající hodnoty vždy nižší než v jiném řádku. +more Říkáme, že dominovaná strategie je dominována dominující strategií, tedy takovým řádkem, kde jsou odpovídající hodnoty vždy vyšší než v dominovaném řádku. Silně dominované strategie nebudou nikdy optimální strategií, proto je možné je z matice vynechat. Sníží se tak rozměr matice a rychleji bude možné nalézt optimální strategie.

Aplikujeme dominování na výše uvedenou matici, kde jsme hledali sedlový bod:

Obr.2: Dominované řádky vyznačeny přeškrtnutím

Na obrázku č. 2 vidíme matici se dvěma dominujícími a dvěma dominovanými strategiemi prvního hráče. +more V druhém řádku jsou hodnoty výhry vždy nižší než ve třetím řádku a v pátém řádku jsou vždy nižší než ve čtvrtém řádku. Třetí a čtvrtý řádek je tedy dominující a druhý a pátý řádek je dominovaný. Dominované řádky jsou dominované strategie a můžeme je tedy z matice vynechat. Získáme tak jednodušší matici o třech řádcích:.

Obr.3: Matice bez dominovaných řádků

Pokračujme nyní v dominování z hlediska druhého hráče. Strategie, která vede k větším ztrátám při jakékoli strategii prvního hráče, se nazývá dominovaná strategie, je to ten sloupec, kde jsou odpovídající hodnoty vždy vyšší než v jiném sloupci. +more Opět říkáme, že dominovaná strategie je dominována dominující strategií, tedy takovým sloupcem, kde jsou odpovídající hodnoty vždy nižší než v dominovaném sloupci:.

Obr.4: Dominované sloupce vyznačeny přeškrtnutím

Na obrázku č. 4 vidíme matici s jednou dominující a dvěma dominovanými strategiemi. +more V prvním a pátém sloupci jsou hodnoty ztráty vždy vyšší než ve třetím sloupci. Pátý sloupec a dominuje oba dominované sloupce - první i pátý. Dominované sloupce jsou dominované strategie a můžeme je tedy také z matice vynechat. Vznikne matice o rozměru 3x3, která neobsahuje už žádné další dominované strategie, a její sedlový bod je stále stejný:.

Obr.5: Matice s vynechanými dominovanými strategiemi

Dominantní strategie ve smíšeném rozšíření hry

Na rozdíl od řešení v ryzích strategiích, které zdaleka ne u každé hry lze nalézt, v případě, že budeme hru řešit v jejím smíšeném rozšíření, rovnovážné řešení vždy existuje. Každá maticová hra má Nashovo rovnovážné řešení ve smíšených strategiích. +more Optimální strategie se v tomto případě získává řešením úlohy lineárního programování pomocí simplexové metody . Pokud však má matice pouze dva řádky nebo pokud má dva sloupce, je možné použít grafickou metodu, která lze využít pouze pro dvě proměnné. Pokud tedy pomocí dominování snížíme rozměr matice až na m x 2 nebo 2 x n, zajistíme si možnost použití grafického řešení.

A jak se konkrétně využívá dominování v případě smíšeného rozšíření maticové hry. Smíšené strategie jsou rozložením pravděpodobností na prostoru ryzích strategií, udávají tak vlastně pravděpodobnosti, s jakými se při dokonalé racionalitě mají jednotlivé strategie volit. +more Všechny dominované strategie mají přiřazenou vždy nulovou pravděpodobnost. Dominování lze tedy při smíšených strategiích využít dvěma způsoby. Buď přímo v simplexové metodě, kde dominovaným řádkům a sloupcům přiřadíme pravděpodobnost 0, nebo ještě před použitím simplexové metody vynecháme z matice všechny dominované řádky a sloupce jako jsme vysvětlili na příkladě výše a dále pro výpočty použijeme zjednodušenou matici. Cena hry se takovým vynecháním dominovaných strategií nemění. V praxi za nás simplexovou metodou úlohu lineárního programování vyřeší speciální software a přiřadí tak dominovaným strategiím nulové pravděpodobnosti automaticky. Pozor potom ale na vyhodnocení, neplatí totiž obrácený vztah, že by každá strategie s nulovou pravděpodobností byla dominovaná.

Dominantní strategie v neantagonistickém konfliktu

V případě neantagonistických konfliktů probíhá dominování principiálně stejně jako v antagonistických konfliktech. Jen s tím, že se buď využívá samostatných matic pro každého hráče, nebo se v jedné matici objevují vždy dvě hodnoty - jedna pro prvního hráče a druhá pro druhého. +more A protože už každý z hráčů má v matici své hodnoty výher, snaží se je oba maximalizovat (nikoli, že druhý hráč se snaží o minimalizaci, jako tomu bylo v případě antagonistických konfliktů):.

Obr.6: Dvojmatice s vyznačenými dominovanými strategiemi

Na obrázku č. 6 vidíme dvojmatici hry s nekonstantním součtem (neantagonistický konflikt) a vedle je dvojmatice převedena na dvě samostatné matice (v různých učebnicích se používá různý zápis). +more Je nutné mít pořád na paměti, že i v případě dvou matic se u druhého hráče stále strategie určují pomocí sloupců. Na obrázku jsou opět dominované strategie vyznačeny přeškrtnutím. Zjednodušená matice bez dominovaných strategií je na následujícím obrázku:.

Obr.7: Dvojmatice s vynechanými dominovanými strategiemi

Typy dominovanosti

Silná (striktní) dominovanost (strict domination)

Strategie je silně dominovaná tehdy, když je ostře horší než jiná strategie při jakékoli strategii protihráče. Je zde velmi důležité slovo ostře. +more U tohoto typu se požaduje, aby všechny hodnoty dominovaného řádku byly ostře menší než u dominujícího řádku a aby všechny hodnoty u dominovaného sloupce byly ostře větší než u dominujícího sloupce.

Strategie_{siln\breve{e}.dominovan\acute{a}}

Slabá dominovanost (weak domination)

Aby byla strategie slabě dominovaná, stačí, aby byla stejná nebo horší než dominující strategie. Všechny hodnoty dominovaného řádku musí být menší nebo stejné jako u dominujícího řádku a všechny hodnoty u dominovaného sloupce musí být větší nebo stejné jako u dominujícího sloupce.

Strategie_{slab\breve{e}.dominovan\acute{a}} \leq Strategie_{dominuj\acute{i}c\acute{i}}

Pro ilustraci uveďme příklad z knihy Martina J. Osborna : Přijíždíte v autě na křižovatku, kde právě svítí červená. +more Silnice je rozdělena na dva pruhy, levý je prázdný, v pravém pruhu stojí modrý automobil. Modrý automobil může jet rovně nebo zahnout doprava. Pokud bude zahýbat doprava, musí dát přednost přecházejícím chodcům. Stojíte před rozhodnutím, do jakého pruhu se zařadit. Samozřejmě intuitivně vyberete levý prázdný pruh. Je to proto, že výběr pravého pruhu je silně dominován výběrem levého pruhu. I kdyby modrý automobil nezatáčel, ale jel rovně, vždy by zařazení do pravého pruhu znamenalo zdržení oproti levému pruhu. V případě, že v pravém pruhu bude stát modrý automobil a k tomu v levém pruhu červený automobil, a budete se znovu rozhodovat, do jakého pruhu se zařadíte, možná už budete aspoň sekundu váhat, ale opět zvolíte levý pruh. Výběr pravého pruhu je v tomto případě jen slabě dominován výběrem levého pruhu. Modrý automobil totiž může odbočovat - v tom případě by zvolení pravého pruhu bylo horší, ale může jet také rovně - v tom případě by výběr pravého pruhu vedl ke stejnému výsledku jako levý pruh.

Problémy slabé dominovanosti

Slabá dominovanost přináší technické problémy při eliminaci matice, protože pro vznik slabé dominovanosti záleží na pořadí, ve kterém dominuje své strategie protihráč. Problém se slabou dominovaností vyvstává také v případě slabé Nashovy rovnováhy (tedy v případě že matice obsahuje více sedlových bodů). +more Strategie, kde se nachází slabá Nashova rovnováha, totiž může být často slabě dominovaná a její eliminací bychom si vyloučili možné optimální řešení. Proto se v praxi využívá v podstatě jen silná dominovanost.

Hry řešitelné pomocí opakované eliminace silně dominovaných strategií

Pokud lze ve hře postupně odebírat dominované strategie, až zbude pouze jedna jediná strategie pro každého hráče, je hra řešitelná pomocí opakované eliminace silně dominovaných strategií. Nemusíme v jednom kroku odebrat všechny dominované strategie jednoho hráče, naopak pokud odebereme určitý dominovaný řádek a potom určitý dominovaný sloupec, objeví se mezi řádky další dominovanost. +more A takto v případě hry řešitelné opakovanou eliminací silně dominovaných strategií postupujeme až ke stavu, kdy v matici zůstane jedna optimální strategie pro každého hráče. Při odebírání silně dominovaných strategií nezáleží na pořadí eliminovaných strategií. Oproti tomu, jak už bylo zmíněno výše, při odebírání slabě dominovaných strategií na pořadí eliminace záleží.

Dominování ve známých hrách

Vězňovo dilema

Ve vězňově dilematu je strategie zapírání silně dominovaná strategií prásknutí. Ať už bude protihráč volit jakoukoli strategii (zapírat nebo práskat), vždycky je pro prvního hráče výhodnější práskat - v případě protihráčova zapírání dostane 0 let za mřížemi oproti 1 roku, kdyby také mlčel, v případě protihráčova prásknutí dostane 5 let oproti 10 letům, kdyby mlčel. +more Proto nakonec při plné racionalitě zúčastněných a při nemožnosti kooperace hra dopadne tak, že budou oba hráči práskat, protože zapírání je dominovaná strategie a bude z matice vyloučena. Vězňovo dilema je příklad hry řešitelné opakovanou eliminací silně dominovaných strategií:.

Obr.8: Dominované strategie ve Vězňově dilematu

Bitva pohlaví

Naopak v konfliktní situaci, která je v teorii her nazývána souboj pohlaví, nejsou žádné dominující ani dominované strategie. Pokud by tam byly, tak by se z rozhodování vyloučily a situace by rázem přestala být „bitvou“.

Obr.8: Bitva pohlaví neobsahuje žádné dominované strategie

Dominantní strategie ve vícekriteriálním rozhodování

Většina lidských rozhodnutí je založena na vícekriteriálním hodnocení variant. Například rozhodování, jaký mobilní telefon si koupit. +more V tomto případě budou variantami jednotlivé značky telefonů a kritérii například cena, hmotnost, počet pokročilých funkcí a výdrž baterie. Některá kritéria jsou maximalizační, jiná naopak minimalizační. Mezi cíle vícekriteriálního rozhodování patří výběr jedné z variant - tzv. kompromisní varianta, uspořádání variant a klasifikace variant.

Varianty mohou mít mezi sebou různé vztahy: * varianta A dominuje variantu B, pokud jsou všechna kritéria varianty A výhodnější nebo maximálně stejná jako kritéria varianty B. Ovšem varianty nesmějí být shodné ve všech kritériích. +more * varianta B dominuje variantu A, pokud jsou všechna kritéria varianty B výhodnější nebo maximálně stejná jako kritéria varianty A. Opět nesmějí být varianty shodné ve všech kritériích. * varianta A a varianta B jsou navzájem nedominované.

Při hledání kompromisní varianty by se měl rozhodovatel soustředit na nedominované varianty, tedy na takové, k nimž neexistuje varianta, která by je dominovala. Nedominovaných variant však bohužel bývá při rozhodování více, a proto existuje několik metod, jak vybrat ze zbývajících variant tu pravou. +more Mezi metody patří například Metoda pořadí, Budovací metoda nebo Fullerův trojúhelník . I tak ale dominování při řešení úloh vícekriteríálního hodnocení variant může velmi usnadnit práci a existuje i spousta úloh, které lze vyřešit jen právě pomocí dominantních strategií.

Aplikace dominantní strategie

V tabulce je příklad úlohy vícekriteriálního hodnocení variant se třemi variantami a čtyřmi kritérii. První dvě kritéria jsou minimalizační, to znamená, čím menší hodnota, tím lépe. +more Poslední dvě kritéria jsou maximalizační, čím vyšší jsou hodnoty, tím lépe. Varianta Nokia v tomto případě dominuje variantu Siemens, protože všechna její kritéria jsou výhodnější. Dominovanou variantu Siemens tedy můžeme pro účely rozhodování vypustit. Zbylé dvě varianty Nokia a Samsung jsou nedominované a musíme se mezi nimi rozhodnout pomocí k tomu určených metod.

Stejného principu se potom využívá i v úlohách vícekriteriálního programování.

Reference

Související články

Teorie her * Strategie (teorie her) * John Nash * Nashova rovnováha * Equilibrium * Vězňovo dilema

Kategorie:Teorie her