Michaela Tichá. Univerzita Karlova v Praze Matematicko-fyzikální fakulta. Katedra pravděpodobnosti a matematické statistiky

Univerzita Karlova v Praze Matematicko-fyzikáln´ı fakulta

´ PRACE ´ DIPLOMOVA

Michaela Tichá V´ıcekriteri´ aln´ı hry Katedra pravdˇepodobnosti a matematické statistiky

Vedouc´ı diplomové práce: Doc. RNDr. Petr Lachout, CSc. Studijn´ı program: Matematika Studijn´ı obor: Pravdˇepodobnost, matematická statistika a ekonometrie

Praha 2012

Podˇekován´ı: Chtˇela bych podˇekovat vedouc´ımu diplomové práce, doc. RNDr. Petru Lachoutovi, CSc., za poskytnuté rady a pˇripom´ınky a pˇredevˇs´ım za poskytnutou volnost ve v´ ybˇeru tématu i zp˚ usobu jeho zpracován´ı. Dále bych chtˇela podˇekovat mamince, tat´ınkovi a partnerovi za mnohé rady pˇri práci i do ˇzivota.

Prohlaˇsuji, ˇze jsem tuto diplomovou práci vypracovala samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u, literatury a dalˇs´ıch odborn´ ych zdroj˚ u. Beru na vˇedom´ı, ˇze se na moji práci vztahuj´ı práva a povinnosti vypl´ yvaj´ıc´ı ze zákona ˇc. 121/2000 Sb., autorského zákona v platném znˇen´ı, zejména skuteˇcnost, ˇze Univerzita Karlova v Praze má právo na uzavˇren´ı licenˇcn´ı smlouvy o uˇzit´ı této práce jako ˇskoln´ıho d´ıla podle §60 odst. 1 autorského zákona.

V Praze dne 22.3.2012

Podpis autorky

Název práce: V´ıcekriteriáln´ı hry Autor: Michaela Tichá Katedra: Katedra pravdˇepodobnosti a matematické statistiky Vedouc´ı diplomové práce: Doc. RNDr. Petr Lachout, Csc., Katedra pravdˇepodobnosti a matematické statistiky Abstrakt: Diplomová práce pojednává o konceptech ˇreˇsen´ı v´ıcekriteriáln´ıch her. V´ıcekriteriáln´ı hra je speciáln´ı pˇr´ıpad z teorie her, kdy v´ yplatn´ı funkce alespoˇ n jednoho hráˇce je vektor, a hráˇc chce maximalizovat vˇsechna kritéria zároveˇ n. Práce je rozˇclenˇena do ˇctyˇr kapitol. Nejprve je pˇredloˇzeno nˇekolik motivaˇcn´ıch pˇr´ıklad˚ u. Poté je nast´ınˇena historie v´ıcekriteriáln´ıch her. Následuje teoretická kapitola, která obsahuje 5 podkapitol - zaveden´ı nov´ ych pojm˚ u; rovnováˇzné body v jistém smyslu omezen´ ych pˇr´ıklad˚ u her dvou hráˇc˚ u; hledán´ı rovnováˇzn´ ych bod˚ u pomoc´ı skalarizace vektorové v´ yplatn´ı funkce; koncept hledán´ı tzv. ideáln´ıch rovnováˇzn´ ych bod˚ u; srovnán´ı metod. Dále je posledn´ı koncept ˇreˇsen´ı názornˇe demonstrován na reálném pˇr´ıkladˇe. Nakonec je zaˇrazena kapitola s nov´ ymi teoretick´ ymi poznatky t´ ykaj´ıc´ımi se ˇreˇsen´ı v ˇcist´ ych strategi´ıch. Kl´ıˇcová slova: v´ıcekriteriáln´ı hry, teorie her, vektorová v´ yplatn´ı funkce

Title: Multicriteria games Author: Michaela Tichá Department: Department of Probability and Mathematical Statistics Supervisor: Doc. RNDr. Petr Lachout, Csc., Department of Probability and Mathematical Statistics Abstract: The concern of this thesis is to discuss different multicriteria games solution concepts. Multicriteria game is a special case from the game theory if the payoff function of at least one player is a vector and the player wants to maximize all the criteria at the same time. The thesis is divided into four chapters. In the first instance a few motivation examples are introduced. Subsequently the history of the multicriteria games is mentioned. The theoretical chapter follows. It contains five sections - introduction of new definitions; the structure of the set of equilibria for two person multicriteria games; searching equilibria points by the help of scalarization of the vector-valued function; introduction of ideal equilibria points and ways how to find them; the comparison of used methods. The last solution concept is demonstrated by the real example. Finally a theoretical chapter with new results is included. Keywords: multicriteria games, game theory, vector payoff

Obsah ´ Uvod

2

1 Motivace 1.1 Konkurence mezi organizacemi . . . . . . . . . . . . . . . . . . . . 1.2 Veˇrejné statky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Volebn´ı boj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 4 5 5

2 Historie

9

3 Teoretick´ e koncepty 3.1 Základn´ı pojmy . . . . . . . . . 3.2 Struktura ˇreˇsen´ı hry dvou hráˇc˚ u 3.3 Skalarizace v´ yplatn´ı funkce . . . 3.4 Ideáln´ı rovnováˇzné body . . . . 3.5 Srovnán´ı . . . . . . . . . . . . .

. . . . .

11 11 15 23 28 32

4 Aplikace 4.1 Sestaven´ı u ´lohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˇ sen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Reˇ 4.3 Anal´ yza v´ ysledk˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . .

34 34 40 48

5 Teoretick´ e v´ ysledky ˇ 5.1 Reˇsen´ı v ˇcist´ ych strategi´ıch . . . . . . . . . . . . . . . . . . . . . .

53 53

Z´ avˇ er

66

Seznam pouˇ zit´ e literatury

68

1

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

´ Uvod Kaˇzd´ y den se ocitáme v situac´ıch, v nichˇz se mus´ıme rozhodnout pro jednu z moˇznost´ı tak, abychom z´ıskali co nejv´ıce. Pokud je v´ ysledek závisl´ y pouze na nás ˇci nˇejak´ ych nepˇredv´ıdateln´ ych vlivech, b´ yvá rozhodován´ı snazˇs´ı neˇz v situac´ıch, kdy v´ ysledek ovlivn´ı i nˇekdo jin´ y. B´ yvá ovˇsem velmi ˇcasté, ˇze oproti nám rozhoduje závoveˇ n dalˇs´ı ˇclovˇek ˇci lidé, které zase zaj´ımá co nejvˇetˇs´ı prospˇech z jejich strany. Zde pak pˇricház´ı ke slovu teorie her. Teorie her se zab´ yvá mnoˇzstv´ım rozhodovac´ıch situac´ı, v nichˇz proti sobˇe stoj´ı v´ıce hráˇc˚ u a kaˇzd´ y se snaˇz´ı maximalizovat sv˚ uj prospˇech. Mohou to b´ yt hry v pravém slova smylu, ale také r˚ uzné konfliktn´ı situace napˇr´ıklad mezi obchodn´ımi spoleˇcnostmi, politick´ ymi stranami, biologick´ ymi druhy apod. Kromˇe bˇeˇzn´ ych standardn´ıch konflikt˚ u, ve kter´ ych hráˇci maximalizuj´ı jedno kritérium (nˇejak´ y zisk - finanˇcn´ı ˇci jin´ y), se vˇsak ˇcasto setkáváme se situacemi, kdy alespoˇ n jeden z hráˇc˚ u rozhoduje na základˇe v´ıce kritéri´ı, jeˇz chce maximalizovat zároveˇ n. Nˇekdy lze zisk z kritéri´ı jednoduˇse seˇc´ıst (napˇr. prodává-li firma dva produkty a chce maximalizovat zisk z nich, lze vytvoˇrit jediné kritérium jako souˇcet zisk˚ u z jednotliv´ ych produkt˚ u), vˇetˇsinou to vˇsak nelze. Proto zde byla aplikována teorie v´ıcekriteriáln´ı optimalizace do teorie her a vznikla tak nová teorie v´ıcekriteriáln´ıch her. Ta se zab´ yvá hledán´ım v urˇcitém smyslu rovnováˇzn´ ych bod˚ u her, kdy alespoˇ n jeden hráˇc má v´ıce neˇz jednu v´ yplatn´ı funkci. Z tohoto d˚ uvodu se v´ıcekriteriáln´ım hrám také ˇcasto ˇr´ıká hry s vektorovou v´ yplatn´ı funkc´ı. ˇ dosud nepublikoC´ılem práce je seznámit ˇctenáˇre s pomˇernˇe novou a v CR vanou problematikou v´ıcekriteriáln´ıch her. Jsou zavedeny nové pojmy a definice a pˇredstaveny nˇekteré ze zaj´ımav´ ych koncept˚ u ˇreˇsen´ı. Jeden z koncept˚ u je pak pˇredveden na konkrétn´ım pˇr´ıkladˇe. Nakonec je prezentován nov´ y zp˚ usob ˇreˇsen´ı, kter´ y rychlou cestou nalezne vˇetˇsinu ˇreˇsen´ı v ˇcist´ ych strategi´ıch. Pˇredpokládá se, ˇze se ˇctenáˇr orientuje v základech teorie her a optimalizace. Práce je rozdˇelena do nˇekolika ˇca´st´ı. Nejprve se ˇctenáˇr seznám´ı s nˇekolika motivaˇcn´ımi pˇr´ıklady, které demonstruj´ı, proˇc se zab´ yvat touto problematikou. Následnˇe je zaˇrazen struˇcn´ y historick´ yu ´vod, ze kterého je zˇrejmé, jak velice mlad´ ym tématem v´ıcekriteriáln´ı hry jsou - aˇz teprve v posledn´ıch deseti letech se jim vˇenuje trochu vˇetˇs´ı pozornost. Dále je zpracována teoretická ˇca´st, která pˇredstav´ı nˇekteré publikované koncepty ˇreˇsen´ı. Následuje aplikaˇcn´ı ˇcást, která obsahuje vlastn´ı sestaven´ı pˇr´ıkladu, jeho vyˇreˇsen´ı na základˇe konceptu z teoretické kapitoly a anal´ yzu dosaˇzen´ ych v´ ysledk˚ u. Na závˇer je zaˇrazena kapitola s vlastn´ımi ˇ v´ ysledky. Ctenáˇr se seznám´ı se snadn´ ym zp˚ usobem hledán´ı ˇreˇsen´ı v ˇcist´ ych strategi´ıch. 2

Z odborné literatury byly pouˇzity v´ yhradnˇe novˇe publikované ˇclánky, nebot’ ˇza´dné jiné zdroje doposud nejsou dostupné. Základn´ı informace jsem ˇcerpala z ˇclánk˚ u The Structure of the Set of Equilibria for Two Person Multicriteria Games autor˚ u P. Borma, D. Vermeulena a M. Voornevelda a Ideal Equilibria in Noncooperative Multicriteria Games autor˚ u M. Voornevelda, S. Grahnové a M. Dufwenberga.

3

Kapitola 1 Motivace Teprve v´ıce neˇz deset let poté, co byla vytvoˇrena ucelená teorie her, zaˇcali matematici zkoumat moˇznost v´ıce kritéri´ı. Nyn´ı se pod´ıváme na pár motivaˇcn´ıch pˇr´ıklad˚ u, které je k tomu mohly vést. Oblast´ı, kde lze vyuˇz´ıt hry s v´ıce kritérii, je v bˇeˇzném ˇzivotˇe velmi mnoho. Ukáˇzeme si moˇznost vyuˇzit´ı v konfliktu dvou organizac´ı, v projektován´ı veˇrejn´ ych statk˚ u a v boji volebn´ıch stran o voliˇce.

1.1

Konkurence mezi organizacemi

Konkurenˇcn´ı boj mezi organizacemi, firmami ˇci obchodn´ımi spoleˇcnostmi je jedn´ım z nejvˇetˇs´ıch c´ıl˚ u zkoumán´ı v rámci teorie her. Nejˇcastˇeji se jedná o jednu v´ yplatn´ı funkci - zisk. Moˇznost´ı je vˇsak mnohem v´ıce a mnohdy chtˇej´ı organizace optimalizovat v´ıce c´ıl˚ u zároveˇ n. Ve vˇetˇs´ıch firmách se obvykle objevuj´ı dva ˇcásteˇcnˇe protich˚ udné c´ıle. Majitelé chtˇej´ı co nejvˇetˇs´ı zisk, protoˇze ten jde do jejich kapsy a stává se pro nˇe prioritou. Manaˇzeˇri zase chtˇej´ı co nejvˇetˇs´ı obraty, protoˇze maj´ı pevn´ y plat a jejich prestiˇz závis´ı na tom, jak firma expanduje a jak je známá. Tyto dva c´ıle jdou vˇsak velmi ˇcasto proti sobˇe. Dalˇs´ı moˇznost´ı je, ˇze firmy maj´ı v´ıce sekc´ı, pracuj´ı v r˚ uzn´ ych oblastech. Jednotlivé sekce funguj´ı samostatnˇe, je nutno je zachovat vˇsechny, nejsou-li vyslovenˇe prodˇeleˇcné. Nen´ı tedy moˇzné rozhodovat pouze na základˇe maximalizace celkového zisku, ale firma se snaˇz´ı maximalizovat zisky ve vˇsech oblastech zvláˇst’. V tˇechto pˇr´ıkladech se berou jako hráˇci firmy a jejich v´ yplatn´ı funkce jsou hodnoty jednotliv´ ych kritéri´ı. Prostory strategi´ı jsou obecnˇe r˚ uzné, m˚ uˇze to b´ yt volba vyrobeného mnoˇzstv´ı jednotliv´ ych produkt˚ u, volba dodavatel˚ u, rozhodnut´ı, do ˇceho budou investovány finance firmy apod.

4

1.2

Veˇ rejn´ e statky

V´ıcekriteriáln´ı hry se uplatˇ nuj´ı také v projektován´ı veˇrejn´ ych statk˚ u. Pˇredpokládáme nˇekolik subjekt˚ u. Kaˇzd´ y subjekt vkládá stejné finance do spoleˇcné kasy. Z té je pak financováno a uskuteˇcn ˇováno nˇekolik projekt˚ u. Pˇritom kaˇzd´ y subjekt má jin´ y uˇzitek a zájem o r˚ uzné projekty. Jednotlivé subjekty se pˇritom snaˇz´ı maximalizovat dvˇe v´ yplatn´ı funkce - jednak veˇrejné blaho, které je rovno souˇctu uˇzitk˚ u jednotliv´ ych subjekt˚ u, a zároveˇ n vlastn´ı zisk, kter´ y je roven vlastn´ımu uˇzitku zmenˇsenému o ˇca´stku zaplacenou do spoleˇcného rozpoˇctu vyjádˇrenou v ekvivalentu uˇzitku. Jako konkrétn´ı ukázku si pˇredstav´ıme tˇri mˇesta, která mezi sebou obchoduj´ı. Chtˇej´ı zjednoduˇsit a urychlit dopravu a postavit mezi sebou dálnice. Kaˇzdé dá do rozpoˇctu urˇcitou ˇca´stku, ze které se budou financovat dálnice mezi mˇesty. Kaˇzdé mˇesto má dan´ y uˇzitek z dálnice mezi kaˇzd´ ymi dvˇema mˇesty. Ten závis´ı jednak na tom, s kter´ ymi mˇesty nejv´ıce obchoduje, jednak na tom, která cesta je pro nˇej nejkratˇs´ı. Bude-li napˇr´ıklad realizována dálnice mezi mˇesty A a B a mezi mˇesty B a C, ale nikoli pˇr´ımo mezi mˇesty A a C, budou m´ıt mˇesta A a C z trasy A↔C menˇs´ı uˇzitek, neˇz kdyby byla postavena pˇr´ımá dálnice. Tento uˇzitek bude o to menˇs´ı, o kolik bude trasa A-B-C delˇs´ı neˇz A-C. Zároveˇ n kaˇzdé mˇesto vyjádˇr´ı ˇca´stku, kterou dává do spoleˇcné kasy, v uˇzitku, kter´ y by z té ˇca´stky mˇelo. Nyn´ı se mˇesta mus´ı dohodnout, kolik daj´ı do spoleˇcné kasy a které dálnice budou realizovat. Zohledˇ novat pˇritom budou dvˇe v´ yplatn´ı funkce - veˇrejné blaho a vlastn´ı uˇzitek. Tento pˇr´ıklad je ukázka kooperativn´ı v´ıcekriteriáln´ı hry.

1.3

Volebn´ı boj

Dalˇs´ım zaj´ımav´ ym pˇr´ıkladem je pˇredvolebn´ı boj politick´ ych stran. Jedná se v podstatˇe o speciáln´ı pˇr´ıpad konkurenˇcn´ıho boje dvou organizac´ı. Organizacemi jsou v tomto pˇr´ıpadˇe politické strany. Obvykle má kaˇzdá politická strana dvˇe kritéria - jednak se samozˇrejmˇe snaˇz´ı maximalizovat poˇcet voliˇc˚ u, ale zároveˇ n se snaˇz´ı co nejv´ıce pˇribl´ıˇzit základn´ı politické ideologii své strany. Prostorem strategi´ı je pak zvolen´ y volebn´ı program. U tohoto pˇr´ıkladu si ukáˇzeme, jak konkrétnˇe by mohlo vypadat sestaven´ı volebn´ıho boje jako v´ıcekriteriáln´ı hry. Budeme pˇredpokládat souboj 5 hlavn´ıch politick´ ych stran, jak je v posledn´ıch letech na naˇs´ı politické scénˇe zvykem (byt’ se trochu stˇr´ıdaj´ı). Mˇejme tedy mnoˇzinu pˇeti hráˇc˚ u n = 5, N = {1, 2, 3, 4, 5}. Zvol´ıme 8 základn´ıch oblast´ı, podle nichˇz se rozhoduje nejv´ıce lid´ı: zdravotnictv´ı, sociáln´ı politika, ˇskolstv´ı, danˇe, doprava, ekonomika státu, podpora podnikán´ı a ˇzivotn´ı prostˇred´ı. Pro kaˇzdou oblast urˇc´ıme stupnici 1-10, kaˇzdá volebn´ı strana pak vol´ı u kaˇzdé oblasti stupeˇ n. Vektor tˇechto osmi stupˇ n˚ u je pak zvolená strategie. 5

Ve zdravotnictv´ı stupnici stanov´ıme takto: 1 znamená, ˇze vˇse plat´ı zdravotn´ı pojiˇst’ovny, nezb´ yvá pak mnoho penˇez na financován´ı nov´ ych v´ yzkum˚ u a zaˇr´ızen´ı; 10 znamená, ˇze vˇetˇsinu u ´kon˚ u si plat´ı pacient sám a pen´ıze se investuj´ı do nov´ ych drah´ ych stroj˚ u pro léˇcbu tˇeˇzk´ ych nemoc´ı. Sociáln´ı politika: 1 znamená vysoké sociáln´ı platby, tj. vysoké d˚ uchody, mateˇrské, podpory v nezamˇestnanosti, sociáln´ı dávky atd.; 10 naopak znamená n´ızké sociáln´ı platby. ˇ Skolstv´ ı: 1 znamená zcela bezplatné ˇskolstv´ı, ˇskoln´ı pom˚ ucky k p˚ ujˇcován´ı, pˇr´ıspˇevek na ˇskoln´ı potˇreby pro prvˇ na´ˇcky apod.; 10 znamená zaveden´ı ˇskolného na vysok´ ych ˇskolách, samostatné financován´ı uˇcebnic apod., pen´ıze do ˇskolstv´ı jdou naopak napˇr. na nové poˇc´ıtaˇce a podobná zaˇr´ızen´ı, modern´ı ˇskoln´ı pom˚ ucky atd. Danˇe: 1 znamená vysoké zdanˇen´ı, vysokou m´ıru progresivity, vysoká cla; 10 znamená n´ızké zdanˇen´ı, tzv. rovnou daˇ n, n´ızká cla. Doprava: 1 znamená n´ızké investice do dopravy, 10 naopak vysoké investice do dopravy. Ekonomika: 1 znamená vysoké investice státn´ıho rozpoˇctu a t´ım i vˇetˇs´ı zadluˇzován´ı; 10 znamená malé investice, ale menˇs´ı zadluˇzován´ı. Podpora podnikán´ı: 1 znamená malou podporu podnikán´ı; 10 naopak vysoké investice do podpory podnikán´ı. ˇ Zivotn´ ı prostˇred´ı: 1 znamená nezájem o ˇzivotn´ı prostˇred´ı; 10 naopak velké ohledy na ˇzivotn´ı prostˇred´ı, investice apod. Máme tedy prostor strategi´ı n

X =

n Y

X i,

i=1

kde

                Xi =                 

1 1 1 1 1 1 1 1

            ,          

1 1 1 1 1 1 1 2

            ,          

1 1 1 1 1 1 1 3





          ,...,          

10 10 10 10 10 10 10 9

            ,          

10 10 10 10 10 10 10 10

             .           

Kaˇzdá politická strana tedy m˚ uˇze zvolit jednu mnoˇzinu strategi´ı Xi , jejich celkov´ y 8 poˇcet je 10 . Nyn´ı upˇresn´ıme v´ yplatn´ı funkce. Kaˇzdá strana má dvˇe v´ yplatn´ı funkce.

6

Pod prvn´ı v´ yplatn´ı funkc´ı si pˇredstav´ıme poˇcet voliˇc˚ u, kteˇr´ı ji s takov´ ym programem (za pˇredpokladu zvolen´ ych program˚ u ostatn´ıch stran) zvol´ı. Budeme ˇ brát CR - aktuáln´ı poˇcet obyvatel je nˇeco málo pˇres 10,5 milionu obyvatel, ˇ U ´ z toho pˇribliˇznˇe 8,5 milionu zletil´ ych - pˇribliˇzn´ y poˇcet voliˇc˚ u (jak uvád´ı CS k 31.12.2010). Pˇredpokládejme 60% volebn´ı u ´ˇcast. Prvn´ı v´ yplatn´ı funkce tak m˚ uˇze nab´ yvat hodnot z intervalu [0; 5, 1]. Politická strana se snaˇz´ı dosáhnout co nejvˇetˇs´ıho poˇctu voliˇc˚ u. Pod druhou v´ yplatn´ı funkc´ı si pˇredstav´ıme m´ıru zachován´ı ideologie. Budeme pˇredpokládat, ˇze kaˇzdá strana má svou základn´ı ideologii, s n´ıˇz byla zaloˇzena a ze které vycház´ı. Oznaˇc´ıme ji idx = idxi , kde i ∈ {1, 2, . . . , 8} je oblast a x ∈ {1, 2, . . . , 5} politická strana. Oznaˇc´ıme jeˇstˇe zvolenou strategii strx = strix , kde opˇet i je oblast a x politická strana. M´ıru zachován´ı stranické ideologie politické strany x budeme mˇeˇrit souˇctem kvadratick´ ych odchylek zvolené strategie od základn´ı ideologie: 8 X (idxi − strix )2 , i=1

