Multi-agentní systémy (A4M33MAS)

• Stránky předmětu: http://cw.felk.cvut.cz/doku.php/courses/ae4m36mas/start
• Přednášející: Michal Pěchouček, Michal Jakob
• Cvičící: Peter Novák, Branislav Bošanský, Viliam Lisý

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

1. (15b) Second-price sealed bid, omezene bidy: bid je bud 1 nebo 2, 2 agenti, kazdy value nejakeho zbozi bud 1 nebo 2 (se stejnou psti 0.5).
   1. prevest do normal-form game, jednou kdyz v1=1 a druha hra kdyz v1=2 reseni: ty 2 hry se lisi v payout maticich, tabulka 2×2
   2. jaky je expected revenue pro sellera?
   3. upravena aukce, ex. reservation price R, 1<R<2, kdyz highest bid >=R, tak je prodano a plati max(2nd_highest_bid,R). Kolik je expected revenue pro sellera pro R = 1.5?
   4. jaka je optimalni hodnota R? Zduvodnete.
2. (15b) Taxi sharing
   1. dana koalice jake je spravedlive (fair) rozdeleni? reseni: Sharpley value nebo intuici
   2. modifikovany problem. najit vsechna reseni v „core“ (koalice i ohodnoceni)
3. (15b) Social choice, zadany preference
   1. winner podle plurality, Borda, STV
   2. dokazte ci najdete protipriklad na tvrzeni: Kazdy Condocet winner musi vyhrat pairwise elimination. Plati, treba sporem.
4. (15b) Uvazujte BDI architekturu pro vozitko na Marsu, ma 3 ukoly, nejake akce.
   1. Jake bude mit beliefs, desires, intentions?
   2. 5 mini otazek:
      1. Mohou byt desires inconsistent a proc
      2. Mohou byt intentions inconsistent a proc
      3. Co je vysledkem delibaration?
      4. Co je vysledkem means-end reasoning?
      5. ???

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

1. (20b) Games
   1. popsana karetni hra, udelat extension form game tree a prevest na normal form
   2. nakresleny game tree, vyskrtat dominovane stratigie
2. (15b) Voting
   1. definovat voting rule
   2. urcite viteze podle plularity a STV
   3. pridat dalsiho kandidata aby jiny kandidat vyhral podle borda
   4. udelat poradi pairwise eliminace aby vyhral kandidat jestli to jde
3. (15b) DCSP
   1. formalizovat popsany problem (planovani 3 meetingu behem dne) jako DSCP
   2. napsat mozne reseni
   3. jak z toho udelat DCOP se soft constraints
4. (10b) Auctions
   1. co je to truthfulness, ktery auction model to ma a napsat dukaz

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

040216.pdf

Řešení (chybí aukce):

reseny_ukazkovy_test_mas.pdf