Zavedení pˇredmˇetu "Teorie her" do výuky v magisterském studijním programu na FIT VUT v Brnˇe Martin Hrubý FIT VUT v Brnˇe, Božetˇechova 2, BRNO, 612 66
[email protected] 21. ledna 2008 Abstrakt ˇ Clánek pojednává o zavedení nového pˇredmˇetu "Teorie her" do výuky v magisterském studijním programu na Fakultˇe informaˇcních technologií VUT v Brnˇe. Jsou diskutovány d˚uvody pro zavedení této tématiky do výuky, celkový kontext magisterského studia, zamˇeˇrení absolvent˚u pˇredmˇetu, cílové znalosti a dovednosti a struˇcný pˇrehled zamýšlených pˇrednášek.
1 Úvod Fakulta informaˇcních technologií Vysokého uˇcení technického v Brnˇe se ˇradí mezi nejvˇetší informatické fakulty v naší republice. Vznikla pˇred nˇekolika lety odtržením tehdejšího Ústavu informatiky a výpoˇcetní techniky na elektrofakultˇe VUT. Z poˇcáteˇcního stavu cca 100 student˚u v roˇcníku a jediného inženýrského studijního programu (resp. dále pak doktorského) se nám podaˇrilo vybudovat informatickou školu s pr˚umˇerným poˇctem 400-500 student˚u v roˇcníku (v bakaláˇrském studiu), a oddˇeleným studiem v bakaláˇrském studijním programu a navazujícím magisterském studijním programu se zamˇeˇreními do informaˇcních systém˚u, grafiky, hardwaru a inteligentních systém˚u. Množství pˇrijímaných student˚u fakultˇe zabezpeˇcilo ekonomickou stabilitu a prospertiu, je však velmi zavazující. Snažíme se proto o další zkvalitˇnování výuky a to v tˇechto smˇerech: • Zavádˇení nových studijních program˚u s cílem zavést informatiku do dalších obor˚u lidské cˇ innosti (pˇredevším však do technických obor˚u). • Modernizace zp˚usobu výuky a zkvalitˇnování souˇcasných pˇredmˇet˚u. FIT technicky zabezpecˇ uje možnost poskytnout student˚um videozáznamy pˇrednášek, pˇrímý pˇrenos právˇe provádˇených pˇrednášek a množství elektronických studijních materiál˚u. Za velmi významný m˚užeme považovat projekt financovaný ESF na vypracování skript pro vˇetšinu našich pˇredmˇet˚u. 1
• Zavádˇení nových pˇredmˇet˚u do studijních program˚u. Tento cˇ lánek pojednává o zavedení nového pˇredmˇetu “Teorie her" do stávající struktury našich studijních obor˚u. • Zapojování student˚u do výzkumu fakulty. Z tohoto pohledu m˚užeme naše pˇredmˇety chápat jako nábor student˚u na výzkumné projekty. V rámci oddˇelení bakaláˇrského a magisterského studia jsme se pˇred lety rozhodli koncipovat bakaláˇrské studium spíše jako praktickou a rychlou pˇrípravu student˚u pro okamžité nasazení do zamˇestnání s relativnˇe jednoduchým zamˇeˇrením. Magistra jsme plánovali jako teoretické prohloubení znalostí student˚u vedoucích k jejich pochopení informatiky a schopnosti samostatnˇe inženýrsky pracovat. Naše koncepce se ukázala jako v zásadˇe správná, protože skuteˇcnˇe urˇcitá cˇ ást student˚u po získání bakaláˇrského diplomu fakultu opouští. Navazující studenti v magisterském programu si pak volí jedno ze cˇ tyˇrech zamˇeˇrení, pˇriˇcemž se ukazuje, že ono zamˇeˇrení chápou z vˇetší cˇ ásti jako pˇredurˇcující pro celý jejich profesní život. Magistˇri si volí z obor˚u smˇeˇrujících do grafiky, hardwaru, informaˇcních systém˚u a inteligentních systém˚u. Nám se na Ústavu inteligentních systém˚u, který obor “Inteligentní systémy” zabezpeˇcuje, zaˇcalo daˇrit studenty pˇresvˇedˇcovat o smysluplnosti našeho zamˇerˇení. Mezi studenty se zaˇcínají objevovat zájemci o nároˇcnˇejší pr˚upravu v poˇcítaˇcovém modelování, umˇelé inteligenci, bezpeˇcnosti a algoritmizaci složitých problém˚u. My je v tomto pochopitelnˇe chceme podporovat a proto je naší prioritou obor Inteligentní systémy v magisterském studijním programu dále zpestˇrovat.
2 Úvod do teorie her Tématem tohoto pˇríspˇevku je ukázka zpracování matematické teorie her do podoby studijního pˇredmˇetu. Teorie her se zabývá studiem interakce inteligentních entit v situacích spolupráce nebo konfliktu. Na bázi konceptu strategií a užitku ukazuje, jak se inteligentní entity budou ve zkoumaných situacích rozhodovat. P˚uvodní motivace pro studium her byly smˇeˇrovány pˇredevším do ekonomických model˚u, dnešní pojetí her je však mnohem širší. Teorie her (mnohdy také nazývána jako matematická teorie her nebo matematika interaktivního rozhodování) je matematická teorie, která vznikla pˇribližnˇe pˇred sto lety. Nejvˇetším impulsem pro její vznik byla publikace "Theory of Games and Economic Behavior" [1] dvou vynikajících vˇedc˚u - matematika Johna von Neumanna a ekonoma Oskara Morgensterna. Kniha vyšla v roce 1944 a vzbudila velkou pozornost. Von Neumann v ní mimo jiné publikoval sv˚uj koncept minimaxu, tedy rovnovážného stavu ve hrách s nulovým souˇctem. Na toto reagoval za nˇekolik let další výjimeˇcný matematik John F. Nash ve svém výzkumu, když v roce 1951 ukázal smysluplnost her s nenulovým souˇctem a koncept jeho rovnovážného stavu [2] (Nashovo ekvilibrium). Tento zásah do teorie her byl snad ještˇe významnˇejší a celý obor se zaˇcal razantnˇe rozvíjet. S rozšíˇrením Nobelových cen o cenu za
2
ekonomii také spousta herních teoretik˚u získala Nobelu cenu za ekonomii (z jistých d˚uvod˚u J. Nash až v roce 1994).
3 Studium modelování a umˇelé inteligence Studijní obor Inteligentí systémy je stavˇen na tˇechto hlavních pilíˇrích: • Poˇcítaˇcové modelování a simulace, kde chápeme modelování jako absolutní základ všech úvah inženýra. • Umˇelá inteligence a robotika, která smˇeˇruje k moderním aplikacím informaˇcích technologií. • Poˇcítaˇcová analýza a verifikace, kde studenti hloubˇeji zabˇrednou do studia matematiky a dnes velmi podporovaného oboru verifikaˇcního inženýrství. • Bezpeˇcnost, která bude stále významnˇejší a beztak se stala nosným tématem výzkumného zámˇeru fakulty. Pro náš cˇ lánek je relevantní zejména ono poˇcítaˇcové modelování a umˇelá inteligence.
4 Pˇredmˇet “Teorie her" Cílem zavedení pˇredmˇetu "Teorie her" je dát student˚um vzdˇelání v oblastech racionálního rozhodování v krizových situacích, vyjednávání a predikce chování inteligentních entit. Aplikace m˚užeme smˇeˇrovat do predikce chování lidí, a´t už v otázkách bezpeˇctnostních, ekonomických nebo sociologickým. Dále pak m˚užeme aplikace vidˇet v robotických problémech, pokud budeme cˇ asem schopni konstruovat autonomní roboty s vlastními cíly a snahou o maximalizování vlastního užitku. V obecnˇejší rovinˇe dává studium racionálního rozhodování jistou pr˚upravu ve schopnosti problémy analyzovat, hledat možné strategie v jejich ˇrešení, strategiím pˇrisuzovat možný užitek a v rámci toho se pak správnˇe rozhodovat. Matematické modely v teorii her také ukazují jasná ˇrešení mnoha problém˚u v bˇežném životˇe. Pˇredmˇet "Teorie her” stojí svým zamˇeˇrením a koncepcí nˇekde na pomezí: • Velmi specializovaného volitelného pˇredmˇetu v magisterském studijním programu. • Pˇrípravy na velmi úzce zamˇeˇrenou vˇedeckou profesi analytika a prognostika. • A jak již bylo naznaˇceno, velmi zajímavé pr˚upravy pro život. Z hlediska studia informatiky je také velmi významné, že zpracování úloh z teorie her vyžaduje velké programátorské schopnosti a znalosti, a to pˇredevším v oblastech implementace složitých algoritm˚u, rozsáhlých datových struktur a výpoˇcetní paralelizace. 3
Struktura hodnocení pˇredmˇetu Vˇetšina pˇredmˇet˚u na naší fakultˇe zavádí tˇri složky hodnocení v pˇredmˇetu a pˇredmˇet "Teorie her" je bude následovat: • P˚ulsemestrální zkouška - test v p˚ulce semestru. Smyslem je studenty pˇrimˇet pr˚ubˇežnˇe studovat. • Projekt - samostatná nebo skupinová studijní a implementaˇcní úloha, která procviˇcuje nebo prohlubuje studium v rámci pˇredmˇetu. Vypracování projektu bývá mnohdy pˇredpokladem pro udˇelení zápoˇctu v pˇredmˇetu. • Závˇereˇcná zkouška - tvoˇrí 60-80% hodnocení v pˇredmˇetu. V pˇredmˇetu "Teorie her" rozhodnˇe bude projekt zaveden a dokonce je i plánováno, aby studenti své projekty veˇrejnˇe prezentovali. Projekty by mˇely být ze cˇ tyˇrech oblastí a to: • Studijní - student prozkoumá nˇejakou teorii nad rámec pˇrednášek a vlastním zp˚usobem ji popíše. V ideálním pˇrípadˇe i ukaže její aplikace. • Implementaˇcní - student implementuje vlastní ˇrešení zvolené problematiky v teorii her, typicky nˇejaký analytický algoritmus. Oˇcekává se i zamyšlení nad zlepšením algoritm˚u. • Aplikaˇcní - student za použití existujících dostupných (programových) prostˇredk˚u vytvoˇrí model zvolené situace. Pochopitelnou souˇcástí je i experimentování s modelem a diskuze dosažených výsledk˚u. • Infiltraˇcní - cením si velmi projekt˚u, ve kterých se studenti odvážnˇe pustí do vyhledání komerˇcní nebo nekomerˇcní organizace zabývající se zkoumaným tématem. O svém pobytu v organizaci pak podají zprávu doplnˇenou o praktické zajímavosti z cˇ innosti organizace.
Osnova pˇrednášek Vzhledem k charakteru pˇredmˇetu se hlavní výuková cˇ innost koncentruje do pˇrednášek. Cviˇcení zavedena nebudou. Pˇredmˇet bude spíše pˇrehledový a každá pˇrednáška by mˇela zahrnovat jedno ucelené téma v rámci teorie her. 1. Úvod, historie, motivace, základní pojmy - úvodní pˇrednáška, která uvede tématiku do širších souvislostí. 2. Dvouhráˇcové hry s nulovým souˇctem - dvouhráˇcové hry s nulovým souˇctem jsou základem teorie her. Zkoumat se bude jejich význam, ˇrešení v podobˇe sedlového bodu a podobnˇe.
4
3. Dvouhráˇcové hry s ne-nulovým souˇctem - úvod do her s nenulovým souˇctem, zkoumání dominantnosti strategií, eliminace dominovaných strategií, náznak Nashova ekvilibria. 4. Matematické metody ve hrách s nenulovým souˇctem - rozbor d˚ukazu Nashovy vˇety o ekvilibriu ve hrách s nenulovým souˇctem, algoritmy výpoˇctu ekvilibria ve smíšených strategiích, grafické ˇrešení her. 5. Sekvenˇcní hry s úplnou/neúplnou informací - aplikace sekvenˇcních her, Stackelbergovo ekvilibrium, sub-game perfection a podobnˇe. 6. Opakované hry, reputace - vliv opakování hry na chování hráˇcu˚ , opakované varianty strategických her, aplikace v reputaˇcních systémech. 7. Mechanism design, úvod - úvod do mechanism design (tvorba pravidel pro situaci/soutˇež). 8. Social choice, public voting - vliv racionality na rozhodování v situacích výbˇeru, jako jsou napˇríklad volby. Související ekvilibria, paradoxy a vˇety. 9. Aukce - zkoumání racionality v aukcích z hlediska prodávajícího (tv˚urce mechanismu) a kupujících. Aplikace v obchodu. 10. Hry mnoha hráˇcu˚ , korelované ekvilibrium - zavedení konceptu korelovaného ekvilibria, jak bylo definováno prof. Robertem Aumannem [4]. Algoritmy jeho výpoˇctu. Aplikace. 11. Evoluˇcní biologie - hledání konfliktu ve velkých kolektivech jedinc˚u, hledání evoluˇcnˇe stabilní strategie. 12. Aplikace v ekonomii - základní modely oligopolu a jejich analytické a simulaˇcní ˇrešení. Rozbor jedné netriviální pˇrípadové studie. 13. Aplikace v psychologii, sociologii, mezinárodních vztazích - dle možností na konci semestru další aplikace teorie her v netechnických oborech. 14. Referáty student˚u - jedna z posledních pˇrednášek bude vˇenována veˇrejné prezentaci studentských projekt˚u.
5 Závˇer V tomto cˇ lánku byl prezentován m˚uj zámˇer zavést nový pˇredmˇet "Teorie her" v magisterském studijním programu. Pˇredmˇet bude zˇrejmˇe patˇrit mezi volitelné. Je otázkou, jaký zájem u student˚u vzbudí. Ukazuje se však, že mezioborové pˇredmˇety jsou u student˚u populární, což mohu doložit na pˇríkladˇe svého jiného pˇredmetu Geografické informaˇcní systémy [5], který v tomto akademickém roce bude 5
vypsán už poˇctvrté a navštˇevuje ho pr˚umˇernˇe 200 student˚u. Jako velmi pˇeknou ukázku zpracovaného pˇredmˇetu "Teorie her a optimální rozhodování” si m˚užeme vzít tˇreba pˇredmˇet dr. Hykšové [3] na ˇ Fakultˇe dopravní CVUT v Praze.
Reference [1] John von Neumann, Oskar Morgenstern: Theory of Games and Economic Behavior, Princeton University Press, 1944 [2] John Nash: Non-cooperative games, Annals of Mathematics, 54(2):286–295, 1951. [3] Magdalena Hykšová, pˇredmˇet "Teorie her a optimální rozhodování", http://euler.fd.cvut.cz/predmety/teorie_her/ [4] Robert Aumann: Subjectivity and correlation in randomized strategies, Journal of Mathematical Economics 1:67-96. [5] Martin Hrubý, pˇredmˇet “Geografické informaˇcní systémy”, http://www.fit.vutbr.cz/study/courses/GIS/
6