kde suma bˇeˇz´ı pˇres 8 základn´ıch oblast´ı. Tuto v´ yplatn´ı funkci se politická strana snaˇz´ı naopak minimalizovat. Nyn´ı je jeˇstˇe nutné specifikovat, jak vol´ı voliˇci. Potˇrebujeme algoritmus, podle nˇehoˇz na základˇe zvolen´ ych strategi´ı pˇeti stran z´ıskáme poˇcty voliˇc˚ u kaˇzdé strany. Agentury zab´ yvaj´ıc´ı se pr˚ uzkumy trhu standardnˇe rozdˇeluj´ı voliˇce na základˇe shlukové anal´ yzy do nˇekolika kategori´ı (obvykle napˇr. d˚ uchodci, studenti apod.). Poté se pˇredpokládá, ˇze jednotlivci z kategorie vol´ı stejnˇe. Kaˇzdá kategorie má vlastn´ı osobn´ı preference v kaˇzdé oblasti. Osobn´ı preference se urˇcuj´ı na základˇe pr˚ uzkum˚ u veˇrejného m´ınˇen´ı. Pˇredpokládejme, ˇze tedy máme dan´ ych k kategori´ı voliˇc˚ u, mnoˇzstv´ı voliˇc˚ u v kaˇzdé kategorii wj , j ∈ {1, 2, . . . , k}, a osobn´ı preference kaˇzdé kategorie v 8 oblastech. Osobn´ı preference oznaˇc´ıme prefij , kde i znaˇc´ı oblast a j znaˇc´ı kategorii voliˇc˚ u. Budeme pˇredpokládat, ˇze voliˇci vol´ı pouze na základˇe shody volebn´ıho programu se sv´ ymi osobn´ımi preferencemi. Voliˇci kategorie j tedy vol´ı tu stranu x, pro n´ıˇz bude v´ yraz 8 X 2 prefij − strix i=1

nab´ yvat minima. Pˇredpokládáme, ˇze nenastane situace, ˇze by v´ yraz byl minimáln´ı pro v´ıce stran. U kaˇzdé kategorie je tedy jasné, kterou stranu by zvolili. Kaˇzdá politická strana x tedy chce maximalizovat v´ yraz k X

wj I (j vol´ı stranu x) ,

j=1

7

kde j jsou kategorie a I znaˇc´ı identifikátor. Tedy pˇresnˇeji k X j=1

wj

Y y={1,2,3,4,5}\{x}

I

8 X

prefij

−

i=1

2 strix

<

8 X

prefij

−

2 striy

! .

i=1

Nyn´ı bychom mˇeli pˇresnˇe zadanou v´ıcekriteriáln´ı hru - 5 hráˇc˚ u, kaˇzd´ y má 100 milion˚ u moˇzn´ ych strategi´ı a dvˇe pˇresnˇe zadané v´ yplatn´ı funkce, pˇriˇcemˇz jednu chce maximalizovat a druhou minimalizovat. Pokud bychom potˇrebovali obˇe funkce maximalizaˇcn´ı, je moˇzné k druhé pˇridat minusové znaménko, pak bude u ´loha ekvivalentn´ı s p˚ uvodn´ı. Nyn´ı bychom mˇeli naj´ıt rovnováˇzné body této hry. K tomu je nejprve nutné zavést definici takového rovnováˇzného bodu. Ve tˇret´ı kapitole si ukáˇzeme, ˇze existuje nˇekolik moˇzn´ ych definic. Na tomto m´ıstˇe jeˇstˇe poznamenáme, ˇze v tomto pˇr´ıkladu bylo udˇeláno mnoˇzstv´ı pˇredpoklad˚ u, které v praxi nejsou zcela splnˇeny. To je ovˇsem u ´dˇelem toho, ˇze realita jde málokdy pˇrevést do matematické ˇreˇci bez urˇcit´ ych zjednoduˇsen´ı.

8

Kapitola 2 Historie Modern´ı teorie her byla zavedena prac´ı Neumann and Morgenstern: The Theory of Games and Economic Behavior v roce 1944. Uˇz dˇr´ıvˇejˇs´ı studie se zab´ yvaly tématy okolo teorie her, ale ˇza´dná netvoˇrila precizn´ı ucelenou teorii jako tato. Práce byla pˇredevˇs´ım kompilac´ı pˇredchoz´ıch tez´ı a neobsahovala ˇza´dné nové poznatky. Byly v n´ı vˇsak dokázány nˇekteré dˇr´ıve formulované vˇety. Druhé vydán´ı v roce 1947 pˇrineslo jeˇstˇe nav´ıc rozvoj teorie uˇzitku. V 50. letech v´ yvoj smˇele pokraˇcoval. Pˇrispˇelo velké mnoˇzstv´ı autor˚ u, nejv´ yznamnˇejˇs´ımi osobami se vˇsak stali J. F. Nash a L. S. Shapley. Nash v roce 1950 pˇredstavil svou teorii rovnováˇzného bodu v nekooperativn´ıch hrách ve strategické formˇe. Neomezoval se pouze na hry s nulov´ ym souˇctem jako mnoz´ı jeho kolegové. Zobecnil téˇz minimaxové teorémy i na hry s nenulov´ ym souˇctem. V roce 1953 prezentoval i své v´ ysledky v ˇreˇsen´ı kooperativn´ıch her. Jeho koncepty byly v té dobˇe pˇrevratné a dodnes se z nich vycház´ı pˇri studi´ıch r˚ uzn´ ych nov´ ych situac´ı v teorii her. V roce 1953 publikoval Shapley svou studii, kde dokázal existenci a jednoznaˇcnost kooperativn´ıch model˚ u her n hráˇc˚ u. Prezentoval také spoustu dalˇs´ıch v´ ysledk˚ u jako anal´ yzy volebn´ıch model˚ u, stochastické hry a dalˇs´ı. Shapley byl také velmi d˚ uleˇzitou postavou v teorii v´ıcekriteriáln´ıch her. Nejprve vˇsak v roce 1956 pˇriˇsel D. Blackwell se svou tez´ı Analog of the Minimax Theorem for Vector Payoffs, v n´ıˇz zobecnil minimaxovou vˇetu na v´ıcekriteriáln´ı hry. Ten také jako prvn´ı pouˇzil pojem v´ıcekriteriáln´ı hra (resp. hra s vektorovou v´ yplatn´ı funkc´ı). Nezávisle na nˇem pak v roce 1959 pˇredvedl svou definici Shapley ve své studii Equilibrium Points in Games with Vector Payoffs. V této práci zároveˇ n pˇredstavil koncept hledán´ı rovnováˇzn´ ych bod˚ u, z nˇehoˇz pak vycházeli dalˇs´ı autoˇri, kteˇr´ı se zaˇcali zab´ yvat hrami s v´ıce moˇzn´ ymi nesrovnateln´ ymi kritérii. Zejména v 60. letech pak bylo prezentováno velké mnoˇzstv´ı studi´ı t´ ykaj´ıc´ıch se teorie her, ale hrám s vektorovou v´ yplatn´ı funkc´ı pˇr´ıliˇs mnoho autor˚ u pozornost nevˇenovalo. Za zm´ınku z pozdˇejˇs´ıch let stoj´ı nˇekolik prac´ı. M. Zelen´ y v roce 1976 prezentoval sv˚ uj koncept v´ıcekriteriáln´ıch her Game with Multiple Payoffs, kde se zab´ yval hrami proti pˇr´ırodˇe a hrami dvou hráˇc˚ u s nulovou v´ yplatn´ı funkc´ı. V roce 1985 pˇriˇsel H. W. Corley se svou prac´ı Games with Vector Payoffs, v n´ı dokázal vˇetu o existenci rovnováˇzného bodu pro v´ıcekriteriáln´ı hru dvou hráˇc˚ u.

9

Dále se teori´ı v´ıcekriteriáln´ıch her zab´ yval D. B. Ghose. Ten napsal v roce 1989 spoleˇcnˇe s U. R. Prasadem tezi Solution Concepts in Two-Persons Multicriteria Games, v n´ıˇz pˇredstavil nov´ y koncept ˇreˇsen´ı za pˇredpokladu hry o dvou hráˇc´ıch a srovnal ho s pˇredchoz´ımi. V roce 1991 jeˇstˇe publikoval práci A Necessary and Sufficient Condition for Pareto-Optimal Security Strategies in Multicriteria Matrix Games, ve které dokázal, ˇze urˇcitou skalarizac´ı hry vytvoˇr´ıme hru s jednou vektorovou funkc´ı, jej´ıˇz rovnováˇzné body jsou v urˇcité definici rovnováˇzn´ ymi body p˚ uvodn´ı v´ıcekriteriáln´ı hry. Na druhou uvedenou práci Ghoseho navázali v roce 1998 autoˇri F. R. Fernandez, L. Monroy a J. Puerto ve své studii Multicriteria Goal Games. Zkoumaj´ı v n´ı problémy skalarizace hry a vytvoˇrili tak obecnˇejˇs´ı koncept ˇreˇsen´ı. O ˇctyˇri roky pozdˇeji jeˇstˇe publikovali ve sloˇzen´ı F. R. Fernandez, M. A. Hinojosa, J. Puerto práci Core Solutions in Vector-Valued Games. Zab´ yvaj´ı se zde kooperativn´ımi hrami a aplikuj´ı teorii standardn´ıch kooperativn´ıch her na ty s vektorovou v´ yplatn´ı funkc´ı. Teprve v posledn´ıch deseti letech se v´ıcekriteriáln´ım hrám dostalo vˇetˇs´ı pozornosti. Ze standardn´ı teorie her byly jiˇz hlavn´ı studie vytvoˇreny, a tak mnoz´ı autoˇri zamˇeˇrili svou pozornost na vektorové v´ yplatn´ı funkce. S r˚ uzn´ ymi ˇclánky s nov´ ymi ˇreˇsen´ımi, specifick´ ymi ˇreˇsen´ımi i moˇzn´ ymi aplikacemi se doslova roztrhl pytel. Zkoumaj´ı se r˚ uzné aproximace, uˇzit´ı v soupeˇren´ı organizac´ı ˇci firem, ve volebn´ıch ˇ ast modelech, dále r˚ uzné specifické pˇr´ıpady, které maj´ı jednoduˇsˇs´ı ˇreˇsen´ı apod. C´ z nich je i obsahem této práce.

10

Kapitola 3 Teoretick´ e koncepty 3.1

Z´ akladn´ı pojmy

Nejprve zformulujeme nekooperativn´ı v´ıcekriteriáln´ı hru v´ıce hráˇc˚ u, poté zavedeme nerovnosti dvou vektor˚ u a následnˇe zadefinujeme rovnováˇzné body v´ıcekriteriáln´ı hry. Definice 3.1. Necht’ n ∈ N a N = {1, 2, . . . , n} je mnoˇzina n hráˇc˚ u, Xi je mnoˇzina ˇcist´ ych strategi´ı hráˇce i ∈ N a pro kaˇzdého hráˇce i ∈ N máme v´ yplatn´ı funkci Y ui : Xj −→ Rr(i) , j∈N

která pˇriˇrazuje kaˇzdé kombinaci strategi´ı hráˇc˚ u bod v r(i)-dimenzionáln´ım Euklidovském prostoru, kde r(i) je poˇcet kritéri´ı hráˇce i ∈ N . Mnoˇzinu G = hN, (Xi )i∈N , (ui )i∈N i nazveme v´ıcekriteriáln´ı hra. Obdobnˇe provedeme rozˇs´ıˇren´ı na sm´ıˇsené strategie. Oznaˇcme 4(Xi ) mnoˇzinu sm´ıˇsen´ ych strategi´ı hráˇce i ∈ N . Pro sm´ıˇsenou strategii xi ∈ 4(Xi ), j ∈ Xi oznaˇc´ıme xij pravdˇepodobnost, ˇze hráˇc i odpov´ı ˇcistou strategi´ı j. Definice 3.2. Necht’ G = hN, (Xi )i∈N , (ui )i∈N i je v´ıcekriteriáln´ı hra z definice 3.1. Nyn´ı pod mnoˇzinou strategi´ı (Xi )i∈N uvaˇzujeme mnoˇziny sm´ıˇsen´ ych strategi´ı 4(Xi ) a hru G nazveme sm´ıˇsené rozˇs´ıˇren´ı v´ıcekriteriáln´ı hry. Dále budeme uvaˇzovat pod pojmem v´ıcekriteriáln´ı hra jej´ı sm´ıˇsené rozˇs´ıˇren´ı a mnoˇzinu vˇsech sm´ıˇsen´ ych rozˇs´ıˇren´ı v´ıcekriteriáln´ı hry oznaˇc´ıme Γ. Jeˇstˇe pˇripomeˇ nme, ˇze hru s koneˇcnou mnoˇzinou ˇcist´ ych strategi´ı nazveme koneˇcnou v´ıcekriteriáln´ı hrou a pokud jsou zisky jednoho vˇzdy kompenzovány ztrátami jin´ ych, naz´ yváme hru hrou s nulovým souˇctem. 11

V dalˇs´ı ˇca´sti práce budeme potˇrebovat porovnávat vektory, zavedeme tedy vektorové nerovnosti: Definice 3.3. Necht’ a, b ∈ Rm . Pak a = b a ≥ b a > b

pokud aj ≥ bj pro vˇsechna j ∈ {1, . . . , m} , pokud a = b a a 6= b, pokud aj > bj pro vˇsechna j ∈ {1, . . . , m} .

ˇ Rekneme, ˇze a dominuje b, pokud a > b. Koneˇcnˇe se dostáváme k definici rovnováˇzného bodu v´ıcekriteriáln´ı hry. Budeme pouˇz´ıvat obvyklé oznaˇcen´ı x−i pro mnoˇzinu strategi´ı vˇsech hráˇc˚ u kromˇe hráˇce i: x−i = (x1 , . . . , xi−1 , xi+1 , . . . , xn ). V jednokriteri´ aln´ı hˇre pro Nash˚ uv rovnováˇzn´ y bod plat´ı, ˇze je to strategick´ y proQ fil x ∈ i∈N 4(Xi ), pokud ˇzádn´ y hráˇc nemá alternativn´ı strategii yj ∈ 4(Xj ), pro kterou by jeho v´ yplatn´ı funkce byla (za pˇredpokladu stejn´ ych strategi´ı protihráˇc˚ u) vyˇsˇs´ı, tj. uj (yj , x−j ) > uj (x). Ve v´ıcekriteriáln´ı hˇre plat´ı stejná definice. V´ yplatn´ı funkce jsou vektorové, ale uˇz máme zadefinovány vektorové nerovnosti, a tak m˚ uˇzeme pˇrej´ıt pˇr´ımo k definici. Standardnˇe se pouˇz´ıvaj´ı dvˇe definice - siln´ y rovnováˇzn´ y bod a slab´ y rovnováˇzn´ y bod. Definice 3.4. Slabým rovnováˇzným bodem nazveme strategick´ y profil Y x∈ 4(Xi ), i∈N

pokud pro ˇzádného hráˇce i ∈ N neexistuje strategie x ei ∈ 4(Xi ) taková, ˇze ui (e xi , x−i ) > ui (xi , x−i ). Definice 3.5. Silným rovnováˇzným bodem nazveme strategick´ y profil Y x∈ 4(Xi ), i∈N

pokud pro ˇzádného hráˇce i ∈ N neexistuje strategie x ei ∈ 4(Xi ) taková, ˇze ui (e xi , x−i ) ≥ ui (xi , x−i ). Siln´ y rovnováˇzn´ y bod je v jistém smyslu analogie eficientn´ıho bodu ve v´ıcekriteria´ln´ı optimalizaci. Pro hráˇce je mnohem lepˇs´ım rovnováˇzn´ ym bodem, protoˇze ˇr´ıká, ˇze pro ˇza´dného hráˇce neexistuje jiná strategie, pˇri které by mˇel za dan´ ych strategick´ ych profil˚ u protihráˇc˚ u alespoˇ n jednu v´ yplatn´ı funkc´ı vyˇsˇs´ı a ostatn´ı stejné. Pˇrirozenˇe i kdyˇz je jediné kritérium lepˇs´ı, je pro hráˇce vektor v´ yplatn´ıch funkc´ı lepˇs´ı. Hledán´ı silného rovnováˇzného bodu b´ yvá ovˇsem mnohem nároˇcnˇejˇs´ı, a tak se vyuˇz´ıvá definice slabého rovnováˇzného bodu. Slab´ y rovnováˇzn´ y bod je narozd´ıl od silného rovnováˇzného bodu mnohem slabˇs´ı 12

ˇ ıká nám pouze to, ˇze pro definice, kterou bychom nejsp´ıˇs pˇrirozenˇe nepouˇzili. R´ ˇza´dného hráˇce neexistuje alternativn´ı strategie, pˇri které by mˇel za dan´ ych strategick´ ych profil˚ u protihráˇc˚ u vˇsechny v´ yplatn´ı funkce vyˇsˇs´ı. Pokud vˇsak napˇr. pˇri strategii xi má pˇri daném strategickém profilu protihráˇc˚ u x−i vektor v´ yplatn´ıch funkc´ı (2,2), zat´ımco pˇri strategii xei by mˇel vektor v´ yplatn´ıch funkc´ı (2,100), patˇr´ı do mnoˇziny rovnováˇzn´ ych bod˚ u, jak bod (xi , x−i ), tak bod (xei , x−i ). Poznamenejme, ˇze rovnováˇzn´ ych bod˚ u m˚ uˇze b´ yt a také ˇcasto b´ yvá velmi mnoho. Jeˇstˇe si ukáˇzeme ilustraˇcn´ı pˇr´ıklad. Pˇ r´ıklad 3.6. Uvaˇzujme maticovˇe zadanou hru dvou hráˇc˚ u. Kaˇzd´ y hráˇc má dvˇe v´ yplatn´ı funkce. Hráˇc 1 má strategie M a N, hráˇc 2 má strategie P a Q. Hodnoty v´ yplatn´ıch funkc´ı hráˇce 1 jsou zobrazeny v matici A, hodnoty v´ yplatn´ıch funkc´ı hráˇce 2 v matici B. (1, 1) (0, 3) A= (3, 5) (2, 4) (2, 4) (3, 1) B= (2, 0) (2, 1) To tedy znamená následuj´ıc´ı tabulku v´ yplatn´ıch funkc´ı prvn´ıho hráˇce P Q M (1,1) (0,3) N (3,5) (2,4)

a tabulku v´ yplatn´ıch funkc´ı druhého hráˇce M N

P Q (2,4) (3,1) . (2,0) (2,1)

Zaj´ımá nás, jak je to s rovnováˇzn´ ymi body. Pod´ıváme-li se na tabulku v´ yplatn´ıch funkc´ı hráˇce 1, vid´ıme, ˇze strategie N dominuje strategii M. To znamená, ˇze at’ hráˇc 2 zvol´ı jakoukoli strategii, vˇzdy bude pro hráˇce 1 nejlepˇs´ı zvolit strategii N, hodnota obou v´ yplatn´ıch funkc´ı je v takovém pˇr´ıpadˇe nejlepˇs´ı. Strategie hráˇce 1 v rovnováˇzném bodˇe tedy mus´ı b´ yt nutnˇe ˇcistá strategie N. Kdyby mˇel nenulovou pravdˇepodobnost zvolen´ı strategie M, vˇzdy by existovala lepˇs´ı sm´ıˇsená strategie (vektor (0, 1)), pro niˇz by byla v´ yplatn´ı funkce vˇetˇs´ı ve vˇsech smyslech definice 3.3. Nesplˇ novala by tedy ani jednu definici rovnováˇzného bodu. Hráˇc 1 má tedy v rovnováˇzném bodˇe sm´ıˇsenou strategii (0, 1). U hráˇce 2 je situace zaj´ımavˇejˇs´ı. Hledáme rovnováˇzn´ y bod, a proto se nemus´ıme zab´ yvat hodnotami jeho v´ yplatn´ı funkce v pˇr´ıpadˇe zvolen´ı strategie M hráˇcem 1 (zvol´ı ji s nulovou pravdˇepodobnost´ı). Zaj´ımaj´ı nás tedy pouze vektory (2, 0) pˇri strategii P a (2, 1) pˇri strategii Q. Na prvn´ı pohled vid´ıme, ˇze je pro hráˇce 2 13

v´ yhodnˇejˇs´ı strategie Q. Ta splˇ nuje definici 3.4 i definici 3.5. Je to ale jedin´ y rovnováˇzn´ y bod? Vektor sm´ıˇsen´ ych strategi´ı (0, 1) hráˇce 2 je siln´ y rovnováˇzn´ y bod skuteˇcnˇe jako jedin´ y. Pokud by hráˇc 2 zvolil jakoukoli jinou sm´ıˇsenou strategii, pak by existovala strategie (vektor (0, 1)), pro kterou by byla hodnota vektoru v´ yplatn´ıch funkc´ı vˇetˇs´ı ve smyslu ≥ (viz definice 3.3), tj. hodnota jedné v´ yplatn´ı funkce by byla stejná a hodnota druhé v´ yplatn´ı funkce by byla vyˇsˇs´ı. Ovˇsem podle definice 3.4 je slab´ ym rovnováˇzn´ y bodem jakákoli sm´ıˇsená strategie ’ hráˇce 2. Protoˇze at hráˇc zvol´ı libovolnou strategii (α, 1 − α), nikdy nebude vektor v´ yplatn´ıch funkc´ı vˇetˇs´ı ve smyslu >, hodnota prvn´ı v´ yplatn´ı funkce bude stále 2 a nikdy vyˇsˇs´ı. Hra má tedy jeden siln´ y rovnováˇzn´ y bod ((0, 1) , (0, 1)) a nekoneˇcnˇe mnoho slab´ ych rovnováˇzn´ ych bod˚ u {((0, 1), (α, 1 − α)) , α ∈ [0, 1]}. M Závˇerem této podkapitoly jeˇstˇe zm´ın´ıme obvyklé znaˇcen´ı pro konvexn´ı polyedr, které budeme pouˇz´ıvat v podkapitole 3.2. Definice 3.7. Pro neprázdnou mnoˇzinu S ∈ Rn definujeme konvexn´ı obal jako ( ) X X conv(S) = λ(s)s : λ(s) ≥ 0 ∀s ∈ I, λ(s) = 1, I ⊂ S koneˇcná . s∈I

s∈I

Pro prázdnou mnoˇzinu definici rozˇs´ıˇr´ıme: conv(∅) = ∅. Definice 3.8. Mnoˇzinu A ⊂ Rn naz´ yváme konvexn´ı polyedr, existuje-li koneˇcná n mnoˇzina S ⊂ R taková, ˇze A = conv(S).

14

3.2

Struktura ˇ reˇ sen´ı hry dvou hr´ aˇ c˚ u

Tato podkapitola je pˇrevzata z [2]. Nyn´ı pˇredpokládejme koneˇcnou v´ıcekriteriáln´ı hru pouze dvou hráˇc˚ u. Oznaˇc´ıme si tedy mnoˇzinu ˇcist´ ych strategi´ı prvn´ıho hráˇce X := X1 , mnoˇzinu ˇcist´ ych strategi´ı druhého hráˇce Y := X2 , mnoˇzinu sm´ıˇsen´ ych strategi´ı prvn´ıho hráˇce 4(X) := 4(X1 ) a mnoˇzinu sm´ıˇsen´ ych strategi´ı druhého hráˇce 4(Y ) := 4(X2 ). Mnoˇzinu r(1) kritéri´ı prvn´ıho hráˇce oznaˇc´ıme S, mnoˇzinu r(2) kritéri´ı druhého hráˇce T . Pro kaˇzdou dvojici ˇcist´ ych strategi´ı x ∈ X, y ∈ Y dostaneme vektor hodnot v´ yplatn´ı funkce hráˇce i: ui (x, y). Pro kaˇzdé kritérium s ∈ S si oznaˇc´ıme (As )xy := es .ui (x, y), kde es .ui (x, y) znaˇc´ı skalárn´ı souˇcin vektoru v´ yplatn´ıch funkc´ı a jednotkového vektoru, kter´ y má jedniˇcku na s-tém m´ıstˇe a nuly jinde. Je to tedy hodnota s-tého kritéria prvn´ıho hráˇce pˇri ˇcist´ ych strategi´ıch x a y. Obdobnˇe oznaˇc´ıme (Bt )xy := et .ui (x, y), kde et .ui (x, y) znaˇc´ı skalárn´ı souˇcin vektoru v´ yplatn´ıch funkc´ı a jednotkového vektoru, kter´ y má jedniˇcku na t-tém m´ıstˇe a nuly jinde. Tedy obdobnˇe jako v pˇr´ıpadˇe prvn´ıho hráˇce to je hodnota t-tého kritéria druhého hráˇce pˇri ˇcist´ ych strategi´ıch x a y. V´ıcekriteriáln´ı hra je jednoznaˇcnˇe zadána posloupnostmi matic A a B: A := (As )s∈S

