výuka

12. přednáška (4. ledna 2006)

Nashova rovnováha je proti koalicím slabá. Silná Nashova rovnováha (odolnost vůči libovolné podmnožině agentů, kteří si zvýší užitek změnou své strategie) pak téměř neexistuje.

Vytváření koalic se převádí na hru charakteristických funkcí (CFG), ve které je cena každé koalice dána funkcí. Vytvoření koalice spočívá ve třech krocích, které jsou na sobě závislé a překrývají se: Generování struktury koalice, optimalizace cílů a zdrojů a dělení získané hodnoty.

Generování struktury koalizace je faktorizací množiny agentů. Všechny hry nejsou superaditivní (pak by byla triviální velká koalice, ale samotné vytvoření koalice něco stojí).

Hledání nejlepší koalice je superexponenciální. Algoritmus lze stáhnout na exponenciální složitost tak, že nenalezneme optimální řešení, ale víme, kolikrát je nalezené řešení horší.

Je potřeba projít alespoň 2^(|A|-1) koalic, nalezené řešení je pak |A|-krát horší než optimální.

Běžná predikátová logika 1. řádu na popis agentů nestačí. Řešení jsou ve změně syntaxe i sémantiky a vedou např. k modálním logikám v Kripkeho sémantice možných světů.

Možné světy jsou tzv. epistemické alternativy. Co platí ve všech možných světech, tomu agent věří. Pravda může být nutná nebo nahodilá. Splnitelnost, pravdivost v modelech a platnost formulí odvozujeme na základě platnosti atomů ve světech.

Logické systémy budujeme na základě osvojení některých z modálních axiomů: K-axiom (ten vždy), T (reflexivita), D (sériovost), 4 (tranzitivita), 5 (euklidicita).

Při více agentech znásobujeme relaci možných světů a modální operátory.

Sdílené a distribuované znalosti.

Čtení

Modal logic