DOI: 10.5300/2011-OSSConf/95
ˇ EDME ˇ TU PROGRAM GAMBIT VE VY´UCE PR ˇ ´ NI´ V RIZIKU A NEJISTOTE ROZHODOVA ˇ I´Zˇ, Pavel (CZ) STR Abstrakt. V tomto prˇ´ıspeˇvku si prˇedstavı´me Open Source Software pojmenovany´ Gambit, http: // www. gambit-project. org/ , ktery´ je vyuzˇ´ıva´n ve vy´uce v prˇedmeˇtu Manazˇerske´ rozhodova´nı´ v riziku a nejistoteˇ na Fakulteˇ managementu a ekonomiky Univerzity Toma´sˇe Bati ve Zlı´neˇ. Autor pouka´zˇe na uka´zky z teorie her i z rozhodovacı´ch stromu˚. Klı´cˇova´ slova. Gambit, teorie her, rozhodovacı´ strom, hry proti prˇ´ırodeˇ.
THE USE OF GAMBIT SOFTWARE IN THE DECISION-MAKING UNDER RISK AND UNCERTAINTY COURSE Abstract. In this article the author introduces Open Source Software called Gambit, downloadable at http: // www. gambit-project. org/ , which is used in the Managerial Decision-Making Under Risk and Uncertainty course at Faculty of Management and Economics, Tomas Bata University in Zlı´n, The Czech Republic. The author also points out at several game theory problems as well as a few problems which can be stated and drawn as decision tree situation. Key words and phrases. Gambit, Game Theory, Decision Tree, Games Against Nature.
1
Nabı´dka u´vodem
Ucˇinı´m va´m nabı´dku! Zahra´li byste si proti autorovi cˇla´nku ka´men-nu˚zˇky-papı´r, kdyzˇ mozˇnosti volı´ na´hodneˇ? A co kdyby volil zarputile ka´men cˇasteˇji (40 %) nezˇ nu˚zˇky a papı´r (30 %) a svou strategii by nehodlal zmeˇnit?
2
Prvnı´ kroky v Gambitu
Abychom se doka´zali raciona´lneˇ rozhodnout, vyuzˇijeme program Gambit [1], ktery´ umı´ rˇesˇit situace teorie her (prvnı´ autorova nabı´dka), i rozhodovacı´ strom (druha´ nabı´dka), vcˇetneˇ zahrnutı´ pravdeˇpodobnostnı´ho hra´cˇe, to je role, do ktere´ se autor prˇ´ıspeˇvku sa´m uvrhl.
96
Konferencia OSSConf 2011
Program Gambit se da´ sta´hnout z oficia´lnı´ch stra´nek, www.gambit-project.org, verze z roku 2007 je obdobna´ verzi 2010, pro Linux, Mac OS X i Microsoft Windows. Pro Windows zvolte verzi z roku 2007, neb bina´rky nejsou plneˇ prˇipravene´ u verze 2010 a i prˇi vyuzˇitı´ Cygwinu nebo MinGW bude cˇtena´rˇ za´pasit s graficky´m uzˇivatelsky´m prostrˇedı´m (nutnost doinstalovat wxWidgets) a nemozˇnostı´ uzˇitı´ jednoho z algoritmu˚ na 64bitovy´ch strojı´ch. Pokud si tyto prˇepychove´ veˇci odpustı´te, stacˇ´ı po rozbalenı´ (za prˇedpokladu, zˇe ma´te jizˇ nainstalovane´ gcc-c++, make atd.) da´t: $ ./configure --disable-enumpoly --disable-gui $ make $ make install Instalace verze 2007 na nativnı´ch Windows je prˇ´ımocˇara´. Budete mı´t k dispozici graficke´ uzˇivatelske´ rozhranı´ i algoritmy spustitelne´ jako exe soubory z prˇ´ıkazove´ rˇa´dky. Uzˇivatele´ pracujı´cı´ na Linuxu cˇi Mac OS X na tom budou z pohledu instalace le´pe.
2.1
ˇ esˇenı´ proble´mu z teorie her R
Vyrˇesˇ´ıme si nasˇi prvnı´ situaci, cozˇ je dle klasifikace hra dvou raciona´lneˇ uvazˇujı´cı´ch hra´cˇu˚ s nulovy´m soucˇtem (co prvnı´ zı´ska´, druhy´ ztra´cı´ a vice versa). Spustı´me si Gambit a da´va´me File→New→Strategic game. V leve´ cˇa´sti si prˇida´me jeden rˇa´dek a jeden sloupec dı´ky ikonka´m ,Add a strategy for this player‘. Dvojklikem zmeˇnı´me popisky rˇa´dku˚ a sloupcu˚ na Ka´men, Nu˚zˇky a Papı´r. Nynı´ si ohodnotı´me jednotlive´ mozˇnosti her. Kdyzˇ vyhraji da´va´me kladnou hodnotu, naprˇ. +10, kdyzˇ je remı´za tak nula, a kdyzˇ prohrajeme tak −10. Cˇervena´ pole jsou prvnı´ho hra´cˇe, modra´ pak druhe´ho. Tabulka (dvojmatice) je symetricka´ podle hlavnı´ osy, v kazˇde´m rˇa´dku, sloupci i dvojbunˇce je soucˇet vy´her nula. Dosta´va´me:
Po vyrˇesˇenı´ (druha´ ikonka zprava s na´zvem ,Compute Nash equilibria of this game‘) s prˇedvoleny´mi mozˇnostmi ,Compute all Nash equilibria‘ a ,with Gambit’s recommended method‘ zı´ska´va´me: To je rˇesˇenı´ nasˇ´ı hry. Kazˇdy´ z hra´cˇu˚ by meˇl jednotlive´ mozˇnosti (rˇa´dky, sloupce) volit na´hodneˇ a se stejnou pravdeˇpodobnostı´. Po stisknutı´ ,OK‘ v leve´ cˇa´sti pod jme´ny uvidı´me dvakra´t ,Payoff: 0‘, tedy u te´to hry nenı´ vı´teˇzu˚ ani porazˇeny´ch v dlouhe´m obdobı´.
Pavel Stříž: Program Gambit ve výuce předmětu rozhodování v riziku a nejistotě
2.2
97
ˇ esˇenı´ rozhodovacı´ho stromu R
Pokud se vsˇak nasˇe volby lisˇ´ı a strategie je nemeˇnna´, lze hru sehra´t jako hru proti prˇ´ırodeˇ. K tomu budeme potrˇebovat apara´t rozhodovacı´ch stromu˚, ten Gambit take´ umı´. V Gambitu si naklikneme File→New→Extensive game. Uvidı´me jeden cˇerny´ uzel. Na ten klikneme pravy´m tlacˇ´ıtkem mysˇi a volı´me ,Insert move‘, zmeˇnı´me ,2‘ na ,3‘ a da´va´me ,OK‘. Objevı´ se na´m trˇi nove´ cˇerne´ uzly. Vybereme hornı´ pravy´m tlacˇ´ıtkem na mysˇi a volı´me ,Insert move‘. Navolı´me ,Insert move for the chance player‘ v prvnı´ rolovacı´ sˇipce. I zde zmeˇnı´me dvojku na trojku a potvrdı´me ,OK‘. Dvojklikem na cˇervenou a zelenou ,1‘ mu˚zˇeme nastavit na´zvy strategiı´ (Label) a i pravdeˇpodobnosti (Probability) u prˇ´ırody (Chance). Pole volı´me dvojklikem leve´ho tlacˇ´ıtka mysˇi, volby pote´ potvrdı´me ,OK‘. Pravy´m tlacˇ´ıtkem mysˇi volı´me uzel u Nu˚zˇek cˇervene´ho hra´cˇe, ,Insert move‘. Meˇnı´me na: ,Insert move for the chance player‘, ,at information set 1 (3 actions, 1 member node)‘, da´va´me ,OK‘. Stejneˇ to zrealizujeme u poslednı´ho uzlu cˇervene´ho hra´cˇe. Poslednı´ fa´ze je vyplnit cenove´ sˇtı´tky, v programu Gambit zaznacˇeno jako ,(u)‘ (angl. utility). Budeme jich potrˇebovat deveˇt v u´plneˇ prave´ cˇa´sti stromu. Postupneˇ je vybereme dvojklikem a prˇipisujeme vy´hry a prohry prvnı´ho a druhe´ho hra´cˇe. Ve fina´le dostaneme: Po vyrˇesˇenı´ zı´ska´va´me optimum, volit vzˇdy Papı´r. Opeˇt v leve´ cˇa´sti pod jme´ny hra´cˇu˚ uvidı´me vy´hru/prohru. Nynı´ by si prvnı´ hra´cˇ polepsˇil z nuly na jednotku vy´hry a druhy´ hra´cˇ (ktery´ se de facto hry raciona´lnı´m zpu˚sobem neu´cˇastnı´) ztra´cı´ jednotku vy´hry.
3 3.1
Pro na´rocˇneˇjsˇ´ı cˇtena´rˇe Veˇznˇovo dilema
Pokud je cˇtena´rˇ obezna´m s touto disciplı´nou aplikovane´ matematiky, tak jej zna´my´ proble´m veˇznˇova dilema neprˇekvapı´. Je to hra s nenulovy´m soucˇtem a ma´ jednu Nashovu rovnova´hu (oba veˇzni si veˇrˇ´ı a zapı´rajı´) a jedno Paretovo optimum (veˇzni si neveˇrˇ´ı a druhe´ho podvedou). Neprˇekvapı´ na´s tedy, zˇe mezi 140 uka´zkami (podadresa´rˇ /games/ ve verzi 2007; podadresa´rˇ /contrib/games/ ve verzi 2010) tento proble´m nalezneme. Jedna´ se konkre´tneˇ o soubor pd.nfg (angl. Prisoner’s Dilemma). Po otevrˇenı´ a vyrˇesˇenı´ zı´ska´va´me:
98
3.2
Konferencia OSSConf 2011
Gambit z prˇ´ıkazove´ rˇa´dky
Prˇ´ıjemne´ zjisˇteˇnı´ je fakt, zˇe lze dany´ proble´m vyrˇesˇit z prˇ´ıkazove´ rˇa´dky, z libovolne´ho ze trˇ´ı operacˇnı´ch syste´mu˚. Vstupem je textovy´ nesˇifrovany´ soubor pd.nfg, ktery´ ma´ jasneˇ definovanou strukturu, ktera´ je popsa´na v manua´lu.
Pavel Stříž: Program Gambit ve výuce předmětu rozhodování v riziku a nejistotě
99
$ cat pd.nfg # Linux a Mac OS X nebo > more pd.nfg & rem Microsoft Windows NFG 1 R "Two person Prisoner’s Dilemma game" { "Player 1" "Player 2" } { { "1" "2" } { "1" "2" } } "" { { { { { } 1
"" "" "" ""
9, 9 } 10, 0 } 0, 10 } 1, 1 }
2 3 4
Rˇesˇenı´ zı´ska´me spusˇteˇnı´m jednoho z algoritmu˚, naprˇ. na Linuxu a Mac OS X, z adresa´rˇe /contrib/games/: $ gambit-enummixed
gambit-enummixed.exe
100
Konferencia OSSConf 2011
Compute Nash equilibria by enumerating extreme points Gambit version 0.2007.12.04, Copyright (C) 2006, The Gambit Project Enumeration code based on lrslib 4.2b, Copyright (C) 1995-2005 by David Avis ([email protected]) This is free software, distributed under the GNU GPL NE,0,1,0,1
3.3
Vy´hody a nevy´hody
Shrneme-li, tak mu˚zˇeme rˇ´ıci, zˇe + + + + + + + +
Program Gambit pracuje v graficke´m rezˇimu i z prˇ´ıkazove´ rˇa´dky. Vstupnı´ soubory efg a nfg jsou nesˇifrovane´, tedy snadno generovatelne´. Informacˇnı´ banner u vy´stupu se da´ vypnout parametrem -q. V graficke´m rezˇimu snadno zı´ska´me dominantnı´ rˇa´dky a sloupce. Verze 2007 beˇzˇ´ı na vsˇech verzı´ch Windows, se ktery´mi autor prˇisˇel do styku. Gambit obsahuje sadu 140 uka´zek, rˇada z nich je z odborny´ch knih. Dokumentace programu je prˇehledna´. Prˇi ulozˇenı´ vy´sledku v graficke´m rezˇimu se sta´va´ soucˇa´stı´ efg cˇi nfg souboru pod tagem analysis.
Na druhe´ straneˇ vsˇak: − Nevy´hodou zu˚sta´va´, zˇe z prˇ´ıkazove´ rˇa´dky nelze zı´skat matici vy´her hra´cˇu˚, ty by se musely dohledat (rˇesˇenı´ v cˇiste´ strategii) cˇi dopocˇ´ıtat (rˇesˇenı´ ve smı´sˇene´ strategii). − Osoba neznala´ teorie her mu˚zˇe snadno narazit na situaci, kdy vybrany´ algoritmus zkolabuje. Pak zkolabuje i program Gambit cˇi dany´ spustitelny´ soubor. Nenı´ to uzˇivatelsky prˇ´ıveˇtiveˇ rˇesˇene´ v graficke´m rezˇimu pod Windows a v rˇadeˇ prˇ´ıpadu˚ je potrˇeba ukoncˇit proces azˇ prˇes Spra´vce u´loh. − Verze 2010 zatı´m neobsahuje podporu pro nativnı´ Windows a nepodporuje 64bitovou platformu pro algoritmus enumpoly. Kompilace verze 2010 s grafickou podporou (wxWidgets) je pod Cygwinem na Windows 7 64bit te´meˇrˇ nemozˇna´, pro neprograma´tora je to nad lidske´ sı´ly. − Acˇkoliv je to zmı´neˇno v cı´lech autoru˚ programu, tak Gambit v soucˇasnosti nepodporuje kooperativnı´ hry, podporuje jen nekooperativnı´ hry a hry proti prˇ´ırodeˇ.
4
Nabı´dka mı´sto Za´veˇru
Za´veˇrem opeˇt jedna autorska´ nabı´dka ke hrˇe s nulovy´m soucˇtem, kterou kantor da´va´ svy´m studentu˚m ve vy´uce, a ktera´ snad zprˇ´ıjemnı´ zacˇa´tek partiı´ do rozhodovacı´ch stromu˚, na´m necht’poslouzˇ´ı na oveˇrˇenı´ si znalostı´ pra´ce s Gambitem.
Pavel Stříž: Program Gambit ve výuce předmětu rozhodování v riziku a nejistotě
101
Pokud se hry nezu´cˇastnı´te, nic nevyhrajete ani nic nezı´ska´te. Pokud do hry pu˚jdete (cˇerveny´ hra´cˇ), jedna´ se o hod korunovou mincı´ (z Cˇeske´ republiky) dle na´sledujı´cı´ch pravidel. Hra je smysˇlena´, ve vy´sˇi vy´hry a prohry netrˇeba hledat hlubsˇ´ı smysl. Nehrajete-li, nic nezı´ska´te a nic neztratı´te (0 Kcˇ). Ha´zı´ se mincı´, maxima´lneˇ cˇtyrˇikra´t, pokud cˇtyrˇikra´t po sobeˇ padne orel, autor cˇla´nku platı´ u´cˇastnı´ku konference 57 Kcˇ. V opacˇne´m prˇ´ıpadeˇ je vypla´ceno jemu. U prvnı´ho hodu prˇi panneˇ korunu a hra koncˇ´ı (prˇi orlu pokracˇuje), u druhe´ho dveˇ, u trˇetı´ trˇi koruny a u poslednı´ho, je-li panna, cely´ch 19 korun. Pokud se s autorem cˇla´nku na OSSConf2011 v Zˇilineˇ potka´te, ma´te mozˇnost pozˇadovat vy´hru, nebo naopak zaplatit autorovi prohru, s odkazem na tento cˇla´nek. , Zde je forma´lneˇ zapsana´ hra – hodnoty pro 2. hra´cˇe jsou postupneˇ 0; 1; 2; 3; 19 a −57, pro prvnı´ho hra´cˇe jsou s opacˇny´m zname´nkem:
Abych netrpeˇlive´ho cˇtena´rˇe cˇla´nku nenechal na pochyba´ch, na dalsˇ´ı straneˇ je rˇesˇenı´. S teoriı´ her se mu˚zˇeme setkat v ekonomii, politice, pra´vnı´ch sporech [2–4] a ostatneˇ i ve filmu, kdy jeden ze zlocˇincu˚ (veˇznˇovo dilema) si odpyka´va´ trest za sve´ho part’a´ka, ktery´ ho podrazil, a pak se po propusˇteˇnı´ z veˇzenı´ mstı´. Ovsˇem nechod’me daleko, za´jemce necht’shle´dne film ,Cˇista´ dusˇe – A Beautiful Mind‘, ktery´ je o Johnu Nashovi, pru˚kopnı´ku v teorii her a nositeli Nobelovy ceny za ekonomii z roku 1994 (vedle Reinharda Seltena a Johna Harsanyie). Klı´cˇovy´ moment filmu a jeho netradicˇnı´ rˇesˇenı´, ktere´ ovlivnilo celou ekonomii, je zna´m pod termı´nem bitva pohlavı´ (angl. Battle of Sexes cˇi Bach or Stravinsky – BoS). Problematiku rozhodovacı´ch stromu˚ potka´me ve hra´ch jako jsou go, sˇachy, poker i bridzˇ (angl. double-dummy problems, cˇa´stecˇneˇ lze pouzˇ´ıt i na single-dummy problems).
102
Konferencia OSSConf 2011
Podeˇkova´nı´ Vznik tohoto cˇla´nku byl cˇa´stecˇneˇ podporˇen ESF projektem cˇ´ıslo CZ.1.07./2.2.00/15.0104. Za procˇtenı´ prvnı´ chaoticke´ verze rukopisu autor deˇkuje kolegovi Martinu Jura´skovi.
ˇ esˇenı´ hry proti autorovi R Kra´sa u´lohy zmı´neˇne´ na prˇedchozı´ straneˇ spocˇ´ıva´ v tom, zˇe prˇi velke´m opakova´nı´ takove´ hry je autor cˇla´nku skutecˇneˇ ztra´tovy´, a to jedna koruna cˇeska´ na hru. Tu si zaslouzˇ´ı kazˇdy´ cˇtena´rˇ, ktery´ by do hry sˇel, prˇ´ıpadneˇ student, ktery´ rozhodovacı´ strom spra´vneˇ ohodnotil a do hry vstoupil. V Gambitu si navı´c mu˚zˇeme nakliknout jednotlive´ uzly, ktere´ jsou po vyrˇesˇenı´ numericky ohodnoceny. V rea´lne´m zˇivoteˇ to vsˇak znamena´, zˇe autor cˇla´nku by takovou hru hra´l s kazˇdy´m za´jemcem jen jednou a je tu sportovnı´ sˇance, zˇe cˇtyrˇikra´t po sobeˇ autorovi cˇla´nku orel nepadne a na svy´ch ztra´tovy´ch 57 Kcˇ si peˇknou rˇa´dku her pocˇka´, tedy veˇtsˇina u´cˇastnı´ku˚ OSSConf2011 by naopak musela autorovi platit, i kdyzˇ jen polozˇky korunove´. Autor cˇla´nku je vzˇdy ochotny´ uznat svou prohru v dlouhodobe´m horizontu a onu korunu kazˇde´mu u´cˇastnı´kovi/studentovi uhradit, at’ uzˇ z pohledu sportovnı´ho nebo kantorske´ho. A kdo nehraje, nevyhraje ani nema´ sˇanci prˇijı´t si ke ztra´teˇ!
Literatura [1] MCKELVEY, R. D. – MCLENNAN, A. M. – TUROCY, T. L. (2010). Gambit: Software Tools for Game Theory, Version 0.2010.09.01. Dostupne´ na serveru: http://www.gambit-project.org/ ´ , A.: Modely rozhodovania v konfliktny´ch situa´cia´ch [2] CHOBOT, M. – TURNOVCOVA a za neurcˇitosti, Alfa, Bratislava, 1980. ˇ AS, Miroslav. Teorie her a jejı´ aplikace : Ucˇebnice pro studenty VSˇE. 1. vyd. [3] MAN Praha : Sta´tnı´ nakladatelstvı´ technicke´ literatury, 1991. 278 s. ISBN 80-03-00358-X. [4] PITEL, J. a kol. Ekonomicko-matematicke´ meto´dy. Bratislava, Prı´roda, 1988. Kontaktnı´ adresa ˇ I´Z ˇ (Ing., Ph.D.), Pavel STR Tomas Bata University in Zlı´n, na´m. T. G. Masaryka 5555, 760 01 Zlı´n, Czech Republic, [email protected]