a

B := (Bt )t∈T ,

As := [(As )xy ](x,y)∈X×Y

a

Bt := [(Bt )xy ](x,y)∈X×Y .

Matice A a B budeme chápat jako matice vektor˚ u. Rozmˇer tˇechto matic: |X|×|Y |. Za pˇredpokladu sm´ıˇsen´ ych strategi´ı p ∈ 4(X) a q ∈ 4(Y ) nazveme vektorem v´ yplatn´ıch funkc´ı v´ yraz pAq := (pAs q)s∈S

a

pBq := (pBt q)t∈T .

Nyn´ı si pˇripomeneme definici nejlepˇs´ı odpovˇedi. Definice 3.9. Necht’ q ∈ 4(Y ) je strategie druhého hráˇce. Strategie p ∈ 4(X) prvn´ıho hráˇce se naz´ yvá nejlepˇs´ı odpovˇed´ı prvn´ıho hráˇce proti q, pokud neexistuje strategie pe ∈ 4(X) taková, ˇze vektor v´ yplatn´ıch funkc´ı peAq dominuje vektor v´ yplatn´ıch funkc´ı pAq. Mnoˇzinu nejlepˇs´ıch odpovˇed´ı prvn´ıho hráˇce proti q budeme znaˇcit BR1 (q). Obdobnou definici uvaˇzujeme i pro druhého hráˇce. Jeho mnoˇzinu nejlepˇs´ıch odpovˇed´ı proti p pak budeme znaˇcit BR2 (p).

15

Definici 3.4 lze pak ekvivalentnˇe vyjádˇrit tak, ˇze strategick´ y pár (p, q) je rovnováˇzn´ ym bodem právˇe tehdy, kdyˇz p ∈ BR1 (q) a q ∈ BR2 (p). Necht’ nyn´ı druh´ y hráˇc pˇriˇrad´ı kaˇzdému kritériu t ∈ T váhu λt . Potom vektor X λ = (λt )t∈T ) , λt ≥ 0, λt = 1, t∈T

jehoˇz t-tá sloˇzka pˇriˇrad´ı váhu t-tému kritériu druhého hráˇce, nazveme vektor vah kritéri´ı druhého hráˇce. Poté m˚ uˇzeme vyjádˇrit zisk druhého hráˇce pˇri sm´ıˇsen´ ych strategi´ıch (ei , ej ), ei ∈ X, ej ∈ Y (tedy hráˇc 1 vol´ı ˇcistou strategii i s pravdˇepodobnost´ı 1 a hráˇc 2 vol´ı ˇcistou strategii j s pravdˇepodobnost´ı 1) jako reálné ˇc´ıslo ! X X λt ei Bt ej = ei λt Bt ej . t∈T

t∈T

Pˇri daném vektoru vah λ hráˇce 2 oznaˇc´ıme matici X B(λ) := λt Bt t∈T

pro v´ ypoˇcet jeho zisku. Nyn´ı m˚ uˇzeme formulovat v´ ysledek Shapleyho [12]. Lemma 3.10. Necht’ p je strategie prvn´ıho hráˇce a necht’ q je strategie druhého hráˇce. Pak jsou následuj´ıc´ı tvrzen´ı ekvivalentn´ı. (i) q je nejlepˇs´ı odpovˇed´ı druhého hráˇce proti p (ii) existuje vektor vah λ := (λt )t∈T takový, ˇze q je nejlepˇs´ı odpovˇed´ı druhého hráˇce proti p, uvaˇzujeme-li pro druhého hráˇce jediné kritérium dané matic´ı B(λ). D˚ ukaz. D˚ ukaz lze nalézt v [12]. Jin´ ymi slovy lemma ˇr´ıká, ˇze q je nejlepˇs´ı odpovˇed´ı druhého hráˇce proti p tehdy a jen tehdy, m˚ uˇze-li druh´ y hráˇc ohodnotit kaˇzdé kritérium t ∈ T nezápornou váhou λt tak, ˇze v´ ysledné kritérium je maximáln´ı pro q, hraje-li prvn´ı hráˇc strategii p. Nyn´ı zkonstruujeme dekompozici mnoˇziny rovnováˇzn´ ych bod˚ u hry zadané maticemi A, B na koneˇcn´ y poˇcet mnoˇzin, tj. rozloˇz´ıme mnoˇzinu ˇreˇsen´ı na disjunktn´ı sjednocen´ı podmnoˇzin. Pˇredpokládejme, ˇze máme hru dvou hráˇc˚ u a podmnoˇzinu V ⊆ X ˇcist´ ych strategi´ı prvn´ıho hráˇce. Oznaˇc´ıme 4(V ) mnoˇzinu sm´ıˇsen´ ych strategi´ı prvn´ıho hráˇce na podmnoˇzinˇe ˇcist´ ych strategi´ı V . Dále oznaˇc´ıme U (V ) mnoˇzinu sm´ıˇsen´ ych strategi´ı druhého hráˇce, která reprezentuje mnoˇzinu nejlepˇs´ıch odpovˇed´ı proti (minimálnˇe) vˇsem strategi´ım z 4(V ). Takovou mnoˇzinu U (V ) nazveme region stability. Obdobnˇe oznaˇc´ıme 4(W ) mnoˇzinu sm´ıˇsen´ ych strategi´ı druhého hráˇce, kde W ⊆ Y , a U (W ) mnoˇzinu sm´ıˇsen´ ych strategi´ı prvn´ıho hráˇce, které jsou nejlepˇs´ı odpovˇed´ı proti (minimálnˇe) vˇsem strategi´ım z 4(W ). Rozhoduj´ıc´ı pro nás je, ˇze vˇsechny tyto mnoˇziny 4(V ), 4(W ), U (V ), U (W ) jsou 16

konvexn´ı polyedry a pro kaˇzd´ y konvexn´ı polyedr je moˇzné naj´ıt systém lineárn´ıch nerovnost´ı, které jej popisuj´ı. Z toho zároveˇ n plyne, ˇze mnoˇzina (4(V ) ∩ U (W )) × (4(W ) ∩ U (V )) je také konvexn´ı polyedr. Kromˇe toho máme pouze koneˇcn´ y poˇcet takov´ ych mnoˇzin a lze ukázat, ˇze jejich sjednocen´ı je právˇe mnoˇzina rovnováˇzn´ ych bod˚ u dané hry dvou hráˇc˚ u. Nakonec jeˇstˇe uved’me definici: Definice 3.11. Necht’ m ∈ Rn a P necht’ P je konvexn´ı polyedr v Rn . Pro dva n vektory k, l ∈ Rn necht’ hk, li := arn´ı souˇcin k a l. Vektor m i=1 ki .li je skal´ dosahuje svého maxima na P v bodˇe k ∈ P , pokud hm, ki ≥ hm, li

pro vˇsechna l ∈ P.

Následnˇe zformulujeme známé lemma (d˚ ukaz lze nalézt v [11]). Lemma 3.12. Necht’ m je vektor v Rn . Dále necht’ P je konvexn´ı polyedr v Rn a F je stˇena konvexn´ıho polyedru P . Pokud m dosahuje svého maxima na P v nˇejakém bodˇe l relativn´ıho vnitˇrku F , pak dosahuje svého maxima na P také v jakémkoli dalˇs´ım bodˇe F . Poznamenejme dále, ˇze 4(V ) je vlastnˇe mnoˇzina strategi´ı p ∈ 4(X), jejichˇz nosiˇc je podmnoˇzina V . (Nosiˇcem sm´ıˇsené strategie naz´ yváme soubor ˇcist´ ych strategi´ı, které maj´ı pozitivn´ı pravdˇepodobnost v této dané sm´ıˇsené strategii.) Definujeme region stability U (V ) druhého hráˇce takto: U (V ) := {q ∈ 4(Y )|4(V ) ⊂ BR1 (q)} . Obdobnˇe oznaˇc´ıme 4(W ) mnoˇzinu strategi´ı q ∈ 4(Y ), jejichˇz nosiˇc je podmnoˇzinou W a definujeme region stability U (W ) prvn´ıho hráˇce takto: U (W ) := {p ∈ 4(X)|4(W ) ⊂ BR2 (p)} . Koneˇcnˇe m˚ uˇzeme zformulovat kl´ıˇcovou vˇetu. Vˇ eta 3.13. Mnoˇzina rovnováˇzných bod˚ u hry zadané maticemi A, B se rovn´ a sjednocen´ı mnoˇzin (4(V ) ∩ U (W )) × (4(W ) ∩ U (V )) pˇres vˇsechny V ⊂ X a W ⊂ Y . D˚ ukaz. Nejprve ukáˇzeme, ˇze je-li strategick´ y pár (p, q) prvkem mnoˇziny (4(V ) ∩ U (W )) × (4(W ) ∩ U (V )), pak je to rovnováˇzn´ y bod. Poté ukáˇzeme, ˇze je-li (p, q) rovnováˇzn´ y bod, pak je prvkem (4(V ) ∩ U (W )) × (4(W ) ∩ U (V )) pro nˇejaké mnoˇziny V ⊂ X a W ⊂ Y . (i) Pˇredpokládejme tedy, ˇze strategick´ y pár (p, q) je prvkem (4(V ) ∩ U (W )) × (4(W ) ∩ U (V )) pro nˇejakou podmnoˇzinu V ⊆ X a podmnoˇzinu W ⊆ Y . Ukáˇzeme pouze, ˇze p je nejlepˇs´ı odpovˇed´ı proti q. Tedy je-li q prvkem U (V ), v´ıme, ˇze jakákoli strategie z 4(V ) je nejlepˇs´ı odpovˇed´ı proti q. Avˇsak p je ˇ iq prvkem 4(V ) dle pˇredpoklad˚ u. Tedy p je nejlepˇs´ı odpovˇed´ı proti q. Ze je nejlepˇs´ı odpovˇed´ı proti p, by se ukázalo analogicky. 17

(ii) Naopak, necht’ (p, q) je rovnováˇzn´ y bod. Vezmˇeme mnoˇzinu V jako lineárn´ı obal vektoru p: V = C(p) a W jako lineárn´ı obal vektoru q: W = C(q). Ukáˇzeme, ˇze p je prvkem (4(V ) ∩ U (W )). Zˇrejmˇe p je prvkem 4(V ). Takˇze staˇc´ı ukázat, ˇze p je také prvkem U (W ). Jin´ ymi slovy, potˇrebujeme ukázat, ˇze kaˇzdá strategie qe ∈ 4(W ) je nejlepˇs´ı odpovˇed´ı proti p. Vezmˇeme tedy nˇejakou strategii qe ∈ 4(W ). Jelikoˇz q je nejlepˇs´ı odpovˇed´ı proti p, v´ıme z lemmatu 3.10, ˇze existuje vektor vah λ = (λt )t∈T takov´ y, ˇze q je nejlepˇs´ı odpovˇed´ı proti p podle kritéria daného matic´ı B(λ). Jin´ ymi slovy, vektor pB(λ) dosahuje maxima na 4(Y ) v bodˇe q. Avˇsak protoˇze q je prvkem relativn´ıho vnitˇrku 4(W ), tak pB(λ) mus´ı dosahovat svého maxima podle lemmatu 3.12 také v bodˇe qe ∈ 4(W ). Tedy qe je nejlepˇs´ı odpovˇed´ı proti p podle kritéria daného matic´ı B(λ). Proto opˇet dle lemmatu 3.10 je qe nejlepˇs´ı odpovˇed´ı proti p, a tedy p ∈ (4(V ) ∩ U (W )). ˇ q je prvkem (4(W ) ∩ U (V )), by se opˇet dokázalo analogicky. Ze

Mnoˇziny 4(V ) a 4(W ) jsou konvexn´ı polyedry pro vˇsechny podmnoˇziny V ∈ X a W ∈ Y . Proto z pˇredchoz´ı vˇety plyne, ˇze mnoˇzina rovnováˇzn´ ych bod˚ u hry zadané maticemi A, B je koneˇcné sjednocen´ı konvexn´ıch polyedr˚ u tehdy a jen tehdy, jsou-li mnoˇziny U (V ) a U (W ) konvexn´ı polyedry. Bohuˇzel to vˇsak neplat´ı vˇzdy. Ukáˇzeme si názorn´ y protipˇr´ıklad, na nˇemˇz si zároveˇ n pˇredvedeme zp˚ usob ˇreˇsen´ı v´ıcekriteriáln´ı hry. ˇ e strategie Pˇ r´ıklad 3.14. Mˇejme dva hráˇce, oba maj´ı tˇri ˇcisté strategie. Cist´ prvn´ıho hráˇce pojmenujeme T , M a B, ˇcisté strategie druhého hráˇce pojmenujeme L, C a R. Prvn´ı hráˇc má dvˇe kritéria a druh´ y hráˇc pouze jedno kritérium. V´ yplatn´ı funkce druhého hráˇce je stále nula. V´ yplatn´ı matice A prvn´ıho hráˇce je   (1, 1) (0, 0) (0, 0) A =  (0, 0) (4, 0) (0, 0)  . (0, 0) (0, 0) (0, 4) Pˇripom´ınáme, ˇze prvn´ı hráˇc vol´ı ˇrádkové strategie a druh´ y hráˇc vol´ı sloupcové strategie. Jelikoˇz druh´ y hráˇc je zcela nestrann´ y - jeho kritérium je stále stejné, je jakákoli jeho strategie q nejlepˇs´ı odpovˇed´ı na jakoukoli strategii p prvn´ıho hráˇce. Je tedy zˇrejmé, ˇze strategick´ y pár (p, q) je rovnováˇzn´ ym bodem právˇe tehdy, kdyˇz p ∈ BR1 (q). Jin´ ymi slovy, mnoˇzina rovnováˇzn´ ych bod˚ u se rovná grafu nejlepˇs´ıch odpovˇed´ı BR1 . Abychom mohli nakreslit v´ ysledn´ y graf, mus´ıme nejprve spoˇc´ıtat regiony stability druhého hráˇce. Nejprve poznamenejme, ˇze hraje-li druh´ y hráˇc strategii q = (qL , qC , qR ) a prvn´ı hráˇc ˇcistou strategii eT = (1, 0, 0), pak v´ yplatn´ı funkce prvn´ıho hráˇce je vektor ’ eT Aq = (qL , qL ). To je zˇrejmé, nebot i bez násoben´ı vektor˚ u snadno nahlédneme, ˇze hodnota jeho prvn´ı v´ yplatn´ı funkce bude 1 s pravdˇepodobnost´ı qL a 0 jinak, stejnˇe tak i jeho druhá v´ yplatn´ı funkce bude 1 s pravdˇepodobnost´ı qL a 0 jinak. Podobnˇe hraje-li prvn´ı hráˇc ˇcistou strategii eM = (0, 1, 0), je jeho v´ yplatn´ı funkce vektor eM Aq = (4qC , 0), a hraje-li ˇcistou strategii eB = (0, 0, 1), je jeho v´ yplatn´ı 18

funkce vektor eB Aq = (0, 4qR ). Vid´ıme, ˇze bod (qL , qL ) leˇz´ı na pˇr´ımce x = y, bod (4qC , 0) leˇz´ı na ose y = 0 a bod (0, 4qR ) leˇz´ı na ose x = 0. M˚ uˇzeme tak snadno znázornit 5 situac´ı, které mohou nastat:

Situace I Z obrázku 3.1 vid´ıme, ˇze eT Aq = (qL , qL ) dominuje eM Aq = (4qC , 0) i eB Aq =

Obrázek 3.1: Situace I (0, 4qR ).

Situace II a III Z obrázku 3.2 vid´ıme, ˇze v situaci II eT Aq = (qL , qL ) dominuje eB Aq = (0, 4qR ),

Obrázek 3.2: Situace II a III ale nedominuje eM Aq = (4qC , 0). Situace III je symetrická s t´ım, ˇze eT Aq =

19

(qL , qL ) dominuje eM Aq = (4qC , 0), ale nedominuje eB Aq = (0, 4qR ).

Situace IV Z obrázku 3.3 vid´ıme, ˇze v situaci IV eT Aq = (qL , qL ) nedominuje eB Aq =

Obrázek 3.3: Situace IV (0, 4qR ), ani eM Aq = (4qC , 0).

Situace V Z obrázku 3.4 vid´ıme, ˇze v situaci V je pak eT Aq = (qL , qL ) dominován nˇejakou

Obrázek 3.4: Situace V konvexn´ı kombinac´ı eB Aq = (0, 4qR ) a eM Aq = (4qC , 0). Kdyˇz poté dáme dohromady vˇsech pˇet situac´ı, které mohou nastat, z´ıskáme regiony stability druhého hráˇce, které vid´ıme na obrázku 3.5.

20

Obrázek 3.5: Regiony stability druhého hráˇce Regiony stability na obrázku 3.5 urˇc´ıme pˇr´ımoˇcaˇre následuj´ıc´ım zp˚ usobem. Spoˇcteme, pro jaké hodnoty q = (qL , qC , qR ) vypadá situace jako v situaci I. Zjist´ıme, ˇze pˇri situaci qL ≥ 4qC , qL ≥ 4qR , coˇz je pˇresnˇe znázornˇeno zakreslen´ ymi dvˇema u ´seˇckami. ˇ ımské ˇc´ıslice v oblastech obrázku právˇe koresponduj´ı s v´ R´ yˇse popsan´ ymi situacemi. Hranice mezi oblastmi I a II a oblastmi III, IV a V jsou dány rovnost´ı qL = 4qR . Podobnˇe qL = 4qC urˇcuje hranici mezi oblastmi I a III a mezi oblastmi II, IV a V. Koneˇcnˇe nejv´ıce nás zaj´ımá hranice mezi oblast´ı V a ostatn´ımi. Hranice je pˇresnˇe tam, kde eT Aq je prvkem u ´seˇcky mezi eM Aq a eB Aq. To znamená, ˇze se jedná o mnoˇzinu strategi´ı (qL , qL ) splˇ nuj´ıc´ı lineárn´ı rovnici qR x + qC y = 4qC qR . Proto to mus´ı b´ yt mnoˇzina strategi´ı splˇ nuj´ıc´ı kvadratickou rovnici qL qR + qL qC = 4qC qR (kromˇe ˇreˇsen´ı (qL , qC , qR ) = (1, 0, 0)). Nyn´ı z obrázk˚ u 3.1, 3.2, 3.3, 3.4 a 3.5 snadno m˚ uˇzeme popsat regiony stability druhého hráˇce. Staˇc´ı si uvˇedomit, ˇze v situaci I je dle obrázku 3.1 nejlepˇs´ı odpovˇed´ı ˇcistá strategie T , tedy situace I patˇr´ı do regionu stability U ({T }). V situaci II je dle obrázku 3.2 nejlepˇs´ı odpovˇed´ı sm´ıˇsená strategie pˇrisuzuj´ıc´ı veˇskerou váhu na strategie T a M , tedy situace II patˇr´ı do regionu stability U ({T }), U ({M }) a U ({T, M }). Situace III symetricky patˇr´ı do regionu stability U ({T }), U ({B}) a U ({T, B}). V situaci IV je pak dle obrázku 3.3 nejlepˇs´ı odpovˇed´ı bud’ sm´ıˇsená strategie pˇrisuzuj´ıc´ı veˇskerou váhu na strategie T a M nebo na strategie T a B, tedy situace IV patˇr´ı do regionu stability U ({T }), U ({M }) a U ({B}), U ({T, M }) a U ({T, B}). V situaci V je dle obrázku 3.4 nejlepˇs´ı odpovˇed´ı sm´ıˇsená strategie pˇrisuzuj´ıc´ı veˇskerou váhu na strategie M a B, tedy situace V patˇr´ı do regionu stability U ({M }), U ({B}) 21

a U ({M, B}). Specifick´ y je region stability U ({T, M, B}). Sm´ıˇsená strategie libovolnˇe rozloˇzená mezi strategie T , M , B je nejlepˇs´ı odpovˇed´ı pouze, pokud jsou vˇsechny body na jedné pˇr´ımce. To je vˇsak pouze v pˇr´ıpadˇe pr˚ uniku situac´ı IV a V. Regiony stability tedy vypadaj´ı následovnˇe: U ({T }) = I ∪ II ∪ III ∪ IV U ({M }) = II ∪ IV ∪ V U ({B}) = III ∪ IV ∪ V U ({T, M }) = II ∪ IV U ({T, B}) = III ∪ IV U ({M, B}) = V U ({T, M, B}) = IV ∩ V

Koneˇcnˇe se dostáváme k tomu, co jsme chtˇeli ukázat na tomto pˇr´ıkladˇe. Jak m˚ uˇzeme vidˇet, mnoˇzina U ({T, M, B}) je kvadratická kˇrivka. To znamená, ˇze podmnoˇzinu 4 ({T, M, B}) × U ({T, M, B}) mnoˇzin rovnováˇzn´ ych bod˚ u nelze vyjádˇrit jako koneˇcné sjednocen´ı konvexn´ıch polyedr˚ u. M Pˇr´ıklad nám ukázal, ˇze pokud alespoˇ n jeden hráˇc má v´ıce kritéri´ı, neplat´ı automaticky, ˇze mnoˇzina rovnováˇzn´ ych bod˚ u je koneˇcné sjednocen´ı konvexn´ıch polyedr˚ u. M˚ uˇze obsahovat kvadratickou sloˇzku právˇe tehdy, kdyˇz oba hráˇci maj´ı alespoˇ n tˇri ˇcisté strategie. Pokud se vˇsak omez´ıme na pˇr´ıpad, kdy alespoˇ n jeden hráˇc má nejv´ yˇse dvˇe ˇcisté strategie, pak budeme m´ıt zaruˇceno, ˇze mnoˇzina rovnováˇzn´ ych bod˚ u bude vskutku nutnˇe koneˇcn´ ym sjednocen´ım konvexn´ıch polyedr˚ u. D˚ ukaz, ˇze nutnou a postaˇcuj´ıc´ı podm´ınkou, aby mnoˇzina rovnováˇzn´ ych bod˚ u vznikla koneˇcn´ ym sjednocen´ım konvexn´ıch polyedr˚ u, je, aby alespoˇ n jeden hráˇc mˇel nejv´ yˇse dvˇe ˇcisté strategie, m˚ uˇzeme nalézt v [2]. Tento koncept ˇreˇsen´ı je jeˇstˇe o nˇeco podrobnˇeji rozebrán a aplikován ve ˇctvrté kapitole.

22

3.3

Skalarizace v´ yplatn´ı funkce

