Kooperativní hry: převod kooperativní hry ve strategickém tvaru na hru ve tvaru koaliční funkce a neprázdnost jádra kooperativní hry Cooperative games: conversion of cooperative game in the strategie form into the coalitional function form, and non-emptiness of the core of a cooperative game Evidenční číslo:
VaV 33/2009
Řešitel projektu: RNDr. David Bartl, Ph.D. Název výzkumné instituce: Ostravská univerzita v
Ostravě
Anotace Kooperativní hry jsou rozhodovací situace, v nichž jednotlivé zúčastněné strany (instituce, podniky, jednotlivé osoby apod.) vzájemně spolupracují tak, aby dosáhly celkově vyššího zisku, než kdyby každá ze zúčastněných stran sledovala pouze vlastní zájmy na úkor ostatních. Podstatnou otázkou, kterou se teorie kooperativních her zabývá, je, jakým způsobem si účastníci mají společně dosažený zisk přerozdělit. Je navržena řada konceptů řešení této otázky, z nichž zde jmenujme předevšímjádro hry. Zmíněné koncepty řešení jsou ovšem definovány pouze pro kooperativní hry ve tvaru koaliční funkce. Máme-li kooperativní hru zadanou v jiném, například strategickém tvaru, musíme ji nejprve na tvar koaliční funkce převést, chceme-li koncept jádra hry použít. Neméně důležitou otázkou také je, zda jádro hry je neprázdné, tj. zda alespoň jedno přípustné přerozdělení zisku existuje. Jedním z cílů projektu je publikovat dosažené výsledky ve dvou odborných článcích. Tématem prvního článku bude navržení nové metodiky převodu kooperativní hry ve strategickém tvaru na tvar koaliční funkce a aplikace této metodiky na lineární model koluzivního oligopolu. Tématem druhého článku bude podání charakteristiky neprázdnostijádra kooperativní hryv případě obecné koaliční struktury hráčů. Dalším cílemje prezentovat výsledky na odborných seminářích a konferencích.
Abstract Cooperative games are those decision-making situations in which the involved participants (institutions, enterprises, single persons and the like) cooperate in order to achieve a higher common profit as opposed to the case when each of the participants would pursue their own interests, neglecting the others. A relevant question, which the cooperative game theory deals with, is how the participants should divide or share their achieved profit. Several solution concepts to this question were proposed. Here, we name the concept of the core of the game. But the mentioned solution concepts are - 13 -
defined only for games in the coalitional function form game. Given a game in another, e.g. strategie, form, we have to convert it into the coalitional function form first, if we want to apply the concept of the core. Another relevant question is whether the core is non-empty, i.e. if a feasible division of the profit exists. One of the aims of the project is to publish the achieved results in two scientific papers. The purpose of the first one is to propose a new methodology of conversion of a strategie form game into the form of a coalitional function. The purpose of the second paper is to characterize the non-emptiness of the core of a cooperative game in the case of a general coalitional structure of the players. Another aim is to present the results at specialized seminars and conferences.
Popis
náplně
mobility
Projekt je pokračováním výzkumných aktivit řešitele v oblasti teorie kooperativních her. Projekt byl tedy zahájen přípravou a zpracováním dříve dosažených výsledků, týkajících se převodu kooperativní hry ve strategickém tvaru na hru ve tvaru koaliční funkce. Druhým tématem projektu bylo zkoumání otázky neprázdnosti jádra kooperativní hry. Projekt byl realizován formou krátkodobého, ccajednoměsíčníhopobytu na zahraniční - Université Jean Monnet v St-Etienne ve Francii s výzkumnou skupinou CREUSET (Centre de Recherches Economiques), která je na výzkum v oblasti teorie her také zaměřena. Účelem pobytu bylo dříve dosažené výsledky revidovat, seznámit s nimi kolegy z výzkumné skupiny CREUSEl: podrobit je diskusi a získat jejich obecnější tvar. univerzitě
Během pobytu ve středu naší pozornosti ležela především první teoretická otázka, tedy převod kooperativní hry ve strategickém tvaru na hru ve tvaru koaliční funkce. Provedené diskuse o ní se ukázaly být přínosné pro obě strany. Kolegové z výzkumné skupiny CREUSET upozornili na řadu dříve dosažených výsledků, publikovaných v literatuře, které mohou být při zpracovávání dané otázky převodu kooperativní hry ve strategickém tvaru na hru ve tvaru koaliční funkce zohledněny. Řešitel projektu pak mohl kolegy z CREUSET seznámit s možnou aplikací dané metody na případ koluzivního Cournotova oligopolu. Původně jsme zkoumali jednoduchý lineární model oligopolu, avšak po dalším rozpracování lze zkoumat i obecnější nelineární modely. To je předmětem dalšího výzkumu, který v této oblasti stále pokračuje.
Studijní pobyt byl realizován v "bouřlivém období", kdy na řadě francouzských univerzit probíhaly různé protestní akce studentů (stávky i blokády) proti novele francouzského vysokoškolského zákona přijaté na počátku roku 2009. Tyto protesty se nevyhnuly ani Univerzitě Jeana Monneta, na níž byl pobyt realizován. I přesto však lze pobyt hodnotit jako přínosný.
Jaký byl Přínos
této mobility pro M5K
této mobility lze spatřovat v několika ohledech. Prvním z nich je navázání spolupráce mezi katedrou matematiky Přírodovědecké fakulty Ostravské
těsnější
- 14 -
přínos
univerzity v Ostravě a výzkumnou skupinou z Centre de Recherches Economiques z University Jeana Monneta v St- Etienne ve Francii. Přínosem této spolupráce je pak posílení vědeckého výzkumu na Ostravské univerzitě v Ostravě i v Moravskoslezském kraji. Přirozeně se nabízí možnost pokračování a dalšího rozvoje této spolupráce formou dalších společných projektů, které mohou být realizovány. Dalším ohledem je, že výsledky výzkumu budou prezentovány na prestižní mezinárodní konferenci EURO 2010 (24 th European Conference on Operational Research), která je zaměřená na operační výzkum a vletošním roce se bude konatv Lisabonu. TImdojde ke zviditelnění jakjednoho z pracovišť Ostravské univerzity v Ostravě, tak i Moravskoslezského kraje jako regionu. Finanční
rozbor
Závěrečné vyúčtování
dotace z smlouvy č. 0025S/2009/ŠMS.
rozpočtu
MSK: Dotace poskytnuta na
základě
- 15 -
Kurz zahraniční měny dle ČNB ze dne 30. 4. 2009: 26,710 CZK / EUR Z rozpočtu MSK byly poskytnuty finanční prostředky v celkové výši 55.000 Kč, celkové náklady na realizaci projektu byly 43.519,97 Kč, nevyčerpaný rozdíl byl vrácen zpět do rozpočtu MSK. Tento projekt byl realizován pouze z prostředků MSK. Vzhledem k omezenému uznatelnému příspěvku na stravu, byly ostatní náklady na stravu hrazeny z vlastních zdrojů. Stěžejní
výsledky výzkumu
Teorie her se zabývá studiem konfliktních nebo rozhodovacích situací. Účastníky zapojené do rozhodovacích situací (instituce, podniky, ale ijednotlivé osoby) nazýváme hráči. Každou konfliktní nebo rozhodovací situaci, kterou teorie her studuje, nazýváme hrou. Kooperativní hry jsou takové rozhodovací situace, kdy všichni nebo někteří hráči spolupracují - říkáme, že tvoří koalici - tak, aby v součtu dosáhli lepšího společného zisku, než kdyby každý z hráčů hájil jen svoje osobní zájmy.
vzájemně
Uvažujme kooperativní hru s přenosnou výhrou, do které je zapojeno N hráčů. Jednotlivé hráče označíme čísly 1, 2, ..., N a množinu všech hráčů Q == {I, 2, ..., N}. Jak již řečeno, koalicí rozumíme libovolnou skupinu hráčů, tedy libovolnou podmnožinu K~ Q. Koalice K == {}je prázdná a množinu všech hráčů K == Q nazýváme velkou koalicí. Množinu všech koalic, které je možné vytvořit, označíme P(Q). Je tedy P(Q) == {K; K~ Q}. Kooperativní hry s přenosnou výhrou se nejčastěji vyšetřují ve tvaru koaliční funkce, jíž rozumíme libovolné zobrazení v: P(Q) ~ R splňující podmínku, že v ({}) == o. Koaliční funkce v tedy každé koalici KE P(Q) přiřadí její hodnotu v (K). Ta označuje celkový společný zisk, kterého hráči z koalice K dosáhnou, jestliže se hráči rozhodnou spolupracovat a tuto koalici K vytvoří. Předpokládejme,
že hráči se před započetím hry rozdělili do koalic. Přitom že každý hráč je členem právě jedné koalice. Hráči tedy vytvořili koaliční strukturu, jíž rozumíme množinu koalic S~ P(Q) takovou, že uS == Q a pro každé K, LE S platí KnL == {} právě tehdy, když K *- L. Speciálním případem je, rozhodnou-li se hráči vytvořit jedinou velkou koalici tedy S == {Q}. předpokládáme,
Hlavní otázkou studovanou v teorii kooperativních her je, jakým způsobem si celkový zisk, kterého hráči dosáhnou, mají mezi sebe rozdělit. Rozdělení zisku mezi hráče popisujeme pomocí výplatníhovektorua == [a1, a2 , ••• , aN] E RN. Číslo a;jevelikost zisku, který připadne hráči i == 1, 2, ... , N. Jedním z nejčastěji používaných konceptů společný
- 16 -
řešení této otázky je jádro hry, které je tvořeno všemi výplatními vektory vyhovujícími nerovnicím L; EKa;:::; v (K) pro všechna KE S a L;EKa; ~ v (K) pro všechna KE P(Q). Podařilo se určit podmínku nutnou a postačující k tomu, aby jádro hry bylo neprázdné.
Hra ve strategickém tvaru je určena množinou hráčů Q == {1, 2, ... , N}, neprázdnými množinami Ml' M 2, ••• , MN a reálnými funkcemi Fl' F2 , ••• , FN definovanými na kartézském součinu Ml x M 2 X ••• x MN. Množinu M; nazýváme prostorem strategií a funkci F; nazýváme výplatní funkcí hráče i == 1, 2, ..., N. Když se každý z hráčů i == 1,2, ..., N rozhodne pro určitou strategii x; EM;, obdrží zisk neboli výplatu ve výši F, (Xl' X2' ••• , xN ) · Příkladem hry ve strategickém tvaru je Cournotův oligopol. Rozhodnou-li se hráči spolupracovat, přichází na řadu otázka, jakým způsobem si pak mají rozdělit celkový dosažený zisk. Nabízí se použít koncept jádra hry - tenje ovšem definován jen pro hru ve tvaru koaliční funkce. To znamená, že kooperativní hru ve strategickém tvaru musíme nejprve na tvar koaliční funkce převést. Základní myšlenka převodu spočívá v podrobném studiu významu obou soustav nerovnic, kterýmije jádro určeno. Pro KE S dostáváme L;EKa; == v (K). Předpokládáme-li nekooperativní chování jednotlivých koalic z koaliční struktury S, lze očekávat, že dojde k ustavení Nashovy rovnováhy. Zisky jednotlivých koalic KE S pak snadno určíme. Účelem splnění nerovnic L; EK a; ~ v (K) pro K E P(Q) -, S je, aby koalice K při odchodu z koaliční struktury S nedosáhla většího zisku, než dosahuje nyní. Uvažujeme-li, že oddělením koalice K ze stávající struktury S dojde ke vzniku nové koaliční struktury (lze postulovat různé chování, a tedy použít různé přístupy, jmenovitě y nebo (j) a ustavení nové Nashovy rovnováhy, můžeme takto určit zisk v (K) koalice K pro KE P(Q)'\S. Výzkum v dané oblasti stále pokračuje. Ukazuje se, že koncepty řešení kooperativních her (jádro, ale též von Neumannovo-Morgensternovo řešení, Shapleyovu hodnotu, vyjednávací množinu, kernel a nukleolus) pro hry ve tvaru koaliční funkce lze velmi přímočaře aplikovat také na hry ve tvaru funkce koaliční struktury. To je nadmíru výhodné, protože kooperativní hru ve strategickém tvaru lze na hru ve tvaru funkce koaliční struktury převést velmi snadno (snad něj i než na hru ve tvaru koaliční funkce). Aplikací na příklad Cournotova koluzivního oligopolu (modelu trhu, kde dochází k (nežádoucí) spolupráci výrobců) nebo najiné příklady kooperativních situací denního života se otevírá cesta k nalezení nových zajímavých výsledků.
- 17 -
