2010
ZK:
1:BDI architektura. Popis struktury,atd
2:Aukce- popsat aukční systém. Všechny akce a porovnat je vůči riziku, regredu a tomu poslednímu
3:Najít ve hrách NE a PO strategii
4:Lineární čas: jaký potřebuje axiomy, jak modelujeme lin. čas.
prevzato z diskuse
12.1.2011
1) Napište hru vězeňského dilematu, najděte Nash ekvilibrium, a pareto optimální strategie
2) Arrow theorem, způsoby hlasování, ukázat na příkladu, že můžou různé způsoby hlasování dopadnout různě a ještě něco k tomu..
3) Nakreslený herní strom, najít subgame perfect ekvilibria, převést do normální formy, najít Nash ekvilibria, formulovat slabou dominanci a odstranit dominované strategie
4) Popsat architekturu BDI, vyjmenovat různé druhy cílů a podrobně popsat achievement a maintenance a popsat je nějakou z formálních logik
17.1.2012
1) a) hlasovani: usporadani typu a>c>b pro 3 agenty, vybrat viteze podle- plurality, Borda,
„porovnani dvou s eliminaci“
b) zaradit D tak, aby podle Borda vyhralo C
2) aukce, popis protokolu, cim se lisi od hlasovani. Vyjmenuj a popis jake mechanismy (Dutch,engl.,1st price, 2nd,..) + jestli pro ne existuje dominantni strategie (ano, pro 2nd pr & Jap.) + dokaz.
3) herni strom v extenzivni forme: najit subperfect eq. SPE, prevod do normalni formy (tabulka), nejdi NE a ukaz (slabe) dominovane strategie + algoritmus jejich odstranovani.
4) Modalni logiky, popisty fci robota Vysavace, jake mod. operatory je treba zadefinovat, popiste 3 fce/cile robota temito oper. v nejake modalni logice. Jake typy logik znate (LTL,BTTL,KTD45B)
7.1.2013
1) Voting: Byly zadane usporadani typu a>b>c pro celkem 7 agentu, ukol byl vybrat viteze podle plurality, Borda a pairwise elimination. Potom pridat do usporadani kandidata D tak, aby podle Borda vyhral C
2) Popsat protokol Auction a napsat, v cem se lisi od protokolu Voting. Vyjmenovat a kratce popsat mechaniky vsech verzi auction (english/jap/first-price,…). Popsat, co je to truthful auction, rict ktere verze auction jsou truthful, a presne napsat proc.
3) Nakreslený herní strom, najít subgame perfect ekvilibria, převést do normální formy, najít Nash ekvilibria, odstranit vsechny slabe dominované strategie
4) Jake modalni operatory (?) se pouzivaj v temporal logice (chteli tam X,F,G,U) a kratce vysvetlit, co znamenaj. Kratce popiste, jake druhy temporal logik znate. Predstavte si situaci vacuum cleaning robota - napiste aspon 3 vlastnosti systemu (properties) nebo 3 cile robota (goals) a pouzijte k tomu ruzne modalni operatory.
21.1.2013
1) otázka na volby , posat druhy, Arrow teorem, Condorcet condition,
2) …. (Who knows…)
3)Nakreslený herní strom, najít subgame perfect ekvilibria, převést do normální formy, najít Nash ekvilibria, odstranit vsechny slabe dominované strategie
4) Jake modalni axiomy se pouzivaj v temporal logice (K,T,D,4,5,B) a kratce vysvetlit, co znamenaj. Popsat které jsou třeba na model of belief a model of kowledge,…
Predstavte si situaci vacuum cleaning robota - napiste aspon 3 vlastnosti systemu (properties) nebo 3 cile robota (goals) a pouzijte k tomu ruzne modalni operatory.
20.1.2014
reseni 4: a) Ne (ja si myslim, ze proto, ze se nemusi commitovat) b) Ano (asi proto, ze se musi commitovat) c) Intention d) Plan
8.1.2015
23.1.2019
Zkouska byla na 2 hod. 30 min. a bylo to tak tak. Test se skladal ze 4 okruhu - 1) Game theory (20b), 2) DCSP (15b), 3) Coalitions (15b) a 4) Voting s Auctions dohromady (10b). Zkouska byla opravdu dlouha, obsahovala jak priklady tak teorii a byla obsahove nekolikanosbne obsahlejsi nez ukazkovy test na webu. Vse si nepamatuji, tak alespon co dam z hlavy nize popisu:
1) Zadana NFG:
a)
- Napsat matematicky program pro nalezeni NE
- Odstranit slabe dominovane strategie a najit mixed NE
b)
- Zadana pravidla karetni hry (2 hraci, balicek obsahuje JQK), udelat EFG a vypsat Utility alespon k polovine listu
- Vypsat vsechny strategie hrace 1
- Lze prevezt vzdy konecnou EFG na NFG a zduvodnit proc.
Pak zde bylo jeste nekolik teoretickych otazek, jez si nepamatuji.
2) DCSP:
Jsou ctyri firmy A,B,C,D a L. Firma A,B,C a D produkuje produkty A,B,C a D. Firma L je prepravni spolecnost. Produkt A trva vyrobit 4 dny, produkt B trva vyrobit 8 dnu a produkt C trva vyrobit 3 dny. Produkt D trva vyrobit 2 dny, ale lze jej vyrobit pouze pokud uz jsou vyrobeny produkty A,B a C. Produkty A a B nelze vyrabet soucasne. Bud jeden nebo druhy. Kazdy z produktu A,B a C ma trvanlivost 5 dnu a produkt D musi byt vyroben do te doby nez se produkty A,B a C zkazi (tohle je pozor chytak, viz. nize). Vse se odehrava v Lednu a produkt D lze nejpozdeji zacit vyrabet 29. Ledna.
-Formalizovat jako DSCP, promenne, domena, agenti, constraints.
-Nakreslit graf priorit mezi agenty za predpokladu, ze A ma nejvyssi prioritu.
-Najit reseni (tady reseni neexistuje! To byl ten chytak, protoze se nejaky z produktu vzdy stihne zkazit! Mame to potvrzene od p. Bosanskeho)
-Popsat jak bude probihat prijata a odeslana komunikace a inicializace agenta D.
3) Coalitions:
Byla zadana mapa silnice a byli tri cestovatele, kteri si chteli vzit taxika aby jeli domu. Na mapce byli napsane vzdalenosti v Km a byla zadana cena 20Kc za Km.
-Napiste jak by se meli ferove rozdelit mezi sebou, pokud by jeli v grand coalition.
-Definujte Core a intuitivni souvislost se Shapley Value.
-Ukazte pripad, kdy bude mit grand coalition prazdny core.
-Muze mit v superaditivni hre grand coalition prazdny core? Zduvodnit.
Potom do mapky pridana jeste objizdka.
-Bude grand koalice mit prazdny core ano/ne zduvodnit.
-Bude existovat jina nez grand koalice s neprazdnym corem? Ano/ne popsat a zduvodnit.
Dal si bohuzel nevzpominam.
4) Voting a Auctions:
- zadan preferenci profil, spocitat viteze podle Plurality, Borda a STV.
- prohodit 2 radky v preferencich tak, aby byl vitez zadany kandidat, pokud lze a pokud ne tak vysvetlit proc.
- jaky aukcni model je blizky single sealed vote aukcnimu modelu.
- definovat Condorcet winner.
- najit condorce losera.
Opet si dalsi podotazky nevzpominam.
Ukázková písmenka z roku 2019
Řešení (chybí aukce):