Nyn´ı se pod´ıváme na pˇr´ımoˇcaré ˇreˇsen´ı, které nás pravdˇepodobnˇe napadne pˇri stˇretnut´ı s v´ıcekriteriáln´ı hrou, aniˇz bychom znali jakékoli koncepty ˇreˇsen´ı. Zjednoduˇsenˇe ˇreˇceno, v´ yplatn´ı funkce ocen´ıme, pˇriˇrad´ıme-li jim váhy podle toho, které kritérium preferujeme, a poté je seˇcteme. Ve v´ ysledku máme jedno kritérium, které chceme maximalizovat, stejnˇe ostatn´ı hráˇci. Dostali jsme tedy standardn´ı jednokriteriáln´ı hru, u které m˚ uˇzeme nalézt Nash˚ uv rovnováˇzn´ y bod. Pokud váhy máme, ˇci je z´ıskáme, m˚ uˇzeme hru pomˇernˇe snadno pˇrevést na známou a probádanou u ´lohu a nepotˇrebujeme k tomu znát ˇza´dné dalˇs´ı v´ıce ˇci ménˇe obt´ıˇzné zp˚ usoby specifického hledán´ı rovnováˇzn´ ych bod˚ u v´ıcekriteriáln´ı hry. Za pˇredpokladu koneˇcné hry máme i zaruˇcenu existenci Nashova rovnováˇzného bodu. Jedin´ ym problémem se m˚ uˇze zdát, ˇze dané preference nemus´ıme m´ıt k dispozici a dokonce nemus´ıme m´ıt moˇznost, jak se k nim nˇejak´ ym zp˚ usobem dostat, ˇci je odhadnout. Pak tento koncept pouˇz´ıt nem˚ uˇzeme a mus´ıme zkusit jin´ y. Nejprve pˇredstavme základn´ı vˇetu pˇrevzatou z literatury, poté si prakticky ukáˇzeme na pˇr´ıkladˇe, jak takové ˇreˇsen´ı prob´ıhá. Pro zjednoduˇsen´ı zápisu jeˇstˇe oznaˇc´ıme intuitivnˇe Y X := Xj j∈N

a 4(X) :=

Y

4(Xj )

j∈N

Nyn´ı pro danou v´ıcekriteriáln´ı hru G = hN, (Xi )i∈N , (ui )i∈N i , kde ui :

Y

Xj −→ Rr(i) ,

j∈N r(i)

pˇritom jednotlivé sloˇzky vektoru ui hráˇce i odliˇs´ıme: ui = (u1i , . . . , ui ), definujeme klasickou jednokriteriáln´ı hru G = hN, (Xi )i∈N , (vi )i∈N i , kde vi :

Y

Xj −→ R,

j∈N r(i)

vi (x) := λ1i · u1i (x) + . . . + λi kde λ := (λi )i∈N ,

23

r(i)

· ui (x),

λi :=

r(i) (λ1i , . . . , λi ),

r(i) X

λji = 1, λji ≥ 0

j=1

je soubor vah jednotliv´ ych hráˇc˚ u. Koneˇcnˇe m˚ uˇzeme vyslovit stˇeˇzejn´ı vˇetu pˇrevzatou z [9]. Obdobnou verzi uˇz vˇsak pˇredvedl Shapley v [12]. Vˇ eta 3.15. Necht’ x ∈ 4(X) je slabý Nash˚ uv rovnováˇzný bod klasické jednokriteriáln´ı hry G = hN, (Xi )i∈N , (vi )i∈N i , tj. pro vˇsechna i je xi nejlepˇs´ı odpovˇed´ı na strategický profil x−i protihráˇc˚ u. Pak x je slabý rovnováˇzný bod pˇr´ısluˇsné v´ıcekriteriáln´ı hry G = hN, (Xi )i∈N , (ui )i∈N i . D˚ ukaz. D˚ ukaz je snadn´ y a pˇr´ımoˇcar´ y. Pˇredpokládáme, ˇze x je Nash˚ uv rovnováˇzn´ y bod klasické hry. To znamená, ˇze pro vˇsechny hráˇce i ∈ N plat´ı tvrzen´ı: Pro vˇsechny strategie y ∈ 4(X) takové, pro nˇeˇz plat´ı, ˇze vˇsichni hráˇci kromˇe hráˇce i maj´ı strategii xi (tedy m˚ uˇzeme psát y = (yi , x−i )) plat´ı nerovnost vi (x) ≥ vi (y). Nyn´ı pro spor pˇredpokládejme, ˇze x nen´ı slab´ y rovnováˇzn´ y bod v´ıcekriteriáln´ı hry. To znamená, ˇze existuje hráˇc i ∈ N , pro nˇehoˇz plat´ı: Existuje taková strategie y ∈ 4(X) splˇ nuj´ıc´ı pˇredpoklad, ˇze vˇsichni hráˇci kromˇe hráˇce i maj´ı strategii xi (tedy m˚ uˇzeme psát y = (yi , x−i )), ˇze ui (y) > ui (x). Pak ovˇsem mus´ı platit vztah r(i)

vi (yi , x−i ) = vi (yi ) = λ1i · u1i (y) + λ2i · u2i (y) + . . . + λi r(i)

> λ1i · u1i (x) + λ2i · u2i (x) + . . . + λi

r(i)

· ui (y)

r(i)

· ui (x) = vi (x)

To ovˇsem neplat´ı, protoˇze jsme pˇredpokládali, ˇze x je Nash˚ uv rovnováˇzn´ y bod. Pozn´ amka 3.16. Povˇsimnˇeme si analogie s lemmatem 3.10. Vˇeta nám tedy jin´ ymi slovy ˇr´ıká, ˇze pokud jednotliv´ ym kritéri´ım pˇriˇrad´ıme váhy a pˇrevedeme tak v´ıcekriteriáln´ı hru na klasickou jednokriteriáln´ı, nalezneme podmnoˇzinu slab´ ych rovnováˇzn´ ych bod˚ u p˚ uvodn´ı v´ıcekriteriáln´ı hry odpov´ıdaj´ıc´ı preferenc´ım hráˇc˚ u.

24

Ted’ si pˇredvedeme pˇr´ıklad, na kterém si ukáˇzeme praktickou aplikaci v´ yˇse uvedeného postupu.

Pˇ r´ıklad 3.17. Pˇredstavme si standardn´ı hru kámen, n˚ uˇzky, pap´ır“. Pˇredpoklá” dejme, ˇze hráˇci A a B maj´ı dvˇe r˚ uzné v´ yplatn´ı funkce, které chtˇej´ı maximalizovat zároveˇ n a které jdou proti sobˇe. Tj. pokud hráˇc vyhraje dle standardn´ıch pravidel, jeho prvn´ı v´ yplatn´ı funkce vzroste (resp. neklesne), kdeˇzto druhá klesne (resp. nevzroste). Jin´ ymi slovy, pˇri maximalizaci prvn´ı v´ yplatn´ı funkce by se snaˇzil vyhrát, ale pˇri maximalizaci druhé v´ yplatn´ı funkce by se snaˇzil prohrát. Pˇredpokládejme hru s nulov´ ym souˇctem. Hra je zadaná matic´ı A (B je pak urˇcena vztahem B = −A):   (0, 0) (2, −1) (−1, 0) A =  (−2, 3) (0, 0) (3, −1)  (2, −3) (−1, 4) (0, 0) Nyn´ı pˇredpokládejme, ˇze známe preference hráˇc˚ u. Hráˇc A vol´ı váhy λ1 = (λ11 , λ21 ) = (0, 25; 0, 75), hráˇc B vol´ı váhy λ2 = (λ12 , λ22 ) = (0, 65; 0, 35). Chceme naj´ıt slabé rovnováˇzné body. Nejprve uvaˇzujme hráˇce A. Jeho matice hodnot prvn´ı v´ yplatn´ı funkce U11 :

K N P

K N P 0 2 -1 -2 0 3 2 -1 0

a matice druhé v´ yplatn´ı funkce U12 :

K N P

K N P 0 -1 0 3 0 -1 -3 4 0

Nyn´ı vytvoˇr´ıme skalarizovanou v´ yplatn´ı funkci v1 , resp. jej´ı matici V1 = 0, 25 · U11 + 0, 75 · U12 :   0 −0, 25 −0, 25 . 0 0 V1 =  1, 75 −1, 75 2, 75 0

25

Obdobnˇe uvaˇzujme hráˇce B. Jeho matice hodnot prvn´ı v´ yplatn´ı funkce U21 : K N P 0 -2 1 2 0 -3 -2 1 0

K N P a matice druhé v´ yplatn´ı funkce U22 :

K N P 0 1 0 -3 0 1 3 -4 0

K N P

Opˇet vytvoˇr´ıme skalarizovanou v´ yplatn´ı funkci v2 , resp. jej´ı matici V2 = 0, 65 · U21 + 0, 35 · U22 :   0 −0, 95 0, 65 0 −1, 6  . V2 =  0, 25 −0, 25 −0, 75 0 Nyn´ı tedy máme standardn´ı jednokriteriáln´ı hru - dva hráˇce, kaˇzd´ y má tˇri strategie a jednu v´ yplatn´ı funkci. M˚ uˇzeme znám´ ymi zp˚ usoby nalézt Nash˚ uv rovnováˇzn´ y bod. Standardn´ı maticovou hru vyˇreˇs´ıme pomoc´ı dominantn´ıch strategi´ı. Vid´ıme, ˇze v matici V1 druh´ y ˇrádek ostˇre dominuje prvn´ı ˇra´dek. Odtud v´ıme, ˇze plat´ı p1 = 0, a m˚ uˇzeme tedy prvn´ı ˇrádek - strategii kámen“ - z matice vypustit a uvaˇzovat ” matici bez nˇej. Dále vid´ıme, ˇze v matici V2 prvn´ı sloupec ostˇre dominuje druh´ y sloupec. Odtud opˇet v´ıme, ˇze plat´ı q2 = 0, a m˚ uˇzeme z matice vypustit druh´ y sloupec - strategii n˚ uˇzky“. ” Z˚ ustanou nám tak v´ yplatn´ı matice: V1 =

V2 =

1, 75 0 −1, 75 0

0, 25 −1, 6 −0, 25 0

,

.

Nyn´ı bychom mohli hru snadno ˇreˇsit graficky, ale ˇreˇsen´ı je zˇrejmé. Uvˇedom´ıme si, ˇze skalarizac´ı dvou funkc´ı antagonistického konfliktu nám vznikla hra, která vˇsak jiˇz antagonistická nen´ı. Hráˇci maj´ı r˚ uzné v´ yplatn´ı funkce a zisk nebo ztráta protihráˇce je nijak nezaj´ımá. Vid´ıme, ˇze hráˇc A má nejvyˇsˇs´ı hodnotu v´ yplatn´ı funkce v bodˇe (N, K) (v oznaˇcen´ı p˚ uvodn´ıch strategi´ı) a hráˇc B má nejvyˇsˇs´ı hodnotu v´ yplatn´ı funkce také v bodˇe (N, K). Ani jeden z hráˇc˚ u nem˚ uˇze v ˇza´dné jiné 26

dvojici strategi´ı z´ıskat v´ıce, a proto je bod (N, K) rovnováˇzn´ ym bodem této hry. Hra tedy má ˇreˇsen´ı v ˇcist´ ych strategi´ıch. Hodnota v´ yplatn´ı funkce prvn´ıho hráˇce je 1,75 a hodnota v´ yplatn´ı funkce druhého hráˇce je 0,25. Nyn´ı se m˚ uˇzeme vrátit k p˚ uvodn´ı v´ıcekriteriáln´ı hˇre. Pˇri ˇcist´ ych strategi´ıch (N, K) je vektor v´ yplatn´ıch funkc´ı prvn´ıho hráˇce (-2,3) a vektor v´ yplatn´ıch funkc´ı druhého hráˇce (2,-3). Dle vˇety 3.15 v´ıme, ˇze je to slab´ y rovnováˇzn´ y bod zadané v´ıcekriteriáln´ı hry. M

27

3.4

Ide´ aln´ı rovnov´ aˇ zn´ e body

Tato podkapitola je pˇrevzata z [13]. V pˇredchoz´ı podkapitole jsme si ukázali moˇznost ˇreˇsen´ı pomoc´ı skalarizace v´ yplatn´ı funkce. Obvykle vˇsak neznáme preference hráˇc˚ u, které k ˇreˇsen´ı potˇrebujeme. Proto byl zkonstruován koncept hledán´ı ideáln´ıch rovnováˇzn´ ych bod˚ u. Ideáln´ı rovnováˇzné body jsou robustn´ı v˚ uˇci preferenc´ım hráˇc˚ u, jsou stejné pro jakékoli váhy. Jejich existence bohuˇzel nen´ı zaruˇcena. Uvedeme vˇsak nˇekteré pˇr´ıpady, kdy existuj´ı. Na rozd´ıl od nˇekter´ ych jin´ ych koncept˚ u ˇreˇsen´ı nalezen´ı ideáln´ıch rovnováˇzn´ ych bod˚ u je pomˇernˇe snadné. Pˇresná horn´ı hranice pro poˇcet proveden´ ych skalarizac´ı je maximum z poˇctu kritéri´ı jednotliv´ ych hráˇc˚ u. Definice 3.18. Pˇredpokládejme v´ıcekriteriáln´ı hru G = hN, (Xi )i∈N , (ui )i∈N i . Ideáln´ı rovnováˇzný bod je strategick´ y profil x ∈ 4(X) takov´ y, ˇze pro kaˇzdého hráˇce i ∈ N a kaˇzdou strategii x ei ∈ 4(Xi ) plat´ı ui (xi , x−i ) = ui (e xi , x−i ) dle definice 3.3. Pˇ r´ıklad 3.19. Je snadné ukázat, ˇze ideáln´ı rovnováˇzn´ y bod nemus´ı existovat, staˇc´ı uvaˇzovat hru jednoho hráˇce o dvou kritéri´ıch: (1, 0) A= . (0, 1) Vid´ıme, ˇze zvol´ı-li hráˇc prvn´ı strategii, jeho zisk bude (1, 0), zvol´ı-li druhou strategii, jeho zisk bude (0, 1) a zvol´ı-li sm´ıˇsenou strategii (p, 1 − p), jeho zisk bude ˇ adné p nesplˇ (p, 1 − p). Z´ nuje definici ideáln´ıho rovnováˇzného bodu, protoˇze se zvyˇsován´ım p roste prvn´ı v´ yplatn´ı funkce, ale klesá druhá v´ yplatn´ı funkce. M Ukáˇzeme si také dva pˇr´ıklady, které ideáln´ı rovnováˇzn´ y bod maj´ı. Pˇ r´ıklad 3.20. Nyn´ı uvaˇzujme dva hráˇce A a B, kaˇzd´ y má dvˇe ˇcisté strategie a dvˇe kritéria. (1, 1) (0, 1) A= (1, 0) (1, 1) (1, 1) (1, 0) B= (0, 1) (1, 1) Hra má dvˇe ˇreˇsen´ı v ˇcist´ ych strategi´ıch: zvol´ı-li oba hráˇci prvn´ı strategii nebo zvol´ı-li oba hráˇci druhou strategii. Jejich v´ yplatn´ı funkce pak budou (1, 1) a (1, 1). M

28

Pˇ r´ıklad 3.21. Jeˇstˇe si ukáˇzeme, ˇze ideáln´ı rovnováˇzn´ y bod nemus´ı leˇzet nutnˇe v prostoru ˇcist´ ych strategi´ı. Uvaˇzujme následuj´ıc´ı hru dvou hráˇc˚ u zadanou v´ yplatn´ımi maticemi (1, 0) (0, 1) A= (0, 1) (1, 0) (0, 1) (1, 0) B= . (1, 0) (0, 1) V tomto pˇr´ıkladˇe hrá nemá ideáln´ı rovnováˇzn´ y bod v ˇcist´ ych strategi´ıch, ale existuje ideáln´ı rovnov´ a ˇ z n´ y bod ve sm´ ıˇ s en´ y ch strategi´ ıch. Hra má jediné ˇreˇsen´ı, 1 1 1 1 1 1 a to ( 2 , 2 ), ( 2 , 2 ) . Pokud totiˇz jeden hráˇc hraje strategii 2 , 2 , pak nejlepˇs´ı odpovˇed´ı druhého hráˇce je jakákoli sm´ıˇsená strategie a druh´ y hráˇc bude m´ıt vˇzdy stejn´ y zisk. Totéˇz plat´ı naopak. Je to tedy ideáln´ı rovnováˇzn´ y bod. Pokud zvol´ı jeden z hráˇc˚ u jinou strategii, pak uˇz druh´ y hráˇc nem˚ uˇze zvolit strategii tak, y ideáln´ı aby byli v ideáln´ım rovnováˇzném bodˇe. Bod ( 12 , 21 ), ( 12 , 12 ) je tedy jedin´ rovnováˇzn´ y bod hry. M Pokud si vezmeme bˇeˇznou v´ıcekriteriáln´ı hru, kaˇzd´ y hráˇc má nˇekolik kritéri´ı. Vˇsechna se snaˇz´ı maximalizovat zároveˇ n. V podstatˇe si nejdˇr´ıve spoˇc´ıtá optimáln´ı hodnotu kaˇzdé v´ yplatn´ı funkce zvláˇst’ a poté se snaˇz´ı pˇribl´ıˇzit tomuto ideáln´ımu bodu u vˇsech v´ yplatn´ıch funkc´ı zároveˇ n. Pokud hra ideáln´ı rovnováˇzn´ y bod má, hráˇci mohou ideáln´ıho bodu dosáhnout. Ideáln´ı rovnováˇzné body jsou pˇresnˇe ty strategické profily, pˇri nichˇz kaˇzd´ y hráˇc dosáhne svého ideáln´ıho bodu za pˇredpokladu daného strategického profilu jeho oponent˚ u. Uvaˇzujme v´ıcekriteriáln´ı hru G = hN, (Xi )i∈N , (ui )i∈N i. IdeáQ ln´ı bod pro hráˇce i ∈ N za pˇredpokladu strategického profilu oponent˚ u x−i ∈ j∈N \{i} 4(Xj ) je r(i) definován jako ψi (x−i ) ∈ R s vlastnost´ı ∀k ∈ {1, . . . , r(i)} : ψik (x−i ) = max uki (xi , x−i ). xi ∈4(Xi )

Pokud se jedná o hru jednoho hráˇce, je ideáln´ı bod jednoduˇse definován jako ψi ∈ Rr(i) s vlastnost´ı ∀k ∈ {1, . . . , r(i)} : ψik = max uki (xi ). xi ∈4(Xi )

Dále oznaˇcme mnoˇzinu vah vektor˚ u symbolem Λ a pojmenujeme ji reprezentativn´ı, pokud pro kaˇzdého hráˇce a kaˇzdou jeho v´ yplatn´ı funkci obsahuje takov´ y vektor, kter´ y dané v´ yplatn´ı funkci pˇriˇrad´ı váhu rovnu jedné, tj. pro které: ∀i ∈ N, ∀k ∈ {1, . . . , r(i)} , ∃λ = (λj )j∈N : λi = ek , myˇsleno λi = ek ⇐⇒ (λjk = 1; λjκ = 0 pro k 6= κ), κ ∈ {1, . . . , r(i)}. Nyn´ı si pˇredstav´ıme vˇetu, která nám pˇribl´ıˇz´ı charakteristiku ideáln´ıch rovnováˇzn´ ych bod˚ u: 29

Vˇ eta 3.22. Q Mˇejme v´ıcekriteriáln´ı hru G = hN, (Xi )i∈N , (ui )i∈N i, sm´ıˇsenou strategii x ∈ i∈N 4(Xi ) a Λ reprezentativn´ı mnoˇzinu vah vektor˚ u. Pak jsou následuj´ıc´ı tvrzen´ı ekvivalentn´ı: (i) x je ideáln´ı rovnováˇzný bod G (ii) ∀i ∈ N : ui (x) = ψi (x−i ) (iii) x patˇr´ı do pr˚ uniku Nashových rovnováˇzných bod˚ u klasické hry se skalarizovanou výplatn´ı funkc´ı pˇres vˇsechny moˇzné váhy λ = (λi )i∈N vˇsech hráˇc˚ u i∈N (iv) x patˇr´ı do pr˚ uniku Nashových rovnováˇzných bod˚ u klasické hry se skalarizovanou výplatn´ı funkc´ı pˇres reprezentativn´ı mnoˇzinu vah vektor˚ uΛ D˚ ukaz. D˚ ukaz je moˇzno nalézt v [13]. Je zˇrejmé, ˇze bod (ii) motivoval k názvu konceptu. Bod (iii) indikuje robustnost ˇreˇsen´ı - nezáleˇz´ı na zvolen´ı vah, pro jakékoli zvolené váhy hráˇc˚ u bude x rovnováˇzn´ ym bodem klasické hry se skalarizovanou v´ yplatn´ı funkc´ı. Bod (iv) ˇ ıká, ˇze staˇc´ı provést nˇekolik je pro nás pak d˚ uleˇzit´ y z v´ ypoˇcetn´ıch d˚ uvod˚ u. R´ ˇreˇsen´ı klasické hry se skalarizovanou v´ yplatn´ı funkc´ı, konkrétnˇe poˇcet, kter´ y je roven poˇctu kritéri´ı hráˇce s nejv´ıce kritérii, abychom nalezli ˇreˇsen´ı. Je zˇrejmé, ˇze nalezneme-li ideáln´ı rovnováˇzn´ y bod, je i siln´ ym rovnováˇzn´ ym bodem. Pˇ r´ıklad 3.23. Uvaˇzujme v´ıcekriteriáln´ı hru dvou hráˇc˚ u, prvn´ı hráˇc má 3 kritéria a druh´ y hráˇc 7 kritéri´ı. Reprezentativn´ı mnoˇzina vah by pak byla napˇr. Λ = {(e1 , e1 ), (e2 , e2 ), (e3 , e3 ), (e1 , e4 ), (e1 , e5 ), (e1 , e6 ), (e1 , e7 )} Pro v´ ypoˇcet ideáln´ıch rovnováˇzn´ ych bod˚ u bychom tedy provedli sedm v´ ypoˇct˚ u Nashova rovnováˇzného bodu klasick´ ych her se skalarizovan´ ymi v´ yplatn´ımi funkcemi váˇzen´ ymi v´ yˇse uveden´ ymi vektory. Jejich pr˚ unik by pak byla mnoˇzina ideáln´ıch rovnováˇzn´ ych bod˚ u. M Pokud tedy máme hru, která má ideáln´ı rovnováˇzné body, snadno a rychle je pomoc´ı algoritm˚ u hledán´ı Nashova rovnováˇzného bodu najdeme. Vzhledem k rychlému ˇreˇsen´ı se pˇri relativnˇe malém poˇctu v´ yplatn´ıch funkc´ı vyplat´ı pˇred uˇzit´ım jin´ ych koncept˚ u zkusit, zda náhodou hra nemá ideáln´ı rovnováˇzné body. Teprve pokud nám mnoˇzina vyjde prázdná, m˚ uˇzeme poté hledat jiná sloˇzitˇejˇs´ı ˇreˇsen´ı. Jak vˇsak bylo pˇredesláno, ideáln´ı rovnováˇzné body neexistuj´ı v mnoha hrách. Je tomu tak jednoduˇse proto, ˇze v´ yplatn´ı funkce jdou ˇcasto proti sobˇe - zv´ yˇs´ı-li se jedna, klesne druhá a naopak. Ukáˇzeme si ale skupinu v´ıcekriteriáln´ıch her, kdy je zaruˇcena neprázdná mnoˇzina ideáln´ıch rovnováˇzn´ ych bod˚ u. Jedná se o hry s potenciály. Hra s potenciálem je jednokriteriáln´ı hra, v n´ıˇz lze v´ yznamnou informaci t´ ykaj´ıc´ı

