Kooperativní hry POLb1123, 6.4. 2021 team work
Kooperativní hry a kooperativní řešení •Kooperativní hry předpokládají, že hráči mohou uzavírat závazné dohody. •Vězňovo dilema není dilematem, pokud je možné uzavřít závaznou dohodu •Některé z kooperativních her jsou charakteristické tím, že si hráči mezi sebou předají část užitků (tzv. vedlejší platby- side payments). Cílem je, aby na tom žádný z hráčů nebyl hůře jako výsledek toho, že souhlasil s koordinací strategie. •U her bez vedlejších plateb vyjednávají hráči o řešeních (různých párech korelovaných strategií), každý pár pro ně přináší trochu jiné užitky. Kooperativní hry dvou hráčů •Někteří autoři tvrdí, že u 2PG neexistují „kooperativní hry“, jen „kooperativní výsledky“ •Př. následující situace: Pepa má peníze- 100 Kč, ale chtěl by si za ně koupit komiks, který chce raději než peníze, které má (= cení si ho na 100 Kč). Franta má komiks, ale nemá peníze na alkohol v ceně 80 Kč, který by měl raději než komiks (= Franta si cení komiks na 80 Kč). Výsledkem jejich komunikace je, že Franta dá Pepovi komiks a dostane za něj 90 Kč. • Franta dá nechá si Pepa dá 110,90 10,170 nechá si 200,0 100,80 Nekooperativní výsledek je (nechá si-nechá si)- ekvilibrium, není Pareto-optimální. „Kooperativní výsledek“ (dá-dá) je Pareto-optimální. [080] ... mára Vyjednávání v kooperativních hrách: jiný pohled •Závazná dohoda znamená, že hráči vystupují jako koalice (vzdávají se unilaterálních strategií ve prospěch koordinované, viděli jsme jako možnost u případu s odpadky). • •Řada sociálních institucí, podporujících závazné dohody. • •Je naznačená dohoda jedinou, kterou mohli Pepa a Franta uzavřít, aby šlo o kooperativní hru/řešení? Alokace (Imputace) •Plán plateb členům koalice se nazývá imputace • •Množina imputací bývá obvykle poměrně velká, typicky ji omezují: tlaky ostatních prodávajících/kupujících, jak je pociťována férovost, vyjednávání. Vyjednávání mezi imputacemi v kooperativních hrách •Vyjednávání je typické pro situace, kdy existuje více kooperativních řešení (párů strategií), které hráči preferují před nedohodou. •Důležité je, že každý z hráčů může výsledek vyjednávání (dohodu) odmítnout. • •Příklad: Prezident trvá na rozpočtových škrtech, nejméně v rozsahu 50 miliard, parlament je ochotný jednat o škrtech od 0 až do výše 80 miliard. Pokud se neshodnou do určitého data, vstoupí v platnost zákon, který stanovuje škrty v rozpočtu 40 miliard a v následujícím roce opět 40 miliard. Prezident preferuje tento zákon, pokud parlament nenavrhne škrty alespoň 50 miliard. Vyjednávání v kooperativních hrách (II.) •Pokud se obě strany nedohodnou (prezident bude navrhovat škrty větší než 80mld. nebo vláda menší než 50mld.) nazývá se takový výsledek konfliktní bod. •Každá ze stran má krajní pozici (reservation level), při níž už preferuje nedohodu před dohodou. Území mezi krajními pozicemi se nazývá zóna dohody (zone of agreement). V příkladu je tato zóna definována pozicemi 50-80 mld. •Výsledkem dohody je Pareto optimální pár strategií v rámci zóny dohody. •Výsledek vyjednávání shrnuje Nashovo vyjednávací řešení Nashovo vyjednávací řešení (charakteristiky) 1.Pareto optimální výsledek (řešení je na horní hranici užitkové funkce v zóně dohody) 2.Symetrie ( výsledek vyjednávání je uprostřed zóny dohody, nebere v úvahu další charakteristiky hráčů). 3.Nezávislost nezávislých alternativ pokud se odstraní některá možná řešení, (ale Nashovo řešení a konfliktní bod zůstává), je výsledkem stále Nashovo řešení 4.Nezávislost k transformacím užitkových funkcí- řešení je nezávislé na lineárních transformacích užitkových funkcí hráčů. Vyjednávací řešení (vlastnosti) •Nash: je rozdělena veškerá nadhodnota • •Kalai-Smorodinsky: přírůstek je dělen férově • •Kalai: navržené dělení respektuje princip, že dohoda je lepší než nedohoda • •Rubinstein: při tom, jak je nadhodnota dělena, záleží na pořadí, v němž je vyjednává. Příklad: hra s nemovitostmi Koalice Hodnota K,L,M 10 K,L 7 L,M 7 K,M 6 K 3 L 3 M 3 K,L, M= velká koalice, K nebo L nebo M= jednočlenná koalice Jak musí být rozděleny zisky mezi hráče velké koalice, aby byla dohoda stabilní? Jádro kooperativní hry • •Jádrem (the core) kooperativní hry jsou všechny imputace, které jsou stabilní v tom smyslu, že žádný hráč nemá pobídku z koalice odstoupit a vylepšit si tím svůj zisk. •Jádro představuje možný přístup k řešení kooperativních her Příklad: hra s nemovitostmi (II.) Koalice Hodnota K,L,M 10 K,L 7 L,M 7 K,M 7 K 3 L 3 M 3 Zde je jádrem velké koalice prázdná množina imputací, velká koalice nemá takovou hodnotu, aby bylo možné zaplatit všem tak, aby někdo z hráčů neměl pobídky jednostranně z dohody odstoupit. Typické znaky koaličních her •Neanalyzují, co koalice „dělá“, jen její vytvoření •Jsou superaditivní- pokud se spojí dvě koalice, je hodnota nové koalice stejná nebo větší než předchozích dvou •Vedlejší platby (hráči si platí za zaujetí určitých strategií) •Mají buďto přenosný nebo nepřenosný užitek (u přenosného užitku jsou zisky snadno korelovány s penězi Shapleyho hodnota (jiné vyjednávací řešení koaličních her než jádro) K L M K,L,M 3 4 3 K,M,L 3 4 3 L,K,M 4 3 3 L,M,K 3 3 4 M,K,L 3 4 3 M,L,K 3 4 3 PRŮMĚR 3 1/6 3 2/3 3 1/6 Klíčové, v jakém pořadí přistupují hráči do koalice. Je otázka, jaké řešení je lepší (Shapleyho jakoby lépe demonstruje reálný proces, námitka: první hráč je krátkozraký, reálně by nikdo s koalicí nechtěl začít). Hry s nepřenositelným užitkem: příklad s hudebníky Abe Barb Curt Deb Rock 2 2 2 2 Bluegrass 4 1 4 1 Jazz 1 5 1 5 Country 5 3 5 4 Folk 3 4 3 3 (A,B,C,D)- všechny žánry (A,B,C)- Jazz, Country, Folk (A,B,D)- Country, Folk (A,C,D)- Jazz, Country, Folk (B,C,D)- Jazz, Country Folk Dvoj a jednočlenné koalice- Country nebo Folk Je koalice A,B,D jádrem? Je koalice A,B,C jádrem? Má situace nějaké jádro? Koalice s nepřenositelnými užitky •Každá z koalice vede k určitému preferenčnímu profilu, příklad A,B,D k profilu (3,4,3) nebo (5,3,4). •Koalice koordinuje své strategie, aby dosáhla určitého výsledku (efektivní koalice pro určitý výsledek) •Výběr strategií závisí na preferencích členů koalice •Koaliční hra reprezentovaná tímto způsobem, je koalice v efektivní formě •Výsledkem her s nepřenositelnými užitky složitý objekt (v tomto případě různé typy kapel) •Jádrem preferenční profil, 1. pro který existuje efektivní koalice a 2. v jakékoliv jiné koalici, která může být v preferenčním profilu zformována, je na tom alespoň jeden z členů stávající koalice hůře než doposud. Kooperativní hry více než dvou hráčů v politice •Kterékoliv z řešení (core, Shaplyeho hodnota) obvykle není v politice prázdnou množinou •V tomto typu her je hlavním výzkumným problémem vytváření koalic •Koalice je podmnožina množiny všech hráčů, která není prázdná. •Koalice vznikají, pokud hráči souhlasí s koordinací strategií, neboť tak doufají, že suma zisků všech, kdo se koalice účastní, bude vyšší, než kdyby postupovali samostatně (předpokládá se, že čistý zisk z koordinované akce oproti samostatné akci si hráči dělí po hře v rámci vedlejších plateb). Pokud tomu tak je, jde o esenciální hry, pokud ne, o hry neesenciální (v nich není motivace k vytváření koalic). •Pro politologii (ale např. i ekonomii- kartely, akciové společnosti) je klíčovou otázkou analýza vyjednávací pozice aktérů při vytváření koalic. Souvisí s „mocí aktérů“. •Kvantitativně se jí snaží popsat Banzhafův index a Shapley-Shubikův index (moci). Shapley-Shubik index (1953) •Pracuje s kategorií „rozhodujícího subjektu“ (critical subject). Zkoumá, kdo je při tvorbě požadované většiny „rozhodujícím“ (critical) hráčem. •Vychází z předpokladu, že záleží na pořadí, ve kterém se hráči k většině přidávají (pozdě příchozí nejsou potřeba). •Postup výpočtu: •1. Seřadí se všechna možná pořadí všech hráčů •2. Zkoumá se, po hlasování kterého z nich má koalice požadovanou většinu •3. Tento hráč získává bod. Součet bodů jednotlivých hráčů je určen po posouzení všech pořadí. Př. •Vypočtěte Shapley-Shubikův index, pro situaci: A:50,B:49,C:1, 1) potřebná většina 50, 2) potřebná většina 49, 3) potřebná většina je 51 • Kritický hráč situace 1 Kritický hráč situace 2 Kritický hráč situace 3 A,B,C A A B A,C,B A A C B,A,C A B A B,C,A C B A C,B,A B B A C,A,B A A A Banzhafův index •Označuje politickou sílu subjektu (strany, státu) a pravděpodobnost, že jeho hlas rozhodne výsledek volby. •Navržen J. Banzhafem (advokát v oblasti public health, jeho pomocí dokumentoval nerovnoměrnou distribuci hlasovací síly v radě Nassau County). •Využívá se při analýze parlamentních hlasování, či např. hlasování v EU. •Jeho výpočet je následující: 1.Určí se všechny koalice s potřebnou většinou 2.Pro každý subjekt se vypočítá, kolikrát je členem koalice, která, když o něj přijde jako o člena, ztratí požadovanou většinu 3.Sečte se počet sub 2 pro všechny hráče •4. Normalizovaná síla subjektu je vyjádřena jako zlomek kombinací, v nichž je členem koalic sub 2 a počtu sub 3. Příklad •Vypočtěte Banzhafův index pro následující situaci •(51; A: 50 hlasů B:49 hlasů C: 1 hlas) • •Řešení: •Koalice: AB, AC, ABC •Počet „kritických“ účastí v koalicích, tj. těch, v nichž dochází při odstranění subjektu k přechodu od většiny k menšině (= ke změně rozhodnutí) A:3, B:1, C:1 •Síla: A: 3/5 (60%), B: 1/5 (20%), C: 1/5 (20%) Příklad: Vypočtěte Banzhafův index pro povolební situaci 2006 (většina 101, všichni musí hlasovat) •a) ODS:81, KDU-ČSL:13, SZ:6, ČSSD:74 •KSČM:26 •b) ODS:81, KDU-ČSL:13, SZ:6, ČSSD:72, •KSČM:26, Melčák/Pohanka:2 • •Vyzkoušejte si online třeba zde: http://people.math.binghamton.edu/fer/courses/math130/ZIS_Spr14/chapter1/Banzhaf.html • • Příklad: vypočtěte Banzhafův index pro následující situaci (zastupitelstvo MČ Brno- Líšeň) •(většina 15, ODS: 10, ČSSD:5, Líšeňský Blok: 5, KDU: 4, KSČM:3, ZB: 2) • •http://people.math.binghamton.edu/fer/courses/math130/ZIS_Spr14/chapter1/Banzhaf.html Příklad koalice s vyrovnanou silou hráčů (McCain: 433-436) Strana Hlasů Program Křesťanstí demokrati 40% Konzervativní v morálních otázkách, umírněná ekonomicky, podporující small business Sociální demokraté 40% Podporouje dělníky, kontrolu ekonomiky, neutrální v mprálních otázkách Radikálové 20% Podporuje malou vládu, extrémně libertariánská v morálních otázkách Témata: jaká vnikne koalice? (vedlejší platby zakázány) Téma Konzervativci Socialisté Radikálové 1 Volný obchod +1 -3 +10 2 Výhody same-sex partnerů v systému sociálního zabezpečení -10 0 +9 3 Omezení sociálních dávek +3 -10 +8 4 Přímé platby farmářům, kteří bojují s importem +6 +3 -10 Koalice a zisky aktérů Koalice Složení Projde C S R 1 (C,S,R) 1,3 4 -13 18 2 (C,R) (S) 1,3 4 -13 18 3 (S,R) (C) 2 -10 0 9 4 (C,S) (R) 4 6 3 -10 5 (C) (S) (R) 0 0 0 0 Pouze koalice 4 je stabilní