30

se mnoˇziny Nashov´ ych rovnováˇzn´ ych bod˚ u shrnout do jedné reálné funkce definované na strategickém prostoru. Jin´ ymi slovy, koneˇcná jednokriteriáln´ı hra G = hN, (Xi )i∈N , (vi )i∈N i je ordináln´ı hra s potenciálem, pokud existuje funkce Y P : Xi → R i∈N

takováQ , ˇze pro kaˇzdého hráˇce i ∈ N , pro kaˇzd´ y strategick´ y profil jeho oponent˚ u x−i ∈ j∈N/{i} Xj a kaˇzd´ y pár strategi´ı xi , yi ∈ Xi hráˇce i: vi (yi , x−i ) − vi (xi , x−i ) > 0 ⇐⇒ P (yi , x−i ) − P (xi , x−i ) > 0. Funkce P je pak naz´ yvána ordináln´ı potenciál hry G. Nyn´ı pˇredpokládejme koneˇcnou jednokriteriáln´ı hru G = hN, (Xi )i∈N , (vi )i∈N i s ordináln´ım potenciálem P a zkonstruujeme vicekriteriáln´ı hru G = hN, (Xi )i∈N , (ui )i∈N i tak, ˇze kaˇzd´ y hráˇc i ∈ N má dvˇe kritéria. Prvn´ı kritérium hráˇce i se rovná ui , druhé kritérium se rovná potenciálu P : ∀i ∈ N : ui1 = vi a ui2 = P. Vˇ eta 3.24. V´ıcekriteriáln´ı hra popsána výˇse má ideáln´ı rovnováˇzný bod v ˇcistých strategi´ıch. D˚ ukaz. D˚ ukaz lze opˇet nalézt v [13]. Hra se m˚ uˇze zdát pˇr´ıliˇs umˇele vytvoˇrená a nereálná, je tedy vhodné zm´ınit reáln´ y model, kde je moˇzné v´ ysledek pouˇz´ıt. Koster, Reijnierse a Voorneveld pˇredstavili v tezi [8] skupinu her, ve kter´ ych hráˇci pˇrisp´ıvaj´ı do sb´ırky, ze které se projektuj´ı veˇrejné statky. Bl´ıˇze popsaná je hra v podkapitole 1.2. Ordináln´ım potenciálem je pak celkové veˇrejné blaho. V takové hˇre je zaruˇcena existence ideáln´ıho rovnováˇzného bodu dle vˇety 3.24. T´ım jsme poskytli netriviáln´ı skupinu her, v n´ıˇz ideáln´ı rovnováˇzn´ y bod existuje.

31

3.5

Srovn´ an´ı

Ukázali jsme si tˇri r˚ uzné koncepty ˇreˇsen´ı. Nyn´ı se pod´ıváme na jejich v´ yhody a nev´ yhody. ˇ sen´ı funguje na veNejprve jsme se zab´ yvali strukturou ˇreˇsen´ı hry dvou hráˇc˚ u. Reˇ lice specifické mnoˇzinˇe her - dva hráˇci, z nichˇz jeden má nejv´ yˇse dvˇe ˇcisté strategie. Toto omezen´ı je pomˇernˇe znatelné, a proto lze ˇreˇsen´ı pouˇz´ıt pouze v malém poˇctu reáln´ ych pˇr´ıpad˚ u, coˇz je velká nev´ yhoda. Ovˇsem naopak máme-li takov´ y pˇr´ıklad, pak nalezneme vˇsechna rovnováˇzná ˇreˇsen´ı pomˇernˇe snadno a rychle. V kapitole 4 uvid´ıme, ˇze pro pˇr´ıklad, kde máme dva hráˇce, jeden má dvˇe ˇcisté strategie a druh´ y má ˇctyˇri ˇcisté strategie, je to ˇreˇsen´ı vskutku elegantn´ı a relativnˇe jednoduché. Pokud by mˇel druh´ y hráˇc v´ yraznˇe vˇetˇs´ı poˇcet ˇcist´ ych strategi´ı, nebylo by to tak snadné, ale stále by mnoˇzina ˇreˇsen´ı byla koneˇcné sjednocen´ı konvexn´ıch polyedr˚ u, tj. popsatelná koneˇcnˇe mnoho lineárn´ımi nerovnostmi, a ˇreˇsen´ı je tud´ıˇz reálnˇe pouˇzitelné. Tedy po shrnut´ı pˇredeˇslé u ´vahy nev´ yhodou této metody je jeho omezená moˇznost vyuˇzit´ı, v´ yhodou je jednoduchost, efektivnost a v neposledn´ı ˇradˇe pˇr´ımé nalezen´ı vˇsech rovnováˇzn´ ych bod˚ u. Následnˇe jsme se seznámili s metodou hledán´ı rovnováˇzn´ ych bod˚ u skalarizac´ı v´ yplatn´ı funkce. Tato metoda funguje tak, ˇze hráˇci pˇriˇrad´ı jednotliv´ ym kritéri´ım váhy a vytvoˇr´ı tak jednu v´ yplatn´ı funkci - váˇzen´ y souˇcet jednotliv´ ych kritéri´ı. Tento koncept má dvˇe nedokonalosti. Ne vˇzdy jsou kritéria ve stejném mˇeˇr´ıtku, nˇekdy se tˇreba jedno kritérium poˇc´ıtá na desetiny a má malé rozpˇet´ı, zat´ımco druhé se poˇc´ıtá na tis´ıce a má mnohonásobnˇe vˇetˇs´ı rozpˇet´ı. Pak je nutné sloˇzitˇe funkce upravovat, aby bylo moˇzné jim pˇriˇradit nˇejaké rozumné váhy. Ale s t´ım se dá jeˇstˇe vypoˇrádat, byt’ to m˚ uˇze b´ yt komplikované. Horˇs´ı vˇsak je, ˇze obvykle nejsou k dispozici pˇriˇrazené váhy jednotliv´ ym kritéri´ım, ani nen´ı moˇzné je zjistit. Pak tato metoda zcela selhává a mus´ıme vyuˇz´ıt jinou. Pokud vˇsak tyto váhy k dispozici máme, nebo je moˇzné je z´ıskat, pak má metoda velkou v´ yhodu v tom, ˇze je jiˇz dobˇre zpracována. Pˇrevede v´ıcekriteriáln´ı hru na standardn´ı hledán´ı Nashova rovnováˇzného bodu, které je dobˇre zpracováno samotn´ ym Nashem a bˇehem dalˇs´ıch ˇsedesáti let podrobnˇe rozebráno velk´ ym mnoˇzstv´ım autor˚ u v jeˇstˇe vˇetˇs´ım mnoˇzstv´ı ˇclánk˚ u. Jako posledn´ı koncept jsme popsali ideáln´ı rovnováˇzné body ve v´ıcekriteriáln´ı hˇre. Ideáln´ı rovnováˇzn´ y bod je jeˇstˇe silnˇejˇs´ı definice neˇz definice silného rovnováˇzného bodu. Je vˇsak natolik striktn´ı, ˇze ideáln´ı rovnováˇzn´ y bod ve vˇetˇsinˇe pˇr´ıpad˚ u v˚ ubec neexistuje. To je základn´ı nedostatek konceptu. Autoˇri sami vˇsak popsali pomˇernˇe velkou mnoˇzinu pˇr´ıpad˚ u, kdy tento ideáln´ı rovnováˇzn´ y bod existuje jedná se o hry s potenciálem. Jejich podstata je popsána také v podkapitole 3.4. V takov´ ych pˇr´ıkladech - existuje-li ideáln´ı rovnováˇzn´ y bod - je jeho nalezen´ı velmi snadné. Velkou v´ yhodou je jednoznaˇcnost v hodnotˇe v´ yplatn´ı funkce. Jin´ ymi slovy, existuje-li v´ıce ideáln´ıch bod˚ u, vektor v´ yplatn´ıch funkc´ı je v tˇechto bodech totoˇzn´ y. V podstatˇe nám tak staˇc´ı naj´ıt jeden, abychom dosáhli maximáln´ı hodnoty v´ yplatn´ıch funkc´ı. Dalˇs´ı v´ yhodou je jeho pomˇernˇe snadné nalezen´ı. Pokud vˇse shrneme, koncepty se liˇs´ı pˇredevˇs´ım v moˇznosti pouˇzit´ı. V reálném

32

pˇr´ıkladˇe je obvykle moˇzné pouˇz´ıt maximálnˇe jeden z nich. A ani to nemus´ı b´ yt vˇzdy pravda, nen´ı v˚ ubec obt´ıˇzné naj´ıt hru, kde nelze pouˇz´ıt ani jeden popsan´ y zp˚ usob ˇreˇsen´ı - staˇc´ı jednoduchá hra dvou hráˇc˚ u, kde oba maj´ı tˇri ˇcisté strategie, neznáme jejich preference (váhy) jednotliv´ ych kritéri´ı a hra nemá ideáln´ı rovnováˇzn´ y bod. Koncepty tedy zdaleka nejsou vyˇcerpávaj´ıc´ı a stále prob´ıhá mnoho r˚ uzn´ ych v´ yzkum˚ u na toto téma, protoˇze jak bylo pˇredesláno v kapitole 2, aˇz za posledn´ıch deset let je vˇenována v´ıcekriteriáln´ım hrám patˇriˇcná pozornost. Ovˇsem na druhou stranu, máme-li pˇr´ıklad, v nˇemˇz lze jeden z koncept˚ u pouˇz´ıt, pak je jeho pouˇzit´ı efektivn´ı a ne pˇr´ıliˇs obt´ıˇzné.

33

Kapitola 4 Aplikace ´ Nyn´ı vyuˇzijeme poznatk˚ u z podkapitoly 3.2 pro ˇreˇsen´ı reálného pˇr´ıkladu. Uloha je sestavena na základˇe reáln´ ych zkuˇsenost´ı a v´ ysledk˚ u.

4.1

Sestaven´ı u ´ lohy

Uvaˇzujme dvˇe firmy - firmu A a firmu B. Jedná se o stavebn´ı firmy a kaˇzdá z nich kromˇe stavebn´ıch prac´ı provád´ı i jiné profese (napˇr. vzduchotechnika, elektroinstalace, mˇeˇren´ı a regulace apod.). Uvaˇzujeme, ˇze kaˇzdá provád´ı uˇz jen vzduchotechniku. Obˇe plánuj´ı zaplatit si jednu reklamu na lukrativn´ım m´ıstˇe. Reklamy budou vedle sebe. Kaˇzdá z firem se rozhoduje, zda vystav´ı reklamu na odvˇetv´ı stavebn´ıch prac´ı nebo reklamu na odvˇetv´ı vzduchotechniky. Firma B nav´ıc hodnˇe sáz´ı na reklamu a zvaˇzuje, ˇze si pˇriplat´ı za draˇzˇs´ı verzi reklamy (vˇetˇs´ı/propracovanˇejˇs´ı apod.). C´ılem reklamy je pochopitelnˇe zv´ yˇsit poptávku po firmˇe, a tud´ıˇz zisky. Kaˇzdá firma má dvˇe hlavn´ı odvˇetv´ı podnikán´ı (ostatn´ı jsme zanedbali), kaˇzdé provád´ı jiná skupina lid´ı, m˚ uˇzeme je nazvat r˚ uzn´ ymi sekcemi, jedná se vlastnˇe o speciáln´ı pˇr´ıpad pˇr´ıkladu z podkapitoly 1.1. Stejnˇe tedy jako v pˇr´ıkladu 1.1 nem˚ uˇzeme jednoduˇse seˇc´ıst zisky z obou odvˇetv´ı. Obˇe sekce zamˇestnanc˚ u potˇrebuj´ı práci. Pokud by nepracovali a byli pouze ˇziveni ze zisku jiného odvˇetv´ı, firmu by to stálo vysoké náklady, protoˇze zamˇestnanc˚ um mus´ı platit stejnou mzdu at’ pracuj´ı, nebo ne, stejnˇe tak odvody státu. Firma tedy potˇrebuje maximalizovat zisky z obou odvˇetv´ı jednotlivˇe. Zároveˇ n nelze jednoduˇse pˇridˇelit váhy jednotliv´ ym odvˇetv´ım ’ jako v podkapitole 3.3, protoˇze zamˇestnanci by se bouˇrili, nebot maj´ı odmˇeny za dokonˇcené práce, a tak chtˇej´ı co nejv´ıce práce pro sebe. Pokud by firma pˇridˇelila vˇetˇs´ı váhu stavebnictv´ı, bouˇrili by se zamˇestnanci ze vzduchotechnického odvˇetv´ı, proˇc by oni mˇeli m´ıt menˇs´ı prioritu. Pokud by firma pˇridˇelila stejné váhy obˇema odvˇetv´ım, byly by problémy zase se stavebn´ımi dˇeln´ıky, kteˇr´ı by chtˇeli vˇetˇs´ı váhu, nebot’ stavebnictv´ı je základn´ım odvˇetv´ım obou firem. ´ Ulohu snadno pˇrevedeme na v´ıcekriteriáln´ı hru. Máme dva hráˇce - firmu A a firmu B. Firma A má dvˇe ˇcisté strategie, které oznaˇc´ıme M, N :

34

(i) reklama na stavebnictv´ı (strategie M ) (ii) reklama na vzduchotechniku (strategie N ). Firma B má ˇctyˇri ˇcisté strategie, které oznaˇc´ıme I, J, K, L: (i) reklama na stavebnictv´ı, levná verze (strategie I) (ii) reklama na stavebnictv´ı, drahá verze (strategie J) (iii) reklama na vzduchotechniku, levná verze (strategie K) (iv) reklama na vzduchotechniku, drahá verze (strategie L).

Obˇe firmy maj´ı dvˇe v´ yplatn´ı funkce - zisk ze stavebnictv´ı a zisk ze vzduchotechniky. Zisk z jednotliv´ ych odvˇetv´ı budeme mˇeˇrit zmˇenou v procentech oproti stavu pˇred reklamou. Tedy napˇr. pokud bude hodnota prvn´ı v´ yplatn´ı funkce 130, znamená to, ˇze zisky ve stavebnictv´ı se zv´ yˇsily o 30%. Hra je tedy zadána maticemi: 1 2 (a11 , a11 ) A= (a121 , a221 ) a 1 2 (b11 , b11 ) B= (b121 , b221 )

(a112 , a212 ) (a113 , a213 ) (a114 , a214 ) (a122 , a222 ) (a223 , a223 ) (a124 , a224 ) (b112 , b212 ) (b113 , b213 ) (b114 , b214 ) (b122 , b222 ) (b223 , b223 ) (b124 , b224 )

,

kde jednotlivé prvky znamenaj´ı procentuáln´ı zmˇenu zisku s ohledem na strategie hráˇc˚ u a v´ yplatn´ı funkce. Tj. napˇr´ıklad prvek azxy znamená procentuáln´ı zmˇenu zisku firmy A pˇri realizaci ˇcisté strategie x firmy A a ˇcisté strategie y firmy B v odvˇetv´ı z. Konkrétnˇe napˇr´ıklad b213 znamená zmˇenu zisku firmy B pˇri realizaci ˇcisté strategie M (reklama na stavebnictv´ı) firmy A a ˇcisté strategie K (reklama na vzduchotechniku, levná verze) firmy B v odvˇetv´ı vzduchotechniky. Pˇredpokládáme azxy , bzxy ∈ h0, max), kde max je nˇejaká horn´ı hodnota, napˇr. hodnota zv´ yˇsen´ı zisku pˇri uspokojen´ı celé poptávky firmou A, resp. B. Prakticky se vˇsak daj´ı oˇcekávat pˇribliˇznˇe hodnoty azxy , bzxy ∈ (50, 200). Nyn´ı tedy potˇrebujeme konkrétn´ı hodnoty azxy , bzxy . K tomu jeˇstˇe vyslov´ıme nˇekolik pˇredpoklad˚ u a poznámek vycházej´ıc´ıch ze zkuˇsenost´ı: (i) objem prodeje firmy A je i ve stavebnictv´ı i ve vzduchotechnice stejn´ y jako objem prodeje B (ii) zvˇetˇs´ı-li se obraty ve stavebnictv´ı, zvˇetˇs´ı se ˇcásteˇcnˇe i obraty ve vzduchotechnice (pokud poptá investor firmu na stavebn´ı práce, má nˇekdy moˇznost sama poptávat ostatn´ı profese a tedy vzduchotechnické práce udˇelat sama) (iii) reklama firmy A je na u ´rovni levné reklamy firmy B

35

(iv) reklama na vzduchotechniku je u ´ˇcinnˇejˇs´ı, protoˇze stavebn´ıch firem je v´ıce a také jsou ˇcasto poptávány automaticky ze známosti s investorem (v) pˇr´ıklad je situován v menˇs´ım mˇestˇe a reklama je perspektivn´ı a u ´ˇcinná, zisky z reklamy jsou znatelné, zároveˇ n je ve mˇestˇe malá konkurence, a tak se firmy A a B v´ yraznˇe ovlivˇ nuj´ı navzájem (vi) firma B je ve mˇestˇe známˇejˇs´ı a o nˇeco v´ıtanˇejˇs´ı, jej´ı reklamy jsou proto o trochu u ´ˇcinnˇejˇs´ı (vii) za draˇzˇs´ı verzi reklamy je firma B penalizována −20% z aktuáln´ıch zisk˚ u stavebnictv´ı - pˇr´ıplatek nav´ıc je financován z penˇez stavebn´ıho odvˇetv´ı, at’ se jedná o reklamu na vzduchotechniku nebo na stavebnictv´ı Nyn´ı jeˇstˇe budeme pˇredpokládat konkrétn´ı u ´ˇcinnosti reklamy bez vlivu druhé firmy, tj. jak se zmˇen´ı zisky firmy A, resp. B po realizaci konkrétn´ı reklamy (strategie), pokud by ta druhá firma ˇzádnou reklamu nerealizovala. Hodnoty jsou urˇceny na základˇe expertn´ıch odhad˚ u.

Firma A (stejnˇe jako strategie I a K firmy B): strategie specifikace zisk M reklama ve stavebnictv´ı (120,112) N reklama ve vzduchotechnice (100,130) Firma B: strategie I J K L

specifikace reklama ve reklama ve reklama ve reklama ve

stavebnictv´ı, levná verze stavebnictv´ı, drahá verze vzduchotechnice, levná verze vzduchotechnice, drahá verze

zisk po penalizaci (120,112) (135,115) (115,115) (100,130) (100,155) (80,155)

Nyn´ı koneˇcnˇe odhadneme jednotlivé prvky matic A a B. Budeme je odhadovat od nejjednoduˇsˇs´ıch k nejsloˇzitˇejˇs´ım. Pˇresné hodnoty jsou opˇet z´ıskávány na základˇe expertn´ıch odhad˚ u.

prvky a11, b11 strategie M (stavebnictv´ı) vs. strategie I (stavebnictv´ı, levná verze) (120, 112) × (120, 112) ↓ (110, 106) × (110, 106)

36

´ cinnost reklamy se pouze rozloˇz´ı mezi obˇe firmy. Uˇ

prvky a23, b23 strategie N (vzduchotechnika) vs. strategie K (vzduchotechnika, levná verze) (100, 130) × (100, 130) ↓ (100, 115) × (100, 120) ´ cinnost reklamy se ˇcásteˇcnˇe rozloˇz´ı, ˇcásteˇcnˇe se pˇr´ıliv zákazek na základˇe dvou Uˇ reklam nepatrnˇe zv´ yˇs´ı, a to ve prospˇech firmy B, protoˇze má trochu lepˇs´ı jméno ve vzduchotechnickém odvˇetv´ı.

prvky a12, b12 strategie M (stavebnictv´ı) vs. strategie J (stavebnictv´ı, drahá verze) (120, 112) × (135, 115) ↓ (105, 102) × (130, 110) ↓ po penalizaci (105, 102) × (110, 110) Drahá reklama firmy B v´ yraznˇe pˇrebije reklamu firmy A. Firmˇe B klesnou zisky jen nepatrnˇe oproti nerealizaci reklamy firmy A a pro firmu A je jej´ı reklama témˇeˇr ne´ uˇcinná.

prvky a24, b24 strategie N (vzduchotechnika) vs. strategie L (vzduchotechnika, drahá verze) (100, 130) × (100, 155) ↓ (100, 110) × (100, 145) ↓ po penalizaci (100, 110) × (80, 145) 37

Drahá reklama firmy B opˇet v´ yraznˇe pˇrebije reklamu firmy A. Firmˇe B klesnou zisky opˇet jen málo oproti nerealizaci reklamy firmy A a naopak pro firmu B se t´ım zisky citelnˇe sn´ıˇz´ı.

prvky a21, b21 strategie N (vzduchotechnika) vs. strategie I (stavebnictv´ı, levná verze) (100, 130) × (120, 112) ↓ (95, 125) × (120, 106) Reklama na stavebnictv´ı firmy B sn´ıˇz´ı zisky ze stavebnictv´ı firmˇe A, která realizovala reklamu na vzduchotechniku. Reklama firmy B je natolik u ´ˇcinná, ˇze dokonce nepatrnˇe sn´ıˇz´ı zisky ze vzduchotechniky firmy A. Firmˇe B zase lehce klesnou zisky ze vzduchotechniky.

prvky a22, b22 strategie N (vzduchotechnika) vs. strategie J (stavebnictv´ı, drahá verze) (100, 130) × (135, 115) ↓ (80, 125) × (135, 110) ↓ po penalizaci (80, 125) × (115, 110) Drahá reklama firmy B ve stavebnictv´ı znatelnˇe sn´ıˇz´ı zisky firmy A, která realizuje reklamu vzduchotechniky. V´ yraznˇeji se to projev´ı ve stavebnictv´ı, ve vzduchotechnice je d´ıky vlastn´ı reklamˇe ménˇe v´ yrazné. Firmˇe B jen velmi málo sn´ıˇz´ı zisky reklama firmy A, drahá reklama, byt’ na stavebnictv´ı, ztráty minimalizuje.

prvky a13, b13 strategie M (stavebnictv´ı) vs. strategie K (vzduchotechnika, levná verze) (120, 112) × (100, 130) ↓ (120, 105) × (95, 130) 38

Reklama na vzduchotechniku firmy B lehce sn´ıˇz´ı zisky ze vzduchotechniky firmˇe ˇ adné velké zmˇeny A a firma A zase lehce sn´ıˇz´ı zisky ze stavebnictv´ı firmˇe B. Z´ nenastanou.

prvky a14, b14 strategie M (stavebnictv´ı) vs. strategie L (vzduchotechnika, drahá verze) (120, 112) × (100, 155) ↓ (120, 95) × (95, 155) ↓ po penalizaci (120, 95) × (75, 155) Drahá reklama firmy B ve vzduchotechnice velmi v´ yraznˇe sn´ıˇz´ı zisky firmy A, která realizuje reklamu na stavebnictv´ı. Firma A sn´ıˇz´ı zisky ze stavebnictv´ı firmˇe B jen nepatrnˇe a zisky ve vzduchotechnice v˚ ubec.

Nyn´ı máme pˇresnˇe specifikované zadán´ı. Budeme tedy ˇreˇsit v´ıcekriteriáln´ı hru dvou hráˇc˚ u zadanou maticemi A, B: (110, 106) (105, 102) (120, 105) (120, 95) A= . (95, 125) (80, 125) (100, 115) (100, 110) (110, 106) (110, 110) (95, 130) (75, 155) B= (120, 106) (115, 110) (100, 120) (80, 145)

39

4.2

ˇ sen´ı Reˇ

Máme tedy zadanou v´ıcekriteriáln´ı hru dvou hráˇc˚ u, kdy jeden má pouze dvˇe strategie. M˚ uˇzeme tedy vyuˇz´ıt teoretick´ y koncept z podkapitoly 3.2. Nejprve budeme analyzovat nejlepˇs´ı odpovˇed’ firmy A proti strategii q = (q1 , q2 , q3 , q4 ) firmy B. Máme dvˇe v´ yplatn´ı funkce, rozloˇz´ıme si matici A na matice jednotliv´ ych v´ yplatn´ıch funkc´ı: A1 =

A2 =

110 105 120 120 95 80 100 100

106 102 105 95 125 125 115 110

Nyn´ı hledáme rozloˇzen´ı mnoˇziny ( q; q = (q1 , q2 , q3 , q4 ),

4 X

,

.

) qi = 1, 0 ≤ qi ≤ 1

i=1

na mnoˇziny, pro které je nejlepˇs´ı strategi´ı (a) ˇcistá strategie M (b) ˇcistá strategie N (c) sm´ıˇsená strategie M, N. Snadno nahlédneme, ˇze strategie M je alespoˇ n tak dobrá jako strategie N (v obou kriteri´ıch zároveˇ n) právˇe tehdy, kdyˇz pro strategick´ y profil firmy B plat´ı soustava nerovnic: 110q1 + 105q2 + 120q3 + 120q4 ≥ 95q1 + 80q2 + 100q3 + 100q4 106q1 + 102q2 + 105q3 + 95q4 ≥ 125q1 + 125q2 + 115q3 + 110q4 . Po u ´pravˇe dostaneme dvojici nerovnic: 15q1 + 25q2 + 20q3 + 20q4 ≥ 0 19q1 + 23q2 + 10q3 + 15q4 ≤ 0. Na prvn´ı pohled vid´ıme, ˇze druhá nerovnice nikdy nebude splnˇena pro ˇza´dné 40

P ˇ a strategie M tedy nen´ı q = (q1 , q2 , q3 , q4 ) splˇ nuj´ıc´ı 4i=1 qi = 1, 0 ≤ qi ≤ 1. Cist´ jedinou nejlepˇs´ı odpovˇed´ı na ˇzádn´ y strategick´ y profil firmy B. Obdobnˇe nahlédneme, ˇze strategie N je alespoˇ n tak dobrá jako strategie M právˇe tehdy, kdyˇz plat´ı: 110q1 + 105q2 + 120q3 + 120q4 ≤ 95q1 + 80q2 + 100q3 + 100q4 106q1 + 102q2 + 105q3 + 95q4 ≤ 125q1 + 125q2 + 115q3 + 110q4 . Po u ´pravˇe: 15q1 + 25q2 + 20q3 + 20q4 ≤ 0 19q1 + 23q2 + 10q3 + 15q4 ≥ 0. Opˇet na prvn´ı pohled vid´ıme, nebude splnˇena pro ˇzádné P ˇze prvn´ı nerovnice nikdy ˇ a strategie N tedy také q = (q1 , q2 , q3 , q4 ) splˇ nuj´ıc´ı 4i=1 qi = 1, 0 ≤ qi ≤ 1. Cist´ nen´ı jedinou nejlepˇs´ı odpovˇed´ı na ˇza´dn´ y strategick´ y profil firmy B. To znamená, ˇze nejlepˇs´ı odpovˇed´ı na libovoln´ y strategick´ y profil q firmy B je vˇzdy sm´ıˇsená strategie M, N firmy A. Jin´ ymi slovy, m˚ uˇzeme ˇr´ıct, ˇze veˇskeré strategie firmy A jsou vˇzdy nejlepˇs´ı odpovˇed´ı na jak´ ykoli strategick´ y profil firmy B. Liˇs´ı se pouze v hodnotách v´ yplatn´ıch funkc´ı, pro které vˇzdy plat´ı, ˇze zv´ yˇs´ı-li se jedna, klesne druhá a naopak. Tedy v naˇsem názvoslov´ı m˚ uˇzeme zapsat regiony stability firmy B: ( U ({M }) =

q, q = (q1 , q2 , q3 , q4 ), (

U ({N }) =

q, q = (q1 , q2 , q3 , q4 ), (

U ({M, N }) =

q, q = (q1 , q2 , q3 , q4 ),

4 X i=1 4 X i=1 4 X

) qi = 1, 0 ≤ qi ≤ 1 ) qi = 1, 0 ≤ qi ≤ 1 ) qi = 1, 0 ≤ qi ≤ 1

i=1

Ted’ se m˚ uˇzeme pod´ıvat na zaj´ımavˇejˇs´ı situaci firmy B. Opˇet si matici B rozloˇz´ıme na jednotlivé matice v´ yplatn´ıch funkc´ı: B1 =

B2 =

110 110 95 75 120 115 100 80

106 110 130 155 106 110 120 145

41

,

.

Opˇet chceme naj´ıt regiony stability, tentokrát firmy A, zkoumáme tedy nejlepˇs´ı odpovˇed’ firmy B na strategick´ y profil (p, 1 − p) firmy A. Vynásob´ıme-li vektorem (p, 1 − p) matici B1 , z´ıskáme vektor hodnot prvn´ı v´ yplatn´ı funkce (zisk˚ u ve stavebnictv´ı) pˇri pouˇzit´ı jednotliv´ ych strategi´ı: (p, 1 − p) ·

110 110 95 75 120 115 100 80

= (120 − 10p, 115 − 5p, 100 − 5p, 80 − 5p).

To znamená, ˇze napˇr. pˇri pouˇzit´ı strategie J, bude hodnota zisku ve stavebnictv´ı 115 − 5p v závislosti na p. Obdobn´ y v´ ypoˇcet provedeme s matic´ı B2 a z´ıskáme tak vektor hodnot druhé v´ yplatn´ı funkce (zisk˚ u ve vzduchotechnice): (p, 1 − p) ·

106 110 130 155 106 110 120 145

= (106, 110, 120 + 10p, 145 + 10p).

Nyn´ı vektory pˇrevedeme na vektory hodnot obou v´ yplatn´ıch funkc´ı pˇri konkrétn´ı strategii: realizovaná strategie vektor v´ yplatn´ıch funkc´ı I (120 − 10p, 106) J (115 − 5p, 110) K (100 − 5p, 120 + 10p) L (80 − 5p, 145 + 10p) Regiony stability firmy A nyn´ı jiˇz relativnˇe snadno urˇc´ıme z obrázku. Nejprve si nakresl´ıme obrázek pro p = 0. K tomu jeˇstˇe poznamenáme, ˇze obrázky nebudou v reálném mˇeˇr´ıtku, ale poupraveny tak, aby byly zˇrejmé potˇrebné linie. Osa x reprezentuje zisky ze stavebnictv´ı, osa y zisky ze vzduchotechniky. Na obrázku 4.1 vid´ıme, ˇze nejlepˇs´ı odpovˇed´ı firmy B na strategii (0, 1) firmy A ve smyslu definice 3.9 je libovolná lineárn´ı kombinace ˇcist´ ych strategi´ı I a L, tj. sm´ıˇsená strategie q = (q1 , 0, 0, 1 − q1 ). Chceme rozloˇzit mnoˇzinu vˇsech strategi´ı firmy A podle toho, jaká sm´ıˇsená odpovˇed’ firmy B je proti nim nejlepˇs´ı. Z tabulky vektor˚ u v´ yplatn´ıch funkc´ı pˇri jednotliv´ ych ˇcist´ ych strategi´ıch vid´ıme, ˇze zvyˇsován´ım hodnoty p se nám body graficky posouvaj´ı: I se posouvá doleva, J se posouvá doleva, ale pomaleji neˇz I, K i L se posouvaj´ı po stejném vektoru doleva a nahoru. Postupn´ ym zvyˇsován´ım p se body posunou nejprve na pozici, kdy jsou body I, J a L na pˇr´ımce. Potˇrebujeme zjistit, pro které p to nastane. To zjist´ıme analyticky ˇreˇsen´ım tˇri rovnic o tˇrech

42

Obrázek 4.1: p = 0 neznám´ ych: 110 = a(115 − 5p) + b 106 = a(120 − 10p) + b 145 + 10p = a(80 − 5p) + b Vyˇreˇsen´ım nalezneme v´ ysledek p1,2 = Nás zaj´ımá kladné p =

√ − 25 + 9,05 2

− 52 ±

√ 9, 05 . 2

. = 0, 25.

h √ − 5 + 9,05 Tedy obrázek 4.1 plat´ı pro p ∈ 0, 2 2 . Dále na obrázku 4.2 vid´ıme situaci pˇr´ımo v bodˇe p =

√ − 52 + 9,05 . 2

Pokud p dále zvyˇsujeme, posuneme se do situace znázornˇené v obrázku 4.3. Nyn´ı nás zaj´ımá hodnota z z popisu obrázku 4.3 a jak v nˇem bude situace vypadat. Pokud zvyˇsujeme p, dostaneme se tentokrát do situace, kdy leˇz´ı na jedné pˇr´ımce body J, K a L. Opˇet analyticky spoˇcteme, pro které p situace nastane. ˇ s´ıme soustavu rovnic Reˇ 110 = a(115 − 5p) + b 120 + 10p = a(100 − 5p) + b 145 + 10p = a(80 − 5p) + b Snadno dospˇejeme k v´ ysledku p = 0, 875. Tedy obrázek 4.3 plat´ı pro √ − 25 + 9, 05 0, 875 > p > . 2 43

Obrázek 4.2: p =

√ − 52 + 9,05 2

Obrázek 4.3: z > p >

√ − 52 + 9,05 2

Obrázek 4.4: p = 0, 875

44

Na obrázku 4.4 pak vid´ıme, jak to vypadá pro p = 0, 875. Dále se situace nemˇen´ı a aˇz do bodu p = 1 vypadá jako na obrázku 4.5. V bodˇe p = 1 je pak zisk ze stavebnictv´ı stejn´ y pˇri strategii I i J a situace vypadá jako na obrázku 4.6.

Obrázek 4.5: 0, 875 < p < 1 Nyn´ı pro analogick´ y postup jako v pˇr´ıkladu 3.14 oznaˇc´ıme situaci na obrázku 4.1

Obrázek 4.6: p = 1 jako situaci I, situaci na obrázku 4.3 jako situaci II a situaci na obrázku 4.5 jako situaci III. Regiony stability pak snadno urˇc´ıme zcela analogick´ ym zp˚ usobem jako v pˇr´ıkladu 3.14. Vysvˇetlen´ı by bylo stejné, a proto pˇrejdeme rovnou k pˇrehlednému znázornˇen´ı region˚ u stability:

45

U ({I}) = I ∪ II ∪ III U ({J}) = II ∪ III U ({K}) = III U ({L}) = I ∪ II ∪ III U ({I, J}) = II ∪ III U ({I, K}) = ∅ U ({I, L}) = I U ({J, K}) = III U ({J, L}) = II U ({K, L}) = III U ({I, J, K}) = ∅ U ({I, J, L}) = I ∩ II U ({I, K, L}) = II ∩ III U ({J, K, L}) = ∅ U ({I, J, K, L}) = ∅

Nyn´ı z region˚ u stability za pomoci obrázk˚ u 4.1, 4.2, 4.3, 4.4, 4.5, 4.6 pro r˚ uzná p uˇz snadno urˇc´ıme ˇreˇsen´ı. V´ıme, ˇze napˇr. v pˇr´ıpadˇe regionu stability U ({I}) je nejlepˇs´ı odpovˇed´ı (1, 0, 0, 0), v pˇr´ıpadˇe regionu stability U ({I, J}) je nejlepˇs´ı odpovˇed´ı (q, 1 − q, 0, 0) atd. Situace I (obrázek 4.1) tedy zahrnuje 3 r˚ uzné regiony stability √ − 25 + 9,05 - U ({I}), U ({L}), U ({I, L}). Pro 0 ≤ p ≤ je tak nejlepˇs´ı odpovˇed´ı 2 {(q, 0, 0, 1 − q); q ∈ [0, 1]}. Pr˚ unik se situac´ı II, tj. obrázek 4.2 zahrnuje region stability U ({I, J, L}), tedy nejlepˇs´ı odpovˇed´ı je libovolná trojice (q1 , q2 , √ 0, q3 ) P3 − 25 + 9,05 (samozˇrejmˇe splˇ nuj´ıc´ı qi ≥ 0, i=1 qi = 1), coˇz plat´ı právˇe pro p = . 2 Obdobnˇe zkonstruujeme i dalˇs´ı rovnováˇzné body. Z toho sestav´ıme následuj´ıc´ı tabulku. Jednotlivá ˇreˇsen´ı jsou seˇrazena podle obrázk˚ u (6 obrázk˚ u, ˇreˇsen´ı podle jednotliv´ ych obrázk˚ u jsou oddˇelena dvojit´ ymi ˇcarami). Nˇekterá ˇreˇsen´ı se proto pˇrekr´ yvaj´ı (jednou patˇr´ı k neostré nerovnosti a jednou k rovnosti jako napˇr. ˇreˇsen´ı (10) je speciáln´ı pˇr´ıpad (7), ˇreˇsen´ı (11) je speciáln´ı pˇr´ıpad (8), ˇreˇsen´ı (12) je speciáln´ı pˇr´ıpad (9) apod.). Jeˇstˇe poznamenejme, ˇze situace v bodˇe p = 1 je zaj´ımavá v tom, ˇze s odpovˇed´ı (q, 1 − q, 0, 0) tvoˇr´ı slab´ y rovnováˇzn´ y bod, ale nikoli siln´ y rovnováˇzn´ y bod. Z toho d˚ uvodu jsou rovnováˇzné body pro p = 1 prezentovány samostatnˇe, nikoli pouze jako souˇca´st neostré nerovnosti v situaci 0, 875 ≤ p ≤ 1.

46

Rovnováˇzné body √ − 5 + 9,05 2

((p, 1 − p) , (q, 0, 0, 1 − q))

(1)

0≤p≤ 2 0≤q≤1

(2)

p=

(3)

√ − 25 + 9,05 2

((p, 1 − p) , (q, 1 − q, 0, 0))

√ − 25 + 9,05 2

≤ p ≤ 0.875 0≤q≤1

√ − 52 + 9,05 ,1 2

−

√ − 52 + 9,05 , (q , q , 0, q ) 1 2 3 2

(4)

√ − 25 + 9,05 2

≤ p ≤ 0.875 0≤q≤1

((p, 1 − p) , (0, q, 0, 1 − q))

(5)

p = 0.875

((0.875, 0.125) , (0, q1 , q2 , q3 ))

(6)

p = 0.875 0≤q≤1

((0.875, 0.125) , (q, 1 − q, 0, 0))

(7)

0.875 ≤ p ≤ 1 0≤q≤1

((p, 1 − p) , (0, q, 1 − q, 0))

(8)

0.875 ≤ p ≤ 1 0≤q≤1

((p, 1 − p) , (0, 0, q, 1 − q))

(9)

0.875 ≤ p ≤ 1 0≤q≤1

((p, 1 − p) , (q, 1 − q, 0, 0))

(10) p = 1 0≤q≤1

((1, 0) , (0, q, 1 − q, 0))

(11) p = 1 0≤q≤1

((1, 0) , (0, 0, q, 1 − q))

(12) p = 1 0≤q≤1

((1, 0) , (q, 1 − q, 0, 0))

47

V tabulce se nˇekteré rovnováˇzné body pˇrekr´ yvaj´ı, mohli bychom ji tedy trochu zjednoduˇsit. Udˇeláme disjunktn´ı systém slab´ ych rovnováˇzn´ ych bod˚ u:

(1)

√ − 5 + 9,05 2

0≤p< 2 0≤q≤1

(2) p =

(3)

(4)

√ − 25 + 9,05 2

((p, 1 − p) , (q, 0, 0, 1 − q))

√ − 52 + 9,05 ,1 2

−

√ − 25 + 9,05 , (q1 , q2 , 0, q3 ) 2

√ − 25 + 9,05 2

((p, 1 − p) , (q, 1 − q, 0, 0))

√ − 25 + 9,05 2

((p, 1 − p) , (0, q, 0, 1 − q))

< p ≤ 0.875 0≤q≤1

< p < 0.875 0≤q≤1

(5) p = 0.875

((0.875, 0.125) , (0, q1 , q2 , q3 ))

(7)

0.875 < p ≤ 1 0≤q≤1

((p, 1 − p) , (0, q, 1 − q, 0))

(8)

0.875 < p ≤ 1 0≤q≤1

((p, 1 − p) , (0, 0, q, 1 − q))

(9)

0.875 < p ≤ 1 0≤q≤1

((p, 1 − p) , (q, 1 − q, 0, 0))

Tato tabulka je tedy nejjednoduˇsˇs´ı moˇzné znázornˇen´ı rovnováˇzn´ ych bod˚ u. Vid´ıme, ˇze jsou rovnováˇzné body v podstatˇe seˇrazeny podle strategie firmy A. Na zaˇca´tku jsme si ukázali, ˇze nejlepˇs´ı odpovˇed´ı firmy A na strategii firmy B je libovolná strategie. Je tedy logické uspoˇra´dán´ı podle strategie zvolené firmou A.

4.3

Anal´ yza v´ ysledk˚ u

Jeˇstˇe se pod´ıváme, co vlastnˇe pro firmy naˇse ˇreˇsen´ı znamená. Naˇsli jsme velké mnoˇzstv´ı rovnováˇzn´ ych bod˚ u. Kaˇzd´ y rovnováˇzn´ y bod dle definice 3.4 znamená, ˇze ˇzádná z firem nem˚ uˇze zvolit - pˇri dané strategii druhé firmy - jinou neˇz uvedenou strategii tak, aby se j´ı zároveˇ n zv´ yˇsily jak zisky ze stavebnictv´ı, tak zisky 48

ze vzduchotechniky. Jeˇstˇe poznamenejme, ˇze tento koncept ˇreˇsen´ı dokáˇze nalézt silné rovnováˇzné body z definice 3.5 (pˇri hledán´ı slab´ ych rovnováˇzn´ ych bod˚ u je nalezne automaticky, ˇ sen´ı prob´ıhá nebot’ kaˇzd´ y siln´ y rovnováˇzn´ y bod je i slab´ y rovnováˇzn´ y bod). Reˇ zcela analogicky. Pˇri hledán´ı siln´ ych rovnováˇzn´ ych bod˚ u vˇsak neplat´ı nutnˇe moˇzn´ y rozklad mnoˇziny rovnováˇzn´ ych bod˚ u na koneˇcné sjednocen´ı konvexn´ıch polyedr˚ u. Pokud jsou vˇsak splnˇeny urˇcité podm´ınky a mnoˇzina rovnováˇzn´ ych bod˚ u je koneˇcn´ ym sjednocen´ım konvexn´ıch polyedr˚ u, pak lze takto nalézt silné rovnováˇzné body, jako je tomu v tomto pˇr´ıkladˇe. Samotné nalezen´ı rovnováˇzn´ ych bod˚ u vˇsak jeˇstˇe pro firmy moc neznamená, firmy se zaj´ımaj´ı o to, jaké budou m´ıt pˇri jednotliv´ ych rovnováˇzn´ ych bodech hodnoty zisk˚ u z jednotliv´ ych odvˇetv´ı. Z ˇreˇsen´ı máme spoˇc´ıtané zisky firmy B pˇri jednotliv´ ych ˇcist´ ych strategi´ıch za pˇredpokladu sm´ıˇsené strategie (p, 1 − p) firmy A a zisky firmy A pˇri jednotliv´ ych ˇcist´ ych strategi´ıch za pˇredpokladu sm´ıˇsené strategie (q1 , q2 , q3 , q4 ) firmy B:

strategie M N I J K L

vektor v´ yplatn´ıch funkc´ı (110q1 + 105q2 + 120q3 + 120q4 , 106q1 + 102q2 + 105q3 + 95q4 ) (95q1 + 105q2 + 120q3 + 120q4 , 125q1 + 125q2 + 115q3 + 110q4 ) (120 − 10p, 106) (115 − 5p, 110) (100 − 5p, 120 + 10p) (80 − 5p, 145 + 10p)

Staˇc´ı tedy v bodech, které jsme znázornili v tabulce rovnováˇzn´ ych bod˚ u, vyjádˇrit oˇcekávané hodnoty v´ yplatn´ıch funkc´ı, jak vid´ıme ve v´ yˇse uvedené tabulce. Pro rovnováˇzn´ y bod (1) tak pro zisk firmy A vynásob´ıme vektor rovnováˇzného bodu s v´ yˇse uvedenou matic´ı v´ yplatn´ıch funkc´ı firmy A: (p, 1 − p) ·

110q1 + 105q2 + 120q3 + 120q4 106q1 + 102q2 + 105q3 + 95q4 95q1 + 105q2 + 120q3 + 120q4 125q1 + 125q2 + 115q3 + 110q4

.

V rovnováˇzném bodu (1) vˇsak v´ıme, ˇze q1 = q, q2 = 0, q3 = 0, q4 = 1 − q, tedy dostaneme (p, 1 − p) ·

110q + 120(1 − q) 106q + 95(1 − q) 95q + 120(1 − q) 125q + 110(1 − q)

.

Pro zisk firmy B v rovnováˇzném bodu (1) vynásob´ıme vektor rovnováˇzného bodu s v´ yˇse uvedenou matic´ı v´ yplatn´ıch funkc´ı firmy B: 49



 120 − 10p 106  115 − 5p  110  (q, 0, 0, 1 − q) ·   100 − 5p 120 + 10p  . 80 − 5p 145 + 10p

Analogicky z´ıskáme hodnoty zisku v dalˇs´ıch rovnováˇzn´ ych bodech, jak vid´ıme po u ´pravˇe v následuj´ıc´ıch tabulk´ a ch. Pro zjednoduˇ s en´ ı a zpˇrehlednˇen´ı zapsan´ ych √ − 25 + 9,05 . = 0, 25 a hodnoty u v´ yplatn´ıch funkc´ı zaokrouv´ ysledk˚ u zaokrouhl´ıme 2 hl´ıme na jedno desetinné m´ısto.

V´ yplatn´ı funkce firmy A v rovnováˇzn´ ych bodech: (1)

0 ≤ p < 0, 25 0≤q≤1

(2) p = 0, 25

(−5q − 5pq + 20p + 100; 15q − 4pq − 15p + 110)

(98, 8q1 + 86, 2q2 + 106, 2q3 ; 120, 2q1 + 119, 2q2 + 106, 2q3 )

(3)

0, 25 < p ≤ 0.875 0≤q≤1

(15q − 10pq + 25p + 80; 4pq − 23p + 125)

(4)

0, 25 < p < 0.875 0≤q≤1

(−20q + 5pq + 20p + 100; 15q − 4pq − 15p + 110)

(5) p = 0.875

(101, 9q1 + 117, 5q2 + 117, 5q3 ; 104, 9q1 + 106, 2q2 + 96, 9q3 )

(7)

0.875 < p ≤ 1 0≤q≤1

(−20q + 5pq + 20p + 100; 10q − 13pq − 10p + 115)

(8)

0.875 < p ≤ 1 0≤q≤1

(20p + 100; 5q + 5pq − 15p + 110)

(9)

0.875 < p ≤ 1 0≤q≤1

(15q − 20pq + 25p + 80; 4pq − 23p + 125)

50

V´ yplatn´ı funkce firmy B v rovnováˇzn´ ych bodech: (1)

0 ≤ p < 0, 25 0≤q≤1

(2) p = 0, 25

(40q − 5pq − 5p + 80; −39q − 10pq + 10p + 145)

(117, 5q1 + 113, 8q2 + 78, 8q3 ; 106q1 + 110q2 + 147, 5q3 )

(3)

0, 25 < p ≤ 0.875 0≤q≤1

(5q − 5pq − 5p + 115; −4q + 110)

(4)

0, 25 < p < 0.875 0≤q≤1

(35q − 5p + 80; −35q − 10pq + 10p + 145)

(5) p = 0.875

(110, 6q1 + 95, 6q2 + 75, 6q3 ; 110q1 + 128, 8q2 + 153, 8q3 )

(7)

0.875 < p ≤ 1 0≤q≤1

(15q − 5p + 100; −10q − 10pq + 10p + 120)

(8)

0.875 < p ≤ 1 0≤q≤1

(20q − 5p + 80; −25q + 10p + 145)

(9)

0.875 < p ≤ 1 0≤q≤1

(5q − 5pq − 5p + 115; −4q + 110)

Podle tabulek se tedy firmy mohou rozhodnout, kter´ y rovnováˇzn´ y bod preferuj´ı. Pro lepˇs´ı orientaci je pro firmu vhodné zkusit si dosadit konkrétn´ı hodnoty p a q z daného intervalu, sama se mus´ı rozhodnout, které v´ yplatn´ı funkci dá pˇrednost a nakolik. Zaj´ımavé pro nás jeˇstˇe je, ˇze kdyˇz se pod´ıváme na tabulku rovnováˇzn´ ych bod˚ u, vid´ıme, ˇze hra má ˇreˇsen´ı i v ˇcist´ ych strategi´ıch. Pro zaj´ımavost uvedeme tabulku ˇreˇsen´ı v ˇcist´ ych strategi´ıch vˇcetnˇe v´ yplatn´ıch funkc´ı obou firem. Tabulku vypoˇcteme z tabulek v´ yplatn´ıch funkc´ı pˇr´ım´ ym dosazen´ım pˇr´ısluˇsn´ ych p a q. V rovnováˇzném bodˇe (1) tak dosazujeme p = 0 a q = 1 pro zisky pˇri ˇcist´ ych (N, I) a p = 0 a q = 0 pro zisky pˇri ˇcist´ ych strategi´ıch (N, L). Obdobnˇe v rovnováˇzn´ ych bodech (7), (8), (9) dosazujeme p = 1, q = 0 a q = 1, abychom z´ıskali zisky v ˇcist´ ych strategi´ıch (M, I), (M, J), (M, K), (M, L). V´ ysledky shrneme v následuj´ıc´ı tabulce:

51

strategie firmy A strategie firmy B N I N L M I M J M K M L

zisk firmy A zisk firmy B (95, 125) (120, 106) (100, 110) (80, 145) (110, 106) (110, 106) (105, 102) (110, 110) (120, 105) (95, 130) (120, 95) (75, 155)

Tabulka se pochopitelnˇe shoduje s maticemi v´ yplatn´ıch funkc´ı v zadán´ı, vid´ıme tedy, ˇze jsme poˇc´ıtali správnˇe. Zaj´ımavé je, jak vyˇcteme z tabulky, ˇze zvol´ı-li firma A strategii M , m˚ uˇze firma B zvolit jakoukoli ˇcistou strategii a hra bude v rovnováze. Z toho bychom mohli odvodit doporuˇcen´ı volby strategie M pro firmu A. Z´ıská t´ım jistotu, ˇze at’ firma B zvol´ı jakoukoli ˇcistou nebo sm´ıˇsenou strategii, hra z˚ ustane v rovnováze. Pokud vˇsak firma A má urˇcité preference, které sp´ıˇse upˇrednostˇ nuj´ı vzduchotechnické odvˇetv´ı, nejsp´ıˇs by nesouhlasila a zvolila nˇejakou sm´ıˇsenou strategii. Nav´ıc jsme si na zaˇcátku ukázali, ˇze jakákoli odpovˇed’ firmy A je vˇzdy nejlepˇs´ı odpovˇed´ı na jakoukoli odpovˇed’ firmy B, a tak ji vlastnˇe nemus´ı zaj´ımat, zda se nacház´ı v rovnováˇzném bodˇe, nebo ne a trat´ı na tom firma B. Nakonec je nutné poznamenat, ˇze ve v´ıcekriteriáln´ıch nekooperativn´ıch hrách se setkáváme s nov´ ym metodick´ ym problémem. Pokud máme standardn´ı jednokriteriáln´ı hru a nalezneme Nash˚ uv rovnováˇzn´ y bod, znamená to, ˇze obˇe firmy by se mˇely drˇzet doporuˇcené strategie, v opaˇcném pˇr´ıpadˇe na tom jednoznaˇcnˇe budou tratit. Ve v´ıcekriteriáln´ı hˇre jsme vˇsak naˇsli v´ıce r˚ uzn´ ych rovnováˇzn´ ych bod˚ u. A lze obecnˇe ˇr´ıci, ˇze hra s v´ıce v´ yplatn´ımi funkcemi typicky vede k nejednoznaˇcnému rovnováˇznému bodu. A pokud v naˇsem pˇr´ıpadˇe obˇe firmy zvol´ı svou rovnováˇznou strategii, ale kaˇzdá v jiném rovnováˇzném bodˇe, hra v rovnováze b´ yt nemus´ı. Jin´ ymi slovy, jedna ˇci obˇe firmy by mohly zvolit jinou strategii tak, ˇze by mˇely zisky z obou odvˇetv´ı vyˇsˇs´ı. Z tohoto d˚ uvodu je doporuˇceno firmám ˇca´steˇcnˇe spolupracovat a domluvit se. Problému, jak v tomto pˇr´ıpadˇe pˇrimˇet hráˇce spolupracovat, se podrobnˇeji vˇenuje autor A. P. Wierzbicki (napˇr. A mathematical basis for satisficing decision making nebo Negotiation and mediation in conflicts I: The role of mathematical approaches and methods, resp. Negotiation and mediation II: Plural rationality and interactive decision processes). Na závˇer jeˇstˇe uved’me, jakou souvislost má mnoˇzstv´ı kritéri´ı a strategi´ı s mnoˇzstv´ım rovnováˇzn´ ych bod˚ u. Obecnˇe plat´ı, ˇze ˇc´ım v´ıce kritéri´ı a ménˇe strategi´ı máme, t´ım v´ıce rovnováˇzn´ ych bod˚ u existuje. Pokud se tedy jedná o vˇetˇs´ı hru, m˚ uˇze b´ yt systém rovnováˇzn´ ych bod˚ u znaˇcnˇe nepˇrehledn´ y, i kdyˇz se nám podaˇr´ı naj´ıt vˇsechny rovnováˇzné body i hodnoty v´ yplatn´ıch funkc´ı v nich. Se vzr˚ ustaj´ıc´ım poˇctem rovnováˇzn´ ych bod˚ u ovˇsem také roste mnoˇzstv´ı ˇreˇsen´ı v ˇcist´ ych strategi´ıch. Pokud by se nám podaˇrilo vytvoˇrit systém ˇreˇsen´ı v ˇcist´ ych strategi´ıch, byl by rozhodnˇe pˇrehlednˇejˇs´ı. V dalˇs´ı kapitole se tedy budeme zab´ yvat moˇznost´ı hledán´ı ˇreˇsen´ı v´ıcekriteriáln´ıch her v ˇcist´ ych strategi´ıch.

52

Kapitola 5 Teoretick´ e v´ ysledky 5.1

ˇ sen´ı v ˇ Reˇ cist´ ych strategi´ıch

V aplikaci na konkrétn´ı hru jsme si vˇsimli, ˇze existovalo ˇreˇsen´ı v ˇcist´ ych strategi´ıch, a to dokonce nˇekolik. Pod´ıváme se, jak to je s ˇreˇsen´ım v ˇcist´ ych strategi´ıch ve v´ıcekriteriáln´ıch hrách obecnˇe. Ve standardn´ı hˇre je ˇreˇsen´ı v ˇcist´ ych strategi´ıch sp´ıˇse v´ yjimeˇcné a existuje pouze ve speciáln´ıch pˇr´ıpadech. Ve hˇre s vektorovou v´ yplatn´ı funkc´ı je vˇsak situace jiná. ˇ Reˇsen´ı v ˇcist´ ych strategi´ıch naopak velice ˇcasto existuje. A jeho existence je t´ım pravdˇepodobnˇejˇs´ı, ˇc´ım ménˇe ˇcist´ ych strategi´ı a ˇc´ım v´ıce kritéri´ı hráˇci maj´ı. Je to zp˚ usobeno velk´ ym mnoˇzstv´ım rovnováˇzn´ ych bod˚ u, coˇz vypl´ yvá z toho, ˇze eficientn´ıch bod˚ u u v´ıcekriteriáln´ı optimalizace také b´ yvá velmi mnoho. Nalezen´ı nˇekolika ˇreˇsen´ı v ˇcist´ ych strategi´ıch je velice rychlé a snadné. Nyn´ı si na pˇr´ıkladˇe ukáˇzeme moˇzn´ y zp˚ usob hledán´ı rovnováˇzn´ ych bod˚ u v ˇcist´ ych strategi´ıch a poté se pod´ıváme na jeho vlastnosti. Pˇ r´ıklad 5.1. Uvaˇzujme opˇet maticovˇe zadanou hru dvou hráˇc˚ u. Prvn´ı hráˇc má tˇri kritéria, druh´ y hráˇc má dvˇe kritéria. Hráˇc 1 má strategie X a Y , hráˇc 2 má strategie A, B, C. Hodnoty v´ yplatn´ıch funkc´ı jsou zobrazeny v následuj´ıc´ıch matic´ıch. Prvn´ı hráˇc:

(2, 1, 2) (4, 2, 9) (0, 2, 1) (3, 7, 1) (7, 1, 0) (1, 8, 2)

.

Druh´ y hráˇc:

(0, 4) (2, 5) (1, 2) (1, 7) (7, 3) (1, 0)

.

Nyn´ı budeme zkoumat nejlepˇs´ı odpovˇedi hráˇc˚ u. Nejprve se pod´ıváme na nejlepˇs´ı odpovˇedi prvn´ıho hráˇce. Rozep´ıˇseme si matici vektor˚ u v´ yplatn´ıch funkc´ı na jed53

notlivé matice a nahlédneme, jaké ˇcisté strategie jsou nejlepˇs´ı odpovˇed´ı na jednotlivé ˇcisté strategie druhého hráˇce. Prvn´ı kritérium:

2 4 0 3 7 1

1 2 2 7 1 8

2 9 1 1 0 2

,

druhé kritérium:

,

tˇret´ı kritérium:

.

Pokud druh´ y hráˇc zahraje strategii A, nejlepˇs´ı odpovˇed´ı prvn´ıho hráˇce je jak strategie X, tak strategie Y . Vycház´ıme z u ´vahy, ˇze taková ˇcistá strategie, která je alespoˇ n v jednom kritériu maximáln´ı (vzhledem k strategii A druhého hráˇce), je nejlepˇs´ı odpovˇed´ı. Je tomu tak proto, ˇze taková strategie nem˚ uˇze b´ yt dominována ˇzádnou jinou, v daném kritériu bude m´ıt vˇzdy vyˇsˇs´ı hodnotu neˇz jakákoli kombinace ostatn´ıch strategi´ı. Tedy za pˇredpokladu strategie A druhého hráˇce je dle prvn´ıho kritéria nejlepˇs´ı odpovˇed´ı strategie Y , dle druhého kritéria strategie Y a dle tˇret´ıho kritéria strategie X. Takˇze na strategii A je nejlepˇs´ı odpovˇed´ı jak strategie X, tak strategie Y . Obdobnˇe zjist´ıme, ˇze za pˇredpokladu strategie B druhého hráˇce je nejlepˇs´ı odpovˇed´ı strategie X i Y . Za pˇredpokladu strategie C je nejlepˇs´ı odpovˇed´ı pouze strategie Y , nebot’ dominuje strategii X ve vˇsech kritéri´ıch. Nyn´ı provedeme analogickou anal´ yzu ze strany druhého hráˇce. Nejprve si rozep´ıˇseme matici vektor˚ u na matice dle jednotliv´ ych kritéri´ı: Prvn´ı kritérium:

0 2 1 1 7 1

4 5 2 7 3 0

,


.

Pokud prvn´ı hráˇc zahraje strategii X, pak nejlepˇs´ı odpovˇed´ı druhého hráˇce je pouze ˇcistá strategie B, nebot’ v obou kritéri´ıch dominuje strategii A i C. Nejlepˇs´ı odpovˇed´ı na strategii Y jsou pak ˇcisté strategie A a B. Protoˇze plat´ı, ˇze dvojice strategi´ı (p, q) je rovnováˇzn´ ym bodem právˇe tehdy, kdyˇz p je nejlepˇs´ı odpovˇed´ı na q a q je nejlepˇs´ı odpovˇed´ı na p, snadno z pˇredchoz´ıch 54

u ´vah urˇc´ıme nˇekteré rovnováˇzné body. Rovnováˇzn´ ymi body v ˇcist´ ych strategi´ıch tak jsou dvojice strategi´ı (X, B), (Y, A), (Y, B). To plyne z toho, ˇze jsme zjistili, ˇze X je nejlepˇs´ı odpovˇed´ı na B i B je nejlepˇs´ı odpovˇed´ı na X, obdobnˇe i pro zbylé dva body. Prakticky okamˇzitˇe jsme tak naˇsli nˇekolik rovnováˇzn´ ych bod˚ u. M Hlavn´ı v´ yhodou v´ yˇse popsaného zp˚ usobu je jeho nenároˇcnost. Velice rychle nalezneme nˇekolik rovnováˇzn´ ych bod˚ u. Jen tak mimochodem jsou to ˇreˇsen´ı v ˇcist´ ych strategi´ıch. Nyn´ı si jeˇstˇe na nˇekolika pˇr´ıkladech ukáˇzeme vlastnosti v´ yˇse uvedeného zp˚ usobu ˇreˇsen´ı. Nejprve se pod´ıváme na rozd´ılnost hledán´ı siln´ ych a slab´ ych rovnováˇzn´ ych bod˚ u. Uveden´ ym zp˚ usobem lze hledat oba typy rovnováˇzn´ ych bod˚ u, jen postupujeme trochu odliˇsnˇe. Pˇ r´ıklad 5.2. V pˇr´ıkladu 5.1 nedoˇslo nikde ke shodˇe hodnot u v´ıce strategi´ı. Uvaˇzovali jsme dominanci ve smyslu <“ z definice 3.3 a vˇsechny nalezené rovno” váˇzné body byly silné. Pokud vˇsak k nˇejaké shodˇe dojde, m˚ uˇzeme se drˇzet definice dominance a hledat tak silné rovnováˇzné body, nebo m˚ uˇzeme chápat dominanci ve smyslu ≤“ a hledat slabé rovnováˇzné body. Vrát´ıme se k pˇredchoz´ımu pˇr´ıkladu ” a malinko ho pozmˇen´ıme. Prvn´ı hráˇc:

(2, 1, 2) (7, 2, 9) (0, 2, 1) (3, 7, 1) (7, 1, 9) (1, 8, 2)

.

Druh´ y hráˇc:

(0, 4) (2, 5) (1, 2) (1, 7) (7, 3) (1, 0)

.

Zmˇenili jsme hodnoty v´ yplatn´ıch funkc´ı prvn´ıho hráˇce u prvn´ıho a tˇret´ıho kritéria pˇri strategii B druhého hráˇce. Opˇet budeme hledat nejlepˇs´ı odpovˇedi. Vzhledem k nezmˇenˇené matici druhého hráˇce z˚ ustávaj´ı i jeho nejlepˇs´ı odpovˇedi stejné, tedy B je nejlepˇs´ı odpovˇed´ı na strategii X a strategie A a B jsou nejlepˇs´ı odpovˇed´ı na strategii Y . Matici prvn´ıho hráˇce si opˇet rozep´ıˇseme. Prvn´ı kritérium:

2 7 0 3 7 1

1 2 2 7 1 8

,


55

,

tˇret´ı kritérium:

2 9 1 1 9 2

.

Nejlepˇs´ı odpovˇedi na strategie A a C z˚ ustávaj´ı stejné, tedy nejlepˇs´ı odpovˇed´ı na A je X i Y a nejlepˇs´ı odpovˇed´ı na C je Y . Situace je zaj´ımavˇejˇs´ı za pˇredpokladu volby strategie B druh´ ym hráˇcem. U prvn´ıho a tˇret´ıho kritéria jsou hodnoty stejné u strategie X i Y . U druhého kritéria X dominuje Y . Ted’ záleˇz´ı, zda hledáme slabé ˇci silné rovnováˇzné body. Pokud nás zaj´ımaj´ı slabé rovnováˇzné body, pak pˇri rovnosti v´ıce strategi´ı povaˇzujeme za nejlepˇs´ı odpovˇedi obˇe. Pokud nás naopak zaj´ımaj´ı silné rovnováˇzné body, pak pˇri rovnosti v´ıce strategi´ı nepovaˇzujeme (u daného kritéria) za nejlepˇs´ı odpovˇed’ ani jednu, ovˇsem s jednou v´ yjimkou. Pakliˇze by byla rovnost u vˇsech kritéri´ı, pak také povaˇzujeme vˇsechny strategie za nejlepˇs´ı odpovˇedi i za pˇredpokladu hledán´ı siln´ ych rovnováˇzn´ ych bod˚ u. Vˇse snadno vycház´ı z definice slabého a silného rovnováˇzného bodu. Tedy v naˇsem pˇr´ıkladˇe uvaˇzujeme-li slabé rovnováˇzné body, z˚ ustanou jimi dvojice strategi´ı (X, B), (Y, A), (Y, B). Uvaˇzujeme-li silné rovnováˇzné body, situace se zmˇen´ı. Pˇri volbˇe strategie B druh´ ym hráˇcem je strategie Y dominována strategi´ı X, nejlepˇs´ı odpovˇed´ı na strategii B je tak pouze strategie Y . T´ım se nám ztrat´ı rovnováˇzn´ y bod (X, B) a z˚ ustanou pouze rovnováˇzné body (Y, A) a (Y, B). M Dále budeme zkoumat existence rovnováˇzn´ ych bod˚ u v ˇcist´ ych strategi´ıch. Vzhledem k uveden´ ym pˇr´ıklad˚ um by se mohlo zdát, ˇze rovnováˇzné body v ˇcist´ ych strategi´ıch za nˇejak´ ych pˇredpoklad˚ u mus´ı existovat. Obvykle sice skuteˇcnˇe nˇejaké takové ˇreˇsen´ı existuje, ale pro libovolnou velikost pˇr´ıkladu (poˇcet strategi´ı i kritéri´ı) lze nalézt speciáln´ı protipˇr´ıklad, kdy ˇreˇsen´ı v ˇcist´ ych strategi´ıch neexistuje. Nejpˇrirozenˇejˇs´ı protipˇr´ıklad se sestroj´ı tak, ˇze se urˇc´ı vˇsechna kritéria jako toˇ sen´ı tak bude shodné s ˇreˇsen´ım klasické hry s jedinou v´ toˇzná. Reˇ yplatn´ı funkc´ı zadanou jedn´ım z kritéri´ı. Z klasické teorie her pak plyne, ˇze lze naj´ıt protipˇr´ıklad libovolné velikosti takov´ y, ˇze ˇreˇsen´ı v ˇcist´ ych strategi´ıch neexistuje. My si ukáˇzeme jeden pˇr´ıklad hry s nestejn´ ymi kritérii, kdy ˇza´dné ˇreˇsen´ı v ˇcist´ ych strategi´ıch neexistuje. Pˇ r´ıklad 5.3. Uvaˇzujme dva hráˇce, kaˇzd´ y má dvˇe kritéria. Prvn´ı hráˇc má strategie X, Y , druh´ y hráˇc má strategie A, B, C, D. Kritéria prvn´ıho hráˇce jsou zadána následuj´ıc´ımi maticemi: 9 9 1 1 , 1 1 9 9 9 9 1 1 . 1 1 9 9

56

Kritéria druhého hráˇce jsou zadána maticemi: 1 1 9 1 , 1 9 1 1 1 1 1 9 . 9 1 1 1 Pokud hledáme ˇreˇsen´ı pomoc´ı v´ yˇse popsaného zp˚ usobu, snadno zjist´ıme, ˇze ˇza´dné ˇreˇsen´ı nenajde. X je nejlepˇs´ı odpovˇed´ı na strategie A a B, Y je nejlepˇs´ı odpovˇed´ı na C a D. A a B jsou nejlepˇs´ı odpovˇed´ı na X, C a D jsou nejlepˇs´ı odpovˇed´ı na Y . Nenalezli jsme tedy ˇzádné ˇreˇsen´ı. Ovˇeˇr´ıme si, ˇze hra skuteˇcnˇe ˇreˇsen´ı v ˇcist´ ych strategi´ıch nemá. Vyuˇzijeme k tomu konceptu z kapitoly 3.2, kter´ y jsme uˇz podrobnˇe aplikovali v kapitole 4, a tak bude snadné u ´lohu vyˇreˇsit. Nejprve zkoumáme nejlepˇs´ı odpovˇed’ prvn´ıho hráˇce na strategii (q1 , q2 , q3 , q4 ) druhého hráˇce. Strategie X je nejlepˇs´ı odpovˇed´ı právˇe tehdy, kdyˇz plat´ı 9q1 + 9q2 + q3 + q4 ≥ q1 + q2 + 9q3 + 9q4 . Jedná se pouze o jednu nerovnici, nebot’ obˇe kritéria maj´ı stejné hodnoty. Nerovnici snadno uprav´ıme na tvar q1 + q2 ≥ q3 + q4 . Obdobnˇe Y je nejlepˇs´ı odpovˇed´ı právˇe tehdy, kdyˇz plat´ı q1 + q2 ≤ q3 + q4 . Obˇe strategie X i Y jsou pak nejlepˇs´ımi odpovˇed’mi právˇe tehdy, kdyˇz plat´ı 1 = q3 + q 4 . 2

q 1 + q2 =

Dále nás zaj´ımá nejlepˇs´ı odpovˇed’ druhého hráˇce na strategii (p, 1 − p) prvn´ıho hráˇce. Nejprve sestav´ıme vektory kritéri´ı pˇri daném parametru p. Prvn´ı kritérium: 1 1 9 1 (p, 1 − p) · = (1, 9 − 8p, 1 + 8p, 1). 1 9 1 1 Druhé kritérium: (p, 1 − p) ·

1 1 1 9 9 1 1 1

57

= (9 − 8p, 1, 1, 1 + 8p).

Obrázek 5.1: p = 0

Obrázek 5.2: p =

1 2

Nyn´ı se pod´ıváme obrázky 5.1, 5.2 a 5.3, abychom vidˇeli nejlepˇs´ı odpovˇedi.

Situace se zmˇen´ı pouze v bodˇe p = 12 , jak vid´ıme na obrázku 5.2. Z obrázk˚ u nyn´ı snadno sestav´ıme nejlepˇs´ı odpovˇedi druhého hráˇce v závislosti na p:

58

Obrázek 5.3: p = 1 nejlepˇs´ı odpovˇed’

p 0≤p< p= 1 2

1 2

1 2

(q, 1 − q, 0, 0)

q ∈ [0, 1]

(q1 , q2 , q3 , q4 )

qi ≥ 0,

≤ p < 1 (0, 0, q, 1 − q)

P4

i=1 qi

=1

q ∈ [0, 1]

Kdyˇz nyn´ı dáme nejlepˇs´ı odpovˇedi dohromady, zjist´ıme, ˇze jedin´ ym rovnováˇzn´ ym bodem je 1 1 , ; (q1 , q2 , q3 , q4 ), 2 2 kde

1 = q 3 + q4 . 2 Pokud je p ≤ 21 , pak je nejlepˇs´ı odpovˇed´ı druhého hráˇce strategie (q, 1 − q, 0, 0), ale na takovou strategii je nejlepˇs´ı odpovˇed´ı prvn´ıho hráˇce ˇcistá strategie X, tj. p = 1. Obdobnˇe je-li p ≥ 12 , pak je nejlepˇs´ı odpovˇed´ı druhého hráˇce strategie (0, 0, q, 1 − q), ale na takovou strategii je nejlepˇs´ı odpovˇed´ı prvn´ıho hráˇce ˇcistá strategie Y , tj. p = 0. V´ yˇse uveden´ y rovnováˇzn´ y bod je tedy jedin´ y. Hra tedy nemá ˇza´dné ˇreˇsen´ı v ˇcist´ ych strategi´ıch. qi ≥ 0, q1 + q2 =

M ˇ sen´ı v ˇcist´ Reˇ ych strategi´ıch tedy nutnˇe existovat nemus´ı. Ukáˇzeme si, ˇze v pˇr´ıpadˇe, ˇze ˇreˇsen´ı v ˇcist´ ych strategi´ıch existuje, m˚ uˇze pˇresto nastat situace, ˇze v´ yˇse popsan´ y zp˚ usob nenalezne vˇsechna ˇreˇsen´ı v ˇcist´ ych strategi´ıch.

59

Pˇ r´ıklad 5.4. Nyn´ı uvaˇzujeme, ˇze oba hráˇci maj´ı dvˇe kritéria, prvn´ı hráˇc má dvˇe strategie X a Y a druh´ y hráˇc má tˇri strategie A, B a C. Kritéria prvn´ıho hráˇce:

9 1 8 1 9 1

9 1 8 1 9 1

1 9 8 9 1 8

9 1 8 1 9 8

, .

Kritéria druhého hráˇce:

, .

Na prvn´ı pohled vid´ıme, ˇze nejlepˇs´ı odpovˇed´ı prvn´ıho hráˇce na strategii A je strategie X, na strategii B strategie Y a na strategii C strategie X. Nejlepˇs´ı odpovˇed´ı druhého hráˇce na strategii X jsou strategie A a B a na strategii Y taktéˇz strategie A a B. Nalezen´ ym ˇreˇsen´ım tedy jsou (X, A), (Y, B). Nyn´ı najdeme vˇsechny rovnováˇzné body. Nejdˇr´ıve nás zaj´ımá nejlepˇs´ı odpovˇed’ prvn´ıho hráˇce na strategii (q1 , q2 , q3 ) druhého hráˇce. Strategie X je nejlepˇs´ı odpovˇed´ı právˇe kdyˇz 9q1 + q2 + 8q3 ≥ q1 + 9q2 + q3 . Po u ´pravˇe dosad´ıme q2 = 1 − q1 − q3 a dostaneme 16q1 + 15q3 ≥ 8. Obdobnˇe Y je nejlepˇs´ı odpovˇed´ı právˇe kdyˇz 16q1 + 15q3 ≤ 8. V tomto pˇr´ıpadˇe je pˇrehlednˇejˇs´ı obrázek, viz obrázek 5.4. Na obrázku 5.4 bod (0,0) reprezentuje ˇcistou strategii B, bod (1,0) reprezentuje ˇcistou strategii A a bod (0,1) reprezentuje ˇcistou strategii C. Tedy ˇcistá strategie X je nejlepˇs´ı odpovˇed´ı na strategie A a C a ˇcistá strategie Y je nejlepˇs´ı odpovˇed´ı na B. Dále se pod´ıváme na nejlepˇs´ı odpovˇedi druhého hráˇce na strategii (p, 1 − p) 60

Obrázek 5.4: nejlepˇs´ı odpovˇedi prvn´ıho hráˇce prvn´ıho hráˇce. Opˇet sestav´ıme vektory kritéri´ı pˇri daném parametru p. Prvn´ı kritérium: 1 9 8 (p, 1 − p) · = (9 − 8p, 1 + 8p, 8). 9 1 8 Druhé kritérium: (p, 1 − p) ·

9 1 8 1 9 8

= (1 + 8p, 9 − 8p, 8).

Nakresl´ıme si obrázek pro p = 0 a p = 1.


61

Obrázek 5.6: p = 1 Pro 0 < p < 1 se situace mˇen´ı tak, ˇze se body A a B posouvaj´ı navzájem k sobˇe, aˇz se prohod´ı a dostanou se do situace pro p = 1. Pokud bychom chtˇeli pˇr´ıklad doˇreˇsit, nalezli bychom bod, ve kterém je prvn´ı kritérium pˇri strategii A rovno osmi (jako kritériu pˇri strategii C), tj. p = 18 . Analogicky druhé kritérium je rovno osmi pro p = 78 . Pak pro 81 < p < 78 je nejlepˇs´ı odpovˇed´ı pouze ˇcistá strategie C. To vˇsak pro nás nen´ı zaj´ımavá situace. Tedy pˇri 0 ≤ p ≤ 81 vypadá situace jako na obrázku 5.5 a pˇri 78 ≤ p ≤ 1 vypadá situace jako na obrázku 5.6. Takˇze co se t´ yˇce ˇcist´ ych strategi´ı, tak pˇri strategii Y prvn´ıho hráˇce je nejlepˇs´ı odpovˇed’ jakákoli sm´ıˇsená strategie (q1 , q2 , q3 ), tj. jakákoli ˇcistá strategie. Obdobnˇe pˇri strategii X je nejlepˇs´ı odpovˇed´ı také jakákoli ˇcistá strategie. Nyn´ı odpovˇedi porovnáme s v´ ysledky z obrázku 5.4. Nalezli jsme tˇri rovnováˇzné body v ˇcist´ ych strategi´ıch: (X, A), (X, C), (Y, B). Popsan´ ym zp˚ usobem jsme tedy ztratili jedno ˇreˇsen´ı v ˇcist´ ych strategi´ıch, a to dvojici (X, C). M Na pˇredchoz´ım pˇr´ıkladu jsme si mohli vˇsimnout, ˇze ˇreˇsen´ı jsme ztratili u druhého hráˇce t´ım, ˇze existovala strategie, která byla velmi dobrá v obou kritéri´ıch, ale ani v jednom nebyla nejvyˇsˇs´ı. Poznamenejme, ˇze nejlepˇs´ı odpovˇedi prvn´ıho hráˇce (má-li pouze dvˇe strategie) nalezené zp˚ usobem a skuteˇcné se budou vˇzdy shodovat. Jsou totiˇz jen dvˇe a nem˚ uˇze nastat ta situace jako u druhého hráˇce, tj. ˇze existuje jeˇstˇe nˇejaká kompromisn´ı varianta v´ yborná ve vˇsech kritéri´ıch, ale ani v jednom nejlepˇs´ı. Pˇri dvou strategi´ıch je nejlepˇs´ı odpovˇed´ı bud’ X nebo Y nebo obˇe a koresponduje to t´ım, zda je ve vˇsech kritéri´ıch nejlepˇs´ı X, ve vˇsech kritéri´ıch nejlepˇs´ı 62

ˇ sen´ı tedy Y , nebo alespoˇ n v jednom nejlepˇs´ı X a alespoˇ n v jednom nejlepˇs´ı Y . Reˇ ztrat´ıme právˇe tehdy, kdyˇz u druhého hráˇce existuje nˇejaká taková kompromisn´ı varianta. Nyn´ı si jeˇstˇe ukáˇzeme posledn´ı protipˇr´ıklad, ˇze m˚ uˇze nastat i situace, kdy hra má ˇreˇsen´ı v ˇcist´ ych strategi´ıch, ale popsan´ y zp˚ usob ˇza´dné nenajde. Pˇ r´ıklad 5.5. Uvaˇzujeme, ˇze oba hráˇci maj´ı dvˇe kritéria, prvn´ı hráˇc má dvˇe strategie X a Y a druh´ y hráˇc má pˇet strategi´ı A, B, C, D a E. Kritéria prvn´ıho hráˇce:

9 9 9 1 1 1 1 9 9 9

9 9 9 1 1 1 1 9 9 9

1 4 7 1 9 1 9 7 1 4

4 1 7 9 1 9 1 7 1 4

, .

Kritéria druhého hráˇce:

, .

Kdyˇz se pod´ıváme na matice, vid´ıme, ˇze nejlepˇs´ı odpovˇed´ı prvn´ıho hráˇce na strategii A je strategie X, na strategii B strategie X, na strategii C strategie X i Y , na strategii D strategie Y a na strategii E strategie Y . Nejlepˇs´ı odpovˇed´ı druhého hráˇce na strategii X jsou strategie D a E a na strategii Y strategie A a B. Nenalezli jsme tedy ˇza´dné ˇreˇsen´ı. Hra vˇsak ˇreˇsen´ı v ˇcist´ ych strategi´ıch má. Najdeme ho. Vysvˇetlili jsme si, ˇze nejlepˇs´ı odpovˇedi prvn´ıho hráˇce vˇzdy pˇresnˇe odpov´ıdaj´ı pouhému pohledu na matice. Zaj´ımaj´ı nás pouze ˇreˇsen´ı v ˇcist´ ych strategi´ıch, nebudeme tedy podrobnˇe zkoumat nejlepˇs´ı odpovˇedi prvn´ıho hráˇce, nebot’ odpov´ıdaj´ı v´ yˇse zjiˇstˇen´ ym. Hledáme tedy nejlepˇs´ı odpovˇedi druhého hráˇce na ˇcisté strategie X a Y. Sestav´ıme vektory kritéri´ı pˇri daném parametru p. Prvn´ı kritérium: 1 4 7 1 9 (p, 1 − p) · = (1, 9 − 5p, 7, 1, 4 + 5p). 1 9 7 1 4 Druhé kritérium: (p, 1 − p) ·

4 1 7 9 1 9 1 7 1 4

= (9 − 5p, 1, 7, 4 + 5p, 1).

Nakresl´ıme si opˇet obrázek pro p = 0 a p = 1.

63


Obrázek 5.8: p = 1 Pro 0 < p < 1 se situace mˇen´ı tak, ˇze se body A a D posouvaj´ı navzájem k sobˇe, aˇz se prohod´ı a dostanou se do situace pro p = 1. Obdobnˇe se prohod´ı body B a E. Budeme se vˇsak zab´ yvat jen ˇreˇsen´ı v ˇcist´ ych strategi´ıch, tedy pro p = 0 a p = 1. Z obrázku 5.7 vid´ıme, ˇze nejlepˇs´ı odpovˇed´ı na ˇcistou strategii Y jsou strategie A, B a C. Z obrázku 5.8 vid´ıme, ˇze nejlepˇs´ı odpovˇed´ı na ˇcistou strategii X jsou strategie C, D, a E. Nalezli jsme tedy ˇreˇsen´ı v ˇcist´ ych strategi´ıch (X, C), (Y, C). M 64

V pˇredchoz´ım pˇr´ıkladˇe nastala obdobná situace jako v pˇr´ıkladˇe 5.5. Pokud tedy existuj´ı nˇejaké takové kompromisn´ı strategie, pak popsan´ ym zp˚ usobem nˇekterá ˇreˇsen´ı nemus´ıme naj´ıt. V obvykl´ ych pˇr´ıpadech vˇsak t´ımto zp˚ usobem nalezneme vˇetˇsinu ˇreˇsen´ı v ˇcist´ ych strategi´ıch. Snadno a rychle tak zjist´ıme nˇekolik rovnováˇzn´ ych bod˚ u hry a poté se m˚ uˇzeme rozhodnout. Zp˚ usob funguje i pokud oba hráˇci maj´ı v´ıce neˇz dvˇe strategie. Pro takovou hru nemáme zp˚ usob nalezen´ı obecného ˇreˇsen´ı, o to cennˇejˇs´ı je nalézt alespoˇ n ˇreˇsen´ı v ˇcist´ ych strategi´ıch. Na závˇer jeˇstˇe zkus´ıme pouˇz´ıt popsan´ y zp˚ usob na aplikaci z kapitoly 4. Uvaˇzujeme tedy dva hráˇce s v´ yplatn´ımi funkcemi: V´ yplatn´ı funkce prvn´ıho hráˇce: Prvn´ı kritérium: 110 105 120 120 , 95 80 100 100 Druhé kritérium:

106 102 105 95 125 125 115 110

.

V´ yplatn´ı funkce druhého hráˇce: Prvn´ı kritérium: 110 110 95 75 B1 = , 120 115 100 80 Druhé kritérium

B2 =

106 110 130 155 106 110 120 145

.

Vid´ıme, ˇze nejlepˇs´ı odpovˇed´ı prvn´ıho hráˇce na vˇsechny ˇcisté strategie jsou obˇe ˇcisté strategie - M i N . To také odpov´ıdá v´ ypoˇct˚ um z kapitoly 4. Nejlepˇs´ı odpovˇed´ı druhého hráˇce na strategii M jsou strategie I, J a L (uvaˇzujeme slabé rovnováˇzné body). Nejlepˇs´ı odpovˇed´ı na strategii N jsou strategie I a L. Nalezli jsme tedy pˇet rovnováˇzn´ ych bod˚ u: (M, I) (M, J) (M, L) (N, I) (N, L) Kdyˇz to srovnáme se skuteˇcn´ ym ˇreˇsen´ım v ˇcist´ ych strategi´ıch, chyb´ı pouze rovnováˇzn´ y bod (M, K). Rychl´ ym v´ ypoˇctem jsme tedy nalezli 5 ze 6 ˇreˇsen´ı v ˇcist´ ych strategi´ıch.

65

Z´ avˇ er Hledán´ı rovnováˇzn´ ych bod˚ u v´ıcekriteriáln´ı hry je nároˇcnˇejˇs´ı neˇz hledán´ı Nashova rovnováˇzného bodu. Zároveˇ n je to nové téma, které zat´ım nen´ı dostateˇcnˇe prozkoumané. Bylo proto velice zaj´ımavé studovat velice nové a aktuáln´ı ˇclánky na toto téma. Práci jsem uvedla nˇekolika motivaˇcn´ımi pˇr´ıklady, kde jsem pˇredstavila tˇri moˇznosti, ve kter´ ych je nutné ˇreˇsit v´ıcekriteriáln´ı hru. Jednu z nich - volebn´ı model jsem podrobnˇeji propracovala a sestavila pomˇernˇe konkrétn´ı zadán´ı. P˚ uvodnˇe jsem ji chtˇela ˇreˇsit, nakonec jsem ale zjistila dva problémy. Prvn´ı byl, ˇze jsem nenaˇsla koncept ˇreˇsen´ı, pomoc´ı nˇehoˇz by bylo reálné u ´lohu rozumnˇe vyˇreˇsit. Druh´ ym problémem bylo zjiˇstˇen´ı, ˇze hra by byla natolik sloˇzitá, ˇze i kdyby se mi ji podaˇrilo vyˇreˇsit, jej´ı ˇreˇsen´ı by bohuˇzel bylo reálnˇe nevyuˇzitelné. Ve druhé kapitole jsem zm´ınila struˇcnˇejˇs´ı historii, na n´ıˇz jsem ukázala, ˇze do roku 2000 vzniklo na toto téma jen nˇekolik málo prac´ı. V posledn´ıch deseti letech je uˇz naopak tématu vˇenována spousta odborn´ ych ˇclánk˚ u. Ve tˇret´ı kapitole jsem nejprve pˇredstavila základn´ı definice a pˇredvedla je na pˇr´ıkladˇe. Následnˇe jsem pˇredstavila tˇri koncepty ˇreˇsen´ı, které jsem pˇreváˇznˇe pˇrevzala z literatury. Podrobnˇeji jsem rozebrala strukturu ˇreˇsen´ı hry dvou hráˇc˚ u, nebot’ jsem ji poté aplikovala na pˇr´ıkladˇe. Struˇcnˇeji jsem zm´ınila koncept hledán´ı ˇreˇsen´ı pomoc´ı skalarizace v´ yplatn´ı funkce, kde jsem z literatury pˇrevzala pouze základn´ı vˇetu, pˇredvedla ji v jednotném znaˇcen´ı, které bylo deklarováno v definic´ıch dˇr´ıve, a následnˇe aplikovala koncept na vlastn´ı pˇr´ıklad. Nakonec jsem pak opˇet struˇcnˇeji zm´ınila koncept hledán´ı ideáln´ıch rovnováˇzn´ ych bod˚ u. Tˇret´ı kapitolu jsem pak zakonˇcila srovnán´ım jednotliv´ ych metod. Ve ˇctvrté kapitole jsem samostatnˇe zpracovala pˇr´ıklad z praxe, kde se dala pouˇz´ıt jedna z popsan´ ych metod. Nejprve jsem sestavila u ´lohu a pˇrevedla zadán´ı do matematické podoby. Konkrétn´ı ˇc´ısla nejsou pˇresnˇe urˇcena statistick´ ymi studiemi, ale jsou uvedena na základˇe reáln´ ych pozorován´ı a zkuˇsenost´ı experta pohybuj´ıc´ıho se v oboru des´ıtky let. Následnˇe jsem u ´lohu vyˇreˇsila pomoc´ı prvn´ıho popsaného konceptu. Samostatnˇe jsem jej aplikovala a vyˇreˇsila problémy, které se pˇri ˇreˇsen´ı vyskytly. Nakonec jsem provedla podrobnou anal´ yzu ˇreˇsen´ı. Koncept ˇreˇsen´ı se ukázal jako efektivn´ı, zaj´ımav´ y a ne pˇr´ıliˇs obt´ıˇzn´ y pro ˇreˇsen´ı reálného pˇr´ıkladu. V páté kapitole jsem se zab´ yvala ˇreˇsen´ım v ˇcist´ ych strategi´ıch. Ukázalo se, ˇze je moˇzné snadno a rychle nalézt vˇetˇsinu ˇreˇsen´ı v ˇcist´ ych strategi´ıch v´ıcekriteriáln´ıch her. Protoˇze u her s vektorovou v´ yplatn´ı funkc´ı taková ˇreˇsen´ı obvykle existuj´ı a pˇri 66

velkém mnoˇzstv´ı kritéri´ı jich dokonce b´ yvá velké mnoˇzstv´ı, je to jistˇe uˇziteˇcné pozorován´ı. Plyne snadno z definice rovnováˇzného bodu ve v´ıcekriteriáln´ı hˇre. Tato kapitola je v´ ysledkem vlastn´ıho v´ yzkumu. Práce se mi psala velice dobˇre, nebot’ mˇe téma znaˇcnˇe zaujalo. Studovala jsem z nejnovˇejˇs´ıch anglick´ ych ˇclánk˚ u, coˇz pro mˇe bylo velmi pˇr´ınosné. Pˇri z´ıskáván´ı informac´ı jsem vˇsak narazila na problémy - zdaleka ne vˇsechny nejnovˇejˇs´ı ˇclánky má Univerzita Karlova zaplaceny, a proto jsem se bohuˇzel k nˇekter´ ym nedostala. Za pˇr´ınos práce povaˇzuji nˇekolik vlastn´ıch moˇznost´ı aplikace a uveden´ı konkrétn´ıch pˇr´ıklad˚ u v´ıcekriteriáln´ıch her, které jsem názornˇe vysvˇetlila, a pˇredevˇs´ım kompletn´ı pˇreveden´ı teoretického konceptu do praxe ve ˇctvrté kapitole, kde jsem se musela vypoˇra´dávat i s nˇekolika nastal´ ymi specifick´ ymi pot´ıˇzemi. Zároveˇ n jsem také pˇredvedla vlastn´ı anal´ yzu ˇreˇsen´ı, jin´ ymi slovy, co vlastnˇe ˇreˇsen´ı pˇrináˇs´ı pro reálné pouˇzit´ı. Dále jsem pˇrinesla nové poznatky v hledán´ı ˇreˇsen´ı v ˇcist´ ych strategi´ıch, kde jsem ukázala, jak rychle nalézt vˇetˇsinu ˇreˇsen´ı v ˇcist´ ych strategi´ıch. V tématu v´ıcekriteriáln´ıch her se nab´ız´ı jeˇstˇe spoustu moˇznost´ı pro v´ yzkum. Je moˇzné hledat nové koncepty ˇreˇsen´ı i vym´ yˇslet nové pˇr´ıklady z praxe a aplikovat na nˇe r˚ uzné dosud nalezené koncepty.

67

Seznam pouˇ zit´ e literatury [1] BLACKWELL, D., (1954): An Analog of the Minimax Theorem for Vector Payoffs, Pacific Journal of Mathematics, Vol. 6, pp. 1-8. [2] BORM, P.; VERMEULEN, D.; VOORNEVELD, M., (2003): The Structure of the Set of Equilibria for Two Person Multicriteria Games, European Journal of Operation Research, Vol. 148, pp. 480-493. [3] CORLEY, H. W., (1985): Games with Vector Payoffs, Journal of Optimization Theory and Applications, Vol. 42, pp. 491-498. [4] FERNANDEZ, F. R.; HINOJOSA, M. A.; PUERTO, J., (2002): Core Solutions in Vector-Valued Games, Journal of Optimization Theory and Applications, Vol. 112, No. 2, pp. 331-360. [5] FERNANDEZ, F. R.; MONROY, L.; PUERTO, J., (1998): Multicriteria Goal Games, Journal of Optimization Theory and Applications, Vol. 99, No. 2, pp. 403-421. [6] GHOSE, D. B.; (1991): A Necessary and Sufficient Condition for ParetoOptimal Security Strategies in Multicriteria Matrix Games, Journal of Optimization Theory and Applications , Vol. 68, No. 3, pp. 463-481. [7] GHOSE, D. B.; PRASAD, U. R.; (1989): Solution Concepts in Two-Persons Multicriteria Games, Journal of Optimization Theory and Applications, Vol. 63, No. 2, pp. 167-189. [8] KOSTER, M.; REIJNIERSE, H.; VOORNEVELD, M., (1999): Voluntary Contributions to Multiple Public Facilities; a Class of Ordinal Potential Games, CentER DP 9988, Tilburg University, The Netherlands. [9] KRUS, L.; BRONISZ, P., (1994): On n-person Noncooperative Multicriteria Games Described in Strategic Form, Annals of Operation Research, Vol. 51, pp. 83-97. [10] NEUMANN, J. von; MORGENSTERN, O.; (1944): The Theory of Games end Economic Behavior, Princeton University Press, The USA. [11] ROCKAFELLAR, R., T.; (1997): Convex Analysis, Princeton University Press, The USA. [12] SHAPLEY, L. S., (1959): Equilibrium Points in Games with Vector Payoffs, Naval research Logistics Quarterly, Vol. 6, pp. 57-61.

68

[13] VOORNEVELD, M., (2000): Ideal Equilibria in Noncooperative Multicriteria Games, Mathematical Methods of Operations Research, Vol. 52, pp. 65-77. ´ M., (1976): Game with Multiple Payoffs, International Journal of [14] ZELENY, Game Theory, Vol. 4, No. 4, pp. 179-191.

69

Michaela Tichá. Univerzita Karlova v Praze Matematicko-fyzikální fakulta. Katedra pravděpodobnosti a matematické statistiky

Recommend Documents